C++ Reference ยท Containers
C++ std::unordered_map class
Reference for std::unordered_map: average O(1) lookup, hashing, custom hash and equality, buckets, load factor, rehash, reserve and iterator invalidation.
std::unordered_map<Key, T> is a hash table of key-value pairs with unique keys. Lookup, insertion and erasure take O(1) time on average and O(n) in the worst case (when many keys land in the same bucket). Unlike std::map, there is no order: iteration visits the elements in an unspecified sequence that can change when the table grows.
Its interface is almost identical to std::map: operator[], at, find, contains, insert, emplace, try_emplace, erase. What it adds is hash-specific tuning (reserve, rehash, bucket_count, load_factor) and what it lacks is anything based on order (lower_bound, upper_bound, sorted iteration).
#include <unordered_map> std::unordered_map<std::string, int> score = {{"ann", 3}, {"bob", 5}}; score["cy"] = 1;
Try it
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.
Syntax
template <class Key, class T, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class Allocator = std::allocator<std::pair<const Key, T>>> class unordered_map; void reserve(size_type n); void rehash(size_type buckets); size_type bucket_count() const; float load_factor() const; float max_load_factor() const; void max_load_factor(float ml);
| Name | Description |
|---|---|
Hash |
Function object mapping a key to a std::size_t. Equal keys must have equal hashes. |
KeyEqual |
Decides whether two keys are the same key. |
n |
Number of elements to make room for (reserve). |
buckets |
Minimum bucket count (rehash). |
Returns: the lookup and insertion functions behave exactly like their std::map counterparts.
Errors / undefined behavior: at() throws std::out_of_range. If Hash or KeyEqual is inconsistent (equal keys with different hashes), the behavior is undefined. A key must not be modified while it is in the table.
Usage notes
- Order is unspecified and may differ between standard libraries and versions, and after any rehash. Never print or compare iteration order; sort first, as above.
- Complexity: average O(1) for
find,insert,erase,operator[]; worst case O(n). Bad hash functions push you toward the worst case. - Rehashing: when
size() / bucket_count()would exceedmax_load_factor()(1.0 by default), the table grows and all iterators are invalidated, though references and pointers to elements stay valid. Callreserve(n)before a bulk insert to avoid repeated rehashes. - Custom keys need a hash and an equality. Specialize
std::hash<T>or pass your ownHashtype as shown. Combine member hashes; do not just add them. - Do not rely on
std::hashvalues being the same across runs or platforms, and never use them for persistent data. std::hash<std::string>also hashesstd::string_view; with transparent hash and equality (C++20) you can look up bystring_viewwithout allocating.- Versus
std::map: faster on average and no<needed, but no ordering, no range queries, and the occasional expensive rehash. - Memory: node-based like
std::map, plus an array of buckets. Elements are not contiguous.