Iterators: The Glue Between Containers and Algorithms

Iterators abstract the concept of position within a sequence, enabling algorithms to work with any container. They’re the foundation of generic programming in C++.

Iterator Categories

Iterators form a hierarchy based on operations they support:

skinparam monochrome true

rectangle "Input Iterator" as input
rectangle "Forward Iterator" as forward
rectangle "Bidirectional Iterator" as bidir
rectangle "Random Access Iterator" as random
rectangle "Output Iterator" as output
rectangle "Contiguous Iterator (C++20)" as contiguous

input <|-- forward
forward <|-- bidir
bidir <|-- random
random <|-- contiguous

Input Iterator

Read-only, single-pass:

• *it (read)
• ++it, it++
• ==, !=

Example: std::istream_iterator

Output Iterator

Write-only, single-pass:

• *it = value (write)
• ++it, it++

Example: std::ostream_iterator, std::back_inserter

Forward Iterator

Multi-pass read/write:

• All input iterator operations
• *it = value
• Multi-pass guarantee

Example: std::forward_list::iterator

Bidirectional Iterator

Forward + backward:

• All forward iterator operations
• --it, it--

Example: std::list::iterator, std::set::iterator

Random Access Iterator

Bidirectional + arithmetic:

• All bidirectional operations
• it + n, it - n
• it[n]
• <, >, <=, >=

Example: std::vector::iterator, std::deque::iterator

Contiguous Iterator (C++20)

Random access + contiguous memory:

• Guarantees elements are in contiguous memory
• Enables pointer arithmetic optimizations

Example: std::vector::iterator, std::array::iterator

Basic Iterator Operations

std::vector<int> v = {1, 2, 3, 4, 5};

auto it = v.begin();  // Iterator to first element
auto end = v.end();   // Past-the-end iterator

while (it != end) {
    std::cout << *it << ' ';  // Dereference
    ++it;  // Advance
}

// Range-based for is syntactic sugar for iterators
for (auto x : v) {
    std::cout << x << ' ';
}

Iterator Adapters

back_inserter, front_inserter, inserter

Convert containers into output iterators:

std::vector<int> v;
std::fill_n(std::back_inserter(v), 5, 42);  // Pushes 5 copies of 42

std::list<int> lst;
std::fill_n(std::front_inserter(lst), 3, 10);  // Pushes to front

std::set<int> s;
std::copy(v.begin(), v.end(), std::inserter(s, s.begin()));

reverse_iterator

Iterate backwards:

std::vector<int> v = {1, 2, 3, 4, 5};

for (auto it = v.rbegin(); it != v.rend(); ++it) {
    std::cout << *it << ' ';  // 5 4 3 2 1
}

move_iterator

Causes dereference to return rvalue reference:

std::vector<std::unique_ptr<int>> v1;
v1.push_back(std::make_unique<int>(1));
v1.push_back(std::make_unique<int>(2));

std::vector<std::unique_ptr<int>> v2(
    std::make_move_iterator(v1.begin()),
    std::make_move_iterator(v1.end())
);
// v1's unique_ptrs moved to v2

Stream Iterators

istream_iterator

Read from input stream:

std::istringstream iss("1 2 3 4 5");
std::vector<int> v(std::istream_iterator<int>(iss),
                   std::istream_iterator<int>());
// v = {1, 2, 3, 4, 5}

ostream_iterator

Write to output stream:

std::vector<int> v = {1, 2, 3, 4, 5};
std::copy(v.begin(), v.end(),
          std::ostream_iterator<int>(std::cout, " "));
// Outputs: 1 2 3 4 5

Iterator Utilities

std::advance

Move iterator by n positions:

std::list<int> lst = {1, 2, 3, 4, 5};
auto it = lst.begin();
std::advance(it, 3);  // Now points to 4

std::distance

Count elements between iterators:

auto dist = std::distance(lst.begin(), lst.end());  // 5

std::next, std::prev

Return advanced iterator without modifying original:

auto it = v.begin();
auto next = std::next(it, 2);  // Points 2 positions ahead
auto prev = std::prev(it, 1);  // Points 1 position back

Custom Iterators

Creating custom iterators requires defining specific operations based on category:

class Range {
    int current_;
    int end_;
public:
    class Iterator {
        int value_;
    public:
        using iterator_category = std::forward_iterator_tag;
        using value_type = int;
        using difference_type = int;
        using pointer = int*;
        using reference = int&;
        
        Iterator(int v) : value_(v) {}
        
        int operator*() const { return value_; }
        Iterator& operator++() { ++value_; return *this; }
        Iterator operator++(int) { auto temp = *this; ++value_; return temp; }
        
        bool operator==(const Iterator& other) const { return value_ == other.value_; }
        bool operator!=(const Iterator& other) const { return !(*this == other); }
    };
    
    Range(int start, int end) : current_(start), end_(end) {}
    
    Iterator begin() const { return Iterator(current_); }
    Iterator end() const { return Iterator(end_); }
};

// Usage:
for (auto x : Range(1, 6)) {
    std::cout << x << ' ';  // 1 2 3 4 5
}

Iterator Invalidation

Different operations invalidate iterators differently:

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>

int main() {
    std::vector<int> src = {1, 2, 3, 4, 5};
    std::vector<int> dst;
    
    // Using back_inserter
    std::copy(src.begin(), src.end(), std::back_inserter(dst));
    
    std::cout << "Forward: ";
    for (auto it = dst.begin(); it != dst.end(); ++it) {
        std::cout << *it << ' ';
    }
    std::cout << '\n';
    
    std::cout << "Reverse: ";
    for (auto it = dst.rbegin(); it != dst.rend(); ++it) {
        std::cout << *it << ' ';
    }
    std::cout << '\n';
    
    return 0;
}

Forward: 1 2 3 4 5 
Reverse: 5 4 3 2 1