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

All SkipLists have additional typedefs that specify the content of each element. When defining Keyed SkipLists, the X::value_type is a pair<const key_type, data_type>. All other Skiplists have X::value_type identical to T. The following types always specify the actual content (rather than a pair or other compound types).

X::mapped_type is identical to X::data_type in a Pair Associative Container.
X::mapped_type is identical to X::value_type in all other skiplist containers.

Mapped type	X::mapped_type	In keyed SkipLists, identical to X::data_type. Otherwise, identical to X::value_type.
Const mapped type	X::const_mapped_type	Const version of X::mapped_type
Mapped reference	X::mapped_type_reference	Reference version of X::mapped_type
Cosnt mapped reference	X::const_mapped_type_reference	Const reference version of X::mapped_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

Definitions

Valid expressions

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

Expression semantics

Complexity guarantees

Invariants

Models

• KeyedSkipList
• KeyedSSkipList
• AutoKeyedSkipList
• AutoKeyedSSkipList
• MultiKeyedSkipList
• MultiKeyedSSkipList
• MultiAutoKeyedSkipList
• MultiAutoKeyedSSkipList

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, Access Associative Container