C++ concepts: AssociativeContainer

 

C++

Language

Standard library headers

Concepts

Utilities library

Strings library

Containers library

Algorithms library

Iterators library

Numerics library

Input/output library

Localizations library

Regular expressions library (C++11)

Atomic operations library (C++11)

Thread support library (C++11)

 

C++ concepts

Basic
DefaultConstructible CopyAssignable CopyConstructible	MoveAssignable (C++11) MoveConstructible (C++11) Destructible
Library-Wide
EqualityComparable LessThanComparable Swappable (C++11) ValueSwappable (C++11)	NullablePointer (C++11) Hash (C++11) Allocator
Container
Container SequenceContainer ReversibleContainer	AssociativeContainer AllocatorAwareContainer UnorderedAssociativeContainer (C++11)
Container Elements
CopyInsertable (C++11) MoveInsertable (C++11)	EmplaceConstructible (C++11)
Iterator
Iterator OutputIterator InputIterator	ForwardIterator BidirectionalIterator RandomAccessIterator
Stream I/O
FormattedInputFunction UnformattedInputFunction	FormattedOutputFunction UnformattedOutputFunction
Random Numbers
SeedSequence (C++11) RandomNumberEngine (C++11)	RandomNumberDistribution (C++11) UniformRandomNumberGenerator (C++11) RandomNumberEngineAdaptor (C++11)
Concurrency
BasicLockable (C++11) Lockable (C++11) TimedLockable (C++11)	Mutex (C++11) TimedMutex (C++11) SharedMutex (C++14)
Other
CharTraits pos_type off_type Clock (C++11) BitmaskType	UnaryTypeTrait (C++11) BinaryTypeTrait (C++11) TransformationTrait (C++11) TrivialClock (C++11) LiteralType (C++11)

 

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

Requirements

Legend
X	Container type
a	Object of type X
a_uniq	Object in X when X supports unique keys
a_eq	Object in X when X supports multiple keys
a_trans	Object in X when type X::key_compare::is_transparent exists
i, j	InputIterators denoting a valid range
p	const_iterator to a
q	dereferenceable const_iterator to a
q1, q2	const_iterators denoting a valid range in a
il	std::initializer_list<value_type>
t	Object of type X::value_type
k	Object of type X::key_type
c	Object of type X::key_compare
A	Storage allocator used by X, or std::allocator_type<X::value_type>
m	Allocator of a type convertible to A

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

AssociativeContainers 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)