# Chapter 11. Associative Container
Associative containers support efficient lookup and retrieval by a key. The two primary associative container types are map and set. The elements in a map are key-value pairs: The key serves as an index into the map, and the value represents the data associated with that index. A set element contains only a key; a set supports efficient queries as to whether a given key is present.
| Associative Types | Description |
| :--- | :--- |
| map | Associative array; holds key-value pairs. |
| set | Container in which the key is the value. |
| multimap | map in which a key can appear multiple times. |
| multiset | set in which a key can appear multiple times. |
| unordered\_map | map organised by a hash function. |
| unordered\_set | set organised by a hash function. |
| unordered\_multimap | Hashed map; keys can appear multiple times. |
| unordered\_multiset | Hashed set; keys can appear multiple times. |
## 11.1 Using an Associative Container
#### Using a map
```cpp
map<string, size_t> word_count;
string word;
while (cin >> word)
++word_count[word];
```
#### Using a set
A set can hold the words we want to ignore and count only those words that are not in this set.
## 11.2 Overview of the Associative Containers
### 11.2.1 Defining an Associative Container
When we define a map, we must indicate both the key and value type; when we define a set, we specify only a key type.
When we initialise a map, we have to supply both the key and the value `{key, value}`
```cpp
map<string, string> authors = { {"Joyce", "James"},
{"Austen", "Jane"},
{"Dickens", "Charles"} };
```
The keys in a map or a set must be unique; there can be only one element with a given key. The `multimap` and `multiset` containers have no such restriction; there can be several elements with the same key.
### 11.2.2 Requirements on Key Type
For the ordered containers, map, `multimap`, set, and `multiset`, the key type must define a way to compare the elements. By default , the library uses the `<` operator for the key type to compare.
We can also supply our own operation to use in place of the < operator on keys. The specified operation must define a strict weak ordering over the key type. The comparison function must have the following properties:
* Two keys cannot both be "less than" each other; if k1 is "less than" k2, then k2 must never be "less than" k1.
* If k1 is "less than" k2 is "less than" k3, then k1 must be "less than" k3.
* If there are two keys, and neither key is "less than" the other, then we will say that those keys are "equivalent". If k1 is "equivalent" to k2 and k2 is "equivalent" to k3, then k1 must be "equivalent" to k3.
#### Using a Comparison Function for the Key Type
```cpp
bool compareIsbn(const Sales_data &lhs, const Sales_data &rhs) {
return lhs.isbn() < rhs.isbn();
}
multiset<Sales_data, decltype(compareIsbn)*> bookstore(compareIsbn);
```
Here, we use `decltype` to specify the type of our operation, we must add a `*` to indicate that we are using a pointer to the given function type.
### 11.2.3 The pair Type
The **pair** defines in the `utility` header, A pair holds two data members, it is a template from which we generate specific types. We must supply two type names when we create a pair.
The default pair constructor value initialises the data members.
| Operations on pairs | Description |
| :--- | :--- |
| pair<T1, T2> p; | p is a pair with value initialised members of types T1 and T2,m respectively. |
| pair<T1, T2> p\(v1, v2\); | p is a pair with types T1 and T2; the first and second members are initialised from v1 and v2, respectively. |
| pair<T1, T2> p = {v1, v2}; | Equivalent to p\(v1, v2\). |
| make\_pair<v1, v2\); | Returns a pair initialised from v1 and v2. |
| p.first | Returns the data member of p named first. |
| p.second | Returns the data member of p named second. |
| p1 relop p2 | Relational operators. |
| p1 == p2 | Two pairs are equal if their first and second members are respectively equal. |
| p1 != p2 | |
The data members of pair are public.m These members are named first and second, respectively.
Imagine we have a function that needs to return a pair. Under the new standard we can list initialise the return value.
```cpp
pair<string, int> process(vector<string>& v) {
if (!v.empty())
return {v.back(), v.back().size()};
else
return pair<string, int>();
}
```
Under earlier version of C++, we couldn't use braced initialisers to return a type like pair. Instead, we might have written both returns to explicitly construct the return value:
```cpp
pair<string, int>(v.back(), v.back().size());
```
Alternatively, we could have used `make_pair` to generate a new pair of the appropriate type from its two arguments:
```cpp
make_pair(v.back(), v.back().size());
```
## 11.3 Operations on Associative Containers
| Associative Container Additional Type Aliases | Description |
| :--- | :--- |
| key\_type | Type of the key for this container type. |
| mapped\_type | Type associated with each key; map types only. |
| value\_type | For sets, same as the key\_type. |
For the set types, the `key_type` and the `value_type` are the same. Only the map type define `mapped_type`.
### 11.3.1 Associative Container Iterator
It is essential to remember that the `value_type` of a map is pair and that we can change the value but not the key member of that pair.
Although the set types define both the `iterator` and `const_iterator` types, both types of iterators give use read-only access to the elements in the set.
The map and set types provide all the begin and end operations, we can use to traverse the container.
### 11.3.2 Adding Elements
The insert members add one element or a range of elements.
| Associative Container insert Operations | Description |
| :--- | :--- |
| c.insert\(v\); | v value\_type object; args used to construct an element. |
| c.emplace\(args\); | |
| c.insert\(b, e\); | b and e are iterators that denote a range of c::value\_type values. |
| c.insert\(il\); | il is a braced list of such values. |
| c.insert\(p, v\); | Like insert\(v\), but uses iterator p as a hint for where to begin the search for where the new element should be stored. |
| c.emplace\(p, v\); | |
### 11.3.3 Erasing Elements
For the containers with unique keys, the return from erase is always either zero or one. If the return value is zero, then the element we wanted to erase was not in the container.
| Removing Elements from an Associative Container | Description |
| :--- | :--- |
| c.erase\(k\); | Removes every element with key k from c. |
| c.erase\(p\); | Removes the element denoted by the iterator p from c. |
| c.erase\(b, e\); | Removes the elements in the range denoted by the iterator pair b, e. |
### 11.3.4 Subscripting a map
| Subscript Operation for map and unordered\_map | Description |
| :--- | :--- |
| c\[k\] | Return the element with key k. |
| c.at\(k\) | Checked access to the element with key k. |
### 11.3.5 Accessing Elements
For the containers with multiple keys, count has to do more work: If the element is present, it still has to count how many elements have the same key.
When a `multimap` or `multiset` has multiple elements of a given key, those elements will be adjacent within the container.
| Operations to Find Elements in an Associative Container | Description |
| :--- | :--- |
| c.find\(k\); | Returns an iterator to the element with key k, or the off-the -end iterator if k is not in the container. |
| c.count\(k\); | Return the number of elements with key k. |
| c.lower\_bound\(k\); | Returns an iterator to the first element with key not less than k. |
| c.upper\_bound\(k\); | Returns an iterator to the first element with key greater than k. |
| c.equal\_range\(k\); | Return a pair of iterators denoting the elements with key k. |
```cpp
auto entries = authors.count(search_item);
auto iter = authors.find(search_iter);
while(entries) {
++iter;
--entries;
}
```
Alternatively, we can solve our problem using `lower_bound` and `upper_bound`.
The iterator returned from lower\_bound may or may not refer to an element with the given key. If the key is not in the container, then lower\_bound refers to the first point at which this key can be inserted while preserving the element order within the container.
The remaining way to solve this problem is the most direct of the three approaches, we can call `equal_range` :
```cpp
for (auto pos = authors.equal_range(search_item);
pos.first != pos.second; ++pos.first)
cout << pos.first->second << endl;
```
## 11.4 The unordered Containers
The new standard defines four unordered associative containers. Rather than using a comparison operation to organise their elements, these containers use a **hash function** and the key type's `==` operator. An unordered container is most useful when we have a key type for which there is no obvious ordering relationship among the elements.
Aside from operations that manage the hashing, the unordered containers provide the same operations as the ordered containers.
The unordered containers are organised as a collection of buckets, each of which holds zero or more elements. These containers use a hash function to map elements to buckets. To access an element, the container first computes the element's hash code, which tells which bucket to search. The container puts all of its elements with a given has value into the same bucket. If the container allows multiple elements with a given key, all the elements with the same key will be in the same bucket.
| Unordered Container Management Operation | Description |
| :--- | :--- |
| c.bucket\_count\(\); | Number of buckets in use. |
| c.ma\_bucket\_count\(\); | Largest number of buckets this container can hold. |
| c.bucket\_size\(n\); | Number of elements in the nth bucket. |
| c.bucket\(k\); | Bucket in which elements with key k would be found. |
| local\_iterator | iterator type that can access elements in a bucket. |
| const\_local\_iterator | const version of the bucket iterator. |
| c.begin\(n\), c.end\(n\); | Iterator to the first, one past the last element in bucket n. |
| c.cbegin\(n\), c.cend\(n\); | Returns const\_local\_iterator. |
| c.loca\_factor\(\); | Average number of elements per bucket. |
| c.mas\_load\_factor\(\); | Average bucket size that c tries to maintain. |
| c.rehash\(n\); | Reorganise storage so that bucket\_load\_factor >= n and bucket\_count > size/max\_load\_factor. |
| c.reserve\(n\); | |
Be default, the unordered containers use the `==` operator on the key type to compare elements. They also use an object of type `hash<key_type>` to generator hash code for each element. The library supplies version of the hash template for the built-in types, including pointers.
We cannot directly define an unordered container that uses an our own class type for its key type. Instead of using the default hash, we can use a strategy similar to the one we used to override the default comparison operation on keys for the ordered containers.
```cpp
size_t hasher(const Sales_data &sd) {
return hash<string>()(sd.isbn());
}
bool eqOp(const Sales_data &lhs, const Sales_data &rhs) {
return lhs.isbn() == rhs.isbn();
}
using SD_multiset = unordered_multiset<Sales_data, declytype(hasher)*, decltype(eqOp)*>;
```
- Introduction
- Chapter 1. Getting Start
- Chapter 2. Variables and Basic Types
- Chapter 3. String, Vectors, and Arrays
- Chapter 4. Expressions
- Chapter 5. Statements
- Chapter 6. Functions
- Chapter 7. Classes
- Chapter 8. The IO Library
- Chapter 9. Sequential Containers
- Chapter 10. Generic Algorithms
- Chapter 11. Associative Container
- Chapter 12. Dynamic Memory
- Chapter 13. Copy Control
- Chapter 14. Overloaded Operations and Conversions
- Chapter 15. Object-Oriented Programming
- Chapter 16. Template Argument Deduction
- Chapter 17. Specialized Library Facilities
- Chapter 18. Tools for Large Programs
- Chapter 19. Specialized Tools and Techniques