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 DefaultConstructible |
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 DefaultConstructible 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.
https://en.cppreference.com/w/cpp/named_req/AssociativeContainer