Iterator

Learning Objectives

Traverse collections without exposing their representation.

Implement C++ iterators, Python generators and JavaScript iteration protocols.

Handle invalidation and single-pass vs multi-pass iteration.

Prerequisites: Modules 17, 35.

Intuition and Definition

Intent: provide a way to access the elements of an aggregate object sequentially without exposing its underlying representation.

begin()/end() returning iterator objects (*, ++, !=); ranges and concepts (std::input_iterator, std::forward_iterator)

Iterable<T> → Iterator<T> (hasNext, next) IEnumerable<T> → IEnumerator<T>; yield return

__iter__ / __next__, StopIteration; generators with yield

[Symbol.iterator]() returning { next(): { value, done } }; generator functions

Single-pass iterators (reading a stream) can be traversed once; multi-pass iterators (a vector) can be copied and restarted.

Why It Matters

for (auto& x : container) works the same for arrays, trees, ring buffers and lazily generated sequences — callers don't care how elements are stored.

Syntax and Language Notes

def even_numbers(limit):
    n = 0
    while n < limit:
        yield n
        n += 2

function* evenNumbers(limit: number) { for (let n = 0; n < limit; n += 2) yield n; }

Complete Example

A fixed-size ring buffer that hides its wrap-around storage behind an iterator:

Generators produce elements lazily — the "collection" never exists in memory:

#include <array>
#include <cstddef>
#include <iostream>
#include <iterator>
#include <numeric>

template <typename T, std::size_t N>
class RingBuffer {
    std::array<T, N> data_{};
    std::size_t head_ = 0, size_ = 0;                  // head_ = oldest element
public:
    void push(const T& v) {
        data_[(head_ + size_) % N] = v;
        if (size_ < N) ++size_; else head_ = (head_ + 1) % N;   // overwrite the oldest
    }
    class iterator {
        const RingBuffer* rb_; std::size_t i_;
    public:
        using iterator_category = std::forward_iterator_tag;
        using value_type = T;
        using difference_type = std::ptrdiff_t;
        using pointer = const T*;
        using reference = const T&;
        iterator() : rb_(nullptr), i_(0) {}
        iterator(const RingBuffer* rb, std::size_t i) : rb_(rb), i_(i) {}
        const T& operator*() const { return rb_->data_[(rb_->head_ + i_) % N]; }
        iterator& operator++() { ++i_; return *this; }
        iterator operator++(int) { iterator t = *this; ++i_; return t; }
        bool operator==(const iterator& o) const { return i_ == o.i_; }
    };
    iterator begin() const { return {this, 0}; }
    iterator end() cons
…

30 40 50 60 
sum 180

def can_frames(log_lines):
    for line in log_lines:                      # single pass over a stream
        if line.startswith("#"):
            continue
        can_id, data = line.split()
        yield int(can_id, 16), bytes.fromhex(data)

log = ["# trace start", "0C0 FF7D7D401F000000", "1A0 10271227", "# end"]
frames = can_frames(log)
print(next(frames))
print([hex(i) for i, _ in frames])           # continues where it left off
print(list(frames))                          # exhausted: single-pass

(192, b'\xff}}@\x1f\x00\x00\x00')
['0x1a0']
[]

Step-by-Step Walkthrough

The ring buffer stores the last four values in a circular array; after six pushes, head_ points at 30.

The iterator maps logical positions 0..size-1 to physical slots (head + i) % N; callers see 30 40 50 60.

Because it meets std::forward_iterator, standard algorithms (std::accumulate) work on it.

The Python generator yields frames one at a time; once consumed, it is exhausted.

Common Mistakes

Iterator invalidation: modifying a container while iterating (vector::push_back may reallocate; erasing while iterating with a stale iterator).

Treating single-pass iterators as multi-pass (iterating a generator twice).

Exposing internals (std::vector<T>& items()) instead of an iterator range.

Python: modifying a list or dict while iterating over it.

Trade-offs and Alternatives

External iterators (caller drives next) give control; internal iteration (forEach(callback)) is simpler but can't be paused or combined. C++20 ranges and views compose lazily (view::filter | view::transform).

Real-World Use

Every collection library, database cursors, file and network streams, tree traversals (pre-order/in-order iterators), paginated API clients (async iterators).

Practice

Q1. (Easy) Which Python keyword turns a function into a generator?

Answer: yield.

Q2. (Medium) Why can't you iterate a generator twice?

Answer: It's a single-pass iterator; its state advances and is not reset.

Q3. (Advanced) What happens to iterators into a std::vector after push_back causes reallocation?

Answer: All iterators, pointers and references to its elements are invalidated (they point into freed memory); using them is undefined behaviour.

Interview Question

Q1. "Implement an iterator over a binary tree in order without recursion."

Answer: Use an explicit stack: on construction push the root and all its left descendants; next() pops the top node (the next smallest), then pushes its right child and all of that child's left descendants; hasNext() checks whether the stack is non-empty. Each node is pushed and popped once (amortized O(1) per step, O(height) memory).

Quick Quiz

Q1. What does an iterator hide?

Answer: The collection's internal representation.

Q2. JavaScript method that makes an object iterable?

Answer: [Symbol.iterator]().

Q3. What is iterator invalidation?

Answer: An iterator becoming unusable because the container changed underneath it.

Summary

Iterators traverse without exposing representation; generators make them lazy.

Respect invalidation rules and single-pass semantics.

Related: Modules 17, 35.