The Rust Lang Book: Iterators in Rust

This chapter explores the iterator pattern in Rust, demonstrating how to process sequences of items efficiently and idiomatically. We will examine how Rust's standard library abstracts traversal logic, how lazy evaluation optimizes performance, and how to implement custom iterators to unlock powerful functional programming patterns.

1. The Core Mental Model: What is the Iterator Pattern?

The iterator pattern decouples the task of traversing a sequence of elements from the underlying data structure where those elements reside. Whether your data is stored in a contiguous array, a complex hash map, a tree, or a custom graph structure, iterators provide a uniform interface for accessing each element sequentially.

Real-Life Analogy

Imagine a mail carrier delivering letters. The carrier does not need to know how the letters are manufactured, sorted, or stacked inside the mailbag. They only need a consistent interface: "give me the next letter." Once the bag is empty, the process stops.

Similarly, an iterator acts as a delivery mechanism. It encapsulates the traversal logic (e.g., incrementing an index for an array, or traversing pointers in a graph) so that the consumer (like a for loop) can process items without knowing the internal layout of the data structure.

Without iterators, you would have to write custom traversal logic for every data structure:

• Arrays/Vectors: Maintain an index variable, increment it, and check bounds.
• Hash Maps: Traverse buckets and linked lists of key-value pairs.
• Graphs: Implement depth-first or breadth-first search algorithms manually.

Iterators hide this complexity behind a single, unified interface.

2. Laziness and the Basic Anatomy of Rust Iterators

In Rust, iterators are lazy. Creating an iterator does not perform any actual work or allocate memory for the elements; it merely stores the state required to perform the iteration when requested.

The Naive vs. Idiomatic Approach

Consider a vector of integers. We can create an iterator over it using the .iter() method:

fn main() {
    let v1 = vec![1, 2, 3];

    // This step is lazy. No iteration occurs yet.
    let v1_iter = v1.iter();

    // The iterator is consumed here by the for loop.
    for val in v1_iter {
        println!("Got: {}", val);
    }
}

If you create v1_iter but never use it in a loop or call a consumer method on it, the compiler will generate a warning, and no runtime overhead will occur. The work is deferred until the elements are explicitly demanded.

3. The Iterator Trait and Associated Types

All iterators in Rust implement the Iterator trait defined in the standard library. The simplified definition of the trait is as follows:

pub trait Iterator {
    type Item;

    fn next(&mut self) -> Option<Self::Item>;

    // Default implementations for dozens of other methods...
}

Key Components of the Trait

1. Associated Types (type Item): The syntax type Item defines an associated type with this trait. It acts as a placeholder. When you implement the Iterator trait, you must specify what concrete type Item represents (e.g., u32, String, or a reference like &i32). This concrete type is what the next method returns.
2. The next Method: This is the only method you are required to implement. It returns:
   • Some(Item) containing the next element in the sequence.
   • None when the iteration is complete.
3. Mutable Self Reference (&mut self): Calling next mutates the internal state of the iterator to keep track of its current position in the sequence. Therefore, any variable holding an iterator must be declared as mut if you intend to call next manually.

4. Three Flavors of Iteration: iter(), iter_mut(), and into_iter()

When creating an iterator from a collection, Rust provides three primary methods. Each serves a distinct purpose regarding ownership and borrowing:

Demonstrating next() and Mutability

The following test demonstrates how calling .next() directly on an iterator mutates its state, and how it returns immutable references when initialized via .iter():

#[test]
fn iterator_demonstration() {
    let v1 = vec![1, 2, 3];

    // Must be mutable to call .next()
    let mut v1_iter = v1.iter();

    // next() returns Option<&i32>
    assert_eq!(v1_iter.next(), Some(&1));
    assert_eq!(v1_iter.next(), Some(&2));
    assert_eq!(v1_iter.next(), Some(&3));
    assert_eq!(v1_iter.next(), None);
}

5. Iterator Methods: Adapters vs. Consumers

The Iterator trait provides a rich set of default methods. These methods are categorized into two main groups: Consumers and Adapters.

Consumer Example: sum()

The sum method takes ownership of the iterator and loops through the elements by repeatedly calling next, accumulating the values:

#[test]
fn iterator_sum() {
    let v1 = vec![1, 2, 3];
    let v1_iter = v1.iter();

    // sum() consumes the iterator
    let total: i32 = v1_iter.sum();
    assert_eq!(total, 6);
}

Adapter Example: map() and collect()

If you use an adapter like map without a consumer, the Rust compiler will issue a warning because no work will actually be performed:

// WARNING: unused `Map` which must be used. Iterators are lazy and do nothing unless consumed!
let v1 = vec![1, 2, 3];
v1.iter().map(|x| x + 1); 

To make this functional, you must chain a consumer like collect() to transform the resulting iterator back into a concrete collection:

#[test]
fn iterator_map_and_collect() {
    let v1: Vec<i32> = vec![1, 2, 3];

    // map() adapts the iterator; collect() consumes it and builds a new Vector
    let v2: Vec<i32> = v1.iter().map(|x| x + 1).collect();

    assert_eq!(v2, vec![2, 3, 4]);
}

6. Practical Application: Filtering Collections with Environment-Capturing Closures

Iterators shine when combined with closures that capture variables from their surrounding environment. A common pattern is using the filter adapter to select specific items from a collection.

The Shoe Filter Implementation

Below, we define a Shoe struct and a function shoes_in_my_size that filters a vector of shoes, returning only those that match a specified size.

#[derive(PartialEq, Debug)]
struct Shoe {
    size: u32,
    style: String,
}

fn shoes_in_my_size(shoes: Vec<Shoe>, shoe_size: u32) -> Vec<Shoe> {
    // into_iter() takes ownership of the vector
    shoes.into_iter()
        // filter() takes a closure returning a boolean
        .filter(|shoe| shoe.size == shoe_size)
        // collect() gathers the matching elements back into a Vec<Shoe>
        .collect()
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn filters_by_size() {
        let shoes = vec![
            Shoe { size: 10, style: String::from("sneaker") },
            Shoe { size: 13, style: String::from("sandal") },
            Shoe { size: 10, style: String::from("boot") },
        ];

        let in_my_size = shoes_in_my_size(shoes, 10);

        assert_eq!(
            in_my_size,
            vec![
                Shoe { size: 10, style: String::from("sneaker") },
                Shoe { size: 10, style: String::from("boot") },
            ]
        );
    }
}

How the Closure Captures the Environment

In the closure |shoe| shoe.size == shoe_size, the variable shoe_size is not defined inside the closure's parameter list. It is captured from the surrounding scope of the shoes_in_my_size function. Rust handles the borrowing and lifetime constraints of this capture automatically.

7. Building a Custom Iterator: The Counter Implementation

To implement your own iterator, you only need to define a struct, implement the Iterator trait for it, and provide a concrete implementation for the next method.

Step-by-Step Implementation

We will build a Counter struct that counts from 1 to 5 and then stops.

struct Counter {
    count: u32,
}

impl Counter {
    // Constructor to initialize count to 0
    fn new() -> Counter {
        Counter { count: 0 }
    }
}

impl Iterator for Counter {
    // Associated type is u32
    type Item = u32;

    fn next(&mut self) -> Option<Self::Item> {
        if self.count < 5 {
            self.count += 1;
            Some(self.count)
        } else {
            None
        }
    }
}

Testing the Custom Iterator Directly

We can verify the behavior of our custom iterator by calling next manually:

#[test]
fn calling_next_directly() {
    let mut counter = Counter::new();

    assert_eq!(counter.next(), Some(1));
    assert_eq!(counter.next(), Some(2));
    assert_eq!(counter.next(), Some(3));
    assert_eq!(counter.next(), Some(4));
    assert_eq!(counter.next(), Some(5));
    assert_eq!(counter.next(), None);
}

8. Advanced Method Chaining: Zipping, Skipping, Mapping, and Filtering

By implementing the Iterator trait, our custom Counter struct automatically gains access to all default methods defined in the standard library. This allows us to construct complex, declarative processing pipelines.

The Pipeline Flow

Consider the following method chain:

Code Implementation

Here is how this pipeline is written in Rust:

#[test]
fn using_other_iterator_trait_methods() {
    let sum: u32 = Counter::new()
        // zip() pairs elements: (1, 2), (2, 3), (3, 4), (4, 5)
        .zip(Counter::new().skip(1))
        // map() multiplies the pairs: 2, 6, 12, 20
        .map(|(a, b)| a * b)
        // filter() keeps only values divisible by 3: 6, 12
        .filter(|x| x % 3 == 0)
        // sum() adds them up: 6 + 12 = 18
        .sum();

    assert_eq!(sum, 18);
}

Step-by-Step Execution Trace

1. Counter::new(): Generates sequence 1, 2, 3, 4, 5.
2. Counter::new().skip(1): Skips the first element, generating sequence 2, 3, 4, 5.
3. zip(...): Pairs the two sequences up to the shortest length.
   • Pair 1: (1, 2)
   • Pair 2: (2, 3)
   • Pair 3: (3, 4)
   • Pair 4: (4, 5)
   • Note: The fifth element 5 from the first counter is dropped because the second counter has finished.
4. map(|(a, b)| a * b):
   • 1 * 2 = 2
   • 2 * 3 = 6
   • 3 * 4 = 12
   • 4 * 5 = 20
5. filter(|x| x % 3 == 0):
   • 2 is discarded.
   • 6 is kept.
   • 12 is kept.
   • 20 is discarded.
6. sum(): Computes 6 + 12 = 18.

Summary and Key Takeaways

• Encapsulation: Iterators decouple traversal logic from the underlying data structure, providing a uniform interface across arrays, maps, graphs, and custom types.
• Laziness: Rust iterators are lazy. They do not perform computations or consume resources until a consumer method (like collect or sum) is called.
• The Iterator Trait: Implementing the trait requires defining an associated type Item and implementing a single method: next(&mut self) -> Option<Self::Item>.
• Iteration Flavors: Use .iter() for immutable references, .iter_mut() for mutable references, and .into_iter() to consume the collection and take ownership of its elements.
• Adapters vs. Consumers: Adapters (e.g., map, filter, zip) return a new iterator, while Consumers (e.g., sum, collect) execute the iterator pipeline and return a final value.
• Environment Capture: Closures used within iterator adapters (like filter) can seamlessly capture variables from their enclosing scope.
• Zero-Cost Abstractions: Rust's compiler optimizes iterator chains down to assembly code that is as fast as, or faster than, manually written loop equivalents. Implementing next on a custom struct automatically grants access to dozens of highly optimized standard library helper methods.