Associative Containers

Associative containers automatically sort their elements according to some ordering criterion. The default sorting criterion is the operator
<
. 
Internally, associative containers are typically implemented as binary trees. Therefore, finding an element with a specific value is rather fast because it has logarithmic complexity (compared to linear complexity of sequence containers). As a result, searching in an associative container of 1,024 elements will take at most 10 steps as opposed to 1,024.

A drawback to using associative containers is that values can’t be modified directly, as the elements’ position in the sorted data structure depends on the values and modifying the values would corrupt the data structure.

Here are the main properties of associative containers:

Fast search: $O(\log n)$ time, since associative containers are automatically sorted.

Traversing the elements of associative containers is slow, compared to vector or deque, and is mainly due to locality issues.

Since these containers are sorted, some operations no longer make sense, such as
push_front
andpush_back
. 
Associative containers do not provide random access.


The STL provides four associative containers: set, multiset, map and multimap.
Set

A set is a collection in which elements are sorted according to their own values. Each element may occur only once, so duplicates are not allowed.

We can visualize a set as a balanced binary tree:

We can create a set of integers and insert values in it like so:^{[1]}
set<int> courses; courses.insert(203); courses.insert(183); courses.insert(280);
Alternatively, we can use initializer list syntax to create a set with initial values:
set<int> courses = {203, 183, 280};
Internally, the set will sort and rearrange the elements. Therefore,
courses.begin()
will point to the value183
andfor (auto it = courses.begin(); it != courses.end(); ++it) { cout << *it << endl; }
will print
183
,203
and280
, each on a new line. 
We can check if an element exists in a set using the
first
method:auto it = courses.find(183);
This operation only takes $O(\log n)$ time, since the container is sorted. It returns an iterator to the element in the set or
end()
the element is not found. It is thus a good idea to check that before we dereference the iterator:if (it == courses.end()) { cout << "Not found" << endl; } else { cout << *it << " is in the set" << endl; }
Note that none of the sequence containers provide the
find
function, as that would be too costly. 
To insert a new element into the set, use the
insert
method:courses.insert(281);
This function returns a pair, with the first member set to an iterator pointing to either the newly inserted element or to the equivalent element already in the set. The element in the pair is set to
true
if a new element was inserted orfalse
if an equivalent element already existed.Another version of the
insert
method exists that takes an iterator as the first argument and the value to insert as the second argument:courses.insert(it, 281);
This version uses the iterator as a hint for the position where the element can be inserted, which can be used to improve the efficiency of the insertion. This version return an iterator pointing to either the newly inserted element or to the element that already had its same value in the set.

To remove an element from a set, we use the
erase
method and provide either the iterator to the element we’d like to remove of the element itself.courses.erase(it); courses.erase(203);
Note that none of the sequence containers allow you to remove an element by specifying the element itself as it would not be as efficient; they require you to provide the iterator.
Multiset

A multiset is the same as a set except that duplicates are allowed. Thus, a multiset may contain multiple elements that have the same value.

Therefore, insertion in a multiset is always successful, even if there are already elements with the save values.
Map

A map contains elements that are keyvalue pairs. Each element has a key that is the basis for the sorting criterion and a value. This is useful, since sometimes we want to sort the elements according to something other than their value.

Each key may occur only once in a map, so duplicate keys are not allowed.

We can visualize a set as a balanced binary tree where each node is a pair of a key and a value:

Map has the same interface as set, except that each element is a pair of a key and a value.

For example, we might want to store the number of occurrences of each letter. We can declare a map with keys of type
char
and values of typeint
:map<char, int> letterCounts;

When inserting into a map, need to make a pair:
letterCounts.insert(pair<char, int>('a', 10));
or we could use the
make_pair
convenience function that deducing the type from the types of arguments:letterCounts.insert(make_pair('a', 10));
NoteRemember that a function template can infer parameter types, unlike a class that does not infer parameter types. or, even simpler, we could use the initializer syntax:
letterCounts.insert({'a', 10});
The
insert
method can also take an iterator as a hint, just like for the set. 
We can use the
find
method to get the value stored at a certain key:auto it = letterCounts.find('B');
Just like for the set,
find
takes $O(\log n)$ time.This method returns an iterator to an element with key equivalent to the specified key or
end()
if no such element is found. 
Since the map stores pairs containing the key and the value, we must . This is how we can print all the elements in a map:
for (auto it = letterCounts.begin(); it != letterCounts.end(); ++it) { // print key followed by a colon cout << it>first << ": "; // print value cout << it>second << endl; }

The keys of a map cannot be modified. Thus, it is invalid to do
it>first = newValue;

The name associative container comes from the map, where each value is associated with a key.

A set can be considered as a special kind of map, in which the value is identical to the key.
Multimap

A multimap is the same as a map except that duplicates are allowed. Thus, a multimap may contain multiple elements that have the same key.

Multimap has the same interface as multiset, except that each element is a pair of a key and a value.