Chapter Summary

The associative containers support efficient lookup and retrieval of elements by key. The use of a key distinguishes the associative containers from the sequential containers, in which elements are accessed positionally.

There are eight associative containers, each of which

• Is a map or a set. a map stores key-value pairs; a set stores only keys.
• Requires unique keys or not.
• Keeps keys in order or not.

Ordered containers use a comparison function to order the elements by key. By default, the comparison is the < operator on the keys. Unordered containers use the key type’s == operator and an object of type hash<key_type> to organize their elements.

Containers with nonunique keys include the word multi in their names; those that use hashing start with the word unordered. A set is an ordered collection in which each key may appear only once; an unordered_multiset is an unordered collection of keys in which the keys can appear multiple times.

The associative containers share many operations with the sequential containers. However, the associative containers define some new operations and redefine the meaning or return types of some operations common to both the sequential and associative containers. The differences in the operations reflect the use of keys in associative containers.

Iterators for the ordered containers access elements in order by key. Elements with the same key are stored adjacent to one another in both the ordered and unordered containers.