about

06/03/2023

RustBites - Iterators

Rust Bite - Iterators

stepping through collections

Introduction

Rust iterators are types that implement the Iterator trait. That requires them to provide a method:

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

for stepping through collections. The returned value is either Some(item) or None if no more items are available. Iterators always have an associated type: Item, and a number of member functions, shown in Table 2., below.

Many collections implement the IntoIterator trait. That requires them to provide:

into_iter(self) -> Self::IntoIter

where IntoIter is an alias for Iterator<Item = Self::Item>. That call consumes the collection and returns an iterator.

the Item type is a reference to the type of the collection elements. For iterators that are returned from into_iter the collection is consumed and its items are moved out of the Option returned by next(&self).

Functions that accept and return Iterators

In the blocks below are two functions that accept iterators and exercise them. The function on the left uses the iterator directly and retrieves the item with unwrap(). On the right is a function that accepts an IntoIterator and uses a for loop to step through and implicitly unwrap the elements.

Basic Iteration

fn do_iter<T>(iter: &mut T) where T: Iterator + Debug, T::Item: Debug { print!("\n "); loop { let item = iter.next(); if item.is_none() { break; } print!("{:?} ", item.unwrap()); } }

The iterator's function next() returns an Option<Item>.
While there are items it returns Some(item) else None.

Idiomatic iteration

fn do_idiomatic_iter<T>(t:T) where T: IntoIterator, T::Item: Debug { print!("\n "); for item in t { print!("{:?} ", item); } }

Rust for loops are simply wrappers for an
appropriate iterator.

iter() does not consume collection, into_iter() does.

The code below was provided by Matt Brubeck in a reply to a post on users.rust-lang.org.

The block on the left shows how to return an iterator from a custom type. That iterator is simply a rebranding of the Vec member's iterator. The block on the right shows how to implement a custom iterator for a custom type.

Return iterator from custom type

struct MyStruct { items: Vec<String> } impl MyStruct { fn strings(&self) -> impl Iterator<Item = &String> { self.items.iter() } }

Create custom iterator type

struct MyStruct { items: Vec<String> } impl MyStruct { fn strings(&self) -> MyIterator<'_> { MyIterator { index: 0, items: &self.items } } } struct MyIterator<'a> { index: usize, items: &'a [String], } impl<'a> Iterator for MyIterator<'a> { type Item = &'a String; fn next(&mut self) -> Option<&'a String> { let item = self.items.get(self.index); self.index += 1; item } }

Iterating over Collections

Most Rust collections implement at least one of three methods that return iterators:

invoke	operation	signature	returned iterator implements
iter()	Iterates over &T	fn iter(&self) -> Iter<'a, T>	fn next(&self) -> Option<&T>
iter_mut()	Iterates over &mut T	fn iter_mut(&self) -> IterMut<'a, T>	fn next(&mut self) -> Option<&mut T>
into_iter()	Iterates over, consumes T	into_iter(self) -> IntoIterator<T>	fn next(self) -> Option<T>

These functions expect items which all have the same size.

Iterating over Strings

Since types of String and &str contain utf-8 characters, their items may have sizes that vary from 1 to 4 bytes. So their iterators have to search for character boundaries.

Table 1. utf-8 character boundaries

char size	indicator
1 byte, e.g. ASCII	byte starts with bit 0
2 bytes	First byte starts with bits 110
3 bytes	First byte starts with bits 1110
4 bytes	First byte starts with bits 11110
not first byte	byte starts with bits 10

For that reason, instances of std::String and primitive str provide iterators:

chars(&self) -> Chars<'_>
Chars<'_> implements next(&self) -> Option<char>
char_indices(&self) -> CharIndices<'_>
CharIndices<'_> implements next(&self) -> Option<(usize, char)>
bytes(&self) -> Bytes<'_>
Bytes<'_> implements next(&self) -> Option<u8>

The type char is not what String and str hold. The type char consists of 4 bytes which can hold any of the String and str characters. So, a Vec<char> would be expected to usually be up to four times larger than a std::String with the same logical contents.

iterating over ASCII and non-ASCII strings

Iterator Adapters

Iterator adapters are methods that select and/or modify elements of a collection and may then collect them into an instance of a new specified collection type by coping, cloning, or referencing the original collection.

Table 2. - Iterator Methods

Member function	Operation	Note
next(&mut self) -> Option<Self::Item>	Return next element in collection via Option
count(self) -> usize	Returns number of iterations	Terminal, consumes iterator
last(self) -> Option<Self::Item>	Returns last item via Option	Terminal, consumes iterator
nth(&mut self, n: usize) -> Option<Self::Item>	Returns nth element
step-by(self, step: usize) ->StepBy<Self>	Creates new iterator starting at same point, but stepping by given amount at each iteration.	Consumes original iterator
skip(self, n: usize) -> Skip<Self>	Creates an iterator that skips the first n elements	Consumes original iterator
skip_while <P>(self, p: P) -> Skip_while<Self, P> where P: FnMut(&Self::Item) -> bool	Creates an iterator that skips elements if predicate is true. Returns after first false.	Consumes original iterator
take(self, n:usize) -> Take<Self>	Creates an iterator that returns first n elements	Consumes original iterator
find<P>(&mut self, predicate: P) -> Option<Self::Item> where P: FnMut(&Self::Item) -> bool	Searches for first element that satisfies predicate.
enumerate(self) -> Enumerate<Self> <=> Option<(usize, &Item)>	Returns (i, val) where i is current index and val is the value of the current item.	Consumes original iterator
map<B, F>(self, f: F) -> Map<Self, F>	Takes a closure and creates an iterator that calls the closure on each element	Consumes original iterator
filter<P>(self, predicate: P) - > Filter<Self, P> where P: FnMut(&Self::Item) -> bool	Creates an iterator which takes a closure to decide if element should be included in result	Consumes original iterator
collect<B>(self) -> B	Transforms iterator into collection	Terminal, consumes iterator
any<F>(&mut self, f: F) -> bool where F: FnMut(Self::Item) -> bool	Tests if any element of iterator matches a predicate	Terminal
all<F>(&mut self, f: F) -> bool where F: FnMut(Self::Item) -> bool	Tests if every element of iterator matches a predicate	Terminal
for_each<F>(self, f: F) where F: FnMut(Self::Item)	Calls closure on each element of iterator	Terminal, consumes iterator
position<P>(&mut self, p: P) -> Option<usize> where F: FnMut(Self::Item) -> bool	Returns index of first match	Terminal
product<P>(self) -> P where P: Product<Self::Item>	Returns product of all elements, else 1 if empty	Terminal
sum<S>(self) -> S where S: Sum<Self::Item>	Returns sum of all elements, else 0 if empty	Terminal
by_ref(&mut self) -> &mut Self	Supports using these adapters while retaining ownership of the original iterator	Avoids consuming original
copied<'a, T>(self) -> Copied<Self> where Self: Itertor<Item = &'a T>, T: 'a + Copy;	Creates iterator which copies all of its elements	Consumes original iterator
cloned<'a, T>(self) -> Cloned<Self> where Self: Itertor<Item = &'a T>, T: 'a + Clone;	Creates iterator which clones all of its elements	Consumes original iterator

More adapter functions ...	std::iter::Iterator

playground examples of iterator methods

For loops

Rust's for loops are evidently closely related to iterators. The code shown below, taken from Rust keyword for documentation, with minor changes, illustrates that.

for loop code

#![allow(unused)] fn code(i:usize) { print!(" {}", i)} fn main() { let iterator = 0..2; for loop_variable in iterator { code(loop_variable) } }

Output

0 1

code in playground

for loop converts to this code

#![allow(unused)] fn code(i:usize) { print!("{} ", i) } fn main() { let iterator = 0..2; { let mut _iter = std::iter::IntoIterator::into_iter(iterator); loop { match _iter.next() { Some(loop_variable) => { code(loop_variable) }, None => break, } } } }

Output

0 1

code in playground

Rust for loops accept iterators and anything that implements the IntoIterator trait, providing the into_iter() method.

Ranges

A range is an instance of std::ops::Range, e.g.:

Range Definition

pub struct Range<Idx>{ pub start: Idx, pub end: Idx, }

Example:

1..7

with instances start..end, e.g.: 1..7 which includes the values 1, 2, 3, 4, 5, 6.

Ranges implement methods contains and is_empty. They also implement many traits including Iterator and IntoIterator. So for loops can use Ranges directly.

Ranges in playground

Slices

A std::slice is a non-owning view into a contiguous sequence, [T]. It consists of a reference into the sequence and a length

Examples of Slices

let v = vec![1, 2, 3, 4, 5]; let vslice = &v[1..]; let sarray: [&str] = ["zero", "one", "two"]; let aslice: &[&str] = &sarray[0..2]; let bytearr: [u8] = [0, 1, 2]; let bslice = &bytearr;

Slices implement traits: Iter, IterMut, Concat, Join, ...

slice playground code

References

Link	Description
std::iter::Iterator	Documentation for Iterator from the std library
std::iter::IntoIterator	Documentation for IntoIterator from the std library
Iterators in Rust - Thoughtram	Article with clear descriptions and example code
rustomax/rust-iterators	Github readme file with examples of ranges and iterator adapters
Yet Another rust iterators tutorial	Article with clear basics and examples of custom iterators
Rust iterator cheat sheet	Lots of details
keyword for	Rust documentation on for loops
std::ops::Range	Rust documentation for ranges
std::slice	Rust documentation for slices