Thinking in Iterators
An iterator in Rust is a value that produces a sequence, one item at a time, on
request. That description fits iterators in most languages, and it undersells
this one badly, because Rust’s iterators occupy a place in the language that
for loops occupy elsewhere. A large fraction of ordinary Rust — collection
processing, string handling, file reading, numeric work — is written as iterator
chains, and learning to read and write them is most of learning to read and write
Rust.
The trait itself is almost nothing:
#![allow(unused)]
fn main() {
trait MyIterator {
type Item;
fn next(&mut self) -> Option<Self::Item>;
}
}One associated type and one method. next returns Some(item) until the
sequence is exhausted and then None. Everything else — around seventy adapter
and consumer methods — is built on that, supplied as default methods, and
available to anything that implements the one.
Laziness is the mechanism
The first thing to understand is that adapters do no work. map does not
transform anything; it constructs a Map value holding the source iterator and
the closure. filter constructs a Filter. Chaining five adapters builds a
five-layer struct and executes nothing.
fn main() {
let numbers = vec![1, 2, 3, 4, 5, 6];
let pipeline = numbers
.iter()
.map(|n| {
println!(" mapping {n}");
n * 10
})
.filter(|n| n % 20 == 0);
println!("nothing has run yet");
let result: Vec<i32> = pipeline.collect();
println!("{result:?}");
}The mapping messages appear after the “nothing has run yet” line, and each item passes through every stage before the next one starts. Work happens only when something asks for items, and asking is what a consumer does.
Two consequences follow. An infinite sequence is fine as long as something
bounds it, so (1..).map(|n| n * n).take_while(|&n| n < 100) terminates. And a
chain is not a series of passes over the data building intermediate collections
— it is one pass, with each item threaded through every stage, which is why
these chains are as fast as hand-written loops.
Three families
Iterator code reads as a sentence with three parts, and knowing which family a method belongs to makes unfamiliar chains legible.
Creation gets an iterator from something. On collections, iter(),
iter_mut() and into_iter(), which differ in ownership and are covered below.
Ranges are iterators: 0..10, 1..=100, (1..) unbounded. Strings offer
chars(), bytes(), lines(), split_whitespace() and split(pattern). Files
offer lines() through BufRead. std::iter supplies once, repeat,
empty, and successors for generating a sequence from a rule.
Adapters take an iterator and return another one. map transforms, filter
keeps, filter_map does both and drops the Nones, take and skip and their
_while forms bound the sequence, enumerate pairs items with indices, zip
walks two sequences together, chain concatenates, rev reverses, flatten and
flat_map unwrap a level of nesting, peekable allows looking ahead,
step_by samples, scan carries state along, and inspect prints without
changing anything, and is the debugging tool for chains.
Consumers run the chain and produce something that is not an iterator.
collect builds a collection, sum, product, min, max, count reduce to
one value, fold reduces with a closure, any, all, find, position search
and stop early, partition splits in two, for_each runs a side effect, and
last and nth pick.
fn main() {
let text = "the quick brown fox jumps over the lazy dog";
let long_words: Vec<&str> = text
.split_whitespace()
.filter(|word| word.len() > 3)
.collect();
let initials: String = text
.split_whitespace()
.filter_map(|word| word.chars().next())
.collect();
let total_length: usize = text.split_whitespace().map(str::len).sum();
println!("{long_words:?}");
println!("{initials}");
println!("{total_length}");
}The ownership dimension
This is the part that trips people, and it is the place where iterators connect back to the rest of the book. A collection offers three ways to iterate, and they differ in what you get and what happens to the collection.
iter() yields &T. The collection is borrowed and usable afterward. This is
what for item in &collection does.
iter_mut() yields &mut T. The collection is exclusively borrowed, the items
can be modified in place, and the collection’s shape cannot change while you
hold it. This is what for item in &mut collection does.
into_iter() yields T. The collection is consumed and gone. This is what
for item in collection does.
fn main() {
let mut names = vec![String::from("ada"), String::from("grace")];
for name in &names {
println!("borrowed {name}");
}
for name in &mut names {
name.push('!');
}
let lengths: Vec<usize> = names.iter().map(|name| name.len()).collect();
println!("{lengths:?} {names:?}");
let owned: Vec<String> = names.into_iter().map(|name| name.to_uppercase()).collect();
println!("{owned:?}");
}That last line consumes names, which is why it comes last. Choosing among the
three is the same decision as choosing among T, &T and &mut T in a function
signature: does this need the values, or only to look at them, or to change them
in place?
A frequent small confusion: .iter().map(...) gives the closure a &T, so a
closure over a Vec<i32> receives &i32 and often needs a * or a pattern like
|&n|. .copied() or .cloned() convert a &T stream to a T stream when T
allows it, and are usually cleaner than dereferencing inside every closure.
Collect is more capable than it looks
collect builds any type that implements FromIterator, which includes every
standard collection and several types that are not obviously collections:
use std::collections::{HashMap, HashSet, BTreeMap};
fn main() {
let pairs = vec![("a", 1), ("b", 2), ("a", 3)];
let map: HashMap<&str, i32> = pairs.iter().copied().collect();
let ordered: BTreeMap<&str, i32> = pairs.iter().copied().collect();
let keys: HashSet<&str> = pairs.iter().map(|(key, _)| *key).collect();
let joined: String = vec!["a", "b", "c"].into_iter().collect();
println!("{}", map.len());
println!("{ordered:?}");
println!("{}", keys.len());
println!("{joined}");
}Because the target type is what decides the behavior, collect usually needs an
annotation — either on the binding, as above, or with turbofish:
collect::<Vec<_>>(). The _ lets the element type be inferred.
The most useful trick in the method is collecting fallible items. An iterator of
Result can be collected into a Result of a collection, which stops at the
first error:
fn main() {
let good = vec!["1", "2", "3"];
let bad = vec!["1", "two", "3"];
let parsed: Result<Vec<i32>, _> = good.iter().map(|s| s.parse::<i32>()).collect();
let failed: Result<Vec<i32>, _> = bad.iter().map(|s| s.parse::<i32>()).collect();
println!("{parsed:?}");
println!("{}", failed.is_err());
}Written by hand that is a loop, a mutable vector, a match and an early return.
The same works for Option. This one method turns “parse all of these and fail
if any fails” into a single expression, and it appears constantly in real code.
Writing your own
Implementing Iterator requires one method, and everything else comes free:
struct Fibonacci {
current: u64,
next: u64,
}
impl Iterator for Fibonacci {
type Item = u64;
fn next(&mut self) -> Option<u64> {
let value = self.current;
self.current = self.next;
self.next = value.checked_add(self.next)?;
Some(value)
}
}
fn fibonacci() -> Fibonacci {
Fibonacci { current: 0, next: 1 }
}
fn main() {
let values: Vec<u64> = fibonacci().take(10).collect();
println!("{values:?}");
let large = fibonacci().find(|&n| n > 1_000_000).unwrap();
println!("{large}");
println!("{}", fibonacci().take_while(|&n| n < 100).filter(|n| n % 2 == 0).sum::<u64>());
}Thirteen lines of implementation, and the type now works with take, find,
filter, sum, zip, for loops and everything else. The checked_add
returning None through ? ends the sequence at overflow rather than panicking,
the kind of thing that is easy to get right here and easy to forget in a
hand-written loop.
Implementing IntoIterator for your own collection type is the companion move,
and it is what makes for item in my_collection work. Doing it for T, &T and
&mut T gives users the same three choices the standard collections offer.
What the performance claim means
The claim usually made is that iterator chains compile to the same machine code as the equivalent loop. In the common cases that is true, and the reason is monomorphization from chapter 10: every adapter is a concrete type with a concrete closure, nothing is dispatched dynamically, and the optimizer sees one fused loop body with no allocation between stages.
Iterators sometimes beat the hand-written version, because iterating without indices removes bounds checks that an index-based loop has to keep.
Where the claim weakens is worth knowing. collect into a collection allocates,
and a chain that collects in the middle to feed another chain has paid for an
intermediate structure; usually the fix is to keep the chain going. Some
adapters over some sources defeat the optimizer, notably chains through zip on
sources with unknown length. And an iterator holding a trait object goes back to
dynamic dispatch.
None of that changes the practical advice: write the iterator version first, because it is shorter and harder to get wrong, and to measure before rewriting it as a loop for speed. What you should not do is avoid iterators because they feel like they must cost something; that intuition is imported from languages where it was correct.
When a loop is the better answer
Iterator chains are not always clearer. Three situations favor an ordinary loop.
When the body has complex control flow — several early exits, a continue that
skips different amounts of work depending on a condition, or a branch that needs
to do two different things — a chain turns into nested closures returning
Option and is harder to read than the loop it replaced.
When several things are being mutated at once, a loop says so directly.
for_each with a closure capturing three mutable variables is a loop wearing a
costume.
When the logic is genuinely sequential and stateful — a parser stepping through
tokens with a mode, a state machine — the iterator version needs scan or
fold with a tuple accumulator, and reads worse than the statements it encodes.
The test is what a reader has to reconstruct. numbers.iter().filter(...).sum()
states an intent. A five-deep chain with a scan carrying a three-field tuple
states a mechanism, badly.
Note
The
itertoolscrate adds the adapters the standard library left out —chunk_by,sorted,unique,dedup,tuple_windows,joinand several dozen more. If a chain is getting awkward, it is worth checking whether the thing you are hand-rolling is already there.
A related habit: the entry API
Iterators are one instance of a broader idea. The standard library
gives you a way to say what you mean in one operation instead of a read followed
by a write. HashMap’s entry API is the other one you will use daily:
use std::collections::HashMap;
fn main() {
let text = "the quick brown the lazy the";
let mut counts: HashMap<&str, u32> = HashMap::new();
for word in text.split_whitespace() {
*counts.entry(word).or_insert(0) += 1;
}
let mut sorted: Vec<_> = counts.into_iter().collect();
sorted.sort_by(|a, b| b.1.cmp(&a.1).then(a.0.cmp(b.0)));
println!("{sorted:?}");
}entry looks the key up once and returns a handle to the slot, occupied or not.
The alternative — contains_key, then get_mut or insert — hashes twice, and
in a language with references it would also be a chance for the two operations to
disagree. Reach for entry whenever you find yourself checking for a key before
doing something with it.
Conclusion
Iterator is one method with seventy conveniences attached, and it is lazy, so a
chain of adapters describes a computation rather than performing one. Reading
Rust fluently means reading these chains as sentences: something creates, some
things adapt, one thing consumes.
The ownership question runs through it. iter, iter_mut and into_iter are
the same choice as &T, &mut T and T in a signature, and choosing wrong is
the most common source of confusion for newcomers. collect is more capable than
it looks, particularly its ability to turn a sequence of Result into a Result
of a sequence.
Implementing the trait for your own type costs one method and buys the whole vocabulary, which makes it one of the best-value implementations in the language.
The next chapter takes the ownership model across thread boundaries, where the same rule that has been preventing dangling pointers turns out to prevent data races as well.
Questions to think through
Take a loop from your own code that builds a collection. Rewrite it as a chain in your head and decide which version a reader would understand faster. What made the difference?
iter(), iter_mut() and into_iter() correspond to three ways of taking a
parameter. Find a place in code you know where a method iterates a collection and
decide which of the three it should be using.
Collecting into Result<Vec<T>, E> stops at the first error. When would you want
all the errors instead, and what would the chain look like?