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 and push_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 re-arrange the elements. Therefore, courses.begin() will point to the value 183 and
```
for (auto it = courses.begin(); it != courses.end(); ++it) {
    cout << *it << endl;
}
```
will print 183, 203 and 280, 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 or false 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 key-value 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 type int:
```
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));
```
Note
Remember 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.

1. As a freshman, I first took EECS 203 in the fall and EECS 183 in the winter, followed by EECS 280 in the spring.

Associative Containers

Associative Containers

Set

Multiset

Map

Multimap

results matching ""

No results matching ""