## AssociativeContainer
## DescriptionAn 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 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 requirements) must allow assignment. That is, if In SimpleAssociativeContainer, where the elements are the keys, the elements are completely immutable; the nested types In some associative containers, UniqueAssociativeContainer, it is guaranteed that no two elements have the same key. [2] In other associative containers, MultipleAssociativeContainer, multiple elements with the same key are permitted. ## Refinement ofForwardContainer, DefaultConstructible ## Associated typesOne new type is introduced, in addition to the types defined in the ForwardContainer requirements.
## Notation
## DefinitionsIf If ## Valid expressionsIn addition to the expressions defined in ForwardContainer, the following expressions must be valid.
## Expression semantics
## Complexity guaranteesAverage complexity for erase key is at most Average complexity for erase element is constant time. Average complexity for erase range is at most Average complexity for count is at most Average complexity for find is at most logarithmic. Average complexity for equal range is at most logarithmic. ## Invariants
## Models## Notes[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 SortedAssociativeContainer, for example, are always stored in ascending order, and elements in a HashedAssociativeContainer are always stored according to the hash function. It would make no sense to allow the position of an element to be chosen arbitrarily. [2] Keys are not required to be EqualityComparable : associative containers do not necessarily use [3] Note the implications of this member function : it means that if two elements have the same key, there must be no elements with different keys in between them. The requirement that elements with the same key be stored contiguously is an associative container invariant. ## See alsoSimpleAssociativeContainer, PairAssociativeContainer, UniqueAssociativeContainer, MultipleAssociativeContainer, SortedAssociativeContainer, UniqueSortedAssociativeContainer, MultipleSortedAssociativeContainer, HashedAssociativeContainer, UniqueHashedAssociativeContainer, MultipleHashedAssociativeContainer. |