Standard Template Library Programmer's Guide

[2] Keys are not required to be Equality Comparable: associative containers do not necessarily use operator== to determine whether two keys are the same. In Sorted Associative Containers, for example, where keys are ordered by a comparison function, two keys are considered to be the same if neither one is less than the other.

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

Simple Associative Container, Pair Associative Container, Unique Associative Container, Multiple Associative Container, Sorted Associative Container, Unique Sorted Associative Container, Multiple Sorted Associative Container, Hashed Associative Container, Unique Hashed Associative Container, Multiple Hashed Associative Container.

Category: containers

Component type: concept

A Simple Associative Container is an Associative Container where elements are their own keys. A key in a Simple Associative Container is not associated with any additional value.

Associative Container

None, except for those described in the Associative Container requirements. Simple Associative Container, however, introduces two new type restrictions.

XA type that is a model of Simple Associative Container

aObject of type X

kObject of type X::key_type

p, qObject of type X::iterator

None, except for those defined in the Associative Container requirements.

• set

• multiset

• hash_set

• hash_multiset

[1] This is a consequence of the Immutability of Keys invariant of Associative Container. Keys may never be modified; values in a Simple Associative Container are themselves keys, so it immediately follows that values in a Simple Associative Container may not be modified.

Associative Container, Pair Associative Container

Category: containers

Component type: concept

A Pair Associative Container is an Associative Container that associates a key with some other object. The value type of a Pair Associative Container is pair . [1]

Associative Container

One new type is introduced, in addition to the types defined in the Associative Container requirements. Additionally, Pair Associative Container introduces one new type restriction

XA type that is a model of Pair Associative Container

aObject of type X

tObject of type X::value_type

dObject of type X::data_type

kObject of type X::key_type

p, qObject of type X::iterator

None, except for those defined in the Associative Container requirements.

• map

• multimap

• hash_map

• hash_multimap

[1] The value type must be pair , rather than pair , because of the Associative Container invariant of key immutability. The data_type part of an object in a Pair Associative Container may be modified, but the key_type part may not be. Note the implication of this fact: a Pair Associative Container cannot provide mutable iterators (as defined in the Trivial Iterator requirements), because the value type of a mutable iterator must be Assignable, and pair is not Assignable. However, a Pair Associative Container can provide iterators that are not completely constant: iterators such that the expression (*i).second = d is valid.

Associative Container, Simple Associative Container

Category: containers

Component type: concept

A Sorted Associative Container is a type of Associative Container. Sorted Associative Containers use an ordering relation on their keys; two keys are considered to be equivalent if neither one is less than the other. (If the ordering relation is case-insensitive string comparison, for example, then the keys "abcde" and "aBcDe" are equivalent.)

Sorted Associative Containers guarantee that the complexity for most operations is never worse than logarithmic [1], and they also guarantee that their elements are always sorted in ascending order by key.

Reversible Container, Associative Container

Two new types are introduced, in addition to the types defined in the Associative Container and Reversible Container requirements.

XA type that is a model of Sorted Associative Container

aObject of type X

tObject of type X::value_type

kObject of type X::key_type

p, qObject of type X::iterator

cObject of type X::key_compare

In addition to the expressions defined in Associative Container and Reversible Container, the following expressions must be valid.