C++ named requirements: 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 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

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

© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
http://en.cppreference.com/w/cpp/named_req/AssociativeContainer