|
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Unordered associative containers areContainers that provide fast lookup of objects based on keys.Worst case complexity is linear but on average much faster for most of the operations.
Unordered associative containers are parametrized byKey;Hash, aHash function object which acts as hash function onKey; andPred, aBinaryPredicate evaluating equivalence betweenKeys.std::unordered_map andstd::unordered_multimap also have a mapped typeT associated with theKey.
If twoKeys are equal according toPred,Hash must return the same value for both keys.
If both | (since C++20) |
std::unordered_map andstd::unordered_set can contain at most one element with a given key,std::unordered_multiset andstd::unordered_multimap instead can have multiple elements with the same key (which must always be adjacent on iterations).
Forstd::unordered_set andstd::unordered_multiset the value type is the same as the key type and bothiterator andconst_iterator are constant iterators.Forstd::unordered_map andstd::unordered_multimap the value type isstd::pair<const Key, T>.
Elements in an unordered associative container are organized into buckets, keys with the same hash will end up in the same bucket.The number of buckets is increased when the size of the container increases to keep the average number of elements in each bucket under a certain value.
Rehashing invalidates iterator and might cause the elements to be re-arranged in different buckets but it does not invalidate references to the elements.
Unordered associative containers meet the requirements ofAllocatorAwareContainer.Forstd::unordered_map andstd::unordered_multimap the requirements ofvalue_type inAllocatorAwareContainer apply tokey_type andmapped_type (not tovalue_type).
Contents |
Legend | |
X | An unordered associative container class |
| a | A value of typeX |
| a2 | A value of a type withnodes compatible with typeX |
| b | A value of typeX orconst X |
| 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 the qualified identifiersX::key_equal::is_transparent andX::hasher::is_transparent are both valid and denotetypes |
| i,j | Input iterators that refer tovalue_type |
[i, j) | A valid range |
| rg(since C++23) | A value of a typeR that modelscontainer-compatible-range<value_type> |
| p,q2 | Valid constant iterators toa |
| q,q1 | Valid dereferenceable constant iterators toa |
| r | A valid dereferenceable iterator toa |
[q1, q2) | A valid range ina |
| il | A value of typestd::initializer_list<value_type> |
| t | A value of typeX::value_type |
| k | A value of typekey_type |
| hf | A value of typehasher orconst hasher |
| eq | A value of typekey_equal orconst key_equal |
| ke | A value such that
wherer1 andr2 are keys of elements ina_tran |
| kx(since C++23) | A value such that
wherer1 andr2 are keys of elements ina_tran |
| n | A value of typesize_type |
| z | A value of typefloat |
| nh(since C++17) | An rvalue of typeX::node_type |
| Name | Type | Requirements | Notes |
|---|---|---|---|
X::key_type | Key | ||
X::mapped_type | T | std::unordered_map andstd::unordered_multimap only | |
X::value_type | Key | std::unordered_set andstd::unordered_multiset only.Erasable inX | |
| std::pair<const Key, T> | std::unordered_map andstd::unordered_multimap only.Erasable inX | ||
X::hasher | Hash | Hash | |
X::key_equal | Pred | CopyConstructible;BinaryPredicate that takes two arguments of typeKey and expresses an equivalence relation | |
X::local_iterator | LegacyIterator | Category and types are the same asX::iterator | Can be used to iterate through a single bucket, but not across buckets |
X::const_local_iterator | LegacyIterator | Category and types are the same asX::const_iterator | |
X::node_type(since C++17) | A specialization ofnode-handle class template | The public nested types are the same as the corresponding types inX |
| Expression | Result | Preconditions | Effects | Returns | Complexity |
|---|---|---|---|---|---|
| X(n, hf, eq) | Constructs an empty container with at leastn buckets, usinghf as the hash function andeq as the key equality predicate | O(n) | |||
| X(n, hf) | key_equal isDefaultConstructible | Constructs an empty container with at leastn buckets, usinghf as the hash function andkey_equal() as the key equality predicate | O(n) | ||
| X(n) | hasher andkey_equal areDefaultConstructible | Constructs an empty container with at leastn buckets, usinghasher() as the hash function andkey_equal() as the key equality predicate | O(n) | ||
| X a= X(); X a; | hasher andkey_equal areDefaultConstructible | Constructs an empty container with an unspecified number of buckets, usinghasher() as the hash function andkey_equal() as the key equality predicate | Constant | ||
| X(i, j, n, hf, eq) | value_type isEmplaceConstructible intoX from*i | Constructs an empty container with at leastn buckets, usinghf as the hash function andeq as the key equality predicate, and inserts elements from[i, j) into it | Average caseO(N) (N isstd::distance(i, j)), worst caseO(N2) | ||
| X(i, j, n, hf) | key_equal is theDefaultConstructible.value_type isEmplaceConstructible intoX from*i | Constructs an empty container with at leastn buckets, usinghf as the hash function andkey_equal() as the key equality predicate, and inserts elements from[i, j) into it | Average caseO(N) (N isstd::distance(i, j)), worst caseO(N2) | ||
| X(i, j, n) | hasher andkey_equal areDefaultConstructible.value_type isEmplaceConstructible intoX from*i | Constructs an empty container with at leastn buckets, usinghasher() as the hash function andkey_equal() as the key equality predicate, and inserts elements from[i, j) into it | Average caseO(N) (N isstd::distance(i, j)), worst caseO(N2) | ||
| X(i, j) | hasher andkey_equal areDefaultConstructible.value_type isEmplaceConstructible intoX from*i | Constructs an empty container with an unspecified number of buckets, usinghasher() as the hash function andkey_equal() as the key equality predicate, and inserts elements from[i, j) into it | Average caseO(N) (N isstd::distance(i, j)), worst caseO(N2) | ||
| X(std::from_range, rg, n, hf, eq) (since C++23) | value_type isEmplaceConstructible intoX from*ranges::begin(rg) | Constructs an empty container with at leastn buckets, usinghf as the hash function andeq as the key equality predicate, and inserts elements fromrg into it | Average caseO(N) (N isranges::distance(rg)), worst caseO(N2) | ||
| X(std::from_range, rg, n, hf) (since C++23) | key_equal isDefaultConstructible.value_type isEmplaceConstructible intoX from*ranges::begin(rg) | Constructs an empty container with at leastn buckets, usinghf as the hash function andkey_equal() as the key equality predicate, and inserts elements fromrg into it | Average caseO(N) (N isranges::distance(rg)), worst caseO(N2) | ||
| X(std::from_range, rg, n) (since C++23) | hasher andkey_equal areDefaultConstructible.value_type isEmplaceConstructible intoX from*ranges::begin(rg) | Constructs an empty container with at leastn buckets, usinghasher() as the hash function andkey_equal() as the key equality predicate, and inserts elements fromrg into it | Average caseO(N) (N isranges::distance(rg)), worst caseO(N2) | ||
| X(std::from_range, rg) (since C++23) | hasher andkey_equal areDefaultConstructible.value_type isEmplaceConstructible intoX from*ranges::begin(rg) | Constructs an empty container with an unspecified number of buckets, usinghasher() as the hash function andkey_equal() as the key equality predicate, and inserts elements fromrg into it | Average caseO(N) (N isranges::distance(rg)), worst caseO(N2) | ||
| X(il) | X(il.begin(), il.end()) | ||||
| X(il, n) | X(il.begin(), il.end(), n) | ||||
| X(il, n, hf) | X(il.begin(), il.end(), n, hf) | ||||
| X(il, n, hf, eq) | X(il.begin(), il.end(), n, hf, eq) | ||||
| X(b) | Container; Copies the hash function, predicate, and maximum load factor | Average case linear inb.size(), worst caseO(N2) | |||
| a= b | X& | Container; copies the hash function, predicate, and maximum load factor | Average case linear inb.size(), worst caseO(N2) | ||
| 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 | Average case linear inil.size(), worst caseO(N2) | |
| b.hash_function() | hasher | b's hash function | Constant | ||
| b.key_eq() | key_equal | b's key equality predicate | 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 | Average caseO(1), worst caseO(a_uniq.size()) |
| a_eq.emplace(args) | iterator | value_type isEmplaceConstructible intoX fromargs | Inserts avalue_type objectt constructed withstd::forward<Args>(args)... | An iterator pointing to the newly inserted element | Average caseO(1), worst caseO(a_eq.size()) |
| a.emplace_hint(p, args) | iterator | value_type isEmplaceConstructible intoX fromargs | a.emplace( std::forward<Args>(args)...) | An iterator pointing to the element with the key equivalent to the newly inserted element. Theconst_iteratorp is a hint pointing to where the search should start. Implementations are permitted to ignore the hint | Average caseO(1), worst caseO(a.size()) |
| 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 indicates whether the insertion takes place, and theiterator component points to the element with key equivalent to the key oft | Average caseO(1), worst caseO(a_uniq.size()) |
| a_eq.insert(t) | iterator | Ift is a non-const rvalue,value_type isMoveInsertable intoX; otherwise,value_type isCopyInsertable intoX | Insertst | An iterator pointing to the newly inserted element | Average caseO(1), worst caseO(a_eq.size()) |
| a.insert(p, t) | iterator | Ift is a non-const rvalue,value_type isMoveInsertable intoX; otherwise,value_type isCopyInsertable intoX | a.insert(t). The iteratorp is a hint pointing to where the search should start. Implementations are permitted to ignore the hint | An iterator pointing to the element with the key equivalent to that oft | Average caseO(1), worst caseO(a.size()) |
| a.insert(i, j) | void | value_type isEmplaceConstructible intoX from*i. Neitheri norj are iterators intoa | a.insert(t) for each element in[i, j) | Average caseO(N), whereN isstd::distance(i, j), worst caseO(N·(a.size()+1)) | |
| a.insert_range(rg) (since C++23) | void | value_type isEmplaceConstructible intoX from*ranges::begin(rg).rg anda do not overlap | a.insert(t) for each elementt inrg | Average caseO(N), whereN isranges::distance(rg), worst caseO(N·(a.size()+1)) | |
| a.insert(il) | a.insert(il.begin(), il.end()) | ||||
| a_uniq.insert(nh) (since C++17) | 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(). Ensures: 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() | Average caseO(1), worst caseO(a_uniq.size()) | |
| a_eq.insert(nh) (since C++17) | 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. Ensures:nh is empty | Average caseO(1), worst caseO(a_eq.size()) | |
| a.insert(q, nh) (since C++17) | 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 iteratorq is a hint pointing to where the search should start. Implementations are permitted to ignore the hint. Ensures:nh is empty if insertion succeeds, unchanged if insertion fails | An iterator pointing to the element with key equivalent tonh.key() | Average caseO(1), worst caseO(a.size()) |
| a.extract(k) (since C++17) | node_type | Removes an element in the container with key equivalent tok | Anode_type owning the element if found, otherwise an emptynode_type | Average caseO(1), worst caseO(a.size()) | |
| a_tran.extract(kx) (since C++23) | node_type | Removes an element in the container with key equivalent tokx | Anode_type owning the element if found, otherwise an emptynode_type | Average caseO(1), worst caseO(a_tran.size()) | |
| a.extract(q) (since C++17) | node_type | Removes the element pointed to byq | Anode_type owning that element | Average caseO(1), worst caseO(a.size()) | |
| a.merge(a2) (since C++17) | void | a.get_allocator() == a2.get_allocator() | Attempts to extract each element ina2 and insert it intoa using the hash function and key equality predicate 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 and all iterators referring toa will be invalidated, but iterators to elements remaining ina2 will remain valid | Average caseO(N), whereN isa2.size(), worst caseO(N·(a.size()+1)) | |
| a.erase(k) | size_type | Erases all elements with key equivalent tok | The number of elements erased | Average caseO(a.count(k)), worst caseO(a.size()) | |
| a_tran.erase(kx) (since C++23) | size_type | Erases all elements with key equivalent tokx | The number of elements erased | Average caseO(a_tran.count(kx)), worst caseO(a_tran.size()) | |
| a.erase(q) | iterator | Erases the element pointed to byq | The iterator immediately followingq prior to the erasure | Average caseO(1), worst caseO(a.size()) | |
| a.erase(r) (since C++17) | iterator | Erases the element pointed to byr | The iterator immediately followingr prior to the erasure | Average caseO(1), worst caseO(a.size()) | |
| a.erase(q1, q2) | iterator | Erases all elements in the range[q1, q2) | The iterator immediately following the erased elements prior to the erasure | Average case linear instd::distance(q1, q2), worst caseO(a.size()) | |
| a.clear() | void | Erases all elements in the container. Ensures:a.empty() istrue | Linear ina.size() | ||
| b.find(k) | iterator;const_iterator for constantb | An iterator pointing to an element with key equivalent tok, orb.end() if no such element exists | Average caseO(1), worst caseO(b.size()) | ||
| a_tran.find(ke) (since C++17)? | iterator;const_iterator for constanta_tran | An iterator pointing to an element with key equivalent toke, ora_tran.end() if no such element exists | Average caseO(1), worst caseO(a_tran.size()) | ||
| b.count(k) | size_type | The number of elements with key equivalent tok | Average caseO(b.count(k)), worst caseO(b.size()) | ||
| a_tran.count(ke) (since C++17)? | size_type | The number of elements with key equivalent toke | Average caseO(a_tran.count(ke)), worst caseO(a_tran.size()) | ||
| b.contains(k) (since C++20)? | b.find(k)!= b.end() | ||||
| a_tran.contains(ke) (since C++20)? | a_tran.find(ke)!= a_tran.end() | ||||
| b.equal_range(k) | std::pair< iterator, iterator>; std::pair< | A range containing all elements with keys equivalent tok. Returns std::make_pair( | Average caseO(b.count(k)), worst caseO(b.size()) | ||
| a_tran.equal_range(ke) (since C++20)? | std::pair< iterator, iterator>; std::pair< | A range containing all elements with keys equivalent toke. Returns std::make_pair( | Average caseO(a_tran.count(ke)), worst caseO(a_tran.size()) | ||
| b.bucket_count() | size_type | The number of buckets thatb contains | Constant | ||
| b.max_bucket_count() | size_type | An upper bound on the number of buckets thatb can ever contain | Constant | ||
| b.bucket(k) | size_type | b.bucket_count()>0 | The index of the bucket in which elements with keys equivalent tok would be found, if any such element existed. The return value is in[0, b.bucket_count()) | Constant | |
| a_tran.bucket(ke) | size_type | a_tran. bucket_count()>0 | The index of the bucket in which elements with keys equivalent toke would be found, if any such element existed. The return value must be in the range[0, a_tran.bucket_count()) | Constant | |
| b.bucket_size(n) | size_type | n is in[0, b.bucket_count()) | The number of elements in thenth bucket | O(b.bucket_size(n)) | |
| b.begin(n) | local_iterator;const_local_iterator for constantb | n is in[0, b.bucket_count()) | An iterator referring to the first element in the bucket. If the bucket is empty, thenb.begin(n)== b.end(n) | Constant | |
| b.end(n) | local_iterator;const_local_iterator for constantb | n is in[0, b.bucket_count()) | An iterator which is the past-the-end value for the bucket | Constant | |
| b.cbegin(n) | const_local_iterator | n is in[0, b.bucket_count()) | An iterator referring to the first element in the bucket. If the bucket is empty, thenb.cbegin(n)== b.cend(n) | Constant | |
| b.cend(n) | const_local_iterator | n is in[0, b.bucket_count()) | An iterator which is the past-the-end value for the bucket | Constant | |
| b.load_factor() | float | The average number of elements per bucket | Constant | ||
| b.max_load_factor() | float | A positive number that the container attempts to keep the load factor less than or equal to. The container automatically increases the number of buckets as necessary to keep the load factor below this number | Constant | ||
| a.max_load_factor(z) | void | z is positive. May change the container's maximum load factor, usingz as a hint | Constant | ||
| a.rehash(n) | void | Ensures: a.bucket_count()>= | Average case linear ina.size(), worst caseO(N2) | ||
| a.reserve(n) | a.rehash(std::ceil( n/ a.max_load_factor())) |
| This section is incomplete Reason: Requirements regarding member functions. |
The following standard library containers satisfy theUnorderedAssociativeContainer requirements:
(C++11) | collection of unique keys, hashed by keys (class template)[edit] |
(C++11) | collection of keys, hashed by keys (class template)[edit] |
(C++11) | collection of key-value pairs, hashed by keys, keys are unique (class template)[edit] |
(C++11) | collection of key-value pairs, hashed 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 2156 | C++11 | the load factor after rehashing could only be strictly lower than the maximum load factor | allowed to be equal |
