Iterators

A Rust iterator is a conveyor belt. Items sit lined up at one end, the belt has a button at the other, and every press of the button slides one item off into your hand. Nothing on the belt moves on its own. The belt sits still until you press the button. Press once, get one item. Press again, get the next. Press it after the last item has come off and the belt hands you back a little flag that says empty. That single rule — one item per pull, a flag at the end — is the whole Iterator trait. Every fancy thing Rust does with .map(...).filter(...).take(3) is just stations bolted onto a belt that still only moves when someone downstream presses the button.

The idea that a collection should hand out one item at a time through a tiny standard interface is older than Rust by 35 years. Barbara Liskov shipped a language called CLU at MIT in 1975 with a feature she called an iterator — a special kind of function that could yield values one at a time and pause between them. Before that, walking a tree or a hash table meant writing a custom traversal every time and exposing the guts of the data structure to the caller. Liskov's idea was that the data structure should keep its guts private and just hand out items through a uniform pull interface. Python copied the shape in PEP 234 in 2001 with __iter__ and __next__. Haskell built a whole language around lazy lists where nothing computed until you pulled. Rust took the Liskov shape, the Haskell laziness, and the C++ template trick of compiling specialized code for each belt — so a chain of three adapters becomes one tight loop with no virtual calls. Aaron Turon and the early Rust team locked the trait into the 1.0 release in 2015, and it has barely changed since.

The trait is one method. You write a struct that holds the state of the belt, you write a next method that returns the next item or None when the belt is empty, and the language gives you fifty adapter methods for free. Here is the smallest custom belt — a stepped range that walks from a start to an end in jumps of a step.

struct SteppedRange {
    next_value: i32,
    end: i32,
    step: i32,
}

impl Iterator for SteppedRange {
    type Item = i32;

    fn next(&mut self) -> Option<i32> {
        if self.next_value >= self.end {
            return None;
        }
        let current = self.next_value;
        self.next_value += self.step;
        Some(current)
    }
}

The struct holds three numbers and nothing else. The impl Iterator for SteppedRange block does two jobs. The type Item = i32 line tells Rust that every press of the button returns an i32. The next method is the button itself. It checks whether the current value has reached the end, returns None if it has, and otherwise returns the current value wrapped in Some while bumping the state forward by one step. That is the full implementation. No allocations. No heap. The whole iterator lives in a few bytes on the stack.

Press the button by hand and watch one item drop at a time.

fn pull_by_hand() {
    println!("-- pulling items off the belt by hand --");
    let mut belt = SteppedRange {
        next_value: 0,
        end: 10,
        step: 3,
    };
    while let Some(item) = belt.next() {
        println!("pulled {item}");
    }
    println!("belt empty");
}

A while let Some(item) = belt.next() loop is the long way to drain a belt. It is exactly what for item in belt desugars to under the hood. The first call to next returns Some(0), the second Some(3), then 6, then 9, then None. Four items came off the belt, the loop saw the empty flag, and while let stopped.

The interesting part is what happens when you bolt stations onto the belt. Rust gives you map to transform each item as it passes, filter to drop items that do not match a test, take to ask for only the first few. Each station wraps the previous belt and exposes a new belt with the same one-method next interface. Build a three-station chain and ask for the result.

fn chain_of_stations() {
    println!("-- adapters built but nothing moves yet --");
    let belt = SteppedRange {
        next_value: 0,
        end: 100,
        step: 5,
    };
    let pipeline = belt.map(|n| n * n).filter(|n| n % 2 == 0).take(3);
    println!("pipeline built, no items have flowed");
    let collected: Vec<i32> = pipeline.collect();
    println!("after collect: {collected:?}");
}

Read that block twice. The first three lines build a belt, then wrap it in a map station that squares each number, then wrap that in a filter station that keeps even results, then wrap that in a take(3) station that says stop after three items. The println! between the build and the collect proves the central trick — no items have moved yet. Building the pipeline does no work. The struct of structs of structs sits on the stack waiting. Only when collect calls next at the end of the chain does the first item finally get pulled, and the pull propagates back up the belt one station at a time. The output of the run shows the three items that fell out at the end.

-- pulling items off the belt by hand --
pulled 0
pulled 3
pulled 6
pulled 9
belt empty

-- adapters built but nothing moves yet --
pipeline built, no items have flowed
after collect: [0, 100, 400]

-- per-step timeline, two items requested --
  station map     touches 1
  station filter  inspects 10 keep=false
  station map     touches 2
  station filter  inspects 20 keep=false
  station map     touches 3
  station filter  inspects 30 keep=true
  station map     touches 4
  station filter  inspects 40 keep=false
  station map     touches 5
  station filter  inspects 50 keep=false
  station map     touches 6
  station filter  inspects 60 keep=true
final belt output: [30, 60]

The first block is the hand pull. The second block proves the pipeline did not run until collect asked it to. The third block is the part that pays off everything above — a timeline of every station call as the chain runs. The source belt counts 1, 2, 3, 4, 5, 6, 7… one at a time. The map station multiplies each by 10. The filter station keeps only items divisible by 30. The take(2) at the end says stop after the second keeper. Read the timeline top to bottom. Map touches 1, filter inspects 10, rejected. Map touches 2, filter inspects 20, rejected. Map touches 3, filter inspects 30, kept — that is the first of two. The belt keeps going. Map touches 4 and 5 and the filter rejects both. Map touches 6, filter inspects 60, kept — that is the second of two. The belt stops dead. The source values 7 through 19 never get touched. They never get pulled because take stopped pressing the button.

That stop-dead behavior is what makes iterator chains worth the trouble. A for loop with the same logic would also stop early, but it would also need a counter variable, an inner if, a break, and you would have to keep all three in your head while reading the code. The pipeline version pushes that bookkeeping into the trait. You wrote the steps in the order you think about them — first square the items, then keep the ones I care about, then stop after I have enough — and the compiler chained them into a single tight loop with no allocations between stations. Each station inlines into its neighbor at compile time, so the running code is the same speed as the hand-written loop you would have written instead. That is the C++ template trick Rust borrowed. Generic code with zero runtime cost.

What this single-belt model cannot do is hand the same item out to two readers at the same time. Each pull moves the state forward, and once an item has been pulled it is gone. The next lesson is the first one that has to deal with that — what happens when one piece of data needs to live in two places at once, which is the question that forces Rust to talk about the stack and the heap.