Implementation Notes and Warnings

These classes are presently implemented as AVL trees. An AVL tree is a binary tree with the added requirement that the heights of the two subtrees of each node may differ by no more than one

We believe our implementation is reasonably robust. There are, however, a few places where a user might get into trouble:

• If m is a map, referring to m[i] creates it if it did not already exist. It is therefore a bad idea, though a tempting one, to check whether a map element exists by comparing its value to the default value. Use the element function instead.

• A map iterator is conceptually a pointer. Like any pointer, an iterator invites the possibility of a dangling reference if the lifetime of an iterator exceeds that of the associated map. For example:

     Map<K,V>* p;
     p = new Map<K,V>;
     Mapiter<K,V> mi (*p);
     delete p;
  

  Because it is impossible to create an iterator without making it refer to some map, it is somewhat tricky to step into this particular trap. Nevertheless it is possible.

• Removing an element from a map that has an iterator on it causes the element to be ``marked'' for removal. Iterators will skip over any ``marked'' elements. The actual removal takes place after all of the iterators are gone. Therefore it usually makes sense to declare iterators in an inner block, so the removal can take place after the iterator destructors are called.

• Copying a map makes a logical copy of each element. If the map is large, this can take a long time. Many functions that deal with maps can deal just as profitably with pointers or references to maps instead.

• Data types used in maps should only be pointers if it is possible to ensure that those pointers refer to memory at least as persistent as the maps themselves. Otherwise some map element will ultimately contain a pointer to garbage, with chaos as the result.