Maps and sets
A set is a container in which all the contained objects must compare not equal. Thus, adding a new object that is a duplicate of (or is equal to) an element that already exists in the set does not insert a new element. This is useful if one needs to keep track of all of the elements seen thus far. Determining whether an element is contained in a set should be a fairly fast operation (logarithmic in the size of the container for std::map), depending on the backing storage layout, as should adding new members. The standard library set stores the elements in order and uses a binary search to find elements. Maps and sets are often implemented as binary trees, such as a red-black tree, the structure of which is illustrated in Figure 5.2.
Figure 5.2: A simple tree with three nodes, one root node with two child nodes. Each node contains pointers to the left and right child nodes and a pointer to the parent node. Any of these can be null if there is no further node...
