stl · advanced

STL: std::map Internals — Red-Black Tree, O(log n) Guarantee, Rebalancing

std::map is backed by a Red-Black Tree — a self-balancing BST with 5 properties. Property 4 (no two consecutive REDs) and 5 (equal black-height on all paths) together guarantee height ≤ 2·log(n+1) → O(log n) all operations in the WORST CASE (not just average). Insert: new node is RED. If parent is RED → violation. Fix by: Case 1 (uncle RED): recolor parent+uncle BLACK, grandparent RED, propagate up. Case 2 (uncle BLACK, inner child): rotate parent toward uncle. Case 3 (uncle BLACK, outer child): rotate grandparent, recolor. At most O(log n) rotations per insert. In-order traversal always gives sorted output (unlike hash maps). Use map for: range queries (lower_bound/upper_bound), sorted iteration, key types with no good hash. Use unordered_map for: O(1) average, no ordering needed, key has a good hash.

The code

// std::map is a Red-Black Tree — 5 properties guarantee O(log n)
// 1. Every node is RED or BLACK
// 2. Root is BLACK
// 3. Every leaf (NIL) is BLACK
// 4. RED node's children are both BLACK (no two consecutive REDs)
// 5. All paths from root to leaves have the SAME number of black nodes
//    → This guarantees height ≤ 2*log(n+1) → O(log n) all ops

// Rebalancing: 3 cases when inserting
// Case 1: Uncle is RED → recolor parent, uncle BLACK; grandparent RED
// Case 2: Uncle is BLACK, node is inner child → rotate parent
// Case 3: Uncle is BLACK, node is outer child → rotate grandparent + recolor

std::map<int, string> m;
m[10] = "ten";
m[5] = "five";
m[20] = "twenty";
m[3] = "three";
m[7] = "seven";

// map guarantees: all operations O(log n)
m.find(7);                 // O(log n) — tree search
m.lower_bound(6);          // O(log n) — first key >= 6
m.insert({15, "fifteen"}); // O(log n) + rebalance
m.erase(5);                // O(log n) + rebalance

// Iterating is always sorted (in-order traversal):
for (auto& [k, v] : m) // 3, 7, 10, 15, 20
    cout << k << " ";

What this lesson walks through

1. 01std::map — interface and when to use vs unordered_map
2. 02RB tree — 5 properties that guarantee balance
3. 03Insert 3 — RED leaf, no violation yet
4. 04Insert 7 — RED uncle causes recolor
5. 05Tree after rebalancing — all paths have equal black count
6. 06Insert 15 — finds correct position, minimal rebalance

std::map is a sorted associative container backed by a Red-Black Tree. All operations (find, insert, erase, lower_bound) are O(log n) guaranteed. Iteration is always sorted. Use map when you need range queries, sorted iteration, or the key type has no good hash. Use unordered_map when you need O(1) average and don't need ordering.