C++ named requirements: AssociativeContainer

 

C++

Language

Standard Library Headers

Freestanding and hosted implementations

Named requirements

Language support library

Concepts library (C++20)

Diagnostics library

Utilities library

Strings library

Containers library

Iterators library

Ranges library (C++20)

Algorithms library

Numerics library

Input/output library

Localizations library

Regular expressions library (C++11)

Atomic operations library (C++11)

Thread support library (C++11)

Filesystem library (C++17)

Technical Specifications

 

C++ named requirements

Basic
DefaultConstructible CopyAssignable CopyConstructible	MoveAssignable (C++11) MoveConstructible (C++11) Destructible
Layout
TrivialType (C++11) TriviallyCopyable (C++11)	StandardLayoutType (C++11) PODType
Library-Wide
EqualityComparable LessThanComparable Swappable (C++11) ValueSwappable (C++11) NullablePointer (C++11) Hash (C++11)	Allocator FunctionObject Callable Predicate BinaryPredicate Compare
Container
Container SequenceContainer ContiguousContainer (C++17) ReversibleContainer	AssociativeContainer AllocatorAwareContainer UnorderedAssociativeContainer (C++11)
Container Elements
DefaultInsertable (C++11) CopyInsertable (C++11) MoveInsertable (C++11)	EmplaceConstructible (C++11) Erasable (C++11)
Iterator
LegacyIterator LegacyOutputIterator LegacyInputIterator LegacyForwardIterator	LegacyBidirectionalIterator LegacyRandomAccessIterator LegacyContiguousIterator (C++17) ConstexprIterator (C++20)
Stream I/O
FormattedInputFunction UnformattedInputFunction	FormattedOutputFunction UnformattedOutputFunction
Random Numbers
SeedSequence (C++11) RandomNumberEngine (C++11)	RandomNumberDistribution (C++11) UniformRandomBitGenerator (C++11) RandomNumberEngineAdaptor (C++11)
Concurrency
BasicLockable (C++11) Lockable (C++11) TimedLockable (C++11)	Mutex (C++11) TimedMutex (C++11) SharedMutex (C++17) SharedTimedMutex (C++14)
Other
CharTraits RegexTraits (C++11) BitmaskType NumericType LiteralType (C++11)	UnaryTypeTrait (C++11) BinaryTypeTrait (C++11) TransformationTrait (C++11) Clock (C++11) TrivialClock (C++11)

 

An AssociativeContainer is an ordered Container that provides fast lookup of objects based on keys.

Requirements

Legend
X	Container type
a	Value of type X
a2	Value of a type Y whose node handles are compatible with X
b	Possibly const value of type X
u	Arbitrary variable name
a_uniq	Value of type X when X supports unique keys
a_eq	Value of type X when X supports multiple keys
a_tran	Possibly const value of type X when type X::key_compare::is_transparent exists
i, j	LegacyInputIterators denoting a valid range and referring to elements implicitly convertible to X::value_type
p	A valid const iterator to a
q	A valid dereferenceable const iterator to a
r	A valid dereferenceable iterator to a
q1, q2	const iterators denoting a valid range in a
il	An object of type std::initializer_list<value_type>
t	A value of type X::value_type
k	A value of type X::key_type
c	A possibly const value of type X::key_compare
kl	A value such that a is partitioned with respect to c(r,kl), with r the key value of e and e in a
ku	A value such that a is partitioned with respect to !c(ku, r)
ke	A value such that a is partitioned with respect to c(r, ke) and !c(ke, r), with c(r, ke) implying !c(ke, r)
A	Storage allocator used by X, or std::allocator_type<X::value_type>
m	Allocator of a type convertible to A
nh	A non-const rvalue of type X::node_type

expression	return type	pre/requirements	post/effects	complexity
X::key_type	Key	Key is Destructible		compile time
X::key_compare	Compare			compile time
X::value_compare	a type satisfying BinaryPredicate	key_compare for std::set and std::multiset; an ordering relation over Key for std::map and std::multimap		compile time
X(c), X a(c);		key_compare is CopyConstructible	Construct an empty container using a copy of c as key_comp	constant
X(), X a;		key_compare is CopyConstructible	Construct an empty container using a Compare() as key_comp	constant
X(i, j, c), X a(i, j, c);		key_compare is CopyConstructible and value_type is EmplaceConstructible into X from *i	Constructs an empty container using a copy of c as key_comp and inserts all elements from the range [i; j)	generally N log N, or N if [i, j) is sorted (where N is std::distance(i, j))
X(i, j), X a(i, j);		key_compare is CopyConstructible and value_type is EmplaceConstructible into X from *i	Constructs an empty container using a Compare() as key_comp and inserts all elements from the range [i; j)	generally N log N, or N if [i, j) is sorted according to value_comp() (where N is std::distance(i, j))
X(il);		Equivalent to X(il.begin(), il.end());	Equivalent to X(il.begin(), il.end());
a = il	X&	T is CopyInsertable into X and also CopyAssignable	Assign the range [il.begin(), il.end()) into a. Elements of a that were not assigned to are destroyed	generally N log N, or N if [il.begin(), il.end()) is sorted according to value_comp() (where N is il.size() + a.size())
a.key_comp()	X::key_compare		The comparison object with which a was constructed is returned.	constant
a.value_comp()	X::value_compare		An object of type X::value_compare constructed out of the comparison object is returned.	constant

An associative container X that is either std::map and std::multimap additionally supports the expression X::mapped_type, which has a return type of T, with the requirement that T be Destructible, and compile time complexity.

Associative containers in the standard library

set	collection of unique keys, sorted by keys (class template)
multiset	collection of keys, sorted by keys (class template)
map	collection of key-value pairs, sorted by keys, keys are unique (class template)
multimap	collection of key-value pairs, sorted by keys (class template)