C++ named requirements: AssociativeContainer

 

C++

Compiler support

Freestanding and hosted

Language

Standard library headers

Named requirements

Feature test macros (C++20)

Language support library

Concepts library (C++20)

Metaprogramming library (C++11)

Diagnostics library

General utilities library

Strings library

Containers library

Iterators library

Ranges library (C++20)

Algorithms library

Numerics library

Localizations library

Input/output library

Filesystem library (C++17)

Regular expressions library (C++11)

Concurrency support library (C++11)

Technical specifications

Symbols index

External libraries

 

C++ named requirements

Basic
DefaultConstructible CopyAssignable CopyConstructible	MoveAssignable (C++11) MoveConstructible (C++11) Destructible
Type properties
ScalarType TriviallyCopyable (C++11) StandardLayoutType (C++11)	PODType TrivialType (C++11) ImplicitLifetimeType (C++20)
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
Formatting
BasicFormatter (C++20)	Formatter (C++20)
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) SharedLockable (C++14) SharedTimedLockable (C++14)	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 DefaultConstructible	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 DefaultConstructible 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)