Chapter 39 of 48

unordered_set & unordered_map

In the previous chapter, set & map, we got O(log n) search by keeping elements sorted in a balanced tree. But very often we do not care about order at all. We only want to know "have I seen this value?" or "what is the count for this word?", and we want the answer as fast as possible.

std::unordered_set and std::unordered_map (C++11) give us average O(1) insert, find and erase by using a hash table. They are the C++ equivalents of Java's HashSet/HashMap and Python's set/dict, and they are among the most used tools in coding interviews.


What Are They?

std::unordered_set<Key> (header <unordered_set>) stores unique keys in no particular order.

std::unordered_map<Key, Value> (header <unordered_map>) stores key–value pairs with unique keys, in no particular order.

Both are implemented as hash tables, giving average constant-time lookup.

Their interface is almost identical to set and map: insert, emplace, find, count, contains (C++20), erase, operator[], at, try_emplace, insert_or_assign. What is missing is everything that depends on order: no lower_bound, no upper_bound, no smallest/largest element, no reverse iteration.


How a Hash Table Works

A hash table is an array of buckets. To store a key:

  1. Compute h = hash(key), a std::size_t number, using a hash function.

  2. Choose the bucket: b = h % bucket_count.

  3. Store the element in bucket b. If other keys landed in the same bucket (a collision), they are kept together in that bucket's linked chain.

To find a key, we do the same computation and only look inside one bucket, instead of the whole container.

unordered_set<int> with 7 buckets, keys {42, 7, 19, 88}
(GCC's hash for int is the value itself, so bucket = key % 7)

bucket 0: → [42] → [7]        42 % 7 = 0,  7 % 7 = 0   (collision: chained)
bucket 1:
bucket 2:
bucket 3:
bucket 4: → [88]              88 % 7 = 4
bucket 5: → [19]              19 % 7 = 5
bucket 6:

find(19): hash → bucket 5 → compare with 19 → found (1 comparison)

This technique is called separate chaining. The C++ standard's requirements (stable references, a bucket interface) effectively force chaining, and all major implementations use it.

Load Factor and Rehashing

The load factor is size() / bucket_count(): the average number of elements per bucket.

If the load factor grows, chains get longer and lookups slow down. So the container keeps the load factor at or below max_load_factor(), which is 1.0 by default. When an insert would exceed it, the table rehashes: it allocates a larger bucket array (GCC roughly doubles it; the exact growth is implementation-specific) and relinks every element into its new bucket. A rehash is O(n), but it happens rarely enough that inserts are still O(1) amortized, the same idea as vector growth.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m;
    std::cout << "max_load_factor = " << m.max_load_factor() << '\n';

    std::size_t lastBuckets = m.bucket_count();
    std::cout << "empty: buckets = " << lastBuckets << '\n';
    for (int i = 0; i < 100; ++i) {
        m[i] = i * i;
        if (m.bucket_count() != lastBuckets) {
            lastBuckets = m.bucket_count();
            std::cout << "after " << m.size() << " elements: rehash -> "
                      << lastBuckets << " buckets\n";
        }
    }
    std::cout << "load_factor = " << m.load_factor() << '\n';

    std::unordered_map<int, int> r;
    r.reserve(1000);   // room for 1000 elements without rehashing
    std::cout << "after reserve(1000): buckets = " << r.bucket_count() << '\n';
}

Output (GCC 15; bucket counts are implementation-specific):

max_load_factor = 1
empty: buckets = 1
after 1 elements: rehash -> 13 buckets
after 14 elements: rehash -> 29 buckets
after 30 elements: rehash -> 59 buckets
after 60 elements: rehash -> 127 buckets
load_factor = 0.787402
after reserve(1000): buckets = 1031

GCC picks prime numbers of buckets and roughly doubles each time. Notice that the load factor never exceeded 1. If you know how many elements you will insert, call reserve(n) first: it creates enough buckets for n elements so no rehash happens during the inserts.


unordered_set in Action

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> seen = {42, 7, 19, 7, 88};   // duplicate 7 ignored

    std::cout << "size = " << seen.size() << '\n';
    std::cout << "Iteration order: ";
    for (int x : seen) std::cout << x << ' ';             // NOT sorted
    std::cout << '\n';

    seen.insert(5);
    std::cout << std::boolalpha;
    std::cout << "contains(19): " << seen.contains(19) << '\n';   // C++20
    std::cout << "count(100): " << seen.count(100) << '\n';
    std::cout << "erase(42) removed " << seen.erase(42) << '\n';
    std::cout << "size = " << seen.size() << '\n';
}

Output (GCC 15):

size = 4
Iteration order: 88 19 7 42 
contains(19): true
count(100): 0
erase(42) removed 1
size = 4

The iteration order 88 19 7 42 is neither the insertion order nor sorted. It depends on the hash function, the number of buckets and the library implementation, so another compiler can print a different order, and the order can change after a rehash. Never write code (or expected test output) that depends on it. If you need sorted output, copy the elements into a vector and sort it, or use std::set.


unordered_map in Action

All the map rules from the previous chapter carry over, including the operator[] trap (it inserts a missing key):

#include <iostream>
#include <string>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> stock = {{"pen", 10}, {"ink", 0}, {"book", 4}};

    std::cout << "pen: " << stock.at("pen") << '\n';
    stock["pen"] += 5;                               // same [] rules as std::map
    stock.try_emplace("ink", 99);                    // exists: no change
    stock.insert_or_assign("book", 6);               // exists: overwritten

    std::erase_if(stock, [](const auto& kv) { return kv.second == 0; });   // C++20

    std::cout << std::boolalpha << "has ink? " << stock.contains("ink") << '\n';
    std::cout << "pen: " << stock["pen"] << ", book: " << stock["book"] << '\n';
}

(The [](const auto& kv) { ... } argument is a lambda, exactly as in the previous chapter: it receives each key–value pair and returns true for the ones to remove.)

Output:

pen: 10
has ink? false
pen: 15, book: 6

Example: Two Sum in O(n)

Given an array and a target, find two indices whose values add up to the target. The brute force checks every pair: O(n²). With a hash map we remember every value we have passed, and for each new element we ask in O(1) whether its partner target - nums[i] was already seen.

#include <iostream>
#include <unordered_map>
#include <vector>

// Return indices of two numbers that add up to target, in O(n) average time
std::vector<int> twoSum(const std::vector<int>& nums, int target) {
    std::unordered_map<int, int> indexOf;     // value -> index
    for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
        int need = target - nums[i];
        if (auto it = indexOf.find(need); it != indexOf.end())
            return {it->second, i};
        indexOf[nums[i]] = i;
    }
    return {};
}

int main() {
    std::vector<int> nums = {11, 2, 15, 7, 4};
    auto ans = twoSum(nums, 9);
    std::cout << "Indices: " << ans[0] << ", " << ans[1] << '\n';
    std::cout << nums[ans[0]] << " + " << nums[ans[1]] << " = 9\n";
}

Output:

Indices: 1, 3
2 + 7 = 9

Step by step for target 9:

i

nums[i]

need = 9 − nums[i]

need in map?

map after step

0

11

−2

no

{11→0}

1

2

7

no

{11→0, 2→1}

2

15

−6

no

{11→0, 2→1, 15→2}

3

7

2

yes, index 1

return {1, 3}

n lookups and inserts at O(1) average each: O(n) average time, O(n) extra space.


Using Your Own Types as Keys

An unordered container needs two things for its key type:

  1. A hash function: by default std::hash<Key>, which the library provides for built-in types, pointers, std::string, std::string_view and a few others. It is not provided for std::pair, std::tuple or your own structs.

  2. An equality test: by default operator==. (Ordered containers used <; hash containers use ==.)

The rule that ties them together:

If a == b, then hash(a) must equal hash(b). (The reverse is not required: different keys may share a hash value; that is just a collision.)

#include <cstddef>
#include <functional>
#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>

struct Point {
    int x, y;
    bool operator==(const Point&) const = default;   // C++20: needed for key equality
};

struct PointHash {
    std::size_t operator()(const Point& p) const {
        std::size_t h1 = std::hash<int>{}(p.x);
        std::size_t h2 = std::hash<int>{}(p.y);
        return h1 ^ (h2 + 0x9e3779b9 + (h1 << 6) + (h1 >> 2));   // mix the two hashes
    }
};

int main() {
    std::unordered_set<Point, PointHash> visited;
    visited.insert({1, 2});
    visited.insert({3, 4});
    visited.insert({1, 2});          // duplicate
    std::cout << "visited.size() = " << visited.size() << '\n';
    std::cout << std::boolalpha << "contains (3,4): " << visited.contains({3, 4}) << '\n';

    std::unordered_map<Point, std::string, PointHash> label;
    label[{0, 0}] = "origin";
    std::cout << "label at (0,0): " << label[{0, 0}] << '\n';
}

Output:

visited.size() = 2
contains (3,4): true
label at (0,0): origin
  • bool operator==(const Point&) const = default; (C++20) compares all members. Before C++20, write it by hand.

  • PointHash is a function object that combines the hashes of x and y. The mixing formula (the same idea as Boost's hash_combine) spreads the bits so that, for example, (1, 2) and (2, 1) get different hashes. A naive h1 ^ h2 would give those two points the same hash, and every point with x == y would hash to 0, creating many collisions.

  • We pass the hash as the extra template argument: std::unordered_set<Point, PointHash> and std::unordered_map<Point, std::string, PointHash>.

The same technique works for std::pair<int, int> keys, which are very common in grid problems. An alternative for small non-negative coordinates (here 0 ≤ y < 1000003) is to encode the pair into one integer, for example key = 1LL * x * 1000003 + y, and use unordered_set<long long>.


Iterator Invalidation

Each element lives in its own node, and rehashing only relinks nodes into new buckets; it does not move the elements. This gives a rule that differs from vector:

Operation

Iterators

References / pointers to elements

Insert, no rehash

valid

valid

Insert causing a rehash (or calling rehash/reserve)

all invalidated

valid

Erase

only the erased element's

only the erased element's

#include <iostream>
#include <string>
#include <unordered_map>

int main() {
    std::unordered_map<int, std::string> m = {{1, "one"}};
    std::string* p = &m[1];                     // pointer to an element
    std::size_t before = m.bucket_count();

    for (int i = 2; i <= 1000; ++i) m[i] = "x";   // forces several rehashes

    std::cout << "buckets: " << before << " -> " << m.bucket_count() << '\n';
    std::cout << "pointer still valid: " << *p << '\n';   // OK: nodes did not move
    // Any ITERATOR taken before the rehash would now be invalid.
}

Output (GCC 15):

buckets: 13 -> 1109
pointer still valid: one

So it is fine to keep a pointer or reference to a value while inserting, but never keep an iterator across inserts unless you reserved enough space first.


The Worst Case: Why "Average" O(1) Matters

O(1) is an average that assumes the hash function spreads keys evenly. If many keys fall into the same bucket, a lookup must walk a long chain. In the extreme, all n keys collide and every operation becomes O(n), so n inserts cost O(n²).

This is not just theory. GCC's std::hash<int> returns the integer unchanged, and the bucket sequence is predictable, so an adversary can choose keys that are all multiples of the bucket count. On competitive programming sites, such "anti-hash" tests are used to make unordered_map solutions time out. The usual defence, a randomised custom hash, is shown in the C++ for Competitive Programming chapter. In normal applications with ordinary data, the default hashes work well.


Ordered vs Unordered: Which to Choose?

set / map

unordered_set / unordered_map

Data structure

Balanced BST (red-black tree)

Hash table with chaining

Element order

Sorted by key

Unspecified, may change on rehash

Insert / find / erase

O(log n) worst case

O(1) average, O(n) worst case

Key requirement

operator< (or comparator)

std::hash (or custom hash) + operator==

lower_bound, min/max, range queries

Yes

No

Memory

Node per element (3 pointers + color)

Node per element + bucket array

Iterators

Bidirectional

Forward only

Iterators invalidated by insert?

Never

Only if a rehash happens

Rule of thumb: use unordered_map/unordered_set for pure lookups and counting; use map/set when you need order, range queries or guaranteed worst-case performance.

The multi-versions also exist: std::unordered_multiset and std::unordered_multimap allow duplicate keys, with equal_range to fetch all matches, just like their ordered cousins.


Common Mistakes

  1. Expecting sorted or insertion-order output. Iteration order is unspecified. Sort separately if you need order.

  2. Using std::pair or a struct as a key without a hash. std::unordered_set<std::pair<int,int>> does not compile because std::hash<std::pair<int,int>> does not exist. Provide a hash (and operator== for structs).

  3. A hash that disagrees with ==. If equal keys can produce different hashes, lookups fail randomly.

  4. Keeping iterators across inserts. A rehash invalidates all of them.

  5. Reading with m[key], which inserts missing keys, just like std::map.

  6. Assuming O(1) is guaranteed. Bad hashes or adversarial input make it O(n) per operation.

  7. Modifying a key in place. Keys are const for the same reason as in set: the element would sit in the wrong bucket.


Interview / GATE-Style Questions

Q1. What are the average and worst-case time complexities of find in std::unordered_map, and when does the worst case happen?

Average O(1); worst case O(n). The worst case happens when many keys hash to the same bucket, so the lookup must walk a long chain, for example with a poor hash function or deliberately chosen colliding keys.

Q2. What is the load factor and what happens when it exceeds max_load_factor()?

Load factor = number of elements ÷ number of buckets. When an insertion would make it exceed max_load_factor() (1.0 by default), the container rehashes: it allocates a larger bucket array and redistributes all elements. This is O(n) but rare, so insertion stays O(1) amortized on average.

Q3. Does inserting into an unordered_map invalidate references to existing elements? Iterators?

References and pointers to elements are never invalidated by insertion, because nodes are not moved. Iterators are invalidated only if the insertion causes a rehash.

Q4. Why does std::unordered_set<std::pair<int,int>> fail to compile while std::set<std::pair<int,int>> works?

std::set only needs operator<, which std::pair provides (lexicographic). std::unordered_set needs std::hash<std::pair<int,int>>, which the standard library does not define. You must supply a custom hash as the second template argument.

Q5. You need to count word frequencies and then print words in alphabetical order. Which container(s) would you use?

Either a std::map<std::string, int> directly (O(n log m), already sorted), or an unordered_map for faster counting (O(n) average) followed by copying the m distinct entries into a vector and sorting them (O(m log m)). The second is often faster when there are many repeated words.


Summary

  • unordered_set and unordered_map are hash tables: average O(1) insert, find and erase; worst case O(n).

  • Elements go into buckets by hash(key) % bucket_count; collisions are chained.

  • The load factor is kept ≤ max_load_factor() (default 1.0) by rehashing; use reserve(n) to avoid repeated rehashes.

  • Iteration order is unspecified. There is no lower_bound or min/max.

  • Custom keys need a hash and operator==, and equal keys must have equal hashes.

  • Rehashing invalidates iterators but not references; erase invalidates only the erased element.

We now know the main STL containers. In the next chapter, STL Algorithms, we learn the ready-made functions (sorting, searching, counting, transforming) that work on all of them.