Chapter 11. Associative Containers
Contents
- Section 11.1 Using an Associative Container
- Section 11.2 Overview of the Associative Containers
- Section 11.3 Operations on Associative Containers
- Section 11.4 The Unordered Containers
- Chapter Summary
- Defined Terms
Associative and sequential containers differ from one another in a fundamental way: Elements in an associative container are stored and retrieved by a key. In contrast, elements in a sequential container are stored and accessed sequentially by their position in the container.
Although the associative containers share much of the behavior of the sequential containers, they differ from the sequential containers in ways that reflect the use of keys.
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. We might use a set to hold words that we want to ignore during some kind of text processing. A dictionary would be a good use for a map: The word would be the key, and its definition would be the value.
The library provides eight associative containers, listed in Table 11.1. These eight differ along three dimensions: Each container is (1) a set or a map, (2) requires unique keys or allows multiple keys, and (3) stores the elements in order or not. The containers that allow multiple keys include the word multi; those that do not keep their keys ordered start with the word unordered. Hence an unordered_multi_set is a set that allows multiple keys whose elements are not stored in order, whereas a set has unique keys that are stored in order. The unordered containers use a hash function to organize their elements. We’ll have more to say about the hash function in § 11.4 (p. 444).
Table 11.1. Associative Container Types
Elements Ordered by Key
| Data Structure | 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 Collections
| Data Structure | Description |
|---|---|
unordered_map | map organized by a hash function |
unordered_set | set organized by a hash function |
unordered_multimap | Hashed map; keys can appear multiple times |
unordered_multiset | Hashed set; keys can appear multiple times |
The map and multimap types are defined in the map header; the set and multiset types are in the set header; and the unordered containers are in the unordered_map and unordered_set headers.