Standard Template Library Programmer's Guide

Models

• set
• multiset
• hash_set
• hash_multiset

Notes

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

See also

Associative Container, Pair Associative Container

Pair Associative Container

Category: containers

Component type: concept

Description

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<const key_type, data_type>. [1]

Refinement of

Associative Container

Associated types

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

Key type	X::key_type	The type of the key associated with X::value_type.
Data type	X::data_type	The type of the data associated with X::value_type. A Pair Associative Container can be thought of as a mapping from key_type to data_type.
Value type	X::value_type	The type of object stored in the container. The value type is required to be pair<const key_type, data_type>.

Notation

X A type that is a model of Pair Associative Container

a Object of type X

t Object of type X::value_type

d Object of type X::data_type

k Object of type X::key_type

p, q Object of type X::iterator

Valid expressions

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

Models

• map
• multimap
• hash_map
• hash_multimap

Notes

[1] The value type must be pair<const key_type, data_type>, rather than pair<key_type, data_type>, 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<const key_type, data_type> 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.

See also

Associative Container, Simple Associative Container

Sorted Associative Container

Category: containers

Component type: concept

Description

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.

Refinement of

Reversible Container, Associative Container

Associated types

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

X::key_compare

The type of a Strict Weak Ordering used to compare keys. Its argument type