Custom Iterators and Laziness

You have a type that generates values — a counter, a retry schedule, a sensor sampling loop — and you want map, filter, sum, for to work on it without writing them yourself. The whole protocol is one associated type and one method:

struct Countdown {
    remaining: u8,
}

impl Iterator for Countdown {
    type Item = u8;                        // what each step yields

    fn next(&mut self) -> Option<u8> {     // None == end of sequence
        if self.remaining == 0 {
            None
        } else {
            self.remaining -= 1;
            Some(self.remaining + 1)
        }
    }
}

let liftoff: Vec<u8> = Countdown { remaining: 3 }.collect();   // [3, 2, 1]
let total: u8 = Countdown { remaining: 10 }.sum();             // 55

That is the entire contract: next(&mut self) returns Some(item) while values remain and None when finished. Every adapter you already know — map, filter, enumerate, zip, take, chain, collect — is implemented against that contract only, so your three-line type inherits the entire Iterator toolkit with zero extra code. This is the payoff of trait-based design in one screenshot: the std library authors wrote the adapters once, against next, and never again per container.

Two optional overrides improve the machinery without changing behavior:

impl Iterator for Countdown {
    // ...
    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.remaining as usize, Some(self.remaining as usize))
    }
}

size_hint lets collect pre-allocate exactly — Vec::with_capacity for a known count, no wasted buffer, no growth copies. Supply it when you can compute the remaining count cheaply and it is exact or a correct lower bound (over-promising is undefined behavior territory for adapters that trust it, so never guess upward). Beyond that, std::iter::FusedIterator (marker: once None, always None) and ExactSizeIterator (marker: len() is exact) let consumers take faster paths; both are claims about your implementation, and the compiler cannot check them — implement them only when true.

Common shapes for next, so you recognize them immediately:

An iterator delegating to another (next pulling from self.inner) is how composite iterators are written, and the ? inside next works because Option is the return type — the same operator from the error-handling topics, wearing its other hat.

The interview question this topic exists for: "implement an iterator over the Fibonacci sequence." The correct answer is a struct holding the two state values, an Iterator impl whose next computes and yields the next number, and a note that fib().take(10).collect() then works — plus, if you mention size_hint returning (0, None), you have shown you know the protocol beyond the required method:

struct Fib { a: u64, b: u64 }

impl Iterator for Fib {
    type Item = u64;
    fn next(&mut self) -> Option<u64> {
        let out = self.a;
        (self.a < u64::MAX / 2).then(|| { let c = self.a + self.b; self.a = self.b; self.b = c; });
        Some(out)
    }
}

let even_fib_sum: u64 = Fib { a: 0, b: 1 }
    .take_while(|x| *x < 4_000_000)
    .filter(|x| x % 2 == 0)
    .sum();

Note what did not appear: no Vec, no index bookkeeping, no while loop — the state lives in the struct, and every std adapter composes on top of it.

Because adapters are lazy structs and generic types are monomorphized, a chain compiles into a single loop with the closures inlined — no vtable, no allocation, no function-pointer indirection:

let hits: Vec<_> = requests.iter()
    .filter(|r| r.status == 200)
    .map(|r| r.latency_ms)
    .collect();

Under cargo build --release, this typically matches a hand-written for loop instruction for instruction; benchmarks in the wild show iterator chains faster than naive loops more often than slower, because the fused single-pass structure exposes bounds-check elimination and keeps the index in a register. Laziness also means the chain allocates exactly once — for the result Vec — whereas staged loops that build a temporary Vec per stage allocate and copy per stage.

The mistake laziness invites is materializing in the middle:

// Two full passes over N elements, plus an N-element temporary allocation
let a: Vec<_> = data.iter().filter(p).collect();
let b: Vec<_> = a.iter().map(f).collect();

// One pass, zero temporaries
let b: Vec<_> = data.iter().filter(p).map(f).collect();

Each .collect() closes the current pipeline, allocates, and materializes — turning O(n) work into O(n) with an extra constant per intermediate, and turning two logical stages into two traversals (cache-unfriendly for large inputs). Only collect when a value must exist: a final result, something handed across a function boundary, or a Vec you need to mutate while iterating. When you need an intermediate result for debugging, inspect(|x| println!("{x:?}")) is an adapter — it stays lazy and costs nothing in release builds if you remove it... which is the point: keep the chain intact and delete the probe later.

Returning lazy iterators from functions is where the design gets interesting, because you cannot name the compiler-generated type:

// Zero cost, opaque type — the caller sees `impl Iterator<Item = &Request>`
fn bad(requests: &[Request]) -> impl Iterator<Item = &Request> {
    requests.iter().filter(|r| r.status >= 500)
}

// Costly but type-erased — needed when the chain differs per branch
fn either(reqs: &[Request], strict: bool) -> Box<dyn Iterator<Item = &Request> + '_> {
    if strict {
        Box::new(reqs.iter().filter(|r| r.status >= 400))
    } else {
        Box::new(reqs.iter().filter(|r| r.status >= 500))
    }
}

impl Iterator (named in Rust 2024 as -> impl Iterator) keeps everything static and inlinable but can only represent one concrete type per function — different branches with different adapters need Box<dyn Iterator> (one allocation per box, dynamic dispatch) or an enum implementing Iterator manually. Choose impl by default, Box<dyn> only when the pipeline truly varies at runtime.

One rule about ending: consumers like fold and for stop when they see None, and std iterators are fused — but a hand-rolled Iterator whose next can return Some after None (state bugs, restarting an inner iterator) breaks adapters like fuse-based combinators and MultiPeek. Make "after None, forever None" part of your next implementation, and derive it explicitly with impl FusedIterator for Countdown {} when you have proven it.

There is one more laziness trick worth knowing because it prevents a whole class of bugs: by_ref(). A consumer like take or next consumes the iterator by value, so calling it.take(3) moves your iterator and you cannot continue with it. it.by_ref().take(3) borrows it instead, the chain stops after three pulls, and it remains usable for the rest of the work — the standard way to peek at the head of a sequence (process the first record, then loop over the remainder) without splitting state across two objects.

for does not know about your type — it knows about three trait methods, and that is the whole integration surface:

// Desugared by the compiler:
for item in collection { ... }
// becomes:
let mut it = IntoIterator::into_iter(collection);
while let Some(item) = it.next() { ... }

Implement IntoIterator and your type works in every for, every collect destination pattern, and Iterator::chain in the std library. The complete integration for a container with three access modes:

struct Playlist {
    songs: Vec<Song>,
}

impl IntoIterator for Playlist {
    type Item = Song;
    type IntoIter = std::vec::IntoIter<Song>;

    fn into_iter(self) -> Self::IntoIter {      // consumes the playlist
        self.songs.into_iter()
    }
}

impl<'a> IntoIterator for &'a Playlist {
    type Item = &'a Song;
    type IntoIter = std::slice::Iter<'a, Song>;

    fn into_iter(self) -> Self::IntoIter { self.songs.iter() }   // borrows
}

impl<'a> IntoIterator for &'a mut Playlist {
    type Item = &'a mut Song;
    type IntoIter = std::slice::IterMut<'a, Song>;

    fn into_iter(self) -> Self::IntoIter { self.songs.iter_mut() }
}

Three impls, three call sites, all spelled the same way at the use site — and the ownership axis you have been following since Vec decides which one fires:

for s in &playlist { }            // &Song   — playlist still usable
for s in &mut playlist { play(s); } // &mut Song — mark as played in place
for s in playlist { archive(s); } // Song    — moves each song out, playlist consumed

The three impls light up the three loop forms, and seeing them side by side makes the ownership axis concrete:

let mut pl = Playlist::demo();

for s in &pl { report(s); }             // IntoIterator for &Playlist  -> &Song
for s in &mut pl { s.played = true; }   // IntoIterator for &mut Playlist -> &mut Song
for s in pl { archive(s); }             // IntoIterator for Playlist   -> Song (pl is moved)

Common implementation mistakes, so you can spot them in review: forgetting type IntoIter (the compiler asks for the concrete iterator type — name the inner one, e.g. std::vec::IntoIter<Song>), writing fn into_iter(self) -> ... that clones internally (the owned impl should move self.songs.into_iter() — a clone there silently doubles your cost and defeats the purpose of ownership transfer), and implementing only the owned form, which makes for x in &your_type fail with "&Playlist is not an iterator" while every std container supports it.

Delegation to the inner Vec is the standard implementation: you write self.songs.into_iter() and inherit correct behavior, bounds, and performance. There is no reason to hand-roll a next loop for storage you already keep in a Vec.

Design notes that come up beyond the happy path: the type Item can differ per impl (owned vs borrowed is the whole point), for over an array by value yields owned elements since edition 2021 (before that it implicitly borrowed), and implementing FromIterator<Song> for Playlist gives you songs.iter().collect::<Playlist>() — your type as both a source (IntoIterator) and a destination (FromIterator) of pipelines. Keep them symmetric: a container that can be iterated but not collected into feels wrong to everyone who uses it.

Interview framing: "how does for work?" — the compiler calls IntoIterator::into_iter once, then loops on next() until None; your type participates by implementing one trait, with the three-impl pattern (T, &T, &mut T) covering owned and borrowed iteration. From here the roadmap leaves collections for structure: Modules and Visibility decides where all this code lives.