OK, that's not the most mind-blowing title, but in this article, I'll tackle Rust iterators. They are key for writing idiomatic Rust code.
To fully understand the following article, you should have a minimum knowledge of traits, because they are part of the Iterator apparatus, and be aware of the Rust's ownership system.
Iterators are quite simple but sometimes difficult to grab. Specially when it comes to understand the difference between iter() and iter_mut() ad-hoc methods and into_iter() trait method.
Iterators: TL;DR
For those who are in a hurry and just want the essence of Rust iterators.
Iterators
- a Rust iterator is a value (structure, enum, ...) which implements the Iterator trait, which boils down to write the next() method. Once done, the value becomes iterable
- this Iterator::next() method is called either explicitly or under the hood by the for-in construct or by other Iterator trait methods called adapters
-
Iterator::next() returns an Option<T> type:
- if None is returned, iteration stops. If None is never returned, the iterator is infinite
- if Some(T) is returned, iteration continues
- once Iterator::next() is implemented, other trait' methods come for free (e.g.: take())
Adapters
- a Rust iterator adapter (or just an adapter) is a method from the Iterator trait which takes an iterator and returns either another iterator (e.g.: take()), or a single value (e.g: count(), nth(), ...)
- among those methods, collect() is of paramount importance because it converts an iterator into a collection
it's important to note that iterator adapters take their input by value using self as their first parameters, not by reference or mutable reference. This means their input value is moved once used
IntoIterator trait
- this trait defines one method used to transfrom a value into an iterator: into_iter()
- this method consumes self by value:
fn into_iter(self) -> Self::IntoIter;
which means that when used with a value (not a reference), that value is moved and gone forever.
- this method is used implicitly during the for-in construct:
// loop through a vector
let v = vec![0,1,2,3];
// standard loop
for i in v {
// blah blah
}
// this desugars as
let mut iter = IntoIterator::into_iter(v);
loop {
match iter.next() {
Some(i) => {
// blah blah
},
None => break,
}
}
- but can also be used explicitly with adapters:
let v1 = vec![0,1,2,3];
// after that, v1 is moved and not longer accessible
assert_eq!(v1.into_iter().count(), 4);
let mut v2 = vec![0,1,2,3];
// that way, it's possible to re-use v2, but clumsy and not very elegant
assert_eq!((&v2).into_iter().count(), 4);
assert_eq!((&v2).into_iter().nth(1).unwrap(), &1);
assert_eq!((&mut v2).into_iter().nth(1).unwrap(), &mut 1);
Once Iterator is implemented, IntoIterator is automatically implemented.
Rust standard collections
- all Rust standard collections implement into_iter(), but return different types depending on whether it's applied on a reference or a value:
| Variable type | Type returned by into_iter() | Type returned by next() |
|---|---|---|
| Vec<T> | std::iter::IntoIterator<T> | T |
| &Vec<T> | std::slice::Iter<T> | &T |
| &mut Vec<T> | std::slice::IterMut<T> | &mut T |
- to get rid of the previous clumsy syntax, Rust collections usually propose ad-hoc methods iter() to iterate by reference and iter_mut() by mutable reference. This leads to the following cleaner syntax:
// much more elegant and easy to read syntax
assert_eq!(v2.iter().count(), 4);
assert_eq!(v2.iter().nth(1).unwrap(), &1);
assert_eq!(v2.iter_mut().nth(1).unwrap(), &mut 1);
FromIterator trait
The FromIterator trait is used to convert an iterator into a user-defined collection, and called by the Iterator::collect() method.
Implementing your own iterators
Now you've read the overview, it's time to see practical examples on how implementing iterators on your own data structures.
Let's write a Fibonacci sequence which can be infinite or finite depending on how it's created:
// Simplified version of a Fibonacci sequence: F0 and F1 are not returned
// Keep track of n-1 and n values
#[derive(Clone)]
struct Fibonacci {
fib_n_1: u64,
fib_n: u64,
limit: Option<u64>, // maximum Fibonacci number, None if infinite
}
// Fibonacci sequence is well known
impl Fibonacci {
fn new(limit: Option<u64>) -> Fibonacci {
Fibonacci {
fib_n_1: 0,
fib_n: 1,
limit: limit,
}
}
}
Now, we can directly implement the Iterator trait:
// only implements Iterator and not IntoIterator
impl Iterator for Fibonacci {
type Item = u64;
fn next(&mut self) -> Option<Self::Item> {
let next_fib = self.fib_n + self.fib_n_1;
self.fib_n_1 = self.fib_n;
self.fib_n = next_fib;
// infinite sequence?
if self.limit.is_none() {
Some(next_fib)
}
else {
// don't overflow the limit
if next_fib > self.limit.unwrap() {
None
}
// ok we can loop
else {
Some(next_fib)
}
}
}
}
and play and iterate on Fibonacci:
// this is an infinite sequence
let inf_fibo = Fibonacci::new(None);
// we can use adapter on our struct, but as take(), it consumes fibo which is moved and gone. That's why it's cloned
let first_values: Vec<_> = inf_fibo.take(11).collect();
assert_eq!(first_values, vec![1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144]);
// this is an finite sequence
let fin_fibo = Fibonacci::new(Some(100_000));
// our Fibonacci starts from n=2: 24 numbers < 100_000 (from F2 to F26)
assert_eq!(fin_fibo.clone().count(), 24);
// F25 = 75025
assert_eq!(fin_fibo.clone().nth(23).unwrap(), 75025);
// another way, enumerate() yields a tuple
let f25 = fin_fibo.clone().enumerate().nth(23).unwrap();
assert_eq!(f25.0, 23);
assert_eq!(f25.1, 75025);
// F25 is also the last one
assert_eq!(fin_fibo.clone().last().unwrap(), 75025);
// get even Fibonacci numbers
let even_fibo: Vec<_> = fin_fibo.clone().filter(|fib| fib%2 == 0).collect();
assert_eq!(even_fibo, vec![2, 8, 34, 144, 610, 2584, 10946, 46368]);
Now, the previous structure was quite simple and its iterator is consuming its data. How about a user-defined collection?
Let's make a try.
Iterators on user-defined collections
Let's imagine a user-defined collection which splits a phrase into individual words, store those words into a vector:
// a structure holding &str, just a wrapper on &str vector
struct Words<'a> {
words: Vec<&'a str>,
}
// just split input text into invidual words
impl<'a> Words<'a> {
fn new(init: &str) -> Words {
Words {
words: init.split(" ").collect(),
}
}
}
Implementing the Iterator trait makes no sense here because it's only usable once when combined with an adapter. The trick is to implement the IntoIterator trait, which transforms Words into an intermediate structure helper. This latter structure must then implements the Iterator trait to be iterable.
But keep in mind there're 3 implementations to write whether you need to consume collection elements or not: one for a consuming iterator, one for a non-consuming iterator and one for a mutable non-consuming iterator.
First, implement the consuming iterator:
// structure helper for consuming iterator.
struct IntoIteratorHelper<'a> {
iter: ::std::vec::IntoIter<&'a str>,
}
// implement the IntoIterator trait for a consuming iterator. Iteration will
// consume the Words structure
impl<'a> IntoIterator for Words<'a> {
type Item = &'a str;
type IntoIter = IntoIteratorHelper<'a>;
// note that into_iter() is consuming self
fn into_iter(self) -> Self::IntoIter {
IntoIteratorHelper {
iter: self.words.into_iter(),
}
}
}
// now, implements Iterator trait for the helper struct, to be used by adapters
impl<'a> Iterator for IntoIteratorHelper<'a> {
type Item = &'a str;
// just return the str reference
fn next(&mut self) -> Option<Self::Item> {
self.iter.next()
}
}
And now, the non-consuming iterator:
// structure helper for non-consuming iterator.
struct IterHelper<'a> {
iter: ::std::slice::Iter<'a, &'a str>,
}
// implement the IntoIterator trait for a non-consuming iterator. Iteration will
// borrow the Words structure
impl<'a> IntoIterator for &'a Words<'a> {
type Item = &'a &'a str;
type IntoIter = IterHelper<'a>;
// note that into_iter() is consuming self
fn into_iter(self) -> Self::IntoIter {
IterHelper {
iter: self.words.iter(),
}
}
}
// now, implements Iterator trait for the helper struct, to be used by adapters
impl<'a> Iterator for IterHelper<'a> {
type Item = &'a &'a str;
// just return the str reference
fn next(&mut self) -> Option<Self::Item> {
self.iter.next()
}
}
And finally the mutable non-consuming iterator:
// structure helper for mutable non-consuming iterator.
struct IterMutHelper<'a> {
iter: ::std::slice::IterMut<'a, &'a str>,
}
// implement the IntoIterator trait for a mutable non-consuming iterator. Iteration will
// mutably borrow the Words structure
impl<'a> IntoIterator for &'a mut Words<'a> {
type Item = &'a mut &'a str;
type IntoIter = IterMutHelper<'a>;
// note that into_iter() is consuming self
fn into_iter(self) -> Self::IntoIter {
IterMutHelper {
iter: self.words.iter_mut(),
}
}
}
// now, implements Iterator trait for the helper struct, to be used by adapters
impl<'a> Iterator for IterMutHelper<'a> {
type Item = &'a mut &'a str;
// just return the str reference
fn next(&mut self) -> Option<Self::Item> {
self.iter.next()
}
}
We can also implement the FromIterator trait to be fairly comprehensive:
use std::iter::FromIterator;
// implement FromIterator
impl<'a> FromIterator<&'a str> for Words<'a> {
fn from_iter<T>(iter: T) -> Self
where
T: IntoIterator<Item = &'a str> {
// create and return Words structure
Words {
words: iter.into_iter().collect(),
}
}
}
To give the final capstone, we should implement iter() and iter_mut() methods for Words:
// just split input text into invidual words
impl<'a> Words<'a> {
fn iter(&'a self) -> IterHelper<'a> {
self.into_iter()
}
fn iter_mut(&'a mut self) -> IterMutHelper<'a> {
self.into_iter()
}
}
That's a lot of boilerplate code but it can be reduce using ad-hoc macros. I'll tackle Rust macros in another article. Now we can use all the iterator framework on our collection:
let mut uw = Words::new("Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua.");
assert_eq!((&uw).into_iter().count(), 19);
// loop through &uw
for w in &uw {
println!("{}", w);
}
// user iter()
let upper: Vec<_> = uw.iter().map(|w| w.to_uppercase()).collect();
assert_eq!(upper[0], "LOREM");
// we can modify elements now
for w in &mut uw {
println!("{}", w);
}
// FromIterator tryout
let lipsum_short: Words = vec!["Lorem", "ipsum", "dolor", "sit", "amet"].iter().map(|w| *w).collect();
assert_eq!(lipsum_short.words, vec!["Lorem", "ipsum", "dolor", "sit", "amet"]);
Lots of code in this article, but everything compiles with the lastest Rust compiler v1.34.1. Feel free to comment and ask.
Photo by bert sz on Unsplash
Top comments (10)
Hi! I was helped by your post in my stumbling foray into implementing
.zip()on my structs which are basically just wrappers around vectors!Thanks a lot for your insightful post!
It's obvious that I've yet got much to understand on the topic of traits and lifetimes in Rust.
I'm struggling to get my code to work though - I've purposefully only implemented the non-consuming iterators and wrappers, yet I end up with a compile error where my
next(&mut self) -> Option<Self::Item>functions fail becauseself.iter.next()returnsOption<&Self::Item>and notOption<Self::Item>.Is this similar to something you've encountered?
PS: My source code for reference: gitlab.com/x10an14/n-dim-ttt
Hi,
Sorry but I missed your comment. Could you maybe post a link on the Rust playground, if it's not too late ?
This should illustrate my intent =)
It is important for me to be able to use some syntax like
.zip().map().play.rust-lang.org/?version=stable...
Are you sure it's not related to the first error 0658 ?
I dunno, I thought the error message I had was that it ended up in an infinite recursive loop due to somehow making the iterator's next() function refer to itself.
It's unfortunately a bit too long for me to remember.
I know that I get an overflow when I try
at
git checkout 5f7eea2ac51593cf257c62f9a7c25f331ff7226ain my earlier mentioned gitlab git repo.Can you briefly explain why "Implementing the Iterator trait makes no sense here"? I don't get it, what is the conceptual difference from Fibonacci that Words should not be an iterator itself?
Some comments may only be visible to logged-in visitors. Sign in to view all comments.