C++ STL Iterators

[], <, and > at O(1) complexity, while the underlying structure defines its limitations. For example, forward iterators support only single-pass operations.

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.

---

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.

---

Examples

Compile-Time Tag Dispatching: 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); 
}