Iterator Pattern

  • Description: Sequential access to elements of an aggregate without exposing its internal representation — in C++ the canonical iterator pattern is baked into the language via begin/end, range-based for, and C++20 ranges.
  • My Notion Note ID: K2C-2-15
  • Created: 2026-05-22
  • Updated: 2026-05-22
  • License: Reuse is very welcome. Please credit Yu Zhang and link back to the original on yuzhang.io

Table of Contents

1. The Problem

  • Aggregate hides its internal storage (array, linked list, tree, hash table).
  • Clients still need to traverse — without knowing layout.
  • Classic OO answer: hand out an Iterator object exposing next, has_next, current.
  • Each traversal kind (forward, reverse, in-order, level-order) = a different iterator.

C++ takes this further: iterator is a language idiom, not just a pattern.

  • STL containers expose begin() / end().
  • Generic algorithms work on iterator pairs, independent of container.
  • Range-based for is sugar over begin/end.
  • C++20 ranges lifts this to first-class composable views.

This note treats Iterator as a design pattern but anchors every example in STL idioms — that's how it's used in modern C++.

2. Structure

Classic OO roles:

  • Iterator — interface (next, has_next, current / reset).
  • ConcreteIterator — tracks position in a specific Aggregate.
  • Aggregate — interface for creating an iterator (create_iterator()).
  • ConcreteAggregate — returns a ConcreteIterator bound to itself.

C++ STL mapping:

GoF role STL equivalent
Iterator Container::iterator (a type, often a class)
Iterator ops operator++, operator*, operator!=
Aggregate Container
create_iterator Container::begin() / Container::end()

End is represented as a past-the-end sentinel (half-open range [begin, end)), not a has_next() predicate. C++20 generalizes to sentinel types that need only be !=-comparable to the iterator — they don't have to be iterators themselves.

3. C++ Example

3.1 STL idiom — range-based for

#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = {1, 2, 3, 4};
    for (int x : v) std::cout << x << ' ';   // 1 2 3 4
}

Desugars to:

auto&& __r = v;
auto __b = std::begin(__r);
auto __e = std::end(__r);
for (; __b != __e; ++__b) {
    int x = *__b;
    // body
}

Anything with begin()/end() (member or free, ADL-found) works.

3.2 Iterator categories

Iterators classified by supported ops (each subsumes the weaker):

Category Ops Example
Input read, ++, one-pass istream_iterator
Output write, ++, one-pass ostream_iterator, back_inserter
Forward read/write, multi-pass ++ forward_list::iterator
Bidirectional + -- list, map, set iterators
Random access + +n, -n, <, [] deque::iterator
Contiguous (C++20) random access + addresses contiguous vector::iterator, raw pointer

Algorithms require a minimum category — std::sort needs random access, std::reverse needs bidirectional.

3.3 Writing a custom iterator (forward)

#include <cstddef>
#include <iterator>

class IntRange {
    int begin_, end_;
public:
    IntRange(int b, int e) : begin_(b), end_(e) {}

    class iterator {
        int v_;
    public:
        using iterator_category = std::forward_iterator_tag;
        using value_type        = int;
        using difference_type   = std::ptrdiff_t;
        using pointer           = const int*;
        using reference         = const int&;

        explicit iterator(int v) : v_(v) {}
        int operator*() const { return v_; }
        iterator& operator++() { ++v_; return *this; }
        iterator operator++(int) { auto t = *this; ++v_; return t; }
        bool operator==(const iterator& o) const { return v_ == o.v_; }
        bool operator!=(const iterator& o) const { return v_ != o.v_; }
    };

    iterator begin() const { return iterator{begin_}; }
    iterator end()   const { return iterator{end_};   }
};

// Now works with range-for, std::find, std::accumulate, std::ranges::*
for (int x : IntRange{0, 5}) std::cout << x;   // 01234

3.4 C++20 ranges + views

Composable, lazy, no intermediate allocation.

#include <ranges>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8};

    auto even_squared = v
        | std::views::filter([](int x) { return x % 2 == 0; })
        | std::views::transform([](int x) { return x * x; });

    for (int x : even_squared) std::cout << x << ' ';   // 4 16 36 64
}

A view is the modern iterator pair — cheap to copy, lazy, composable. The pattern hasn't changed; the ergonomics have.

3.5 Sentinel-based iterator (C++20)

struct EndsAtZero {};

class CStrIter {
    const char* p_;
public:
    using iterator_category = std::input_iterator_tag;
    using value_type = char;
    using difference_type = std::ptrdiff_t;
    using pointer = const char*;
    using reference = const char&;

    explicit CStrIter(const char* p) : p_(p) {}
    char operator*() const { return *p_; }
    CStrIter& operator++() { ++p_; return *this; }
    CStrIter operator++(int) { auto t = *this; ++p_; return t; }
    bool operator==(EndsAtZero) const { return *p_ == '\0'; }
};

// Range = (begin iterator, end sentinel-of-different-type)

4. When to Use / When Not To

Use when:

  • Multiple traversal strategies for the same aggregate (forward, reverse, in-order, post-order).
  • Aggregate's internal representation must stay hidden.
  • Need a uniform interface for traversing different aggregates.
  • Want to plug into generic algorithms (std::sort, std::find, ranges).

Don't use when:

  • Container exposes random access (operator[]) and that's all you need.
  • Aggregate is trivial and a single hard-coded loop is clearer.
  • Performance dictates inlining — though iterator templates inline well; this is rarely a real concern in C++.

In C++ specifically: always model traversable types with iterators. It's the idiom, not just a pattern — opting out cuts you off from the STL ecosystem.

5. Variants and Pitfalls

Variants:

  • External iterator — caller drives (++it, classic STL).
  • Internal iterator — aggregate drives, takes a callback (for_each(f), std::ranges::for_each).
  • Robust iterator — survives modification of the aggregate (rare in C++; expensive).
  • Lazy iterator — generator-style; values produced on demand (views::iota, coroutines).
  • Reverse iterator — wraps another iterator; ++ calls -- underneath (std::reverse_iterator).
  • Insertion iterator — back_inserter, front_inserter, inserter — writes mutate the container.

Pitfalls:

  • Iterator invalidation. vector reallocation invalidates all iterators; unordered_map rehash invalidates all; list invalidates only erased ones. Read every container's rules — silent UB otherwise.
  • Dereferencing end(). Past-the-end is not a valid element. UB.
  • Mixing iterators from different containers. it1 != it2 where they're from different objects — UB.
  • Returning iterator to a temporary. auto it = make_vec().begin(); — dangling.
  • Forgetting iterator_traits types. Generic algorithms need value_type, difference_type, etc. Missing → SFINAE/concepts failure.
  • Coroutine-based iterators allocate; not zero-cost. Profile before assuming.

6. Related Patterns

  • Iterator in C++ = language-level support. STL begin/end + range-based for + C++20 ranges = the canonical Iterator implementation. Custom iterators plug into std::sort, std::find, std::accumulate, all algorithms, all views. Don't reinvent — write iterators that satisfy STL concepts.
  • Iterator vs Visitor — Iterator walks a homogeneous collection; Visitor dispatches on heterogeneous element types via double-dispatch. Tree walk = often both: iterator yields nodes, visitor handles each by node type.
  • Iterator vs Composite — Composite gives a tree shape; Iterator provides traversal order (in-order, pre-order, level-order) over that tree.
  • Iterator vs Factory Method — Container::begin() IS a Factory Method returning a ConcreteIterator. The container hides which concrete iterator class.
  • Iterator vs Memento — to make an iterator "robust" across mutations, capture position as a Memento independent of the aggregate's current shape.
  • Iterator vs Observer — Iterator pulls (consumer-driven); Observer pushes (producer-driven). Same dataflow, opposite direction.

7. References