|
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
AnAssociativeContainer is an orderedContainer that provides fast lookup of objects based on keys.
An associative container supportsunique keys if it may contain at most one element for each key. Otherwise, it supportsequivalent keys.
Contents |
Legend | |
X | An associative container class |
T | The element type ofX |
A | The allocator type ofX:X::allocator_type if it exists, otherwisestd::allocator<X::value_type> |
| a | A value of typeX |
| a2 | A value of a typeY whosenode handles are compatible withX |
| b | A value of typeX orconst X |
| u | A name of a variable beging declared |
| a_uniq | A value of typeX whenX supports unique keys |
| a_eq | A value of typeX whenX supports equivalent keys |
| a_tran | A value of typeX orconst X when typeX::key_compare::is_transparent exists |
| i,j | TheLegacyInputIterators referring to elements implicitly convertible toX::value_type |
[i, j) | A valid range |
| rg (since C++23) | A value of a typeR that modelscontainer-compatible-range<value_type> |
| p | A valid constant iterator toa |
| q | A valid dereferenceable constant iterator toa |
| r | A valid dereferenceable iterator toa |
| q1,q2 | A valid range of const iterators 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 thata is partitioned with respect toc(x, kl), withx the key value ofe ande ina |
| ku | A value such thata is partitioned with respect to!c(ku, x), withx the key value ofe ande ina |
| ke | A value such thata 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 (since C++23) | A value such that:
|
| m | An allocator of a type convertible toA |
| nh | A non-const rvalue of typeX::node_type |
The typeX satisfiesAssociativeContainer if
X satisfiesContainer(until C++11)AllocatorAwareContainer(since C++11),Key and an ordering relationCompare that induces astrict weak ordering on elements ofKey, andT with theKey.Compare is called thecomparison object of a container of typeX.| Name | Type | Requirements |
|---|---|---|
key_type | Key | |
mapped_type | T (forstd::map andstd::multimap only) | |
value_type |
| Erasable fromX |
key_compare | Compare | CopyConstructible |
value_compare |
| BinaryPredicate |
node_type | A specialization of thenode-handle class template, such that the public nested types are the same types as the corresponding types inX. |
| Expression | Result | Preconditions | Effects | Returns | Complexity |
|---|---|---|---|---|---|
| X(c) | Constructs an empty container. Uses a copy ofc as a comparison object | Constant | |||
| X u= X(); X u; | key_compare meets theDefaultConstructible requirements | Constructs an empty container. UsesCompare() as a comparison object | Constant | ||
| X(i, j, c) | value_type isEmplaceConstructible intoX from*i | Constructs an empty container and inserts elements from the range[i, j) into it; usesc as a comparison object | N·log(N) in general, whereN has the valuestd::distance(i, j); linear if[i, j) is sorted with respect tovalue_comp() | ||
| X(i, j) | key_compare meets theDefaultConstructible requirements.value_type isEmplaceConstructible intoX from*i | Constructs an empty container and inserts elements from the range[i, j) into it; usesCompare() as a comparison object | |||
| X(from_range, rg, c) (since C++23) | value_type isEmplaceConstructible intoX from*ranges::begin(rg) | Constructs an empty container and inserts each element fromrg into it. Usesc as the comparison object | N·log(N) in general, whereN has the valueranges::distance(rg); linear ifrg is sorted with respect tovalue_comp() | ||
| X(from_range, rg) (since C++23) | key_compare meets theDefaultConstructible requirements.value_type isEmplaceConstructible intoX from*ranges::begin(rg) | Constructs an empty container and inserts each element fromrg into it. UsesCompare() as the comparison object | |||
| X(il, c) | X(il.begin(), il.end(), c) | ||||
| X(il) | X(il.begin(), il.end()) | ||||
| a= il | X& | value_type isCopyInsertable intoX andCopyAssignable | Assigns the range[il.begin(), il.end()) intoa. All existing elements ofa are either assigned to or destroyed | N·log(N) in general, whereN has the valueil.size()+ a.size(); linear if[il.begin(), il.end()) is sorted with respect tovalue_comp() | |
| b.key_comp() | X::key_compare | The comparison object out of whichb was constructed | Constant | ||
| b.value_comp() | X::value_compare | An object ofvalue_compare constructed out of the comparison object | Constant | ||
| a_uniq.emplace(args) | std::pair< iterator, bool> | value_type isEmplaceConstructible intoX fromargs | Inserts avalue_type objectt constructed withstd::forward<Args>(args)... if and only if there is no element in the container with key equivalent to the key oft | Thebool component of the returned pair istrue if and only if the insertion takes place, and the iterator component of the pair points to the element with key equivalent to the key oft | Logarithmic |
| a_eq.emplace(args) | iterator | value_type isEmplaceConstructible intoX fromargs | Inserts avalue_type objectt constructed withstd::forward<Args>(args).... If a range containing elements equivalent tot exists ina_eq,t is inserted at the end of that range | An iterator pointing to the newly inserted element | Logarithmic |
| a.emplace_hint(p, args) | iterator | Equivalent to a.emplace( | An iterator pointing to the element with the key equivalent to the newly inserted element | Logarithmic in general, but amortized constant if the element is inserted right beforep | |
| a_uniq.insert(t) | std::pair< iterator, bool> | Ift is a non-const rvalue,value_type isMoveInsertable intoX; otherwise,value_type isCopyInsertable intoX | Insertst if and only if there is no element in the container with key equivalent to the key oft | Thebool component of the returned pair istrue if and only if the insertion takes place, and theiterator component of the pair points to the element with key equivalent to the key oft | Logarithmic |
| a_eq.insert(t) | iterator | Ift is a non-const rvalue,value_type isMoveInsertable intoX; otherwise,value_type isCopyInsertable intoX | Insertst and returns the iterator pointing to the newly inserted element. If a range containing elements equivalent tot exists ina_eq,t is inserted at the end of that range | Logarithmic | |
| a.insert(p, t) | iterator | Ift is a non-const rvalue,value_type isMoveInsertable intoX; otherwise,value_type isCopyInsertable intoX | Insertst if and only if there is no element with key equivalent to the key oft in containers with unique keys; always insertst in containers with equivalent keys.t is inserted as close as possible to the position just prior top | An iterator pointing to the element with key equivalent to the key oft | Logarithmic in general, but amortized constant ift is inserted right beforep |
| a.insert(i, j) | void | value_type isEmplaceConstructible intoX from*i. Neitheri norj are iterators intoa | Inserts each element from the range[i, j) if and only if there is no element with key equivalent to the key of that element in containers with unique keys; always inserts that element in containers with equivalent keys | N·log(a.size()+ N), whereN has the valuestd::distance(i, j) | |
| a.insert_range(rg) (since C++23) | void | value_type isEmplaceConstructible intoX from*ranges::begin(rg).rg anda do not overlap | Inserts each element fromrg if and only if there is no element with key equivalent to the key of that element in containers with unique keys; always inserts that element in containers with equivalent keys | N·log(a.size()+ N), whereN has the valueranges::distance(rg) | |
| a.insert(il) | a.insert(il.begin(), il.end()) | ||||
| a_uniq.insert(nh) | insert_return_type | nh is empty or a_uniq.get_allocator() | Ifnh is empty, has no effect. Otherwise, inserts the element owned bynh if and only if there is no element in the container with a key equivalent tonh.key() | Ifnh is empty,inserted isfalse,position isend(), andnode is empty. Otherwise if the insertion took place,inserted istrue,position points to the inserted element, andnode is empty; if the insertion failed,inserted isfalse,node has the previous value ofnh, andposition points to an element with a key equivalent tonh.key() | Logarithmic |
| a_eq.insert(nh) | iterator | nh is empty or a_eq.get_allocator() | Ifnh is empty, has no effect and returnsa_eq.end(). Otherwise, inserts the element owned bynh and returns an iterator pointing to the newly inserted element. If a range containing elements with keys equivalent tonh.key() exists ina_eq, the element is inserted at the end of that range. Ensures:nh is empty | Logarithmic | |
| a.insert(p, nh) | iterator | nh is empty or a.get_allocator() | Ifnh is empty, has no effect and returnsa.end(). Otherwise, inserts the element owned bynh if and only if there is no element with key equivalent tonh.key() in containers with unique keys; always inserts the element owned bynh in containers with equivalent keys. The element is inserted as close as possible to the position just prior top. Ensures:nh is empty if insertion succeeds, unchanged if insertion fails | An iterator pointing to the element with key equivalent tonh.key() | Logarithmic in general, but amortized constant if the element is inserted right beforep |
| a.extract(k) | node_type | Removes the first element in the container with key equivalent tok | Anode_type owning the element if found, otherwise an emptynode_type | log(a.size()) | |
| a_tran.extract(kx) (since C++23) | node_type | Removes the first element in the container with keyr such that!c(r, kx)&&!c(kx, r) istrue | Anode_type owning the element if found, otherwise an emptynode_type | log(a_tran.size()) | |
| a.extract(q) | node_type | Removes the element pointed to byq | Anode_type owning that element | Amortized constant | |
| a.merge(a2) | void | a.get_allocator() == a2.get_allocator() | Attempts to extract each element ina2 and insert it intoa using the comparison object ofa. In containers with unique keys, if there is an element ina with key equivalent to the key of an element froma2, then that element is not extracted froma2. Ensures: Pointers and references to the transferred elements ofa2 refer to those same elements but as members ofa. Iterators referring to the transferred elements will continue to refer to their elements, but they now behave as iterators intoa, not intoa2. Throws: Nothing unless the comparison object throws | N·log(a.size()+ N), whereN has the valuea2.size() | |
| a.erase(k) | size_type | Erases all elements in the container with key equivalent tok | The number of erased elements | log(a.size()) + a.count(k) | |
| a_tran.erase(kx) (since C++23) | size_type | Erases all elements in the container with keyr such that!c(r, kx)&&!c(kx, r) istrue | The number of erased elements | log(a_tran.size()) + a_tran.count(kx) | |
| a.erase(q) | iterator | Erases the element pointed to byq | An iterator pointing to the element immediately followingq prior to the element being erased. If no such element exists, returnsa.end() | Amortized constant | |
| a.erase(r) | iterator | Erases the element pointed to byr | An iterator pointing to the element immediately followingr prior to the element being erased. If no such element exists, returnsa.end() | Amortized constant | |
| a.erase(q1, q2) | iterator | Erases all the elements in the range[q1, q2) | An iterator pointing to the element pointed to byq2 prior to any elements being erased. If no such element exists,a.end() is returned | log(a.size())+ N, whereN has the valuestd::distance(q1, q2) | |
| a.clear() | a.erase(a.begin(), a.end()). Ensures:a.empty() istrue | Linear ina.size() | |||
| b.find(k) | iterator;const_iterator for constantb | An iterator pointing to an element with the key equivalent tok, orb.end() if such an element is not found | Logarithmic | ||
| a_tran.find(ke) | iterator;const_iterator for constanta_tran | An iterator pointing to an element with keyr such that !c(r, ke)&& | Logarithmic | ||
| b.count(k) | size_type | The number of elements with key equivalent tok | log(b.size()) + b.count(k) | ||
| a_tran.count(ke) | size_type | The number of elements with keyr such that !c(r, ke)&& | log(a_tran.size()) + a_tran.count(ke) | ||
| b.contains(k) | bool | return b.find(k)!= b.end(); | |||
| a_tran.contains(ke) | bool | return | |||
| b.lower_bound(k) | iterator;const_iterator for constantb | An iterator pointing to the first element with key not less thank, orb.end() if such an element is not found | Logarithmic | ||
| a_tran.lower_bound(kl) | iterator;const_iterator for constanta_tran | An iterator pointing to the first element with keyr such that!c(r, kl), ora_tran.end() if such an element is not found | Logarithmic | ||
| b.upper_bound(k) | iterator;const_iterator for constantb | An iterator pointing to the first element with key greater thank, orb.end() if such an element is not found | Logarithmic | ||
| a_tran.upper_bound(ku) | iterator;const_iterator for constanta_tran | An iterator pointing to the first element with keyr such thatc(ku, r), ora_tran.end() if such an element is not found | Logarithmic | ||
| b.equal_range(k) | std::pair< iterator, iterator>; std::pair< | Equivalent to: return | Logarithmic | ||
| a_tran.equal_range(ke) | std::pair< iterator, iterator>; std::pair< | Equivalent to: return | Logarithmic |
Iterators of associative containers satisfy the requirements ofLegacyBidirectionalIterator.
For associative containers wherevalue_type is the same askey_type, bothiterator andconst_iterator are constant iterators. It is unspecified whether or notiterator andconst_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
If the distance fromi toj is positive, thena.value_comp()(*j,*i)==false. Additionally, ifa is an associative container with unique keys, the stronger conditiona.value_comp()(*i,*j)!=false holds.
| This section is incomplete Reason: Finish requirements. |
The following standard library containers satisfy theAssociativeContainer requirements:
| collection of unique keys, sorted by keys (class template)[edit] | |
| collection of keys, sorted by keys (class template)[edit] | |
| collection of key-value pairs, sorted by keys, keys are unique (class template)[edit] | |
| collection of key-value pairs, sorted by keys (class template)[edit] |
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 andupper_bound did notreturn the end iterator if no element is found | they return the end iterator in this case |
| LWG 589 | C++98 | the elements thati andj refer to had the type X::value_type | the elements are implicitly convertible to X::value_type |
