C++ STL Iterators

Iterators Base Architecture: Abstraction of Memory Traversal

Iterators decouple algorithms from the underlying container data structures. They are pointer-like objects that expose a uniform interface for traversal.

Under the Hood Implementation (Core) Iterators are either bare hardware pointers (T*) or lightweight struct/class wrappers over internal container state. The compiler resolves iterator capabilities at compile-time using std::iterator_traits. Every iterator must declare five type aliases:

1. value_type: The type of the element pointed to.
2. difference_type: Signed integer representing the distance between two iterators (typically ptrdiff_t).
3. pointer: Pointer to the element.
4. reference: Reference to the element.
5. iterator_category: An empty struct tag (e.g., std::forward_iterator_tag) used for algorithm optimization via compile-time tag dispatching.

Algorithms like std::advance or std::distance check the iterator_category at compile-time. If it is a Random Access Iterator, they compile into a single O(1) arithmetic operation. Otherwise, they compile into a loop of O(N) increments.

[!CAUTION]

Interview Trap: The erase() Segfault

One of the most common reasons candidates fail live coding interviews in C++ is modifying a container while iterating.

If you write: for(auto it = vec.begin(); it != vec.end(); ++it) { if (*it == 5) vec.erase(it); } you will crash the program. vec.erase(it) invalidates the iterator it. The ++it in the loop header then causes undefined behavior.

The Correct Way: it = vec.erase(it); returns a valid iterator to the next element. (And don't forget to conditionally branch your ++it so you don't skip elements!)

---

Container-to-Iterator Quick Reference

Container	Iterator Category	begin()/end()	Key Operations	Invalidation Rules
std::vector<T>	Random Access	O(1)	it + n, it - it2, it[n]	Insert/erase invalidates at/after position
std::deque<T>	Random Access	O(1)	it + n, it - it2, it[n]	Insert/erase at ends preserves others
std::array<T,N>	Random Access	O(1)	it + n, it - it2, it[n]	Never invalidated (fixed size)
std::string	Random Access	O(1)	it + n, it - it2, it[n]	Same as vector
std::list<T>	Bidirectional	O(1)	++it, --it	Only erased element invalidated
std::set<T>	Bidirectional	O(1)	++it, --it	Only erased element invalidated
std::map<K,V>	Bidirectional	O(1)	++it, --it	Only erased element invalidated
std::forward_list<T>	Forward	O(1)	++it only	Only erased element invalidated
std::unordered_map<K,V>	Forward	O(1)	++it only	Rehash invalidates all
std::unordered_set<T>	Forward	O(1)	++it only	Rehash invalidates all

Key Insight: Random Access Iterators enable O(log N) binary search and O(N log N) sorting. Bidirectional/Forward iterators force O(N) algorithms for these tasks.

---

1. Input Iterator

Under the Hood Implementation Strictly single-pass, read-only traversal. Wraps a transient data source, such as a hardware data stream, a file, or keyboard input. Reading from the iterator consumes the data. Requires: operator* (read), operator->, operator++ (pre/post), operator==, operator!=.

Data Types std::istream_iterator<T>

ASCII Illustration

Stream Buffer: [ 10 ] -> [ 20 ] -> [ 30 ] -> EOF
                 ^
                 | (Read 10, advance, 10 is permanently consumed)

Big O Complexity

• Dereference (Read): O(1)
• Increment: O(1) (Involves I/O wait time, but algorithmically constant)

Typical Usage Scenarios Reading data from std::cin or network sockets directly into a container or algorithm.

---

2. Output Iterator

Under the Hood Implementation Strictly single-pass, write-only traversal. Does not point to existing data; instead, dereferencing and assigning to it executes a write operation. It is often a proxy object. For example, std::back_insert_iterator wraps a container pointer and overrides operator= to invoke container->push_back(value). Requires: operator* (write), operator++ (often a no-op just to satisfy syntax).

Data Types std::ostream_iterator<T>, std::back_insert_iterator<Container>

ASCII Illustration

Algorithm output ->[ Iterator ] -> Calls Container.push_back()
                                 -> Appends to memory dynamically

Big O Complexity

• Dereference + Assignment (Write): O(1) or O(N) if the underlying container requires reallocation during the push.
• Increment: O(1)

Typical Usage Scenarios Piping algorithm results into a stream (e.g., printing out a vector) or dynamically appending to a container whose final size is unknown.

---

3. Forward Iterator

Under the Hood Implementation Combines Input and Output capabilities, but guarantees multi-pass traversal. If an iterator is copied, both copies point to the same valid element, and incrementing one does not invalidate the other. It strictly moves forward. Wraps singly-linked node structures. Requires: All Input/Output operators plus default constructibility.

Data Types Iterators of std::forward_list, std::unordered_map, std::unordered_set.

ASCII Illustration

+----+      +----+      +----+
| 10 | ---> | 20 | ---> | 30 | ---> nullptr
+----+      +----+      +----+
  ^           ^
 it1         it2 (Iterators can exist simultaneously)

Big O Complexity

• Dereference: O(1)
• Increment (++): O(1) (Pointer dereference to _M_next)

Typical Usage Scenarios Algorithms requiring multi-pass over unidirectional data, such as finding a sequence within a singly-linked list.

---

4. Bidirectional Iterator

Under the Hood Implementation Extends Forward Iterator. Supports moving backward via operator--. Wraps doubly-linked nodes or Red-Black Tree nodes. For Red-Black trees (std::map, std::set), operator++ is complex. It does not just follow a next pointer. It calculates the in-order successor:

1. If the right child exists, traverse down the left-most branch of the right child.
2. If the right child does not exist, traverse up the _M_parent pointers until moving up from a left child.

Data Types Iterators of std::list, std::set, std::map.

ASCII Illustration

      Tree Traversal In-Order
             [20]
            /    \
         [10]    [30]
        /   \
      [5]  [15]

it points to 15.
++it:
1. No right child of 15.
2. Parent is 10. 15 is right child. Move up.
3. Parent is 20. 10 is left child. Stop.
4. it now points to 20.

Big O Complexity

• Dereference: O(1)
• Increment/Decrement (++, --): Amortized O(1). Worst-case O(log N) for tree nodes, strictly O(1) for doubly-linked list nodes.

Typical Usage Scenarios Reversing a collection (std::reverse). Traversing a sorted dictionary from the highest key down to the lowest.

---

5. Random Access Iterator

Under the Hood Implementation Extends Bidirectional Iterator. Provides pointer-like arithmetic, allowing O(1) jumps across contiguous or piecewise-contiguous memory. Wraps a raw pointer (T*) or an internal indexing structure. Requires all Bidirectional capabilities plus: operator+, operator-, operator+=, operator-=, operator[], operator<, operator>, operator<=, operator>=. Subtracting two random access iterators yields the exact difference_type distance in O(1) time without traversal.

Data Types Raw pointers (T*), iterators of std::vector, std::array, std::deque, std::string.

ASCII Illustration

Contiguous Memory Block
+----+----+----+----+----+----+----+
| 00 | 11 | 22 | 33 | 44 | 55 | 66 |
+----+----+----+----+----+----+----+
  ^                   ^
  it                it + 4

Jump calculated via memory address: (char*)it + (4 * sizeof(T)).
Executes in a single CPU instruction.

Big O Complexity

• Dereference (*it, it[n]): O(1)
• Increment/Decrement (++, --): O(1)
• Arbitrary Jump (it + n, it - n): O(1)
• Distance calculation (it1 - it2): O(1)

Typical Usage Scenarios Required strictly by algorithms that divide sequences mathematically or require spatial leaps, such as std::sort, std::binary_search, std::make_heap, and std::nth_element.

[!WARNING]

Interview Trap: Iterator Arithmetic

If you have a std::list (Bidirectional Iterator) or std::forward_list (Forward Iterator), you cannot do it + 5. It simply will not compile. You must use std::advance(it, 5), which takes O(N) time.

Similarly, you cannot compute the size of a generic range using it2 - it1 unless you strictly have Random Access Iterators (like std::vector or raw pointers). Instead, use std::distance(it1, it2).

---

Per-Container Iterator Examples

std::vector - Random Access Iterator

#include <vector>
#include <algorithm>

void vector_iterator_examples() {
    std::vector<int> v = {5, 2, 8, 1, 9};

    // 1. Basic iteration (range-based for uses iterators internally)
    for (auto it = v.begin(); it != v.end(); ++it) {
        *it *= 2;  // Modify in place
    }

    // 2. Random access: jump directly to middle
    auto mid = v.begin() + v.size() / 2;  // O(1) - compiles to pointer arithmetic

    // 3. Distance calculation
    auto dist = v.end() - v.begin();  // O(1) - returns ptrdiff_t

    // 4. Sorting (REQUIRES random access)
    std::sort(v.begin(), v.end());  // O(N log N) - uses it+n for partitioning

    // 5. Binary search (REQUIRES random access for O(log N))
    bool found = std::binary_search(v.begin(), v.end(), 8);
    auto lb = std::lower_bound(v.begin(), v.end(), 8);  // First >= 8

    // 6. Reverse iterators
    for (auto rit = v.rbegin(); rit != v.rend(); ++rit) {
        // Traverses 9, 8, 5, 2, 1
    }

    // 7. SAFE erase while iterating
    for (auto it = v.begin(); it != v.end(); ) {
        if (*it % 2 == 0) {
            it = v.erase(it);  // Returns next valid iterator
        } else {
            ++it;
        }
    }
}

std::list - Bidirectional Iterator

#include <list>
#include <algorithm>

void list_iterator_examples() {
    std::list<int> lst = {5, 2, 8, 1, 9};

    // 1. Forward iteration - same syntax as vector
    for (auto it = lst.begin(); it != lst.end(); ++it) {
        *it *= 2;
    }

    // 2. Backward iteration - bidirectional allows --
    for (auto it = lst.end(); it != lst.begin(); ) {
        --it;  // Must decrement BEFORE use (end() is past-the-end)
        // Process *it
    }

    // 3. CANNOT do: auto mid = lst.begin() + lst.size()/2;  // COMPILE ERROR
    //    MUST use:
    auto mid = lst.begin();
    std::advance(mid, lst.size() / 2);  // O(N) - walks the list

    // 4. CANNOT use std::sort (requires random access)
    //    MUST use member function:
    lst.sort();  // O(N log N) - merge sort, stable

    // 5. Splice - O(1) move of nodes between lists
    std::list<int> other = {100, 200};
    auto pos = lst.begin();
    std::advance(pos, 2);
    lst.splice(pos, other);  // other is now empty, nodes moved to lst

    // 6. Erase is SAFE - doesn't invalidate other iterators
    auto it = lst.begin();
    auto next = it;
    ++next;
    lst.erase(it);  // 'next' is still valid!
}

std::unordered_map - Forward Iterator

#include <unordered_map>

void unordered_map_iterator_examples() {
    std::unordered_map<std::string, int> freq;
    freq["apple"] = 3;
    freq["banana"] = 2;
    freq["cherry"] = 5;

    // 1. Iteration - order is NOT guaranteed (hash-based)
    for (auto it = freq.begin(); it != freq.end(); ++it) {
        // it->first is key (const), it->second is value (modifiable)
        it->second *= 2;
    }

    // 2. Range-based for with structured binding (C++17, but works in C++11 with pairs)
    for (auto& kv : freq) {
        // kv.first, kv.second
    }

    // 3. Find returns iterator (O(1) average)
    auto it = freq.find("banana");
    if (it != freq.end()) {
        // Found - it->second is the value
    }

    // 4. CANNOT do: it + 5 or --it  // Forward iterator only!

    // 5. Erase by iterator (O(1))
    it = freq.find("apple");
    if (it != freq.end()) {
        freq.erase(it);  // Returns void in C++11 (iterator in C++14+)
    }

    // 6. WARNING: Rehash invalidates ALL iterators
    freq.reserve(1000);  // May trigger rehash - all existing iterators invalid
}

std::set / std::map - Bidirectional Iterator (Sorted)

#include <set>
#include <map>

void set_map_iterator_examples() {
    std::set<int> s = {5, 2, 8, 1, 9};  // Stored as: 1, 2, 5, 8, 9 (sorted)

    // 1. Iteration is ALWAYS in sorted order
    for (auto it = s.begin(); it != s.end(); ++it) {
        // Visits: 1, 2, 5, 8, 9
    }

    // 2. Reverse iteration
    for (auto it = s.rbegin(); it != s.rend(); ++it) {
        // Visits: 9, 8, 5, 2, 1
    }

    // 3. lower_bound / upper_bound - O(log N) - returns iterator
    auto lb = s.lower_bound(5);   // First element >= 5, points to 5
    auto ub = s.upper_bound(5);   // First element > 5, points to 8

    // 4. Range query: all elements in [3, 7]
    auto start = s.lower_bound(3);  // Points to 5
    auto end = s.upper_bound(7);    // Points to 8
    for (auto it = start; it != end; ++it) {
        // Visits: 5
    }

    // 5. Map: iterator to pair<const Key, Value>
    std::map<std::string, int> m = {{"a", 1}, {"b", 2}, {"c", 3}};
    auto mit = m.find("b");
    if (mit != m.end()) {
        mit->second = 20;  // Modify value OK
        // mit->first = "x";  // COMPILE ERROR - key is const
    }

    // 6. Erase doesn't invalidate other iterators
    auto next = mit;
    ++next;
    m.erase(mit);  // 'next' still valid
}

---

Iterator Patterns in Interview Problems

Pattern 1: Two Pointers with Iterators (Two Sum II, 3Sum)

// Problem 02: Two Sum II - Sorted Array
// Uses two iterators converging from ends
std::vector<int> twoSum(std::vector<int>& nums, int target) {
    auto left = nums.begin();
    auto right = nums.end() - 1;  // Random access: end() - 1 is O(1)

    while (left < right) {  // Pointer comparison works for random access
        int sum = *left + *right;
        if (sum == target) {
            // Convert iterators to indices
            return {static_cast<int>(left - nums.begin()) + 1,
                    static_cast<int>(right - nums.begin()) + 1};
        } else if (sum < target) {
            ++left;
        } else {
            --right;
        }
    }
    return {};
}

Pattern 2: HashMap Iterator for Lookup (Two Sum, Group Anagrams)

// Problem 01: Two Sum - HashMap Complement Lookup
std::vector<int> twoSum(std::vector<int>& nums, int target) {
    std::unordered_map<int, int> seen;  // value -> index

    for (int i = 0; i < nums.size(); ++i) {
        int complement = target - nums[i];

        // find() returns iterator - O(1) average
        auto it = seen.find(complement);
        if (it != seen.end()) {
            // it->second is the index
            return {it->second, i};
        }

        // operator[] inserts if not exists
        seen[nums[i]] = i;
    }
    return {};
}

Pattern 3: List Splice for O(1) Move (LRU Cache)

// Problem 50: LRU Cache - List + HashMap
class LRUCache {
    int capacity;
    std::list<std::pair<int, int>> cache;  // (key, value), front = MRU
    std::unordered_map<int, std::list<std::pair<int,int>>::iterator> map;

public:
    int get(int key) {
        auto it = map.find(key);
        if (it == map.end()) return -1;

        // Move to front using splice - O(1), no iterator invalidation
        cache.splice(cache.begin(), cache, it->second);
        return it->second->second;
    }

    void put(int key, int value) {
        auto it = map.find(key);
        if (it != map.end()) {
            it->second->second = value;
            cache.splice(cache.begin(), cache, it->second);
            return;
        }

        if (cache.size() == capacity) {
            // Evict LRU (back)
            int lruKey = cache.back().first;
            map.erase(lruKey);
            cache.pop_back();
        }

        cache.emplace_front(key, value);
        map[key] = cache.begin();  // Store iterator in map
    }
};

Pattern 4: Erase-While-Iterating (Remove Duplicates, Filter)

// Safe removal pattern for vector
void removeEven(std::vector<int>& v) {
    for (auto it = v.begin(); it != v.end(); ) {
        if (*it % 2 == 0) {
            it = v.erase(it);  // erase returns next valid iterator
        } else {
            ++it;  // Only increment if not erasing
        }
    }
}

// Alternative: erase-remove idiom (more efficient for vector)
void removeEvenFast(std::vector<int>& v) {
    // std::remove_if moves "removed" elements to end, returns new logical end
    auto newEnd = std::remove_if(v.begin(), v.end(),
                                  [](int x) { return x % 2 == 0; });
    v.erase(newEnd, v.end());  // Actually remove
}

Pattern 5: Lower/Upper Bound with Map (Time-Based Key-Value Store)

// Problem 66: Time-Based Key-Value Store
class TimeMap {
    std::unordered_map<std::string, std::map<int, std::string>> store;

public:
    void set(std::string key, std::string value, int timestamp) {
        store[key][timestamp] = value;
    }

    std::string get(std::string key, int timestamp) {
        auto it = store.find(key);
        if (it == store.end()) return "";

        auto& timeMap = it->second;  // std::map<int, string>

        // upper_bound: first timestamp GREATER than query
        auto ub = timeMap.upper_bound(timestamp);

        if (ub == timeMap.begin()) return "";  // All timestamps > query

        --ub;  // Bidirectional: move to largest timestamp <= query
        return ub->second;
    }
};

Pattern 6: Priority Queue (No Direct Iterator Access)

// Problem 61: Kth Largest Element
// std::priority_queue has NO iterators - only top(), push(), pop()
int findKthLargest(std::vector<int>& nums, int k) {
    // Min-heap of size k
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

    for (int num : nums) {
        minHeap.push(num);
        if (minHeap.size() > k) {
            minHeap.pop();  // Remove smallest
        }
    }

    return minHeap.top();  // Kth largest
}

// If you need to iterate a heap, use make_heap with vector:
void iterateHeap(std::vector<int>& v) {
    std::make_heap(v.begin(), v.end());  // Max-heap
    // Now v IS a heap AND you can iterate it (though order is heap order, not sorted)
    for (auto it = v.begin(); it != v.end(); ++it) {
        // ...
    }
}

---

Iterator Gotchas and Interview Traps

1. const_iterator vs iterator

void constIteratorExample() {
    std::vector<int> v = {1, 2, 3};
    const std::vector<int>& cv = v;

    // auto deduces correctly
    auto it1 = v.begin();   // std::vector<int>::iterator
    auto it2 = cv.begin();  // std::vector<int>::const_iterator

    *it1 = 10;  // OK
    // *it2 = 10;  // COMPILE ERROR - can't modify through const_iterator

    // Explicit const_iterator
    std::vector<int>::const_iterator cit = v.cbegin();
}

2. Iterator Invalidation Rules

void invalidationRules() {
    // VECTOR: insert/erase invalidates at and after the position
    std::vector<int> v = {1, 2, 3, 4, 5};
    auto it = v.begin() + 2;  // Points to 3
    v.insert(v.begin(), 0);   // it is NOW INVALID

    // LIST: only erased element is invalidated
    std::list<int> lst = {1, 2, 3, 4, 5};
    auto lit = lst.begin();
    std::advance(lit, 2);  // Points to 3
    auto next = lit; ++next;
    lst.erase(lit);  // 'next' is still valid

    // UNORDERED_MAP: rehash invalidates ALL iterators
    std::unordered_map<int, int> m;
    for (int i = 0; i < 100; ++i) m[i] = i;
    auto mit = m.find(50);
    m.reserve(10000);  // May rehash - mit is NOW INVALID
}

3. end() is Past-the-End

void endIteratorTrap() {
    std::vector<int> v = {1, 2, 3};

    auto it = v.end();
    // *it;  // UNDEFINED BEHAVIOR - end() doesn't point to valid element

    --it;   // Now points to last element (3)
    *it;    // OK

    // Common mistake: empty container
    std::vector<int> empty;
    // auto last = empty.end() - 1;  // UNDEFINED - empty has no elements
    if (!empty.empty()) {
        auto last = empty.end() - 1;  // Safe
    }
}

---

Compile-Time Tag Dispatching Examples

std::advance and std::distance

#include <vector>
#include <list>
#include <iterator>
#include <cassert>

void iterator_tag_dispatch_operations() {
    std::vector<int> contiguous_data = {10, 20, 30, 40, 50};
    std::list<int> node_data = {10, 20, 30, 40, 50};

    auto vec_it = contiguous_data.begin();
    auto list_it = node_data.begin();

    // std::advance checks iterator_traits<T>::iterator_category at compile time.

    // For vector (RandomAccessIterator):
    // Compiles to: vec_it += 3;
    // Complexity: O(1)
    std::advance(vec_it, 3);

    // For list (BidirectionalIterator):
    // Compiles to: for(int i=0; i<3; ++i) ++list_it;
    // Complexity: O(N)
    std::advance(list_it, 3);

    assert(*vec_it == 40);
    assert(*list_it == 40);

    // std::distance behaves identically based on traits.
    // Vector distance: (vec_end - vec_begin) -> O(1)
    // List distance: traverses nodes until end is reached -> O(N)
    std::ptrdiff_t vec_dist = std::distance(contiguous_data.begin(), contiguous_data.end());
    std::ptrdiff_t list_dist = std::distance(node_data.begin(), node_data.end());
}

Stream Iterators: Input and Output

#include <iostream>
#include <vector>
#include <iterator>
#include <numeric>

void stream_iterator_operations() {
    std::vector<int> buffer = {1, 2, 3, 4, 5};

    // Output Iterator proxy.
    // Writing to this iterator executes std::cout << value << " "
    std::ostream_iterator<int> out_it(std::cout, " ");

    // Iterates buffer, assigning each element to out_it.
    // Writes directly to stdout buffer.
    std::copy(buffer.begin(), buffer.end(), out_it);

    // Note: std::istream_iterator reading from std::cin blocks thread execution
    // until valid EOF or non-matching type is encountered.
    // std::istream_iterator<int> in_it(std::cin);
    // std::istream_iterator<int> eof;
    // std::vector<int> input_buffer(in_it, eof);
}

---

Algorithm Requirements Summary

Algorithm	Minimum Iterator	Why
std::find	Input	Single pass, read-only
std::copy	Input + Output	Read source, write dest
std::replace	Forward	Multi-pass, read+write
std::reverse	Bidirectional	Needs -- to work inward
std::sort	Random Access	Needs it+n for partitioning
std::binary_search	Random Access*	Needs it+n for O(log N)
std::lower_bound	Forward*	Works but O(N) without random access
std::nth_element	Random Access	Quickselect needs jumps
std::make_heap	Random Access	Heap indexing: 2i+1, 2i+2

*std::lower_bound accepts Forward iterators but degrades to O(N) instead of O(log N).