Skip to content
LumenaryAcademy
Practice 60 min

Collections, iterators and closures

Vectors, strings, maps and sets, and the iterator pipelines and closures that make everyday Rust short, fast and clear.

Code tested · 4AI-draftedAwaiting review by a computer scientist
MotivationH

Working with many values

Real programs rarely handle one value at a time. They read thousands of lines, count words, group orders by region, find the largest sale, and turn one list into another. This lesson covers the standard library's collections and, more importantly, the iterator style that experienced Rust programmers use to process them.

If you know Python's list comprehensions, JavaScript's map and filter, or Java streams, Rust's iterators will feel familiar. Two things make them special. First, they are lazy: a chain of steps does nothing until something asks for results, so you can describe an infinite sequence and take the first four elements. Second, they are zero-cost: thanks to generics and monomorphisation (lesson 6), a pipeline of filter, map and sum compiles to the same tight loop you would write by hand, often with fewer bounds checks. You do not trade speed for clarity.

Iterators are driven by closures, small anonymous functions that can capture variables from their surroundings. Closures interact with ownership in interesting ways, and understanding the three closure traits will make many compiler messages suddenly make sense.

DefinitionsH

Vectors and strings

Definition— Vec and String

Vec<T> is a growable array: a pointer to a heap buffer, a length and a capacity, exactly like String (which is, underneath, a vector of UTF-8 bytes that is guaranteed to be valid text). When a push exceeds the capacity, the vector allocates a buffer about twice as large and moves the elements, so pushing is fast on average. A vector lends out its contents as a slice, &[T], so every slice method works on vectors.

rust
fn main() {
    // Vec<T>: a growable array on the heap.
    let mut marks: Vec<u32> = Vec::new();
    marks.push(72);
    marks.extend([88, 65, 91, 65, 40]);
    println!("{marks:?}, len {}, first {:?}", marks.len(), marks.first());

    println!("marks[2] = {}, get(10) = {:?}", marks[2], marks.get(10));

    marks.sort();
    marks.dedup(); // removes consecutive duplicates
    marks.retain(|&m| m >= 50); // keep only passing marks
    println!("sorted, unique, passing: {marks:?}");

    let mut names = vec!["Zainab", "bo", "Émile", "Arjun"];
    names.sort_by_key(|n| n.to_lowercase());
    println!("{names:?}");

    // Slices of a Vec: windows and chunks.
    let temps = [14, 17, 21, 19, 23, 25];
    let rises: Vec<i32> = temps.windows(2).map(|w| w[1] - w[0]).collect();
    println!("day-to-day change: {rises:?}");
    for (week, chunk) in temps.chunks(4).enumerate() {
        println!("chunk {week}: {chunk:?}");
    }

    // String: growable UTF-8 text.
    let mut line = String::from("  Lagos, Nairobi ,Cairo  ");
    line = line.trim().to_string();
    let cities: Vec<&str> = line.split(',').map(|c| c.trim()).collect();
    println!("{cities:?}");
    let joined = cities.join(" -> ");
    println!("{joined} ({} bytes)", joined.len());
}
text
[72, 88, 65, 91, 65, 40], len 6, first Some(72)
marks[2] = 65, get(10) = None
sorted, unique, passing: [65, 72, 88, 91]
["Arjun", "bo", "Zainab", "Émile"]
day-to-day change: [3, 4, -2, 4, 2]
chunk 0: [14, 17, 21, 19]
chunk 1: [23, 25]
["Lagos", "Nairobi", "Cairo"]
Lagos -> Nairobi -> Cairo (25 bytes)

Things worth noticing:

  • marks[2] panics if the index is out of range; marks.get(10) returns an Option instead. Use indexing when an out-of-range index would be a bug, and get when it is a normal possibility.
  • retain takes a closure that decides which elements stay. The pattern |&m| copies each number out of the reference that retain passes in.
  • sort_by_key sorts by a computed key. The result shows a real-world subtlety: lowercasing fixes "bo" versus "Zainab", but "Émile" still sorts after "Zainab", because plain string comparison uses Unicode code points and É comes after every ASCII letter. Correct alphabetical order for people's names depends on language and is handled by collation libraries (the ICU4X project publishes Rust crates for this).
  • windows(2) yields overlapping pairs and chunks(4) non-overlapping groups, both as slices, without copying anything.
  • split, trim and join work on &str slices pointing into the original string; only collect and join allocate.
Worked examplesH

Maps and sets

rust
use std::collections::{BTreeMap, HashMap, HashSet};

fn main() {
    let text = "the river feeds the field and the field feeds the village \
                and the village guards the river";

    // Count words with the entry API: one lookup per word.
    let mut counts: HashMap<&str, u32> = HashMap::new();
    for word in text.split_whitespace() {
        *counts.entry(word).or_insert(0) += 1;
    }
    println!("'the' appears {} times", counts["the"]);
    println!(
        "'bridge' appears {} times",
        counts.get("bridge").copied().unwrap_or(0)
    );

    // HashMap iteration order is unspecified; copy into a BTreeMap for sorted output.
    let sorted: BTreeMap<&str, u32> = counts.iter().map(|(w, c)| (*w, *c)).collect();
    for (word, n) in &sorted {
        if *n > 1 {
            println!("{word:>8}: {}", "*".repeat(*n as usize));
        }
    }

    // Sets: membership and set algebra.
    let left: HashSet<&str> = "river field village".split(' ').collect();
    let right: HashSet<&str> = "village market river".split(' ').collect();
    let mut both: Vec<&str> = left.intersection(&right).copied().collect();
    both.sort();
    println!("in both: {both:?}");
    println!(
        "contains 'market'? {} / {}",
        left.contains("market"),
        right.contains("market")
    );

    // Grouping: a map from a key to a Vec of values.
    let people = [
        ("Kenji", "Osaka"),
        ("Aiko", "Tokyo"),
        ("Ren", "Osaka"),
        ("Yui", "Sapporo"),
    ];
    let mut by_city: BTreeMap<&str, Vec<&str>> = BTreeMap::new();
    for (name, city) in people {
        by_city.entry(city).or_default().push(name);
    }
    println!("{by_city:?}");
}
text
'the' appears 6 times
'bridge' appears 0 times
     and: **
   feeds: **
   field: **
   river: **
     the: ******
 village: **
in both: ["river", "village"]
contains 'market'? false / true
{"Osaka": ["Kenji", "Ren"], "Sapporo": ["Yui"], "Tokyo": ["Aiko"]}

The line *counts.entry(word).or_insert(0) += 1; is the idiomatic way to count. entry looks the key up once and returns an Entry; or_insert(0) inserts a zero if the key is absent and, either way, returns a mutable reference to the count, which *... += 1 increments. Compare the naive alternative (check contains_key, then insert or get_mut), which looks the key up two or three times. In the grouping example, or_default() inserts an empty vector the first time a city appears.

A HashMap<K, V> iterates in an unspecified order that changes from run to run, because its hash function is seeded randomly to resist attacks where someone sends keys chosen to collide. That is why the program prints from a BTreeMap, which keeps its keys sorted. Never write code, or tests, that depend on a HashMap's order.

Choosing a collection:

CollectionUse it forKey operations
Veca sequence; the default choicepush/pop at the end O(1), index O(1)
VecDequea queue: add and remove at both endspush/pop at either end O(1)
HashMap, HashSetlookup by key, no order neededinsert/get/remove O(1) on average
BTreeMap, BTreeSetlookup by key, sorted iteration, rangesinsert/get/remove O(log n)
BinaryHeapalways take the largest item next (priority queue)push O(log n), pop max O(log n)

When in doubt, start with a Vec. For small collections a linear scan of a vector often beats a hash map, because the data sits together in memory. Keys of a HashMap must implement Eq and Hash; keys of a BTreeMap must implement Ord. Deriving those traits on your own types is usually all it takes.

DefinitionsH

Iterators

Definition— iterator

An iterator is any value implementing the Iterator trait, whose one required method is fn next(&mut self) -> Option<Self::Item>: each call yields Some(item) until the sequence is exhausted, then None. Item is an associated type naming what the iterator produces. Everything else (map, filter, sum, collect and some seventy more) is a provided method built on next.

Collections offer three ways to iterate, differing in ownership:

CallYieldsThe collection afterwards
v.iter() or for x in &vshared references &Tunchanged, still usable
v.iter_mut() or for x in &mut vmutable references &mut Tchanged in place, still usable
v.into_iter() or for x in vowned values Tconsumed (moved)

Iterator methods come in two kinds. Adaptors (map, filter, enumerate, zip, take, skip, chain, rev, flat_map...) wrap one iterator in another and do no work yet. Consumers (sum, count, collect, fold, max_by_key, any, all, find, position, for_each...) pull items through the chain. If you build a chain and never consume it, the compiler warns: "iterators are lazy and do nothing unless consumed".

rust
use std::cmp::Reverse;

struct Sale {
    region: &'static str,
    item: &'static str,
    units: u32,
    unit_price: f64,
}

impl Sale {
    fn new(region: &'static str, item: &'static str, units: u32, unit_price: f64) -> Sale {
        Sale {
            region,
            item,
            units,
            unit_price,
        }
    }
}

fn main() {
    let sales = [
        Sale::new("north", "tea", 12, 3.5),
        Sale::new("south", "coffee", 5, 4.0),
        Sale::new("north", "coffee", 8, 4.0),
        Sale::new("east", "tea", 20, 3.25),
        Sale::new("south", "mate", 3, 6.0),
    ];

    // A pipeline: nothing runs until a consumer (here `sum`) pulls values through.
    let tea_revenue: f64 = sales
        .iter()
        .filter(|s| s.item == "tea")
        .map(|s| s.units as f64 * s.unit_price)
        .sum();
    println!("tea revenue: {tea_revenue:.2}");

    let biggest = sales.iter().max_by_key(|s| s.units).unwrap();
    println!(
        "biggest order: {} {} in the {}",
        biggest.units, biggest.item, biggest.region
    );

    let any_large = sales.iter().any(|s| s.units > 15);
    let all_priced = sales.iter().all(|s| s.unit_price > 0.0);
    let position = sales.iter().position(|s| s.item == "mate");
    println!("any over 15: {any_large}, all priced: {all_priced}, mate at {position:?}");

    // fold carries an accumulator through the sequence.
    let (units, revenue) = sales.iter().fold((0, 0.0), |(u, r), s| {
        (u + s.units, r + s.units as f64 * s.unit_price)
    });
    println!("{units} units, {revenue:.2} revenue");

    // zip pairs two sequences; enumerate numbers them; take and skip slice them.
    let ranks = ["gold", "silver", "bronze"];
    let mut by_units: Vec<&Sale> = sales.iter().collect();
    by_units.sort_by_key(|s| Reverse(s.units)); // largest first
    for (i, (rank, sale)) in ranks.iter().zip(&by_units).enumerate() {
        println!("{}. {rank}: {} ({})", i + 1, sale.item, sale.units);
    }

    // collect can build many types, including a Result that fails on the first error.
    let good: Result<Vec<u32>, _> = "4 8 15".split(' ').map(|t| t.parse::<u32>()).collect();
    let bad: Result<Vec<u32>, _> = "4 x 15".split(' ').map(|t| t.parse::<u32>()).collect();
    println!("{good:?}");
    println!("{}", bad.is_err());
    let initials: String = sales
        .iter()
        .map(|s| s.item.chars().next().unwrap())
        .collect();
    println!("{initials}");
}
text
tea revenue: 107.00
biggest order: 20 tea in the east
any over 15: true, all priced: true, mate at Some(4)
48 units, 177.00 revenue
1. gold: tea (20)
2. silver: tea (12)
3. bronze: coffee (8)
Ok([4, 8, 15])
true
tcctm

Read a pipeline top to bottom as a sentence: "take the sales, keep the tea, turn each into its revenue, add them up". Some details:

  • sum and collect need to know their result type, which is why tea_revenue is annotated f64. When there is no variable to annotate, use the "turbofish": .sum::<f64>().
  • fold is the general-purpose consumer: you give it a starting accumulator and a closure that combines the accumulator with each item. Here the accumulator is a tuple, so a single pass computes two totals.
  • max_by_key returns an Option (the sequence could be empty), hence the unwrap, safe here because the vector is not empty.
  • zip stops at the shorter sequence, which is why only three of the five sales get medals. To rank them, the program sorts references to the sales with sort_by_key, wrapping the key in std::cmp::Reverse to get largest-first order.
  • Collecting an iterator of Results into Result<Vec<u32>, _> gives Ok with all the values, or the first Err. This idiom validates a whole list in one line.
  • Collecting chars into a String builds a string.

Example— From a loop to a pipeline

A school keeps, for each class, a list of pupils and their reading scores, and wants the names of every pupil, in any class, who scored below 50, in alphabetical order. A first draft uses two nested for loops, an if, a push onto a mutable vector, and a sort at the end. The pipeline version reads like the specification:

rust
let mut needs_help: Vec<&str> = classes
    .iter()
    .flat_map(|class| class.pupils.iter())
    .filter(|pupil| pupil.score < 50)
    .map(|pupil| pupil.name.as_str())
    .collect();
needs_help.sort_unstable();

flat_map turns "an iterator of classes, each with an iterator of pupils" into one flat iterator of pupils, replacing the outer loop. Each later line does one job, and none of them can accidentally modify the data, because they only receive shared references. When a requirement changes ("only the first three classes", "at most ten names"), the change is one more adaptor (.take(3) before flat_map, .take(10) before collect) rather than a new counter variable threaded through two loops. sort_unstable is a slightly faster sort that may reorder equal elements, which does not matter for plain names.

DefinitionsH

Closures

Definition— closure

A closure is an anonymous function written |parameters| expression, which can capture variables from the scope where it is created. The compiler decides how to capture each variable (by shared reference, by mutable reference, or by value) from what the body does with it, and gives the closure one or more of three traits: Fn (only reads its captures; can be called any number of times), FnMut (changes its captures; needs exclusive access while called) and FnOnce (consumes a capture; can be called only once). The move keyword forces every capture to be taken by value.

rust
/// An iterator that cycles through a rota of names forever.
struct Rota<'a> {
    names: &'a [&'a str],
    next: usize,
}

impl<'a> Iterator for Rota<'a> {
    type Item = &'a str;

    fn next(&mut self) -> Option<Self::Item> {
        if self.names.is_empty() {
            return None;
        }
        let name = self.names[self.next];
        self.next = (self.next + 1) % self.names.len();
        Some(name)
    }
}

// Accepts any closure that can be called repeatedly and only reads its captures.
fn apply_to_all(prices: &[f64], adjust: impl Fn(f64) -> f64) -> Vec<f64> {
    prices.iter().map(|&p| adjust(p)).collect()
}

// Returns a closure: `move` makes it own its captured `percent`.
fn discount(percent: f64) -> impl Fn(f64) -> f64 {
    move |price| price * (1.0 - percent / 100.0)
}

fn main() {
    let team = ["Ama", "Bilal", "Chen"];
    let days = ["Mon", "Tue", "Wed", "Thu", "Fri"];
    let rota = Rota {
        names: &team,
        next: 0,
    };
    for (day, person) in days.iter().zip(rota) {
        println!("{day}: {person} washes up");
    }

    // A closure that captures `vat` by reference.
    let vat = 0.25;
    let with_vat = |price: f64| price * (1.0 + vat);
    println!("{:?}", apply_to_all(&[10.0, 25.0], with_vat));

    let ten_off = discount(10.0);
    println!("{:?}", apply_to_all(&[10.0, 25.0], &ten_off));

    // A closure that mutates what it captures is FnMut.
    let mut calls = 0;
    let mut tally = |x: i32| {
        calls += 1;
        x * x
    };
    let squares: Vec<i32> = (1..=4).map(&mut tally).collect();
    println!("{squares:?} after {calls} calls");

    // Iterators are lazy: this chain does no work until `collect`.
    let evens = (1..).filter(|n| n % 2 == 0).map(|n| n * n).take(4);
    let firsts: Vec<u64> = evens.collect();
    println!("{firsts:?}");
}
text
Mon: Ama washes up
Tue: Bilal washes up
Wed: Chen washes up
Thu: Ama washes up
Fri: Bilal washes up
[12.5, 31.25]
[9.0, 22.5]
[1, 4, 9, 16] after 4 calls
[4, 16, 36, 64]

The program shows each closure trait at work:

  • with_vat reads vat, so it captures a shared reference and is Fn. It can be passed to apply_to_all, whose parameter impl Fn(f64) -> f64 accepts any closure (or ordinary function) with that shape.
  • discount returns a closure. Without move, the closure would borrow percent, a parameter that disappears when discount returns, and the compiler would refuse. With move, the closure owns its own copy. The return type impl Fn(f64) -> f64 hides the closure's real type, which has no name you could write.
  • tally changes calls, so it is FnMut and must itself be declared mut. While map holds it, nobody else may touch calls; once the pipeline has finished, calls can be read again.
  • A closure that gives away something it captured (for example, returns a captured String by value) is only FnOnce. Thread spawning in lesson 9 takes an FnOnce closure, usually with move.

The Rota struct shows that implementing Iterator for your own type takes one method. Once next exists, zip, take and every other adaptor work with it for free. Rota never returns None for a non-empty rota, so it is an infinite iterator, which is fine because zip stops when the five weekdays run out. The same is true of (1..), an endless range, tamed by take(4).

ComputationC

What it costs

Because each adaptor is a generic struct and each closure has its own unique type, the compiler sees the whole pipeline at once and can inline everything into a single loop. A chain like v.iter().filter(...).map(...).sum() usually compiles to the same machine code as a hand-written for loop with an if and an accumulator, and iterating a slice avoids the bounds check that v[i] indexing may need. Experienced Rust programmers write iterator chains by default and switch to explicit loops when the logic has early exits or complex state that a chain would obscure.

A few costs are real, and worth knowing:

  • collect allocates. Chaining adaptors is free; collecting into a vector at every step is not. Pass iterators between steps when you can, or reserve capacity with Vec::with_capacity when you know the size.
  • The default HashMap hasher is designed to resist denial-of-service attacks, not for raw speed. For hot maps with trusted keys, teams sometimes plug in a faster hasher from a crate; measure before you do.
  • A BTreeMap lookup is O(log n) but touches few cache lines per level; for many workloads it is competitive with hashing, and it gives you order for free.
  • chars() decodes UTF-8 as it goes, so s.chars().nth(i) is O(i), not O(1). If you need random access by character, collect into a Vec<char> first.
Common misconceptionsH

Common misconceptions

Misconception

"for x in v and for x in &v are the same." The first consumes the vector (it calls into_iter and moves each element out), so v is unusable afterwards; the second borrows it. If you get "value used here after move" after a loop, this is usually why.

Misconception

"Calling map runs the closure." Adaptors are lazy. v.iter().map(|x| println!("{x}")); prints nothing, and the compiler warns that the iterator is unused. Use a for loop for side effects, or end the chain with a consumer.

Misconception

"A HashMap remembers insertion order." It does not, and its order differs between runs. Use a BTreeMap for sorted order, or keep a Vec of keys alongside if you need insertion order (or the popular indexmap crate).

Misconception

"Closures are slow because they are like objects with virtual calls." A closure passed to a generic function (impl Fn) is a concrete type the compiler can inline. Only a boxed closure, Box<dyn Fn(...)>, uses dynamic dispatch.

Exercises

Exercises

1. Collections, iterators and closures

Warm-upComputational

What does this print?

fn main() {
    let v = vec![3, 1, 4, 1, 5, 9, 2, 6];
    let r: i32 = v.iter().filter(|&&x| x % 2 == 1).map(|x| x * 10).sum();
    println!("{r}");
}

2. Collections, iterators and closures

CoreComputational

What does this print?

use std::collections::HashMap;

fn main() {
    let words = ["apple", "avocado", "banana", "blueberry", "cherry"];
    let mut m: HashMap<char, usize> = HashMap::new();
    for w in words {
        *m.entry(w.chars().next().unwrap()).or_insert(0) += w.len();
    }
    println!("{}", m[&'b']);
}

3. Collections, iterators and closures

CoreComputational

What does this print?

fn main() {
    let s: String = "hello world"
        .split(' ')
        .map(|w| w.chars().rev().collect::<String>())
        .collect::<Vec<_>>()
        .join(" ");
    println!("{s}");
}

4. Collections, iterators and closures

CoreComputational

What is (1..=10).skip(2).step_by(3).count()?

5. Collections, iterators and closures

StretchComputational

Which closure trait is the most that this closure can implement?

let name = String::from("Imani");
let greet = move || name;
Choose one

6. Collections, iterators and closures

CoreComputational

Why does this fail to compile?

fn main() {
    let names = vec![String::from("Tunde"), String::from("Mia")];
    for n in names {
        println!("{n}");
    }
    println!("{}", names.len());
}
Choose one

Further reading and resources