Design Patterns in Rust: Easy container traversing using the Iterator

Introduction

In Design Patterns, the Iterator is a way of traversing over a container, that is access each of the container’s elements. It is used as a convenient way to traverse over lists or arrays, but it could also be used to traverse over binary trees for example.

It looks like this:

A bit of explanation:

1. An iterator basically has two methods: next() and hasNext()
2. The next() method returns the next element in the container
3. The hasNext() method returns a bool, true if a next element is available, false if there is no next element

Implementation in Rust

To demonstrate this pattern I will build an iterator that will just yield even numbers up to a certain user-defined limit.

In an empty directory type:

cargo new rustiterator
cd rustiterator

Now open your favourite IDE in this directory and edit the ‘main.rs’ file.

We will start by defining the EvenNumberGenerator struct:

struct EvenNumberGenerator {
    current: u64,
    limit: u64,
}

This defines two fields:

• current: this is the current ‘element’ we are processing
• limit: since we want to limit the number of elements yielded by the iterator, this defines the limit.

We define a constructor like method for this struct:

impl EvenNumberGenerator {
    fn new(limit: u64) -> Self {
        Self { current: 0, limit }
    }
}

Some notes:

• We just pass the limit, since we will always start at 0, for the purposes of this example

The Iterator trait implementation

In order to iterate over this virtual container, we need to implement the Iterator trait:

impl Iterator for EvenNumberGenerator {
    type Item = u64;

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

A short explanation:

1. We define the Item type as u64 (that is also used in the EvenNumberGenerator)
2. The next() method returns Some(u64) if there is a next element in the container, that is if current is smaller than limit. Otherwise None is returned, which signals the Iterator-client, like a for-loop, that there are no more elements. That is why we do not need a hasNext() method here.

The IntoIterator trait implementation

This trait defines how an object can be converted into an iterator. Before we can do that, we need to define an EvenNumberIterable as a wrapper for EvenNumberGenerator and it provides an iterable interface:

struct EvenNumberIterable(EvenNumberGenerator);

All this struct is, is wrap an EvenNumberGenerator in another struct. Now we can implement the IntoIterator trait on this struct:

impl IntoIterator for EvenNumberIterable {
    type Item = u64;
    type IntoIter = EvenNumberGenerator;

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

This certainly needs some explanation:

1. The Item definition defines the type returned by the iterator
2. IntoIter defines the type of the Iterator
3. The into_iter() method returns the iterator. The self.0 means that refer to the first field defined in the struct, i.e. a field of type EvenNumberGenerator

Time to test

We can test it now:

fn main() {
    let even_numbers = EvenNumberGenerator::new(100);
    for number in even_numbers {
        println!("{}", number);
    }
}

Line by line:

1. We construct an EvenNumberGenerator with a limit of 100.
2. We then iterator over this object, and print out the numbers. Notice that we do this in exactly the same way as if even_numbers were a Vec<u64>. That is the power of iterators in Rust, because they can become quite transparent.

Conclusion

Implementing iterators in Rust is not entirely straightforward. However, once you have implemented them, their integration in the language is transparent, and makes using them easy and elegant.

Perhaps in a later post I will try a more complicated example. Let me know in the comments whether you would like to see that (perhaps with some suggestions)