Iterator Categories, Invalidation Rules & Essential STL Algorithms

C++ iterator categories define what physical navigation a container's memory topology supports:

1. Input Iterator: Single-pass read-only stream, advance only via ++ (e.g. std::istream_iterator).
2. Forward Iterator: Multi-pass read/write, advance only via ++ (e.g. std::forward_list).
3. Bidirectional Iterator: Step forward with ++ and backward with --, but cannot jump (e.g. std::list, std::set, std::map).
4. Random-Access Iterator: Jump arbitrary offsets in O(1) via it + n, subtract iterators it2 - it1, and subscript it[n] (e.g. std::deque).
5. Contiguous Iterator (C++20): Random access with elements guaranteed to lie in adjacent physical memory bytes: &*(it + n) == (&*it) + n (e.g. std::vector, std::array, std::string, std::span).

Why std::sort Rejects std::list: std::sort uses Introsort (QuickSort hybrid), which requires jumping to middle pivots (first + (last - first)/2) in O(1) time. Because std::list::iterator is only Bidirectional, it lacks operator+ and operator-. Calling std::sort(lst.begin(), lst.end()) fails compilation! Instead, call the member function lst.sort(), which executes an O(N log N) merge sort by relinking node pointers with zero element copies.

Senior interviewers test whether you realize that an iterator can die while a reference lives on:

• An iterator tracks container traversal logic (e.g. current bucket + position in chain).
• A reference or raw pointer points directly to the element's raw memory address.

Erasing an element inside a naive for loop is the #1 STL bug in production:

// DEADLY BUG: invalidates 'it' before increment!
for (auto it = c.begin(); it != c.end(); ++it) {
    if (shouldDelete(*it)) c.erase(it);
}

Why This Breaks:

1. Node Containers (list, map) -> Use-After-Free: Calling c.erase(it) deallocates the node immediately. The loop header then executes ++it, attempting to read it->next from freed heap memory. Result: segfault or silent memory corruption.
2. Contiguous Containers (vector, deque) -> Skipped Elements: Erasing shifts all subsequent elements left by one slot. The next element slides directly into it's current slot. When the loop header does ++it, it skips that element completely!

The Universal Idiomatic Fix: Control iterator advancing manually: assign it = c.erase(it) when deleting, and only execute ++it when keeping the element:

for (auto it = c.begin(); it != c.end(); /* manual advance */) {
    if (shouldDelete(*it)) {
        it = c.erase(it); // Returns iterator to next valid element!
    } else {
        ++it;
    }
}

Deleting elements one by one with v.erase(it) inside a vector loop runs in O(N^2) time because every erase shifts all remaining elements left.

The Classic Erase-Remove Idiom (O(N)):

v.erase(std::remove(v.begin(), v.end(), val), v.end());

• Why two steps? std::remove operates only on iterators. It has no access to the container itself, so it cannot change v.size(). It slides kept elements to the front and returns an iterator pointing to the first garbage tail element.
• The outer v.erase(new_end, v.end()) call actually truncates the container and updates size().

The Modern C++20 Solution: C++20 obsoletes this boilerplate with unified non-member functions:

std::erase(v, val);                                    // Erase matching values
std::erase_if(v, [](int x) { return x % 2 == 0; });   // Erase by predicate

Runs in linear O(N) time across vector, deque, list, map, and unordered_map with zero boilerplate.

Selecting the right algorithm is a classic systems design question:

1. std::sort (Unstable O(N log N)):
   • Uses Introsort (starts with QuickSort, switches to HeapSort if recursion depth exceeds 2 log N to prevent O(N^2) worst cases, and finishes with InsertionSort on small partitions).
   • Not stable: Equivalent elements may swap relative order.
2. std::stable_sort (Stable O(N log N)):
   • Uses MergeSort to preserve the relative ordering of equivalent keys.
   • Allocates a temporary buffer of up to N/2 elements. If memory allocation fails, it degrades to O(N log^2 N) in-place sorting.
3. std::nth_element (Linear O(N) Selection):
   • Uses Introselect to partition elements such that the element at index nth is the exact element that would be there if the range were fully sorted.
   • Elements before nth are <= *nth; elements after are >= *nth.
   • Performance Superpower: When computing medians, 99th percentiles, or top-K cutoffs, std::nth_element avoids sorting sub-partitions, running up to 10x faster than std::sort.