articles

Any donation is very welcome

Little tour of multiple iterators implementation in Rust

A common issue for Rust newcomers seems to be to actually implement an Iterator. So I decided to write this small blog post in order to look at the basics.

So first, as far as I can tell, there are two types of Iterator:

Iterators over a type

An iterator over a type is simply an iterator which will iterate over a given set of data. It is the most complicated one of the two whereas it isn't that hard to do. Let's take an example:

Let's say you need to wrap a Vec and still want to iterate over the newly created type. First, we need the structure definition:

Runstruct NewType<T>(Vec<T>);

Now, we need to implement the Iterator. The problem is that you can't store a parameter in the actual NewType that will let you know where you are reading into your vector. This is where most people get lost. The solution is actually quite simple:

Run// You can create a new struct which will contain a reference to your set of data.
struct IterNewType<'a, T: 'a> {
    inner: &'a NewType<T>,
    // And there is a position used to know where you are in your iteration.
    pos: usize,
}

// Now you can just implement the `Iterator` trait on your `IterNewType` struct.
impl<'a, T> Iterator for IterNewType<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        if self.pos >= self.inner.0.len() {
            // Obviously, there isn't any more data to read so let's stop here.
            None
        } else {
            // We increment the position of our iterator.
            self.pos += 1;
            // We return the current value pointed by our iterator.
            self.inner.0.get(self.pos - 1)
        }
    }
}

Quite easy right? Now we just need to add the iter method on our NewType struct:

Runimpl<T> NewType<T> {
    fn iter<'a>(&'a self) -> IterNewType<'a, T> {
        IterNewType {
            inner: self,
            pos: 0,
        }
    }
}

And we're good!

A short usage of our class:

Runfor x in NewType(vec![1, 3, 5, 8]).iter() {
    println!("=> {}", x);
}

And it'll display:

=> 1
=> 3
=> 5
=> 8

Generators

This is an interesting and easy thing to do with Rust Iterators. An example is certainly better than an explanation in this case:

Run// Our struct will only iterator over odd numbers.
struct Odd {
    current: usize,
}

// Nothing fancy in here...
impl Odd {
    fn new() -> Odd {
        Odd {
            // The first positive is 1, so let's start at 1.
            current: 1,
        }
    }
}

impl Iterator for Odd {
    type Item = usize;

    fn next(&mut self) -> Option<Self::Item> {
        // We go to the next odd number.
        self.current += 2;
        // We return the current one.
        Some(self.current - 2)
    }
}

fn main() {
    // To avoid the infinite loop we'd have with our `Odd` Iterator, I limited
    // the loop to 3 values.
    for x in Odd::new().take(3) {
        println!("=> {}", x);
    }
}

And it should display:

=> 1
=> 3
=> 5

As you can see, Odd generates its values unlike our previous example which was based on a vector. I made this generator infinite, but it's completely fine to set a limit internally, it's all up to the users.

Conclusion

Iterators in Rust are quite powerful and easy to implement, but newcomers tend to directly handle the data and iterate over it, which generally makes it difficult for them to imagine another solution.

It's all about thinking in Rust or not!

Update: Thanks to @ericfindlay for his review!

Posted on the 09/03/2017 at 01:00