Unordered associative containers are
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
function object which acts as hash function on Key; and Pred, a
evaluating equivalence between Keys.
and
also have a mapped type T associated with the Key.
If two Keys 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.
ExpressionResultPreconditionsEffectsReturnsComplexity 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
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
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) Xa=X();
Xa;hasher and key_equal are
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
into X from *iConstructs 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
. value_type is
into X from *iConstructs 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
. value_type is
into X from *iConstructs 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
. value_type is
into X from *iConstructs 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,
rg, n, hf, eq)
(since C++23)value_type is
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,
rg, n, hf)
(since C++23)key_equal is
. value_type is
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,
rg, n)
(since C++23)hasher and key_equal are
. value_type is
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,
rg)
(since C++23)hasher and key_equal are
. value_type is
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)
; Copies the hash function, predicate, and maximum load factor Average case linear in b.size(), worst case O(N2)a = bX&
; copies the hash function, predicate, and maximum load factor Average case linear in b.size(), worst case O(N2)a = ilX&value_type is
into X and
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()hasherb's hash function Constant b.key_eq()key_equalb's key equality predicate Constant a_uniq.emplace(args)std::pair<
iterator,
bool>value_type is
into X from argsInserts 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 tThe 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 tAverage case O(1), worst case O(a_uniq.size()) a_eq.emplace(args)iteratorvalue_type is
into X from argsInserts 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)iteratorvalue_type is
into X from argsa.emplace(
std::forward<Args>(args)...)An iterator pointing to the element with the key equivalent to the newly inserted element. The const_iteratorp 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<
iterator,
bool>If t is a non-const rvalue, value_type is
into X; otherwise, value_type is
into XInserts t if and only if there is no element in the container with key equivalent to the key of tThe 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 tAverage case O(1), worst case O(a_uniq.size()) a_eq.insert(t)iteratorIf t is a non-const rvalue, value_type is
into X; otherwise, value_type is
into XInserts tAn iterator pointing to the newly inserted element Average case O(1), worst case O(a_eq.size()) a.insert(p, t)iteratorIf t is a non-const rvalue, value_type is
into X; otherwise, value_type is
into Xa.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 tAverage case O(1), worst case O(a.size()) a.insert(i, j)voidvalue_type is
into X from *i. Neither i nor j are iterators into aa.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)
(since C++23)voidvalue_type is
into X from *ranges::begin(rg). rg and a do not overlap a.insert(t) for each element t in rgAverage 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)
(since C++17)insert_return_typenh is empty or a_uniq.get_allocator()
==
nh.get_allocator() is true
If nh is empty, has no effect. Otherwise, inserts the element owned by nh if and only if there is no element in the container with a key equivalent to nh.key(). Ensures: If nh is empty, inserted is false, position is end(), and node is empty. Otherwise if the insertion took place, inserted is true, position points to the inserted element, and node is empty; if the insertion failed, inserted is false, node has the previous value of nh, and position points to an element with a key equivalent to nh.key()Average case O(1), worst case O(a_uniq.size()) a_eq.insert(nh)
(since C++17)iteratornh is empty or a_eq.get_allocator()
==
nh.get_allocator() is true
If nh is empty, has no effect and returns a_eq.end(). Otherwise, inserts the element owned by nh and returns an iterator pointing to the newly inserted element. Ensures: nh is empty Average case O(1), worst case O(a_eq.size()) a.insert(q, nh)
(since C++17)iteratornh is empty or a.get_allocator()
==
nh.get_allocator() is true
If nh is empty, has no effect and returns a.end(). Otherwise, inserts the element owned by nh if and only if there is no element with key equivalent to nh.key() in containers with unique keys; always inserts the element owned by nh in containers with equivalent keys. The iterator q 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 to nh.key()Average case O(1), worst case O(a.size()) a.extract(k)
(since C++17)node_typeRemoves an element in the container with key equivalent to kA node_type owning the element if found, otherwise an empty node_typeAverage case O(1), worst case O(a.size()) a_tran.extract(kx)
(since C++23)node_typeRemoves an element in the container with key equivalent to kxA node_type owning the element if found, otherwise an empty node_typeAverage case O(1), worst case O(a_tran.size()) a.extract(q)
(since C++17)node_typeRemoves the element pointed to by qA node_type owning that element Average case O(1), worst case O(a.size()) a.merge(a2)
(since C++17)voida.get_allocator()
==
a2.get_allocator()Attempts to extract each element in a2 and insert it into a using the hash function and key equality predicate of a. In containers with unique keys, if there is an element in a with key equivalent to the key of an element from a2, then that element is not extracted from a2. Ensures: Pointers and references to the transferred elements of a2 refer to those same elements but as members of a. Iterators referring to the transferred elements and all iterators referring to a will be invalidated, but iterators to elements remaining in a2 will remain valid Average case O(N), where N is a2.size(), worst case O(N·(a.size() + 1)) a.erase(k)size_typeErases all elements with key equivalent to kThe number of elements erased Average case O(a.count(k)), worst case O(a.size()) a_tran.erase(kx)
(since C++23)size_typeErases all elements with key equivalent to kxThe number of elements erased Average case O(a_tran.count(kx)), worst case O(a_tran.size()) a.erase(q)iteratorErases the element pointed to by qThe iterator immediately following q prior to the erasure Average case O(1), worst case O(a.size()) a.erase(r)
(since C++17)iteratorErases the element pointed to by rThe iterator immediately following r prior to the erasure Average case O(1), worst case O(a.size()) a.erase(q1, q2)iteratorErases 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()voidErases all elements in the container. Ensures: a.empty() is trueLinear in a.size()b.find(k)iterator; const_iterator for constant bAn 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)
(since C++17)? iterator; const_iterator for constant a_tranAn 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_typeThe number of elements with key equivalent to kAverage case O(b.count(k)), worst case O(b.size()) a_tran.count(ke)
(since C++17)? size_typeThe number of elements with key equivalent to keAverage case O(a_tran.count(ke)), worst case O(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<
const_iterator,
const_iterator> for constant b
A range containing all elements with keys equivalent to k. Returns std::make_pair(
b.end(), b.end()) if no such elements exist
Average case O(b.count(k)), worst case O(b.size()) a_tran.equal_range(ke)
(since C++20)? std::pair<
iterator,
iterator>; std::pair<
const_iterator,
const_iterator> for constant a_tran
A range containing all elements with keys equivalent to ke. Returns std::make_pair(
a_tran.end(),
a_tran.end()) if no such elements exist
Average case O(a_tran.count(ke)), worst case O(a_tran.size()) b.bucket_count()size_typeThe number of buckets that b contains Constant b.max_bucket_count()size_typeAn upper bound on the number of buckets that b can ever contain Constant b.bucket(k)size_typeb.bucket_count() > 0The 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_typea_tran.
bucket_count() > 0The index of the bucket in which elements with keys equivalent to ke 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_typen 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 bn 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 bn is in [0, b.bucket_count())An iterator which is the past-the-end value for the bucket Constant b.cbegin(n)const_local_iteratorn 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_iteratorn is in [0, b.bucket_count())An iterator which is the past-the-end value for the bucket Constant b.load_factor()floatThe average number of elements per bucket Constant b.max_load_factor()floatA 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)voidz is positive. May change the container's maximum load factor, using z as a hint Constant a.rehash(n)voidEnsures: a.bucket_count() >=
a.size() / a.max_load_factor() and a.bucket_count() >= n
Average case linear in a.size(), worst case O(N2)a.reserve(n)a.rehash(std::ceil(
n / a.max_load_factor()))The following standard library containers satisfy the UnorderedAssociativeContainer requirements:
The following behavior-changing defect reports were applied retroactively to previously published C++ standards.