Associative Containers

Associative Containers provide for fast retrieval of objects from the collection based on keys. The size of the collection can vary at runtime. The collection is maintained in order, based on a comparison function object of type Compare (a default template parameter according to the STL standard, but a non-default template parameter in the current implementation). The STL provides class templates for map, multimap, set, and multiset.

• set<T, Compare>, which supports unique keys (contains at most one of each key value) and provides for fast retrieval of the keys themselves.
• multiset<T, Compare>, which supports duplicate keys (possibly contains multiple copies of the same key value) and provides for fast retrieval of the keys themselves.
• map<Key, T, Compare>, which supports unique keys (contains at most one of each key value) and provides for fast retrieval of another type T based on the keys
• multimap<Key, T, Compare>, which supports duplicate keys (possibly contains multiple copies of the same key value) and provides for fast retrieval of another type T based on the keys

Associative containers store elements based on a key value. Implemented as red-black trees, they provide efficient retrieval of elements based on their key. maps and multimaps allow arbitrary data to be associated with each key. Also, maps and sets only allow elements with unique keys, whereas multimaps and multisets may contain elements with duplicate keys.