C++ concepts: AssociativeContainer

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