stl · high

map vs unordered_map

Same keys in a sorted red-black tree vs hash buckets - compare lookup cost, collisions, and iteration order.

The code

std::map<int, V> m;           // balanced BST (red-black tree)
std::unordered_map<int, V> u; // hash table (buckets)
// both hold keys 1..5

m.find(5); // O(log n): walk root -> 4 -> 5
u.find(5); // O(1) avg: hash(5) % 4 -> bucket 1

for (auto& kv : m) {} // visits 1 2 3 4 5 (sorted)
for (auto& kv : u) {} // visits 4 1 5 2 3 (bucket order)

What this lesson walks through

1. 01Same keys, two data structures
2. 02std::map = red-black tree (sorted)
3. 03std::unordered_map = hash buckets
4. 04find(5) in map: O(log n)
5. 05find(5) in unordered_map: O(1) avg
6. 06Collisions -> chaining
7. 07Iteration order differs
8. 08Which one to use

std::map and std::unordered_map both map keys to values, but store them completely differently. Here both hold keys 1..5.