C++ named requirements: AssociativeContainer
An AssociativeContainer is an ordered Container that provides fast lookup of objects based on keys.
An associative container supports unique keys if it may contain at most one element for each key. Otherwise, it supports equivalent keys.
Requirements
The type X satisfies AssociativeContainer if
- The type X satisfies Container (do C++11) AllocatorAwareContainer (od C++11)
- is parameterized on Key and an ordering relation Compare that induces a strict weak ordering on elements of Key, and
- In addition, std::map and std::multimap associate an arbitrary mapped type T with the Key.
- The object of type Compare is called the comparison object of a container of type X.
Given
a
, a value of type Xa2
, a value of a type Y whose node handles are compatible with Xb
, a value of type X or const Xa_uniq
, a value of type X when X supports unique keysa_eq
, a value of type X when X supports equivalent keysa_tran
, a value of type X or const X when typeX::key_compare::is_transparent
existsi
andj
, LegacyInputIterators denoting a valid range and referring to elements implicitly convertible toX::value_type
p
, a valid constant iterator toa
q
, a valid dereferenceable constant iterator toa
r
, a valid dereferenceable iterator toa
q1
andq2
, const iterators denoting a valid range ina
il
, an object of typestd::initializer_list<X::value_type>
t
, a value of typeX::value_type
k
, a value of typeX::key_type
c
, a value of typeX::key_compare
orconst X::key_compare
kl
, a value such that a is partitioned with respect toc(x, kl)
, withx
the key value ofe
ande
ina
ku
, a value such that a is partitioned with respect to!c(ku, x)
, withx
the key value ofe
ande
ina
ke
, a value such that a is partitioned with respect toc(x, ke)
and!c(ke, x)
, withc(x, ke)
implying!c(ke, x)
and withx
the key value ofe
ande
ina
kx
, a value such thata
is partitioned with respect toc(x, kx)
and!c(kx, x)
, withc(x, kx)
implying!c(kx, x)
and withx
the key value ofe
ande
ina
, andkx
is not convertible to eitherX::iterator
orX::const_iterator
A
, the allocator type of X:X::allocator_type
if it exists, otherwisestd::allocator<X::value_type>
m
, an allocator of a type convertible toA
nh
, a non-const rvalue of typeX::node_type
Types
Name | Type | Requirements |
---|---|---|
key_type | Key | |
mapped_type | T (for std::map and std::multimap only) | |
value_type | * Key (for std::set and std::multiset only) * std::pair<const Key, T>(for std::map and std::multimap only) | Erasable from X |
key_compare | Compare | CopyConstructible |
value_compare | * same as key_compare (for std::set and std::multiset) * an ordering relation on pairs induced by the first component (i.e. Key) (for std::map and std::multimap) | BinaryPredicate |
node_type | A specialization of the node-handle class template, such that the public nested types are the same types as the corresponding types in X. |
Methods and operators
Expression | Return type | Pre/Requirements | Post/Effects | Complexity |
---|---|---|---|---|
X(c) | Construct an empty container using a copy of c as the comparison object | constant | ||
X() ,X a = X(); | X::key_compare is DefaultConstructible | Construct an empty container using a Compare() as the comparison object | constant | |
X(i, j, c) | X::value_type is EmplaceConstructible into X from *i | Constructs an empty container using a copy of c as the comparison object 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::key_compare is DefaultConstructible and X::value_type is EmplaceConstructible into X from *i | Constructs an empty container using a Compare() as the comparison object 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 |
Iterators
Iterators of associative containers satisfy the requirements of LegacyBidirectionalIterator.
For associative containers where value_type is the same as key_type, both iterator and const_iterator are constant iterators. It is unspecified whether or not iterator and const_iterator are the same type.
Iterators of associative containers iterate through the containers in the non-descending order of keys where non-descending is defined by the comparison that was used to construct the containers. That is, given
a
, an associative containeri
andj
, dereferenceable iterators toa
If the distance from i
to j
is positive, then a.value_comp()(*j, *i) == false
.
Additionally, if a is an associative container with unique keys, the stronger condition a.value_comp()(*i, *j) != false
holds.
This section is incomplete
Reason: Unfinished requirements
Associative containers in the standard library
pub | std::set | collection of unique keys, sorted by keys |
pub | std::multiset | collection of keys, sorted by keys |
pub | std::map | collection of key-value pairs, sorted by keys, keys are unique |
pub | std::multimap | collection of key-value pairs, sorted by keys |
Defect reports
The following behavior-changing defect reports were applied retroactively to previously published C++ standards.
DR | Applied to | Behavior as published | Correct behavior |
---|---|---|---|
LWG 354 | C++98 | lower_bound and upper_bound did not return the end iterator if no element is found | they return the end iterator in this case |
LWG 589 | C++98 | the elements that i and j refer to had the type X::value_type | the elements are implicitly convertible to X::value_type |