C++ unordered_map

A std::unordered_map is an associative container from the C++ Standard Template Library that stores elements as key-value pairs, where every key is unique and maps to exactly one value. Unlike std::map, which keeps its keys sorted using a balanced binary tree, unordered_map organizes elements using a hash table, giving average constant-time performance for lookup, insertion, and deletion. It is one of the most widely used containers in real-world C++ code and competitive programming whenever you need fast key-based access and don’t care about ordering.

Overview / How It Works

unordered_map is declared in the <unordered_map> header. Internally, it maintains an array of "buckets." Each bucket is conceptually a small linked list that can hold zero or more key-value pairs. When you insert a pair, the container computes a hash of the key using a hash functor (by default std::hash<Key>), reduces that hash to an index within the bucket array (roughly hash % bucket_count), and places the element in that bucket. Looking up a key follows the same path: hash the key, jump straight to the right bucket, then scan the (usually very short) list inside that bucket for a matching key using an equality functor (by default std::equal_to<Key>).

Because jumping to a bucket is O(1) and each bucket normally holds only one or a few elements, average-case operations are O(1). The worst case, however, is O(n): if the hash function sends many keys into the same bucket, that bucket degenerates into a long list that must be scanned linearly. This is why choosing or providing a good hash function matters for custom key types.

The ratio of stored elements to the number of buckets is called the load factor (size() / bucket_count()). By default, unordered_map keeps the load factor below 1.0 (its max_load_factor). When an insertion would push the load factor above this threshold, the container automatically rehashes: it allocates a larger bucket array and reinserts every existing element into its new bucket. Rehashing is an O(n) operation, but because it happens rarely relative to the number of insertions, insertion is still amortized O(1) on average.

Two properties of the key type are mandatory for using it in an unordered_map: it must be hashable (a std::hash specialization or custom hash functor must exist for it) and it must support equality comparison (operator== or a custom equality functor). Built-in types and std::string already have std::hash specializations, so they work out of the box. Custom structs and classes do not, unless you supply one yourself, as shown in Example 3.

Compared to std::map: map is a red-black tree that keeps keys sorted and guarantees O(log n) worst-case operations. unordered_map gives up ordering in exchange for faster average performance and no guaranteed worst case. If you need sorted iteration or worst-case guarantees, use map; if you just need fast key lookups and don’t care about order, unordered_map is usually the better default.

Syntax

The full template declaration looks like this:

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;

In practice, most declarations only specify the first two parameters:

std::unordered_map<std::string, int> wordCounts;

Part	Meaning
`Key`	The type used to look up elements (must be hashable and equality-comparable).
`T`	The type of value stored/mapped to each key.
`Hash`	Functor used to compute a hash code from a key. Defaults to `std::hash<Key>`.
`KeyEqual`	Functor used to compare two keys for equality. Defaults to `std::equal_to<Key>`.
`Allocator`	Controls memory allocation; almost always left at its default.

Member functions you will use constantly:

Function	Purpose
`m[key]`	Accesses the value for `key`; inserts a default-constructed value if the key doesn’t exist.
`m.at(key)`	Accesses the value for `key`; throws `std::out_of_range` if missing (never inserts).
`m.insert({key, value})`	Inserts a pair only if the key isn’t already present.
`m.emplace(key, value)`	Constructs the pair in place, avoiding a temporary object.
`m.find(key)`	Returns an iterator to the element, or `m.end()` if not found.
`m.count(key)`	Returns 1 if the key exists, 0 otherwise (keys are always unique).
`m.erase(key)`	Removes the element with that key, if present.
`m.size()` / `m.empty()`	Number of elements / whether the container is empty.
`m.bucket_count()` / `m.load_factor()`	Introspect the current hash table state.
`m.reserve(n)`	Pre-allocates enough buckets for `n` elements, reducing future rehashes.

Examples

Example 1: Basic Operations

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

int main() {
    unordered_map<string, int> ages;
    ages["Alice"] = 30;
    ages["Bob"] = 25;
    ages.insert({"Charlie", 35});

    cout << "Alice is " << ages["Alice"] << " years old" << endl;
    cout << "Bob is " << ages["Bob"] << " years old" << endl;
    cout << "Charlie is " << ages["Charlie"] << " years old" << endl;

    auto it = ages.find("Bob");
    if (it != ages.end()) {
        cout << "Found Bob: " << it->second << endl;
    }

    ages.erase("Alice");
    cout << "Size after erase: " << ages.size() << endl;
    cout << "Contains Alice? " << (ages.count("Alice") ? "yes" : "no") << endl;

    return 0;
}

Output:

Alice is 30 years old
Bob is 25 years old
Charlie is 35 years old
Found Bob: 25
Size after erase: 2
Contains Alice? no

This example creates an unordered_map<string, int> and populates it two ways: operator[] and insert(). find() returns an iterator (not a value), so we check it against end() before dereferencing it with it->second. After erasing "Alice", size() drops to 2, and count() confirms the key is gone (it returns 0, since keys can’t repeat in a map).

Example 2: Counting Word Frequencies

#include <iostream>
#include <unordered_map>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
using namespace std;

int main() {
    string text = "the quick brown fox jumps over the lazy dog the fox runs";
    unordered_map<string, int> wordCount;

    istringstream iss(text);
    string word;
    while (iss >> word) {
        wordCount[word]++;
    }

    vector<string> keys;
    for (const auto& entry : wordCount) {
        keys.push_back(entry.first);
    }
    sort(keys.begin(), keys.end());

    for (const auto& key : keys) {
        cout << key << ": " << wordCount[key] << endl;
    }

    return 0;
}

Output:

brown: 1
dog: 1
fox: 2
jumps: 1
lazy: 1
over: 1
quick: 1
runs: 1
the: 3

This is the canonical use case for unordered_map: counting occurrences. wordCount[word]++ relies on operator[] default-constructing a new entry (value 0) the first time a word is seen, then incrementing it. Because unordered_map does not guarantee any iteration order, the code copies the keys into a vector and sorts them before printing, so the output is deterministic and reproducible regardless of the internal hash table layout.

Example 3: Using a Custom Struct as a Key

#include <iostream>
#include <unordered_map>
#include <string>
#include <functional>
using namespace std;

struct Point {
    int x, y;
    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

struct PointHash {
    size_t operator()(const Point& p) const {
        return hash<int>()(p.x) ^ (hash<int>()(p.y) << 1);
    }
};

int main() {
    unordered_map<Point, string, PointHash> labels;
    labels[{0, 0}] = "origin";
    labels[{1, 2}] = "point A";
    labels[{3, 4}] = "point B";

    Point p1{1, 2};
    auto it = labels.find(p1);
    if (it != labels.end()) {
        cout << "(1,2) is labeled: " << it->second << endl;
    }

    cout << "Number of points stored: " << labels.size() << endl;

    Point missing{9, 9};
    if (labels.find(missing) == labels.end()) {
        cout << "(9,9) not found" << endl;
    }

    return 0;
}

Output:

(1,2) is labeled: point A
Number of points stored: 3
(9,9) not found

unordered_map has no built-in std::hash for arbitrary structs, so Point supplies its own hash functor, PointHash, passed as the third template argument. It combines the hashes of the two members with a shift and XOR to spread values across buckets. The struct also defines operator==, which the map uses to resolve collisions within a bucket. Without both pieces, the code would not compile (see Common Mistakes below).

Under the Hood: Step by Step

Here is what actually happens on a call like m[key] = value or m.find(key):

The key is passed to the Hash functor, producing a size_t hash code.
The hash code is reduced to a bucket index, conceptually index = hash % bucket_count().
The implementation jumps directly to that bucket (O(1) array access).
It walks the (normally short) chain of entries in that bucket, comparing each existing key to the target using KeyEqual (operator== by default).
On a hit, the existing value is returned/updated. On a miss during insertion, a new node is created and linked into the bucket.
After insertion, the container checks whether size() / bucket_count() now exceeds max_load_factor(). If so, it rehashes: it allocates a larger bucket array and re-inserts every element by recomputing its bucket index.
On erase(key), the same hash-then-scan process locates the node, which is then unlinked from its bucket’s chain and destroyed.

An important guarantee: rehashing invalidates iterators (because bucket contents move around), but it does not invalidate pointers or references to the stored elements themselves — the key-value pair objects stay at the same memory address; only the bucket bookkeeping changes. Erasing an element only invalidates iterators/references to that specific element, not to others.

Common Mistakes

Mistake 1: Using operator[] to "check" whether a key exists

Because operator[] inserts a default-constructed value for missing keys, using it purely to test existence silently grows the map:

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

int main() {
    unordered_map<string, int> m;
    m["a"] = 1;
    cout << "Size before check: " << m.size() << endl;

    if (m["b"] == 0) {
        cout << "b not found, but now size is " << m.size() << endl;
    }

    return 0;
}

Output:

Size before check: 1
b not found, but now size is 2

Checking m["b"] == 0 inserted "b" with value 0 as a side effect — the map now has two entries even though "b" was never intentionally added. The fix is to use find() or count(), neither of which inserts anything:

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

int main() {
    unordered_map<string, int> m;
    m["a"] = 1;
    cout << "Size before check: " << m.size() << endl;

    if (m.find("b") == m.end()) {
        cout << "b not found, size is still " << m.size() << endl;
    }

    return 0;
}

Output:

Size before check: 1
b not found, size is still 1

Mistake 2: Using a custom key type without a hash function

Built-in types and std::string have a ready-made std::hash specialization, but custom structs do not. Trying to use one directly as a key fails to compile:

#include <unordered_map>
#include <string>

struct Point {
    int x, y;
    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

int main() {
    std::unordered_map<Point, std::string> labels;
    labels[{1, 2}] = "A";
    return 0;
}

Output:

Compilation fails: no matching function for call to 'std::hash<Point>::hash()'. std::unordered_map requires a usable Hash functor for the Key type; built-in std::hash is not defined for arbitrary user types.

The fix, shown in Example 3, is to supply a custom hash functor (or specialize std::hash<Point>) and pass it as the third template argument, alongside an operator== for equality.

Mistake 3: Assuming any particular iteration order

unordered_map makes no promises about the order elements appear in when you iterate with a range-based for loop or iterators — the order depends on hash values and bucket layout, and can even change after a rehash triggered by further insertions. Code that prints a map’s contents directly and expects insertion order, alphabetical order, or a stable order across runs will produce inconsistent-looking results. If order matters, either use std::map (sorted by key) or, as in Example 2, copy the keys into a vector and sort them explicitly before using them.

Best Practices

Use find() or count() to test for a key’s existence — never operator[], which silently inserts a default value on a miss.
Use at() instead of operator[] when you want an out-of-bounds access to fail loudly with std::out_of_range rather than silently insert.
Call reserve(n) up front when you know roughly how many elements you’ll insert, to avoid repeated O(n) rehashes as the map grows.
Provide a well-distributed hash function for custom key types; a poor hash function that clusters keys into a few buckets destroys the O(1) average-case guarantee.
Prefer emplace() over insert() when constructing the value in place avoids an unnecessary temporary object.
Never rely on iteration order; use std::map or an explicit sort if ordering matters.
Remember that rehashing invalidates iterators (but not references/pointers to existing elements) — don’t hold onto iterators across insertions that might trigger a rehash.
Choose unordered_map for fast average-case lookups; choose map when you need sorted order or guaranteed worst-case O(log n) performance.

Practice Exercises

Write a program that counts the frequency of each character (ignoring spaces) in a string using unordered_map<char, int>, then prints each character and its count in alphabetical order.
Given a list of student names and their scores, build an unordered_map<string, int> and write a function that scans it to find and print the name with the highest score.
Implement a memoized recursive Fibonacci function using an unordered_map<int, long long> as a cache, and print fib(30). Compare (in your head, or by timing) how much faster it is than a plain recursive version without memoization.

Summary

unordered_map stores unique key-value pairs in a hash table, giving average O(1) insertion, lookup, and deletion, versus O(log n) for the sorted, tree-based std::map.
Internally it uses a bucket array; a hash function picks the bucket, and an equality functor resolves collisions within a bucket via a chain.
Growth is handled automatically through rehashing when the load factor exceeds a threshold, which is an amortized-cheap but occasionally O(n) operation.
Custom key types need both a hash functor (or a std::hash specialization) and an operator==; without them, the code won’t compile.
operator[] auto-inserts on a miss — use find()/count() for existence checks and at() for bounds-checked access.
Never assume any iteration order; sort keys explicitly if a predictable order is required.

C++ unordered_map

Overview / How It Works

Syntax

Examples

Example 1: Basic Operations

Example 2: Counting Word Frequencies

Example 3: Using a Custom Struct as a Key

Under the Hood: Step by Step

Common Mistakes

Mistake 1: Using operator[] to "check" whether a key exists

Mistake 2: Using a custom key type without a hash function

Mistake 3: Assuming any particular iteration order

Best Practices

Practice Exercises

Summary

Table of Contents