Iterators

Iterator Trait

Iterators allow you to process a sequence of items. An iterator is any type that implements the Iterator↗ trait. This trait requires only one required method: next(). Iterators are lazy, meaning they don't do any work until you ask for the next item (via next()).

pub trait Iterator {
    type Item;
    fn next(&mut self) -> Option<Self::Item>;
    // ... many other methods ...
}

The next() method returns an Option<Self::Item>. If there is a next item, it returns Some(item), otherwise it returns None.

Use Iterators

There are three common methods, which can create iterators from a collection:

• iter(), which iterates over &T,
• iter_mut(), which iterates over &mut T,
• into_iter(), which iterates over T.

Use iter() when you need to iterate over the elements of a collection without modifying them, iter_mut() when you need to modify them in place, and into_iter() when you want to consume the collection. The latter is often used when you're done with the original collection after iteration or when you want to transfer ownership of the elements. The following table summarizes the use cases:

#![allow(clippy::useless_vec)]
#![allow(clippy::manual_contains)]

/// This example demonstrates the difference between `iter()`, `iter_mut()` and
/// `into_iter()`.
fn main() {
    let vec1 = vec![1, 2, 3];

    // `into_iter()` for `Vec<i32>` yields `i32`.
    // It moves the elements out of the vector,
    // so `vec1` CANNOT be used again.
    println!("`2` exists in `vec1`: {}", vec1.into_iter().any(|x| x == 2));
    // ERROR: println!("{:?}", vec1);

    // `any` above tests if any element of the iterator matches a predicate.

    // Very commonly, you'll use a `for` loop to process each element.
    // A `for` loop operating on a collection calls `into_iter()` implicitly.
    let vec2 = vec![10, 20, 30];
    for x in vec2 {
        // Equivalent to vec2.into_iter()
        print!("{x:?} ");
    }
    println!();

    // `iter()` for `Vec<i32>` yields `&i32`.
    let vec3 = vec![42, 43, 44];
    println!("`42` exists in `vec3`: {}", vec3.iter().any(|&x| x == 42));

    // `iter()` only borrows `vec1` and its elements,
    // so they can be used again.
    for x in &vec3 {
        // Calls `iter()` under the covers.
        print!("{x:?} ");
    }
    println!();

    // You can modify values of a collection through the mutable reference
    // provided by `iter_mut()`.
    // Note that the vector has to be `mut`.
    let mut vec4 = vec![4, 5, 6];
    for x in vec4.iter_mut() {
        *x *= 2;
    }
    println!("The modified vector is: {vec4:?}");
}

Create Basic Iterators from Values and Closures

The std::iter↗ module in the standard library provide a number of functions to create basic iterators from values or closures:

use std::iter;

fn main() {
    // Creates an iterator that yields nothing.
    let mut empty_iter = iter::empty::<i32>();
    assert_eq!(empty_iter.next(), None);

    // Creates an iterator that yields an element exactly once.
    let mut once_iter = iter::once("hello");
    assert_eq!(once_iter.next(), Some("hello"));
    assert_eq!(once_iter.next(), None);

    // Creates an iterator that lazily generates a value exactly once by
    // invoking the provided closure.
    let mut once_with_iter = iter::once_with(|| "world");
    assert_eq!(once_with_iter.next(), Some("world"));
    assert_eq!(once_with_iter.next(), None);

    // Creates a new iterator that endlessly repeats a single element.
    #[allow(clippy::manual_repeat_n)]
    let mut repeat_iter = iter::repeat(5).take(2); // Only take 2 elements of the infinite sequence.
    assert_eq!(repeat_iter.next(), Some(5));
    assert_eq!(repeat_iter.next(), Some(5));
    assert_eq!(repeat_iter.next(), None);

    // Creates a new iterator that repeats a single element a given number of
    // times.
    let mut repeat_n_iter = iter::repeat_n('a', 2);
    assert_eq!(repeat_n_iter.next(), Some('a'));
    assert_eq!(repeat_n_iter.next(), Some('a'));
    assert_eq!(repeat_n_iter.next(), None);

    // Creates a new iterator that repeats elements of type A endlessly by
    // applying the provided closure,
    let mut count = 0;
    let mut repeat_with_iter = iter::repeat_with(|| {
        count += 1;
        count * 2
    });
    assert_eq!(repeat_with_iter.next(), Some(2));
    assert_eq!(repeat_with_iter.next(), Some(4));
    assert_eq!(repeat_with_iter.next(), Some(6));

    // Creates an iterator with the provided closure.
    let mut counter = 0;
    let mut from_fn_iter = iter::from_fn(move || {
        if counter < 2 {
            counter += 1;
            Some(counter)
        } else {
            None
        }
    });
    assert_eq!(from_fn_iter.next(), Some(1));
    assert_eq!(from_fn_iter.next(), Some(2));
    assert_eq!(from_fn_iter.next(), None);

    // Creates a new iterator where each successive item is computed based on
    // the preceding one.
    let mut successors_iter =
        iter::successors(Some(1), |n| Some(n * 2)).take(3);
    assert_eq!(successors_iter.next(), Some(1));
    assert_eq!(successors_iter.next(), Some(2));
    assert_eq!(successors_iter.next(), Some(4));
    assert_eq!(successors_iter.next(), None);

    // Converts the arguments to iterators and zips them.
    let a = [1, 2, 3];
    let b = ['a', 'b'];
    let mut zip_iter = iter::zip(a, b);
    assert_eq!(zip_iter.next(), Some((1, 'a')));
    assert_eq!(zip_iter.next(), Some((2, 'b')));
    assert_eq!(zip_iter.next(), None);
}

Use Iterator Adapters to Transform a Collection

Iterators are composable: it's very common to chain them together to do more complex forms of processing.

Functions which take an Iterator↗ as input and return another Iterator are often called "iterator adapters". Common iterator adapters include map, take, and filter:

fn main() {
    let numbers = [1, 2, 3];

    // `map` applies a closure to each element, producing a new iterator.
    // `collect` transforms the iterator back into a collection. It is required,
    // because iterators are lazy.
    let doubled: Vec<_> = numbers.iter().map(|x| x * 2).collect();
    println!("Doubled numbers: {doubled:?}"); // Output: Doubled numbers: [2, 4, 6]

    // `filter` keeps elements that satisfy a predicate (a closure that returns
    // a boolean).
    let even: Vec<_> = numbers.iter().filter(|x| *x % 2 == 0).collect();
    println!("Even numbers: {even:?}"); // Output: Even numbers: [2]

    // `take` takes the first `n` elements of an iterator.
    let first_two: Vec<_> = numbers.iter().take(2).collect();
    println!("First two: {first_two:?}"); // Output: First two: [1, 2]

    // `skip` skips the first `n` elements of an iterator.
    let after_two: Vec<_> = numbers.iter().skip(2).collect();
    println!("After skipping two: {after_two:?}"); // Output: After skipping two: [3]

    // `chain` concatenates two iterators.
    let more_numbers = [4, 5];
    let combined: Vec<_> = numbers.iter().chain(more_numbers.iter()).collect();
    println!("Combined two vectors: {combined:?}");

    // `zip` combines two iterators element-wise into pairs.
    let letters = ['a', 'b', 'c'];
    let zipped: Vec<_> = numbers.iter().zip(letters.iter()).collect();
    println!("Zipped numbers and letters: {zipped:?}"); // Output: Zipped numbers and letters: [(1, 'a'), (2, 'b'), (3, 'c')]

    // `enumerate` adds an index to each element.
    let indexed: Vec<_> = numbers.iter().enumerate().collect();
    println!("Indexed numbers: {indexed:?}"); // Output: Indexed numbers: [(0, 1), (1, 2), (2, 3)]

    // Chain multiple adapters together.
    let even_doubled: Vec<_> = numbers
        .iter()
        .filter(|x| *x % 2 == 0)
        .map(|x| x * 2)
        .collect();
    println!("Even numbers doubled: {even_doubled:?}"); // Output: Even numbers doubled: [4, 8]
}

Return an Iterator from a Function or Method

The impl SomeTrait notation refers to an opaque type that implements a trait; it is only allowed in arguments and return types of functions and methods.

Iterator types produced by a chain of calls to iterator adapters (map, take, filter, etc.) can be quite complex and hard to write. It is therefore common to use impl Iterator<Item = T> as the return type for functions or methods that return an iterator.

Advantageously, this also allows changing the implementation of the iterator within the function without breaking the calling code.

/// Return an iterator from a function using the `impl Iterator<Item = T>`
/// syntax as the return type, where `T` is the type of the items the iterator
/// will yield.
fn count_up_to(max: i32) -> impl Iterator<Item = i32> {
    // In this case, we convert a range into an iterator,
    // then transform it further.
    (0..max).map(|x| x + 1)
}
// You could also return a boxed trait object e.g.,
// `Box<dyn Iterator<Item = T>>`.

fn main() {
    let my_iterator = count_up_to(5);

    for number in my_iterator {
        println!("{number}");
    }
}

Accept Various Iterable Types as the Input of a Function or Method

Many collection types in Rust implement IntoIterator↗, which provides a method into_iter() that returns an iterator.

It is common to use IntoIterator as a trait bound for function parameters. This allows the input collection type to change.

/// This function demonstrates the use of `IntoIterator` as a trait bound,
/// allowing it to accept various iterators or iterable types (like vectors,
/// arrays, and ranges) and compute the sum of their elements.
/// Note that all Iterators implement `IntoIterator` by just returning
/// themselves.
fn sum_all<I>(iterable: I) -> i32
where
    I: IntoIterator<Item = i32>,
    // Additional bounds can be specified by restricting on `Item`.
{
    let mut sum = 0;
    for item in iterable.into_iter() {
        sum += item;
    }
    sum
}

fn main() {
    let numbers_vec = vec![1, 2, 3, 4, 5];
    let numbers_array = [10, 20, 30];

    println!("Sum of vector: {}", sum_all(numbers_vec)); // Output: Sum of vector: 15.
    println!("Sum of array: {}", sum_all(numbers_array)); // Output: Sum of array: 60.
    println!("Sum of range: {}", sum_all(0..5)); // Output: Sum of range: 10.
    println!("Sum of iterator: {}", sum_all(std::iter::repeat_n(5, 2))); // Output: Sum of iterator: 10.
}

Make a Collection Iterable by Implementing IntoIterator

You may define how a (collection) type is iterated by implementing the IntoIterator trait.

One benefit of implementing IntoIterator is that your type will work with the for loop syntax.

//! Example of `IntoIterator` implementation.
//!
//! Note that the iterator is a custom `struct` separate from the collection
//! type.

/// A custom collection type.
/// In this example, we simply wrap a `Vec`.
#[derive(Debug)]
struct MyVec<T> {
    data: Vec<T>,
}

impl<T> MyVec<T> {
    /// Constructor.
    fn new() -> Self {
        MyVec { data: Vec::new() }
    }

    fn push(&mut self, item: T) {
        self.data.push(item);
    }
}

/// Implementation of `IntoIterator`.
impl<T> IntoIterator for MyVec<T> {
    /// Associated type for the iterator.
    type IntoIter = MyVecIntoIterator<T>;
    /// Type of the elements that the iterator will yield.
    type Item = T;

    /// The `into_iter` method takes `self` by value,
    /// meaning it consumes the collection.
    fn into_iter(self) -> Self::IntoIter {
        MyVecIntoIterator { data: self.data }
    }
}

/// The iterator type for the custom collection.
/// It must implement the `Iterator` trait.
#[derive(Debug)]
struct MyVecIntoIterator<T> {
    data: Vec<T>,
    // Iterator types often store indices to track the progress of the
    // iteration. This is not necessary in this simple example.
}

impl<T> Iterator for MyVecIntoIterator<T> {
    type Item = T;

    /// The core iterator method.
    fn next(&mut self) -> Option<Self::Item> {
        if !self.data.is_empty() {
            // In this example, we use `remove` for simplicity, noting that its
            // complexity is O(n). `remove` takes the item at a given
            // position and returns it to us, giving up the ownership.
            // We use `0` to return the first element.
            Some(self.data.remove(0))
            // We could use `pop` to remove the last element instead.
        } else {
            None
        }
    }
    // `next()` is the only method we are required to implement.
    // The `Iterator` trait implements a large number of default methods, which
    // we get for free.
}

fn main() {
    let mut my_vec = MyVec::new();
    my_vec.push(1);
    my_vec.push(2);

    // Our custom collection can now be used in a `for` loop.
    // The `for` loop calls `into_iter()` under the covers.
    for element in my_vec {
        println!("Element: {element}");
    }
}

References

• Iterators↗.
• What is the correct way to return an Iterator (or any other trait)?↗.
• Implementing Iterator and IntoIterator in Rust↗.

Related Topics

• Closures.
• Data Structures.
• Functional Programming.
• Rust Patterns.
• Vectors.