⟩ What is associative container?
Associative containers provide lookup based on keys. They come in two variants:
• Ordered associative containers do lookup based on an ordering criterion, by default < (less
than). They are implemented as balanced binary trees, usually red-black trees.
• Unordered associative containers do lookup based on a hash function. They are implemented
as hash tables with linked overflow.
Both come as
• maps: sequences of {key,value} pairs
• sets: maps without values (or you could say that the key is also the value)
Finally, maps and sets, whether ordered or unordered, come in two variants:
• ‘‘Plain’’ sets or maps with a unique entry for each key
• ‘‘Multi’’ sets or maps for which multiple entries can exist for each key
The name of an associate container indicates its place in this 3-dimensional space: {set|map,
plain|unordered, plain|multi}. ‘‘Plain’’ is nev er spelled out, so the associative containers are:
Associative Containers (§iso.23.4.1, §iso.23.5.1)
set multiset unordered_set unordered_multiset
map multimap unordered_map unordered_multimap
Their template arguments are described in §31.4.
Internally, a map and an unordered_map are very different. See §31.2.1 for graphical representations.
In particular, map uses its comparison criterion (typically <) on a key to search through a balanced tree (an O(log(n)) operation), whereas unordered_map applies a hash function on a key to find a slot in a hash table (an O(1) operation for a good hash function).
