5.1 · Iterator Fundamentals: The Trait and Its Adapters

Domain 5 — Iterators and Lazy Computation Duration: ~15 minutes Library components: std::iter::Iterator, adapter types in std::iter

Introduction

The Iterator trait is the most used abstraction in the Rust standard library. It has one required method, next(). That one method gives you 75 provided methods (adapters and consumers), and 60 of them are stable in Rust 1.99. Each for loop uses the trait. The compiled code is as fast as a loop that you write manually. Collections, ranges, strings, I/O lines, and command-line arguments all give you iterators.

This tutorial shows:

• The Iterator trait, next(), and the pull model.
• Laziness: why the construction of an adapter chain does no work, and how consumers pull items one at a time.
• The core transformation adapters: map, filter, filter_map, flat_map, flatten, enumerate, zip, chain.
• The selection adapters: take, skip, take_while, skip_while, step_by, cycle, fuse.
• Why iterators are a zero-cost abstraction: the convenience has no runtime cost.

The Trait and the Pull Model

The trait has only one required method:

trait Iterator {
    type Item;                                  // the type of each item
    fn next(&mut self) -> Option<Self::Item>;   // the one required method
    // 75 provided methods call next() (60 of them are stable in Rust 1.99)
}

next() returns Some(item) until the sequence has no more items. Then it returns None. All the other operations (map, sum, collect, and the for loop) call next() again and again. This is a pull model: no stage makes an item until a later stage asks for it.

An iterator is a cursor, not a snapshot. Each call to next() moves the cursor forward permanently. Two calls never return the same element. For this reason, most adapter methods take self by value. When you wrap an iterator, the wrapper owns the cursor. Tutorial 5.3 shows how by_ref lends the cursor instead.

let mut it = [10, 20, 30].iter();   // it: slice::Iter<'_, i32>, each item is an &i32
assert_eq!(it.next(), Some(&10));   // each call moves the cursor one item forward
assert_eq!(it.next(), Some(&20));
assert_eq!(it.next(), Some(&30));
assert_eq!(it.next(), None);        // the sequence has no more items

Laziness: Nothing Happens Until Consumption

Adapters are lazy. map does not loop through the items. It returns a Map<I, F> struct that stores the previous iterator and the closure. filter, take, zip, and the other adapters do the same. Work occurs only when a consumer starts to pull. A consumer is a method that calls next(), such as collect or sum. A for loop is also a consumer.

Figure: A lazy pipeline — adapters store, consumers pull

05_01_lazy_pipeline.rs shows this with a counter in the map closure. The example searches a log for the first ERROR line. It stops at the first match, as ripgrep does:

// log: [&str; 6] holds six log lines. Lines 4 and 6 start with "ERROR".
// pulls counts the calls of the `map` closure.
// A Cell lets the closure change the counter through a shared reference.
let pulls = Cell::new(0_usize);
let mut errors = log
    .iter()
    .map(|line| { pulls.set(pulls.get() + 1); line.trim_start() })
    .filter(|line| line.starts_with("ERROR"));

assert_eq!(pulls.get(), 0);       // the pipeline exists, but no closure ran

let first = errors.next();        // pulls lines 1..=4 and stops at the first ERROR line
assert_eq!(pulls.get(), 4);       // the pipeline did not read lines 5 and 6

Remember these two results of laziness:

• An early exit has no cost. Short-circuiting consumers (find, any, all, position) stop the pull when they have an answer.
• A pipeline without a consumer does nothing. If you make data.iter().map(expensive) and never consume it, no code runs. The compiler gives a warning: iterators are lazy and do nothing unless consumed.

05_01_lazy_pipeline.rs prints:

after building the pipeline: 0 lines processed
first error found after processing 4 lines
second error found after processing 6 lines
`any` stopped after inspecting 2 lines
pipeline result == manual loop result: ["ERROR connection reset by peer", "ERROR disk quota exceeded"]

All assertions passed.

Transformation Adapters

These adapters change what goes through the pipeline. 05_02_transform_adapters.rs uses all of them on one realistic task. The task is to parse a key = value config file that has comments, blank lines, and list values. The example puts the file values on top of the defaults, as cargo does with its configuration layers.

These two are the most instructive:

// meaningful: Vec<&str> holds the trimmed config lines, with no blank lines and no comments.
// filter_map: split_once returns None for a line that has no '=', and filter_map drops it.
let entries: Vec<(&str, &str)> = meaningful
    .iter()
    .filter_map(|line| line.split_once('='))
    .map(|(k, v)| (k.trim(), v.trim()))   // ("replicas ", " 3") becomes ("replicas", "3")
    .collect();

// defaults: [(&str, &str); 2] is [("replicas", "1"), ("log_level", "info")].
// chain: the defaults come first and the file entries come second.
// In a map, a later duplicate key replaces the earlier value.
let merged: BTreeMap<&str, &str> =
    defaults.into_iter().chain(entries.iter().copied()).collect();
assert_eq!(merged["replicas"], "3");   // the file value replaced the default "1"

Option is iterable: it gives zero items or one item. Thus flatten() on an iterator of Options discards each None. You will see this pattern very frequently in code that parses text.

zip stops at the end of the shorter side. It does not panic, and it does not add padding. If you must detect a length mismatch, do a check afterwards, or use zip together with enumerate.

Selection Adapters

These adapters select which items go through, and they do not change the items. 05_03_slicing_adapters.rs shows a concrete use for each one:

• skip(n) with take(n): pagination, as in results.skip(page * size).take(size).
• take_while(p) and skip_while(p): these divide a message into header and body at the first blank line. filter makes a decision for each item, but these adapters make a decision once. take_while stops the stream permanently at the first item that fails the predicate. skip_while stops the skip at the first item that passes the predicate.
• step_by(n): this downsamples a metrics stream. It keeps the first item, then each n-th item after it.
• cycle(): this repeats a cloneable iterator forever. When you zip it with a finite task list, it gives a round-robin assignment. This is safe, because zip stops at the end of the task list.
• fuse(): after its first None, a fused iterator never gives an item again. The basic Iterator contract permits an iterator to give items again after a None. Tutorial 5.4 explains the FusedIterator guarantee in detail.

Figure: take_while vs filter — one-time decision vs per-item decision

Be careful with take_while. It must consume the first item that fails the predicate, because it must test that item. That item is lost: take_while does not put it back. When you need the boundary item, use Peekable::next_if (Tutorial 5.3).

// message: [&str; 5] holds two header lines, one empty line "", and two body lines.
let mut it = message.iter().copied();
// by_ref lends `it` to take_while, so `it` stays usable after the collect (Tutorial 5.3).
let headers: Vec<&str> = it.by_ref().take_while(|l| !l.is_empty()).collect();
assert_eq!(it.next(), Some("body line 1"));  // take_while consumed the empty line ""

Why Iterators Are Zero-Cost

An adapter chain looks as if it allocates intermediate collections and calls through function pointers. It does not do these things:

• No allocation. Each adapter is a plain struct that wraps the previous one. log.iter().map(f).filter(p) is one stack value. Its type is Filter<Map<slice::Iter<'_, &str>, F>, P>, and this type describes the full pipeline.
• No virtual dispatch. Each closure has a unique anonymous type. Thus the compiler dispatches each next() call statically and can inline it.
• Monomorphization. The compiler generates a specialized copy of the chain for these exact types. Then the optimizer merges the nested next() calls into one loop. The result is routinely the same assembly as the manual version, and it is sometimes better. The compiler can remove bounds checks, because it can prove that the iteration stays in bounds. Loops that use indexing do not get this advantage.

// log is the array of six log lines from the laziness example.
let by_pipeline: Vec<&str> = log.iter()
    .map(|line| line.trim_start())
    .filter(|line| line.starts_with("ERROR"))
    .collect();
// by_pipeline holds the two ERROR lines.
// The `for` loop version gives the same results, and routinely the same machine code.

The practical rule: choose between a loop and an iterator chain for readability, never for assumed performance.

Summary

Code Examples