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:

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: