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:
Compute
h = hash(key), astd::size_tnumber, using a hash function.Choose the bucket:
b = h % bucket_count.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 = 1031GCC 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 = 4The 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: 6Example: 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 = 9Step 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:
A hash function: by default
std::hash<Key>, which the library provides for built-in types, pointers,std::string,std::string_viewand a few others. It is not provided forstd::pair,std::tupleor your own structs.An equality test: by default
operator==. (Ordered containers used<; hash containers use==.)
The rule that ties them together:
If
a == b, thenhash(a)must equalhash(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): originbool operator==(const Point&) const = default;(C++20) compares all members. Before C++20, write it by hand.PointHashis a function object that combines the hashes ofxandy. The mixing formula (the same idea as Boost'shash_combine) spreads the bits so that, for example, (1, 2) and (2, 1) get different hashes. A naiveh1 ^ h2would 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>andstd::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 | 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: oneSo 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?
|
| |
|---|---|---|
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 |
|
|
| 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
Expecting sorted or insertion-order output. Iteration order is unspecified. Sort separately if you need order.
Using
std::pairor a struct as a key without a hash.std::unordered_set<std::pair<int,int>>does not compile becausestd::hash<std::pair<int,int>>does not exist. Provide a hash (andoperator==for structs).A hash that disagrees with
==. If equal keys can produce different hashes, lookups fail randomly.Keeping iterators across inserts. A rehash invalidates all of them.
Reading with
m[key], which inserts missing keys, just likestd::map.Assuming O(1) is guaranteed. Bad hashes or adversarial input make it O(n) per operation.
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_setandunordered_mapare 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; usereserve(n)to avoid repeated rehashes.Iteration order is unspecified. There is no
lower_boundor 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.