Skip to content
Smörgåsbord

Iterators

Iterators represent design patterns that handle the logic of iterating over some sequence of elements. Rust provides a set of iterators as part of its “zero-cost abstraction” set, meaning that the overhead of using iterators is minimal or optimized away by the compiler. For example, some “consuming adapters” provided by the standard library are just as efficient, if not more so, than using for loops.

The Iterator Design Pattern

The iterator design pattern involves iterator methods that take iterable objects to produce iterator types that are consumed by some iteration mechanism. This pattern can be illustrated by a rather simple if not contrived example.

1    let v = vec![1, 2, 3, 4];
2    let i = v.iter();
3    let total: i32 = i.sum();
4    assert_eq!(total, 10)

Line 1 introduces the iterable object as a vector bound to v. Vector is a standard collection type whose objects are considered iterable (for reasons discussed later). Line 2 combines an iterator method iter() with the iterable object v to produce an iterator expression. The iterator expression returns an iterator type and binds it to i. Line 3 uses the consuming adapter sum() on the iterator i and binds the resulting value to total. Line 4 proves that some magic happened. Go ahead, test it and see, I’ll wait (he lied, lyingly).

Creating iterators

Each iterable type defines its own iterator methods, that is each iterable type must contain methods that return iterator objects. This means that there is no single universal iterator method that works for all iterable types. By convention Rust uses three method names to create iterators for specific ownership and mutability patterns from each of its standard collection types (besides tuples).

  • iter(): Returns an iterator that yields immutable references to values in the original collection by consuming &T types; This method allows for iterating over the collection without modifying its contents

  • iter_mut(): Returns an iterator that yields mutable references to values in the original collection by consuming &mut T types; This method allows for iterating over the collection and modifying its contents

  • into_iter(): Returns an iterator of owned, immutable values by consuming (owned) T types; Consumes the collection and transfers ownership of its elements to the iterator; This leaves the original collection invalid after calling into_iter()

Rust’s collection types provide implementations of the Iterator and/or IntoIterator traits to create iterator types out-of-the-box. The Vector type is a perfect example of this. You can call iter(), iter_mut(), or into_iter() on Vector types without any implementation.

Using iterators

An iterator is any type that implements the Iterator trait. Implementation is discussed in further detail later on. For now, just know that the Iterator trait has one required method called next() and one required associated type called Item. The next() method represents the heart of the entire design pattern. The next() method returns Option<Self::Item> so that calling next() produces the next element in the iteration. The iteration process yields Some(item) until there are no more items in the collection. Using iterators means that you will never run into an out-of-bounds error operating on a collection.

Iterators (iterator objects) are considered lazy because you must call their next() method to yield the values of their iterable objects. This means that when you create an iterator from a collection, such as a vector, an array, or even a poorly implemented custom linked list type, the iterator does not immediately compute or process all the items. Instead, it waits until you request the next() item before computing it. This lazy evaluation improves efficiency by avoiding unnecessary computation.

To call the next() method and get the values of the underlying iterable objects, you can use iterators with either consuming adapters or constructs. Consuming adapters are methods that consume the iterator and return a value or often another iterator. The sum() method that appears in the initial code example is an example of a consuming adapter that returns a value of a specified integer type. Consuming adapters are described in more detail in the Iterator Adapter section below. Constructs, such for, if let, while let, and match also take iterators. In fact the for loop is probably the most common place you’ll encounter iterators, at least at first.

The for loop construct is actually just syntax sugar for types that implement the Iterator trait. Under the hood, for loops just call the iterator’s next() method until it gets a None value.

    // Simple for loop
    let values = vec![1, 2, 3, 4, 5];
    for element in values.into_iter() {
        println!("{}", element)
    }


    // The same loop de-sugared
    let values = vec![1, 2, 3, 4, 5];
    {
        let result = match IntoIterator::into_iter(values) {
            mut iter => loop {
                let next;
                match iter.next() {
                    Some(val) => next = val,
                    None => break,
                };
                let x = next;
                let () = { println!("{x}"); };
            },
        };
        result
    }

Now that you know how they work its time to look at some examples of iterators in action.

This example illustrates using the iter() method defined on Vec<T> for i32 type values. The iterator produces immutable references to each element in the iterable object. The body of the for loop squares the references and pushes the product to a separate, mutable vector y.

    let x = vec![1i32, 2, 3];
    let mut y: Vec<i32> = vec![];
    for val in x.iter() {
        y.push(val * val)
    }
    assert_eq!(y, [1, 4, 9]);

This example illustrates using the iter_mut() method defined on Vec<T> for i32 type values. The iterator produces mutable references to the mutable, iterable object v. The body of the for loop dereferences each mutable reference and multiplies it by a similarly dereferenced value to square the element it in place. Remember that in Rust the iterator value, shown here as element, is dictated by the return type of the iterator expression. This example operation requires the iter_mut() method in the iterator expression to ensure that the iterator value element is mutable.

    let mut v: Vec<i32> = vec![1, 2, 3];
    for element in v.iter_mut() {
        *element *= *element
    }
    assert_eq!(vec, [1, 4, 9])

See the for loop section of the Control Flow documentation for more examples.

Implementing Iterators

There may be situations in which you need to make a custom type iteratble. A linked list is a perfect example. In a linked list you need to be able to iterate through the nodes for various operations.

Iterator Adapters

There are 70+ methods defined for the Iterator trait. These methods are considered iterator adapters. Adapters consist of consuming and non-consuming type methods. As the classification implies, some consume the iterator object, and some simply transform it.

Consuming adapters

The next() method is only one of 70+ methods defined for Iterator. Many of these methods are called consuming adapters, which is a term that isn’t specific to Iterators, but most commonly associated with them. Each consuming adapter calls the next() method, thus consuming the iterator. For example, the sum() method calls the next() method and consumes the iterator to produce a sum of the elements in a set.

    let v = vec![1, 2, 3];
    let v_iter: i32 = v.iter().sum();
    assert_eq!(v_iter, 6);

Popular consuming adapters include:

  • collect()
  • fold()
  • for_each()
  • find()
  • position()
  • any()/all()
  • max()/min().

Non-consuming adapters

Non-consuming iterator adapters, similar to consuming adapters, are methods defined on the Iterator trait. Non-consuming adapters, as the name implies, do not consume the iterator object. Instead, they simply adapt the iterator object, mostly for consumption. Eventually the iterator object needs to be consumed by some other mechanism.

Take the non-consuming adapter method map(). This method takes a closure and returns an iterator object. The closure is applied to each member of the set. The resultant iterator object can be consumed with the consuming-type adaptercollect() method (defined on the Iterator trait). This example uses the placeholder _ for the output of the consumed iterator, but we can also define this as Vec<i32>.

    let v: Vec<i32> = vec![1, 2, 3];
    let v_sq: Vec<_> = v.iter().map(|x| x * x).collect();
    assert_eq!(v_sq, [1, 4, 9])

Popular non-consuming adapters include:

  • map()

  • filter()/filter_map()

  • take()/skip()

  • enumerate()

  • peekable()

  • rev()

  • zip()

  • flat_map()

  • take_while()/skip_while()

  • cycle()

  • enumerate() - Returns an iterator that yields pairs (i, val), where i is the current index of iteration and val is the value at the index.

    pub fn for_loops_2() {
        let v = vec!['a', 'b', 'c'];
        for (e, val) in v.iter().enumerate() {
            println!("Index {} holds {}", e, val)
        }
    }
Index 0 holds a
Index 1 holds b
Index 2 holds c

The IntoIterator Trait

The IntoIterator trait has two associated types and one required method. These elements define how to convert the type into an iterator.

pub trait IntoIterator {
    type Item;
    type IntoIter: Iterator<Item = Self::Item>;


    // Required method
    fn into_iter(self) -> Self::IntoIter;
}

Rust’s vector type is a great example of a collection type that implements all three of the iterator method conventions. This is done by implementing IntoIterator three different ways to define different ownership and mutability models. This is what makes a vector object iterable as &T, &mut T, and T.

// IntoIterator implementation on Vec<T>


impl<'a, T, A> IntoIterator for &'a Vec<T, A>
where
    A: Allocator,
type Item = &'a T // Defines an immutable reference type
type IntoIter = Iter<'a, T>
fn into_iter(self) -> <&'a Vec<T, A> as IntoIterator>::IntoIter // Returns an iterator over immutable references


impl<'a, T, A> IntoIterator for &'a mut Vec<T, A>
where
    A: Allocator,
type Item = &'a mut T // Defines a mutable reference type
type IntoIter = IterMut<'a, T>
fn into_iter(self) -> <&'a mut Vec<T, A> as IntoIterator>::IntoIter // Returns an iterator over mutable references


impl<T, A> IntoIterator for Vec<T, A>
where
    A: Allocator,
source
fn into_iter(self) -> <Vec<T, A> as IntoIterator>::IntoIter
type Item = T // Defines an owned type
type IntoIter = IntoIter<T, A> // Returns an iterator over owned values

The Iterator Trait

The Iterator trait has only one abstract (undefined or implemented) method named next(). The next() method requires the Item type to be defined. See the Traits section for more information on implementation and trait type. This ultimately means that whatever we’re iterating over must be declared.

Any type that implements the Iterator trait must define the next() method for the trait. The next() method is the only method for the Iterator trait that does not have a concrete definition and thus must be defined when implementing the trait.

pub trait Iterator {
    type Item;


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


    [...and 75 other methods]
}

The implementation can have whatever logic we want, but it must return the Item type. For example, we can implement the Iterator trait on a custom type named Counter and define the next() method to cycle through sets one at a time.

impl Iterator for Counter {
    // we will be counting with usize
    type Item = usize;


    // next() is the only required method
    fn next(&mut self) -> Option<Self::Item> {
        // Increment our count. This is why we started at zero.
        self.count += 1;


        // Check to see if we've finished counting or not.
        if self.count < 6 {
            Some(self.count)
        } else {
            None
        }
    }
}