C++ concepts: AssociativeContainer
From cppreference.com
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.
| This section is incomplete Reason: Finish requirements. |
AssociativeContainers 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) |