# C++ named requirements: UnorderedAssociativeContainer

From cppreference.com
< cpp‎ | named req

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 Hash::transparent_key_equal exists and names a type, then Hash::transparent_key_equal::is_transparent must be valid and name a type, and `Pred` must be either Hash::transparent_key_equal, or std::equal_to<Key> (the program is ill-formed otherwise). When this is the case, member functions `find`, `contains`, `count`, and `equal_range` accept arguments of types other than `Key` and expect that `Hash` is callable with values of those types, and that Hash::transparent_key_equal is a transparent comparison function such as std::equal_to<>. | (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 re-arranged 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`).

### Requirements

### 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 |
`Pred` | (until C++20)
Hash::transparent_key_equal if it's valid and names a type, `Pred` otherwise | (since C++20)
| 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

| This section is incomplete Reason: requirements regarding member functions

### Unordered associative containers in the standard library

unordered_set (C++11) | collection of unique keys, hashed by keys (class template)
unordered_multiset (C++11) | collection of keys, hashed by keys (class template)
unordered_map (C++11) | collection of key-value pairs, hashed by keys, keys are unique (class template)
unordered_multimap (C++11) | collection of key-value pairs, hashed by keys (class template)

Retrieved from "https://en.cppreference.com/mwiki/index.php?title=cpp/named_req/UnorderedAssociativeContainer&oldid=107284"