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.
If both  (since C++20) 
std::unordered_map
and std::unordered_set
can contain at most one element with a given key, std::unordered_multiset
and std::unordered_multimap
instead can have multiple elements with the same key (which must always be adjacent on iterations).
For std::unordered_set
and std::unordered_multiset
the value type is the same as the key type and both iterator
and const_iterator
are constant iterators. For std::unordered_map
and std::unordered_multimap
the value type is std::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 rearranged in different buckets but it doesn't invalidate references to the elements.
Unordered associative containers meet the requirements of AllocatorAwareContainer. For std::unordered_map
and std::unordered_multimap
the requirements of value_type
in AllocatorAwareContainer apply to key_type
and mapped_type
(not to value_type
).
Legend 

X  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 qualifiedids 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 containercompatiblerange<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 
kx (since C++23)  A value such that
where 
n  A value of type size_type 
z  A value of type float 
nh (since C++17)  An rvalue of type X::node_type 
Name  Type  Requirements  Notes 

X::key_type 
Key  
X::mapped_type 
T 
std::unordered_map and std::unordered_multimap only  
X::value_type 
Key 
std::unordered_set and std::unordered_multiset only. Erasable in X  
std::pair<const Key, T> 
std::unordered_map and std::unordered_multimap only. Erasable in X  
X::hasher 
Hash  Hash  
X::key_equal 
Pred 
CopyConstructible; BinaryPredicate that takes two arguments of type Key and expresses an equivalence relation  
X::local_iterator  LegacyIterator  Category and types are the same as X::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 as X::const_iterator 

X::node_type (since C++17)  A specialization of nodehandle class template  The public nested types are the same as the corresponding types in X 
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(); X a; 
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(N^{2}) 

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(N^{2}) 

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(N^{2}) 

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(N^{2}) 

X(std::from_range, rg, n, hf, eq) (since C++23) 
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(N^{2}) 

X(std::from_range, rg, n, hf) (since C++23) 
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(N^{2}) 

X(std::from_range, rg, n) (since C++23) 
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(N^{2}) 

X(std::from_range, rg) (since C++23) 
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(N^{2}) 

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(N^{2}) 

a = b 
X&  Container; copies the hash function, predicate, and maximum load factor  Average case linear in b.size() , worst case O(N^{2}) 

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(N^{2}) 

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(  An iterator pointing to the element with the key equivalent to the newly inserted element. The 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<  If t is a nonconst rvalue, 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 nonconst 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 nonconst 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) (since C++23) 
void 
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) (since C++17) 
insert_return_type 
nh is empty or
 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) 
iterator 
nh is empty or
 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) 
iterator 
nh is empty or
 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_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) (since C++23) 
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) (since C++17) 
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) (since C++17) 
void 
a.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_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) (since C++23) 
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) (since C++17) 
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) (since C++17)? 
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) (since C++17)? 
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) (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< ;
 A range containing all elements with keys equivalent to k . Returns
 Average case O(b.count(k) ), worst case O(b.size() ) 

a_tran.equal_range(ke) (since C++20)? 
std::pair< ;
 A range containing all elements with keys equivalent to ke . Returns
 Average case O(a_tran.count(ke) ), worst case O(a_tran.size() ) 

b.bucket_count() 
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  
b.bucket_size(n) 
size_type 
n is in [ 0 , b.bucket_count() )  The number of elements in the n ^{th} 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 pasttheend 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 pasttheend 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:
 Average case linear in a.size() , worst case O(N^{2}) 

a.reserve(n) 
a.rehash(std::ceil( 
(C++11)  collection of unique keys, hashed by keys (class template) 
(C++11)  collection of keys, hashed by keys (class template) 
(C++11)  collection of keyvalue pairs, hashed by keys, keys are unique (class template) 
(C++11)  collection of keyvalue pairs, hashed by keys (class template) 
© cppreference.com
Licensed under the Creative Commons AttributionShareAlike Unported License v3.0.
https://en.cppreference.com/w/cpp/named_req/UnorderedAssociativeContainer