Iterators

The `Iterator` and `IntoIterator` Traits

Term: An iterator is any value that implements the std::iter::Iterator trait. Put simply, an iterator is value that produces a sequence of values.

Term: The values an iterator produces are called items.

Term: The code that receives an iterator's items is called a consumer.

The heart of the Iterator trait is defined as:


#![allow(unused)]
fn main() {
trait Iterator {
    type Item; // the type of value the iterator produces
    fn next(&mut self) -> Option<Self::Item>;

    // ... a whole bunch of default methods
}
}

If there's a natural way to iterator over some type, it can implement std::iter::IntoIterator, whose into_iter method takes a value and returns an iterator over it:


#![allow(unused)]
fn main() {
trait IntoIterator where Self::IntoIter::Item == Self::Item {
    type Item; // the type of value the iterator produces
    type IntoIter: Iterator; // the type of the iterator value itself
    fn into_iter(self) -> Self::IntoIter;
}
}

Term: Any type that implements std::iter::IntoIterator is called an iterable.

Under the hood, every for loop is just shorthand for calls to IntoIterator and Iterator methods:


#![allow(unused)]
fn main() {
let elems = vec!["antimony", "arsenic", "aluminum", "selenium"];

// Iteration using a for loop..
println!("There's:");
for element in &elems {
    println!("- {}", element);
}

// Is actually just...
println!("Again! There's:");
let mut iterator = (&elems).into_iter();
while let Some(element) = iterator.next() {
    println!("- {}", element);
}
}

Implicit Behavior: All iterators automatically implement IntoIterator, with an into_iter method that simply returns the iterator.

Most collection types provide iter and iter_mut methods that return the natural iterators over the type, producing a shared or mutable reference to each item. The same applies to slices like &[T] and &str too.

`IntoIterator` Implementations

There are three main implementations of IntoIterator.

1. Shared Reference

Idiom: Given a shared reference to a collection, into_iter returns an iterator that produces shared references to its items.


#![allow(unused)]
fn main() {
for element in &collection { ... }
}

2. Mutable Reference

Idiom: Given a mutable reference to a collection, into_iter returns an iterator that produces mutable references to the items.


#![allow(unused)]
fn main() {
for element in &mut collection { ... }
}

3. By Value

Idiom: When passed a collection by value, into_iter returns an iterator that takes ownership of the collection and returns items by value; the items' ownership moves from the collection to the consumer, and the original collection is consumed in the process.
#![allow(unused)]
fn main() {
for element in collection { ... }
}

Not every type provides all three iterator implementations.

Slices implement two of the three IntoIterator variants; since they don't own their elements, there is no "by value" case.

Use Case: IntoIterator can be useful in generic code: you can use a bound like T: IntoIterator to restrict the tyep variable T to types that can be iterator over. Or, you can write T: IntoIterator<Item=U> to further require the iteration to produce a particular type U. For instance, we can create a dump function that receives an iterable whose items implement the Debug trait:


#![allow(unused)]
fn main() {
use std::fmt::Debug;

fn dump<T, U>(t: T) where T: IntoIterator<Item=U>, U: Debug {
    for u in t {
        println!("{:?}", u);
    }
}
dump(vec!["garbage", "rubbish", "waste"]);
}

`drain` Methods

A lot of collection types provide a drain method that takes a mutable reference to the collection and returns an iterator that passes ownership of each element to the consumer.


#![allow(unused)]
fn main() {
use std::iter::FromIterator;

let mut outer = "Earth".to_string();
let inner = String::from_iter(outer.drain(1..4));

println!("outer: {}", outer);
println!("inner: {}", inner);
}

If you need to drain an entire sequence, use the full range, .., as the argument.

Other Iterator Sources

Go here.

Iterator Adapters

Term: Given an iterator, the Iterator trait provides a huge selection of methods called adapters that consume one iterator and build a new one.

`map` and `filter`

A map iterator passes each item to its closure by value, and in turn, passes along ownership of the closure's result to its consumer.

A filter iterator passes each item to its closure by shared reference, retaining ownership in case the item is selected to be passed on to its consumer.

Concept: Calling an adapter on an iterator doesn't consume any items; it just returns a new iterator. The only way to actually get values is to call next (or some other indirect method, like collect, in which case no work takes place until collect starts calling next) on the iterator.

`filter_map` and `flat_map`

The filter_map adapter is similar to map, except that it lets its closure either transform the item into a new item or drop the item from the iteration. Thus, it's a bit like a combination of filter and map.

Use Case: The filter_map adapter is best in situations when the best way to decide whether to include an item in the iteration is to actually try to process it.

The flat_map iterator produces the concatenation of the sequences the closure returns.

`scan`

The scan adapter resembles map, except that the closure is given a mutable value it can consult, and has the option of terminating the iteration early. The closure must return an Option, which the scan iterator takes as its next item.

`take` and `take_while`

The Iterator trait's take and take_while adapters let you end an iteration after a certain number of items, or when a closure decides to cut things off.

Both take and take_while take ownership of an iterator and return a new iterator that passes along items from the first one, possible ending the sequence earlier.

`skip` and `skip_while`

The Iterator trait's skip and skip_while methods are the complement of take and take_while: they drop a certain number of items from the beginning of an iteration, or drop items until a closure finds one acceptable, and then pass the remaining items through unchanged.

Use Case: One common use for skip is to skip the command name when iterating over a programs command-line arguments:


#![allow(unused)]
fn main() {
for arg in std::end::args().skip(1) {
    println!("arg: {}", arg);
}
}

`peekable`

A peekable iterator lets you peek at the next item that will be produced without actually consuming it. Almost any iterator can be turned into a peekable iterator by calling the Iterator trait's peekable method.

Calling peek tries to draw the next item from the underlying iterator, and if there is one, caches it until the next call to next.

Use Case: Peekable iterators are essential when you can't decide how many items to consume from an iterator until you've gone too far. For example, if you're parsing numbers from a stream of characters, you can't decide where the number ends until you've seen the first non-number character:


#![allow(unused)]
fn main() {
use std::iter::Peekable;

fn parse_number<I>(tokens: &mut Peekable<I>) -> u32
    where I: Iterator<Item=char>
{
    let mut n = 0;
    loop {
        match tokens.peek() {
            Some(r) if r.is_digit(10) => {
                n = n * 10 + r.to_digit(10).unwrap();
            }
            _ => return n
        }
        tokens.next();
    }
}

let mut chars = "10212980".chars().peekable();
println!("{}", parse_number(&mut chars));
}

`fuse`

The fuse adapter takes any iterator and turns it into one that will definitely continue to return None once it has done so the first time.

Use Case: The fuse adapter is most useful in generic code that needs to work with iterators of an uncertain origin.

Reversible Iterators and `rev`

Some iterators are able to draw items from both ends of the sequence. You can reverse these iterators by using the rev adapter.

Most iterator adapters, if applied to a reversible iterator, return another reversible iterator.

`inspect`

The inspect adapter is handy for debugging pipelines of iterator adapters, but is rarely used in production code. It applies a closure to a shared reference to each item, and then passes the item through. The closure can't affect the items, but it can do things like print them or make assertions about them.

`chain`

The chain adapter appends one iterator to another (think of the concat operator in RxJS). A chain iterator keeps track of whether each of the two underlying iterators has return None, and directs next and next_back calls to one or the other as appropriate.


#![allow(unused)]
fn main() {
let v: Vec<_> = (1..4).chain(4..6).collect();
println!("{:?}", v);
}

`enumerate`

The Iterator trait's enumerate adapter attaches a running index to the sequence, taking an iterator that produces items A, B, C, ... and returning an iterator that produces pairs (0, A), (1, B), (2, C), ....

`zip`

The zip adapter combines two iterators into a single iterator that produces pairs holding one value from each iterator. The zipped iterator ends when either of the two underlying iterators ends.

`by_ref`

An iterator's by_ref method borrows a mutable reference to the iterator, so that you can apply adaptors to the reference. When you're done consuming items from these adaptors, you drop them, the borrow ends, and you regain access to the original iterator.

by_ref essentially provides a mechanism for starting and stopping iterators as needed.

Concept: When you call an adapter on a mutable reference to an iterator, the adapter takes ownership of the reference, not the iterator itself.

`cloned`

The cloned adapter takes an iterator that produces references, and returns an iterator that produces values cloned from those references.

`cycle`

The cycle adapter returns an iterator that endlessly repeats the sequence produced by the underlying iterator. The underlying iterator must implement std::clone::Clone, so that cycle can save its initial state and reuse it each time the cycle starts again.


#![allow(unused)]
fn main() {
use std::iter::{once, repeat};

let fizzes = repeat("").take(2).chain(once("fizz")).cycle();
let buzzes = repeat("").take(4).chain(once("buzz")).cycle();
let fizzes_buzzes = fizzes.zip(buzzes);

let fizz_buzz = (1..100).zip(fizzes_buzzes)
    .map(|tuple|
        match tuple {
            (i, ("", "")) => i.to_string(),
            (_, (fizz, buzz)) => format!("{}{}", fizz, buzz)
        }
    );

for line in fizz_buzz {
    println!("{}", line);
}
}

Consuming Iterators

Simple Accumulation: `count`, `sum`, `product`

The count method draws items from an iterator until it returns None, and tells you how many it got.

The sum and product methods compute the sum or product of the iterator's items, which must be integers or floating-point numbers.

`max`, `min`

The max and min methods on Iterator return the least or greatest item the iterator produces. The iterator's item type must implement std::cmp::Ord, so that items can be compared with each other.

An implication of the Ord bound is that these methods can't be used with floating-point values.

`max_by`, `min_by`

The max_by and min_by methods return the maximum or minimum item an iterator produces, as determined by a comparator function you provide.

`max_by_key`, `min_by_key`

The max_by_key and min_by_key methods on Iterator let you select the maximum or minimum item as determined by a closure applied to each item.

Comparing Item Sequences

`any` and `all`

The any and all methods apply a closure to each item the iterator produces, and return true if the closure returns true for any or all items, respectively.

These methods consume only as many items as they need to determine the answer.

`position`, `rposition`, and `ExactSizeIterator`

The position method applies a closure to each item from the iterator and returns the index of the first item for which the closure returns true as an Option<bool>.

The rposition methods does the same thing but in reverse.

Term: An exact-size iterator is one that implements the std::iter::ExactSizeIterator trait:


#![allow(unused)]
fn main() {
trait ExactSizeIterator: Iterator {
    fn len(&self) -> usize { ... }
    fn is_empty(&self) -> bool { ... }
}
}

`fold`

The fold method is a very general tool for accumulating some sort of result over the entire sequence of items an iterator produces.

`nth`

The nth method takes an index n, skips that many items from the iterator, and returns the next item, or None if the sequence ends before that point.

Calling .nth(0) is equivalent to calling .next().

It doesn't take ownership of the iterator the way an adapter does, so you can call it many times.

`last`

The last method consumes items until the iterator returns None, and then returns the last item. If the iterator produces no items, then last returns None.

Tip: If you have a reversible iterator and just want the last item, use iter.rev().next() instead.

`find`

The find method draws items from an iterator, returning the first item for which the given closure returns true, or None if the sequence ends before a suitable item is found.

Building Collections: `collect` and `FromIterator`

An iterator's collect method can build any kind of collection from the Rust's standard library, as long as the iterator produces a suitable item type. The return type of collect is its type parameter.

When some collection type like Vec or HashMap knows how to construct itself from an iterator, it implements the std::iter::FromIterator trait, for which collect is a method:


#![allow(unused)]
fn main() {
trait FromIterator<A>: Sized {
    fn from_iter<T: IntoIterator<Item=A>>(iter: T) -> Self;
}
}

Concept: If a collection type implements FromIterator<A>, then its static method from_iter builds a value of that type from an iterable producing items of type A.

The size_hint method of Iterator returns a lower bound and optional upper bound on the number of items the iterator will produce.

The `Extend` Trait

If a type implements the std::iter::Extend trait, then its extend method adds an iterable's items to the collection.

All of the standard collections implement Extend. Arrays and slices do not have this method because they are not of fixed length.

`partition`

The partition method divides an iterator's items among two collections, using a closure to decide where each item belongs.

Whereas collect requires its result type to implement FromIterator, partition instead requires std::default::Default and std::default::Extend.