Skip to content
Tutorials Center
My learning

Topics

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).

C++
#include <unordered_map>
std::unordered_map<std::string, int> score = {{"ann", 3}, {"bob", 5}};
score["cy"] = 1;

Try it

C++ Counting with a hash map (sort before printing)

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.

C++ A custom key type with its own hash

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

C++
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 exceed max_load_factor() (1.0 by default), the table grows and all iterators are invalidated, though references and pointers to elements stay valid. Call reserve(n) before a bulk insert to avoid repeated rehashes.
  • Custom keys need a hash and an equality. Specialize std::hash<T> or pass your own Hash type as shown. Combine member hashes; do not just add them.
  • Do not rely on std::hash values being the same across runs or platforms, and never use them for persistent data.
  • std::hash<std::string> also hashes std::string_view; with transparent hash and equality (C++20) you can look up by string_view without 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.