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 When this is the case, member functions  (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  Container type 
a  Object of type X 
b  const Object of type X 
a_uniq  Object in X when X supports unique keys 
a_eq  Object in X when X supports multiple equivalent keys 
i , j  LegacyInputIterators denoting a valid range 
p , q2  valid const_iterator to a 
q , q1  dereferenceable const_iterator to a denoting a valid range 
il  Object of std::initializer_list<X::value_type> 
t  Object of type X::value_type 
k  Object of type X::key_type 
hf  const Object of type X::hasher 
eq  const Object of type X::key_equal 
n  Value of type X::size_type 
z  Value of type float 
expression  return type  pre/requirements  post/effects  complexity  

X::key_type  Key  compile time  
X::mapped_type  T 
std::unordered_map and std::unordered_multimap only  compile time  
X::value_type  Key 
std::unordered_set and std::unordered_multiset only. Erasable in X  compile time  
X::value_type  std::pair<const Key, T> 
std::unordered_map and std::unordered_multimap only. Erasable in X  compile time  
X::hasher  Hash  Hash  compile time  
X::key_equal 

BinaryPredicate taking two arguments of type Key and expressing an equivalence relation.  compile time  
X::local_iterator  An LegacyIterator whose category and types are the same as X::iterator  Can be used to iterate through a single bucket  compile time  
X::const_local_iterator  An LegacyIterator whose category and types are the same as X::const_iterator  Can be used to iterate through a single bucket  compile time  
X(n,hf,eq)  X 
hasher and key_equal CopyConstructible  Constructs an empty container with at least n buckets, using the given hash function and equality predicate  linear in n 

X(n,hf)  X 
hasher CopyConstructible, key_equal DefaultConstructible  Constructs an empty container with at least n buckets, using the given hash function and key_equal() as equality predicate  linear in n 

X(n)  X 
hasher and key_equal DefaultConstructible  Constructs an empty container with at least n buckets, using hasher() as hash function and key_equal() as equality predicate  linear in n 

X()  X 
hasher and key_equal DefaultConstructible  Constructs an empty container with an unspecified number of buckets, using hasher() as hash function and key_equal() as equality predicate  constant  
X(i,j,n,hf,eq)  X 
hasher and key_equal CopyConstructible, value_type EmplaceConstructible into X from *i  Constructs an empty container with at least n buckets, using the given hash function and equality predicate, and inserts elements from [i,j) into it.  average linear, worst quadratin (on the distance between i and j ) 

X(i,j,n,hf)  X 
key_equal DefaultConstructible
 As above, with eq=key_equal()
 see above  
X(i,j,n)  X 
hasher DefaultConstructible
 As above, with hf=hasher()
 see above  
X(i,j)  X  As above, with an unspecified number of buckets  see above  
X(il)  X  X(il.begin(),il.end()  see above  
X(il,n)  X  X(il.begin(),il.end(),n  see above  
X(il,n,hf)  X  X(il.begin(),il.end(),n,hf  see above  
X(il,n,hf,eq)  X  X(il.begin(),il.end(),n,hf,eq  see above  
X(b)  X  Copy constructors, also copies the hash function, predicate and maximum load factor  average linear, worst quadratic (in b.size() ) 

a = b  X&  Copy assignment, also copies the hash function, predicate and maximum load factor  average linear, worst quadratic (in b.size() ) 

a = il  X& 
value_type CopyAssignable and CopyInsertable into X
 a = X(il)
 see above 
(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.
http://en.cppreference.com/w/cpp/named_req/UnorderedAssociativeContainer