Category: containers
Component type: concept
Description An Associative Container is a variable-sized Container that supports efficient retrieval of elements (values) based on keys. It supports insertion and removal of elements, but differs from a Sequence in that it does not provide a mechanism for inserting an element at a specific position. [1]
As with all containers, the elements in an Associative Container are of type value_type. Additionally, each element in an Associative Container has a key, of type key_type. In some Associative Containers, Simple Associative Containers, the value_type and key_type are the same: elements are their own keys. In others, the key is some specific part of the value. Since elements are stored according to their keys, it is essential that the key associated with each element is immutable. In Simple Associative Containers this means that the elements themselves are immutable, while in other types of Associative Containers, such as Pair Associative Containers, the elements themselves are mutable but the part of an element that is its key cannot be modified. This means that an Associative Container's value type is not Assignable.
The fact that the value type of an Associative Container is not Assignable has an important consequence: associative containers cannot have mutable iterators. This is simply because a mutable iterator (as defined in the Trivial Iterator requirements) must allow assignment. That is, if i is a mutable iterator and t is an object of i 's value type, then *i = t must be a valid expression.
In Simple Associative Containers, where the elements are the keys, the elements are completely immutable; the nested types iterator and const_iterator are therefore the same. Other types of associative containers, however, do have mutable elements, and do provide iterators through which elements can be modified. Pair Associative Containers, for example, have two different nested types iterator and const_iterator . Even in this case, iterator is not a mutable iterator: as explained above, it does not provide the expression *i = t. It is, however, possible to modify an element through such an iterator: if, for example, i is of type map<int, double> , then (*i).second = 3 is a valid expression.
In some associative containers, Unique Associative Containers, it is guaranteed that no two elements have the same key. [2] In other associative containers, Multiple Associative Containers, multiple elements with the same key are permitted.
Refinement of Forward Container, Default Constructible
Associated types One new type is introduced, in addition to the types defined in the Forward Container requirements.
| Key type | X::key_type | The type of the key associated with X::value_type . Note that the key type and value type might be the same. |
Notation X A type that is a model of Associative Container
a Object of type X
t Object of type X::value_type
k Object of type X::key_type
p, q Object of type X::iterator
Definitions If a is an associative container, then p is a valid iterator in a if it is a valid iterator that is reachable from a.begin() .
If a is an associative container, then [p, q) is a valid range in a if [p, q) is a valid range and p is a valid iterator in a.
Valid expressions In addition to the expressions defined in Forward Container, the following expressions must be valid.
| Name | Expression | Return type |
| Default constructor | X() X a; | |
| Erase key | a.erase(k) | size_type |
| Erase element | a.erase(p) | void |
| Erase range | a.erase(p, q) | void |
| Clear | a.clear() | void |
