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.
Next topic:
Another Example: Topological Sorting
Previous topic:
Suggested Applications
© 2004 The SCO Group, Inc. All rights reserved.
UnixWare 7 Release 7.1.4 - 27 April 2004