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

InputIterator s 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 nonconst 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

collection of unique keys, sorted by keys (class template) 

collection of keys, sorted by keys (class template) 

collection of keyvalue pairs, sorted by keys, keys are unique (class template) 

collection of keyvalue pairs, sorted by keys (class template) 