Unordered associative containers are Containers 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 by Key
; Hash
, a Hash function object which acts as hash function on Key
; and Pred
, a BinaryPredicate evaluating equivalence between Key
s. std::unordered_map and std::unordered_multimap also have a mapped type T
associated with the Key
.
If two Key
s are equal according to Pred
, Hash
must return the same value for both keys.
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.
LegendX
An unordered associative container class a A value of type X
a2 A value of a type with nodes compatible with type X
b A value of type X
or const X
a_uniq A value of type X
when X
supports unique keys a_eq A value of type X
when X
supports equivalent keys a_tran A value of type X
or const X when the qualified identifiers X::key_equal::is_transparent
and X::hasher::is_transparent
are both valid and denote types i, j Input iterators that refer to value_type
[
i,
j)
A valid range rg (since C++23) A value of a type R
that models container-compatible-range<value_type>
p, q2 Valid constant iterators to a q, q1 Valid dereferenceable constant iterators to a r A valid dereferenceable iterator to a [
q1,
q2)
A valid range in a il A value of type std::initializer_list<value_type> t A value of type X::value_type
k A value of type key_type
hf A value of type hasher
or const hasher eq A value of type key_equal
or const key_equal ke A value such that
where r1 and r2 are keys of elements in a_tran
kx (since C++23) A value such thatiterator
or const_iterator
,where r1 and r2 are keys of elements in a_tran
n A value of typesize_type
z A value of type float nh (since C++17) An rvalue of type X::node_type Expression Result Preconditions Effects Returns Complexity X(n, hf, eq) Constructs an empty container with at least n buckets, using hf as the hash function and eq as the key equality predicate O(n) X(n, hf) key_equal
is DefaultConstructible Constructs an empty container with at least n buckets, using hf as the hash function and key_equal() as the key equality predicate O(n) X(n) hasher
and key_equal
are DefaultConstructible Constructs an empty container with at least n buckets, using hasher() as the hash function and key_equal() as the key equality predicate O(n) X a = X();
hasher
and key_equal
are DefaultConstructible Constructs an empty container with an unspecified number of buckets, using hasher() as the hash function and key_equal() as the key equality predicate Constant X(i, j, n, hf, eq) value_type
is EmplaceConstructible into X
from *i Constructs an empty container with at least n buckets, using hf as the hash function and eq as the key equality predicate, and inserts elements from [
i,
j)
into it Average case O(N) (N is std::distance(i, j)), worst case O(N2) X(i, j, n, hf) key_equal
is the DefaultConstructible. value_type
is EmplaceConstructible into X
from *i Constructs an empty container with at least n buckets, using hf as the hash function and key_equal() as the key equality predicate, and inserts elements from [
i,
j)
into it Average case O(N) (N is std::distance(i, j)), worst case O(N2) X(i, j, n) hasher
and key_equal
are DefaultConstructible. value_type
is EmplaceConstructible into X
from *i Constructs an empty container with at least n buckets, using hasher() as the hash function and key_equal() as the key equality predicate, and inserts elements from [
i,
j)
into it Average case O(N) (N is std::distance(i, j)), worst case O(N2) X(i, j) hasher
and key_equal
are DefaultConstructible. value_type
is EmplaceConstructible into X
from *i Constructs an empty container with an unspecified number of buckets, using hasher() as the hash function and key_equal() as the key equality predicate, and inserts elements from [
i,
j)
into it Average case O(N) (N is std::distance(i, j)), worst case O(N2) X(std::from_range,value_type
is EmplaceConstructible into X
from *ranges::begin(rg) Constructs an empty container with at least n buckets, using hf as the hash function and eq as the key equality predicate, and inserts elements from rg into it Average case O(N) (N is ranges::distance(rg)), worst case O(N2) X(std::from_range,key_equal
is DefaultConstructible. value_type
is EmplaceConstructible into X
from *ranges::begin(rg) Constructs an empty container with at least n buckets, using hf as the hash function and key_equal() as the key equality predicate, and inserts elements from rg into it Average case O(N) (N is ranges::distance(rg)), worst case O(N2) X(std::from_range,hasher
and key_equal
are DefaultConstructible. value_type
is EmplaceConstructible into X
from *ranges::begin(rg) Constructs an empty container with at least n buckets, using hasher() as the hash function and key_equal() as the key equality predicate, and inserts elements from rg into it Average case O(N) (N is ranges::distance(rg)), worst case O(N2) X(std::from_range,hasher
and key_equal
are DefaultConstructible. value_type
is EmplaceConstructible into X
from *ranges::begin(rg) Constructs an empty container with an unspecified number of buckets, using hasher() as the hash function and key_equal() as the key equality predicate, and inserts elements from rg into it Average case O(N) (N is ranges::distance(rg)), worst case O(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 in b.size(), worst case O(N2) a = b X&
Container; copies the hash function, predicate, and maximum load factor Average case linear in b.size(), worst case O(N2) a = il X&
value_type
is CopyInsertable into X
and CopyAssignable Assigns the range [
il.begin(),
il.end())
into a. All existing elements of a are either assigned to or destroyed Average case linear in il.size(), worst case O(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<
value_type
is EmplaceConstructible into X
from args Inserts a value_type
object t constructed with std::forward<Args>(args)... if and only if there is no element in the container with key equivalent to the key of t The bool component of the returned pair is true 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 of t Average case O(1), worst case O(a_uniq.size()) a_eq.emplace(args) iterator
value_type
is EmplaceConstructible into X
from args Inserts a value_type
object t constructed with std::forward<Args>(args)... An iterator pointing to the newly inserted element Average case O(1), worst case O(a_eq.size()) a.emplace_hint(p, args) iterator
value_type
is EmplaceConstructible into X
from args a.emplace(const_iterator
p is a hint pointing to where the search should start. Implementations are permitted to ignore the hint Average case O(1), worst case O(a.size()) a_uniq.insert(t) std::pair<
value_type
is MoveInsertable into X
; otherwise, value_type
is CopyInsertable into X
Inserts t if and only if there is no element in the container with key equivalent to the key of t The bool component of the returned pair indicates whether the insertion takes place, and the iterator
component points to the element with key equivalent to the key of t Average case O(1), worst case O(a_uniq.size()) a_eq.insert(t) iterator
If t is a non-const rvalue, value_type
is MoveInsertable into X
; otherwise, value_type
is CopyInsertable into X
Inserts t An iterator pointing to the newly inserted element Average case O(1), worst case O(a_eq.size()) a.insert(p, t) iterator
If t is a non-const rvalue, value_type
is MoveInsertable into X
; otherwise, value_type
is CopyInsertable into X
a.insert(t). The iterator p 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 of t Average case O(1), worst case O(a.size()) a.insert(i, j) void value_type
is EmplaceConstructible into X
from *i. Neither i nor j are iterators into a a.insert(t) for each element in
[
i,
j)
Average case O(N), where N is std::distance(i, j), worst case O(N·(a.size() + 1)) a.insert_range(rg)
value_type
is EmplaceConstructible into X
from *ranges::begin(rg). rg and a do not overlap a.insert(t) for each element t in rg Average case O(N), where N is ranges::distance(rg), worst case O(N·(a.size() + 1)) a.insert(il) a.insert(il.begin(), il.end()) a_uniq.insert(nh)
insert_return_type
nh is empty or
a_uniq.get_allocator()
==
nh.get_allocator() is true
iterator
nh is empty or
a_eq.get_allocator()
==
nh.get_allocator() is true
iterator
nh is empty or
a.get_allocator()
==
nh.get_allocator() is true
node_type
Removes an element in the container with key equivalent to k A node_type
owning the element if found, otherwise an empty node_type
Average case O(1), worst case O(a.size()) a_tran.extract(kx)
node_type
Removes an element in the container with key equivalent to kx A node_type
owning the element if found, otherwise an empty node_type
Average case O(1), worst case O(a_tran.size()) a.extract(q)
node_type
Removes the element pointed to by q A node_type
owning that element Average case O(1), worst case O(a.size()) a.merge(a2)
size_type
Erases all elements with key equivalent to k The number of elements erased Average case O(a.count(k)), worst case O(a.size()) a_tran.erase(kx)
size_type
Erases all elements with key equivalent to kx The number of elements erased Average case O(a_tran.count(kx)), worst case O(a_tran.size()) a.erase(q) iterator
Erases the element pointed to by q The iterator immediately following q prior to the erasure Average case O(1), worst case O(a.size()) a.erase(r)
iterator
Erases the element pointed to by r The iterator immediately following r prior to the erasure Average case O(1), worst case O(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 in std::distance(q1, q2), worst case O(a.size()) a.clear() void Erases all elements in the container. Ensures: a.empty() is true Linear in a.size() b.find(k) iterator
; const_iterator
for constant b An iterator pointing to an element with key equivalent to k, or b.end() if no such element exists Average case O(1), worst case O(b.size()) a_tran.find(ke)
iterator
; const_iterator
for constant a_tran An iterator pointing to an element with key equivalent to ke, or a_tran.end() if no such element exists Average case O(1), worst case O(a_tran.size()) b.count(k) size_type
The number of elements with key equivalent to k Average case O(b.count(k)), worst case O(b.size()) a_tran.count(ke)
size_type
The number of elements with key equivalent to ke Average case O(a_tran.count(ke)), worst case O(a_tran.size()) b.contains(k)
std::pair<
const_iterator,
const_iterator> for constant b
std::make_pair(
b.end(), b.end()) if no such elements exist
std::pair<
const_iterator,
const_iterator> for constant a_tran
std::make_pair(
a_tran.end(),
a_tran.end()) if no such elements exist
size_type
The number of buckets that b contains Constant b.max_bucket_count() size_type
An upper bound on the number of buckets that b can ever contain Constant b.bucket(k) size_type
b.bucket_count() > 0 The index of the bucket in which elements with keys equivalent to k 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.[
â0â,
a_tran.bucket_count())
Constant b.bucket_size(n) size_type
n is in [
â0â,
b.bucket_count())
The number of elements in the nth bucket O(b.bucket_size(n)) b.begin(n) local_iterator
; const_local_iterator
for constant b n is in [
â0â,
b.bucket_count())
An iterator referring to the first element in the bucket. If the bucket is empty, then b.begin(n) == b.end(n) Constant b.end(n) local_iterator
; const_local_iterator
for constant b 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, then b.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, using z as a hint Constant a.rehash(n) void Ensures:
a.bucket_count() >=
a.size() / a.max_load_factor() and a.bucket_count() >= n
The following standard library containers satisfy the UnorderedAssociativeContainer requirements:
The following behavior-changing defect reports were applied retroactively to previously published C++ standards.
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4