Standard Template Library Programmer's Guide

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 , 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.

Forward Container, Default Constructible

One new type is introduced, in addition to the types defined in the Forward Container requirements.

XA type that is a model of Associative Container

aObject of type X

tObject of type X::value_type

kObject of type X::key_type

p, qObject of type X::iterator

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 .

In addition to the expressions defined in Forward Container, the following expressions must be valid.

Average complexity for erase key is at most O(log(size()) + count(k)) .

Average complexity for erase element is constant time.

Average complexity for erase range is at most O(log(size()) + N) , where N is the number of elements in the range.

Average complexity for count is at most O(log(size()) + count(k)) .

Average complexity for find is at most logarithmic.

Average complexity for equal range is at most logarithmic.

• set

• multiset

• hash_set

• hash_multiset

• map

• multimap

• hash_map

• hash_multimap

[1] The reason there is no such mechanism is that the way in which elements are arranged in an associative container is typically a class invariant; elements in a Sorted Associative Container, for example, are always stored in ascending order, and elements in a Hashed Associative Container are always stored according to the hash function. It would make no sense to allow the position of an element to be chosen arbitrarily.