Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

7. Collections, Strings, and Iterators

Three subjects that belong together, because in Rust they are one subject: the standard collections, the text type that is not quite a collection, and the iterator machinery that is how you are meant to work with both.

7.1 Vec

A Vec<T> is a growable array of values of one type, stored contiguously on the heap. It is the collection you will use for nearly everything.

fn main() {
    let mut v: Vec<i32> = Vec::new();
    v.push(3);
    v.push(1);
    v.push(2);

    let mut w = vec![10, 20, 30];
    w.extend_from_slice(&[40, 50]);

    println!("{v:?} {w:?}");
    println!("first {:?}, tenth {:?}", w.first(), w.get(9));
    println!("popped {:?}, now {:?}", w.pop(), w);

    v.sort();
    println!("sorted {v:?}, contains 2: {}", v.contains(&2));

    let mut n = vec![1, 2, 3, 4, 5, 6];
    n.retain(|x| x % 2 == 0);
    println!("evens {n:?}");

    let total: i32 = n.iter().sum();
    println!("total {total}, max {:?}", n.iter().max());
}
[3, 1, 2] [10, 20, 30, 40, 50]
first Some(10), tenth None
popped Some(50), now [10, 20, 30, 40]
sorted [1, 2, 3], contains 2: true
evens [2, 4, 6]
total 12, max Some(6)

vec![...] is the macro that builds one from a list, and vec![0; 100] builds a hundred zeros. The type is written once, either in the declaration or by inference from the first push.

Two ways to read an element. v[i] panics if i is out of range:

thread 'main' panicked at index_out_of_bounds.rs:3:21:
index out of bounds: the len is 3 but the index is 5

and v.get(i) hands back an Option, the one to use when the index came from outside the program. first, last, and pop are all Option for the same reason: the vector might be empty, and the type says so.

sort needs the elements to be orderable, which floats are not (Chapter 2), so a Vec<f64> uses sort_by(|a, b| a.partial_cmp(b).unwrap()). dedup removes consecutive duplicates and is usually preceded by a sort. retain keeps the elements a closure approves of. insert and remove take an index and shift everything after it, so they cost time proportional to the length; swap_remove is the fast alternative when order does not matter.

A vector grows by allocating a larger block and moving its contents, so the address of an element is not stable across a push. That is the reason for the borrow rule you met in Chapter 5, and the reason Vec::with_capacity(n) exists when you know the size in advance.

7.2 Slices Again

Passing a whole vector to a function that only reads it means passing &[T], not &Vec<T>. The slice form accepts a vector, an array, or part of either:

fn mean(values: &[f64]) -> Option<f64> {
    if values.is_empty() {
        return None;
    }
    Some(values.iter().sum::<f64>() / values.len() as f64)
}

fn main() {
    let v = vec![1.0, 2.0, 3.0, 4.0];
    println!("{:?}", mean(&v));
    println!("{:?}", mean(&v[..2]));
    println!("{:?}", mean(&[]));
}

Useful slice methods beyond the obvious: windows(n) gives every overlapping run of n elements, chunks(n) gives non-overlapping ones, split_at(i) divides in two, and concat and join put a slice of slices back together.

7.3 Arrays

An array [T; N] has its length in its type, lives wherever it is declared rather than on the heap, and cannot grow. Use one for a fixed-size buffer or a small lookup table, as Chapter 1’s digit counter did. Everything else wants a Vec.

7.4 HashMap

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

fn main() {
    let text = "the quick brown fox jumps over the lazy dog the fox";

    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!("cat appears {:?} times", counts.get("cat"));

    let mut pairs: Vec<(&str, u32)> = counts.into_iter().collect();
    pairs.sort_by(|a, b| b.1.cmp(&a.1).then(a.0.cmp(b.0)));
    println!("{:?}", &pairs[..3]);

    let ordered: BTreeMap<&str, usize> =
        text.split_whitespace().map(|w| (w, w.len())).collect();
    println!("{ordered:?}");

    let unique: HashSet<&str> = text.split_whitespace().collect();
    println!("{} words, {} distinct", text.split_whitespace().count(), unique.len());
}
the appears 3 times
cat appears None times
[("the", 3), ("fox", 2), ("brown", 1)]
{"brown": 5, "dog": 3, "fox": 3, "jumps": 5, "lazy": 4, "over": 4, "quick": 5, "the": 3}
11 words, 8 distinct

The line to learn is this one:

*counts.entry(word).or_insert(0) += 1;

entry names a place in the map, whether or not anything is there yet. or_insert(0) puts a zero there if it was empty and hands back a mutable reference to the value either way, and the * writes through it. Counting things is the most common map operation there is, and this is one line with one lookup rather than a contains-then-get-then-insert dance.

map[key] panics on a missing key; map.get(key) returns an Option. Use the second unless you are certain.

Iteration order of a HashMap is unspecified and varies between runs, on purpose. When you need order, either collect into a Vec and sort, as the example does, or use a BTreeMap, which keeps its keys sorted and iterates in that order at the cost of slower lookups. HashSet and BTreeSet are the same pair without values.

collect is doing quiet work in three places above: it builds a Vec of pairs from a map, a BTreeMap from pairs, and a HashSet from words. What it builds comes from the type you asked for, which is why those declarations carry explicit types.

Keys must be hashable and comparable, which for your own types means deriving Hash, Eq, and PartialEq. Floats are not eligible, for the reason given in Chapter 2.

7.5 Strings

String owns growable UTF-8 text. &str is a borrowed view of UTF-8 text, usually of part of a String or of a literal baked into the executable. Take &str in function parameters, return String when you have made something new.

fn main() {
    let mut s = String::from("hello");
    s.push_str(", world");
    s.push('!');

    let name = "Ada";
    let greeting = format!("{s} My name is {name}.");
    println!("{greeting}");

    let text = "  Grüße, Welt  ";
    println!("[{}]", text.trim());
    println!("bytes {} chars {}", text.trim().len(), text.trim().chars().count());
    println!("upper {}", text.trim().to_uppercase());
    println!("{:?}", text.trim().find('W'));
    println!("{:?}", text.trim().split(", ").collect::<Vec<&str>>());
    println!("{}", text.trim().replace("Welt", "World"));

    for (i, c) in "Grüße".char_indices() {
        print!("{i}:{c} ");
    }
    println!();
}
hello, world! My name is Ada.
[Grüße, Welt]
bytes 13 chars 11
upper GRÜSSE, WELT
Some(9)
["Grüße", "Welt"]
Grüße, World
0:G 1:r 2:ü 4:ß 6:e

Read that output carefully, because it contains everything awkward about text. Eleven characters occupy thirteen bytes. The character positions from char_indices are 0, 1, 2, 4, 6, with gaps where a character took two bytes. find reports byte 9 for the W, not character 9. And uppercasing Grüße produces GRÜSSE, which is one character longer than it started, because the uppercase of ß is two letters.

So: len() is bytes, chars().count() is characters and costs a walk of the whole string, and indices are byte offsets everywhere. &s[0..3] is legal and takes bytes 0 to 3, but only if that lands on character boundaries:

thread 'main' panicked at char_boundary.rs:3:22:
end byte index 3 is not a char boundary; it is inside 'ü' (bytes 2..4 of string)

This looks like Rust being difficult. It is Rust making you notice a problem every language has and most hide until your program meets a name with an accent in it. Slice with indices that came from the string itself, from find or char_indices, and nothing can go wrong.

One further layer exists that the standard library does not address: what a person calls a character can be several Unicode scalars, as with a flag emoji or an e followed by a combining accent. If you need that, the unicode-segmentation crate gives you grapheme clusters. Most programs do not.

The methods you will want: trim, trim_start, trim_end, split, split_whitespace, splitn, lines, starts_with, ends_with, contains, find, replace, to_lowercase, to_uppercase, parse, repeat, and chars().rev() for backwards. Building text is format! for a one-off, push_str in a loop, and String::with_capacity when the size is known.

+ concatenates but takes ownership of its left side and borrows its right: a + &b. It is a wart. Use format!.

7.6 Iterators

An iterator produces values one at a time. Everything in this chapter has one, and most of what you want to do with a collection is a chain of iterator steps ending in something that consumes the chain.

fn main() {
    let words = ["apple", "fig", "banana", "kiwi", "cherry"];

    let shouted: Vec<String> = words
        .iter()
        .filter(|w| w.len() > 3)
        .map(|w| w.to_uppercase())
        .collect();
    println!("{shouted:?}");

    let total_length: usize = words.iter().map(|w| w.len()).sum();
    println!("{total_length}");

    let first_long = words.iter().find(|w| w.len() > 5);
    println!("{first_long:?}");

    let all_lower = words.iter().all(|w| w.chars().all(|c| c.is_lowercase()));
    println!("{all_lower}");

    for (i, w) in words.iter().enumerate().take(2) {
        println!("{i} {w}");
    }

    let pairs: Vec<(usize, &str)> = (1..).zip(words.iter().copied()).take(3).collect();
    println!("{pairs:?}");
}
["APPLE", "BANANA", "KIWI", "CHERRY"]
24
Some("banana")
true
0 apple
1 fig
[(1, "apple"), (2, "fig"), (3, "banana")]

Adapters build a new iterator and do no work: map, filter, take, skip, rev, zip, enumerate, chain, flat_map, step_by, peekable, filter_map. Consumers run the chain: collect, sum, count, fold, min, max, any, all, find, position, last, for_each.

Nothing happens until a consumer asks. That is why (1..), an endless range, appears in the example without hanging the program: take(3) only ever asks for three. It is also why a chain of five adapters is compiled into one loop with no intermediate collections, and runs as fast as the loop you would have written.

Three ways to start an iterator from a collection, and the difference is ownership. .iter() produces &T and leaves the collection alone. .iter_mut() produces &mut T so you can modify in place. .into_iter() consumes the collection and produces T, for when you are done with the original. A for loop over &v is .iter(), over &mut v is .iter_mut(), and over v is .into_iter() and ends the vector’s life.

collect deserves a second mention because it is the most versatile function in the library. It builds whatever the target type says: a Vec, a String, a HashMap from an iterator of pairs, a HashSet, and, in a trick Chapter 8 comes back to, a Result<Vec<T>, E> from an iterator of Results, which is how you parse a list of things and fail on the first bad one.

Here it is doing real work. The five longest distinct words on the input:

// The five longest distinct words on the input, longest first.
use std::collections::HashSet;
use std::io::{self, Read};

fn main() {
    let mut text = String::new();
    io::stdin().read_to_string(&mut text).unwrap();

    let seen: HashSet<String> = text
        .split_whitespace()
        .map(|w| w.trim_matches(|c: char| !c.is_alphanumeric()).to_lowercase())
        .filter(|w| !w.is_empty())
        .collect();

    let mut words: Vec<String> = seen.into_iter().collect();
    words.sort_by(|a, b| b.chars().count().cmp(&a.chars().count()).then(a.cmp(b)));

    for w in words.iter().take(5) {
        println!("{:3} {w}", w.chars().count());
    }
}
$ printf 'The quick brown fox jumps over the lazy dog, extraordinarily.\nUnbelievable! the fox.\n' | cargo run -q -p ch07 --bin longwords
 15 extraordinarily
 12 unbelievable
  5 brown
  5 jumps
  5 quick

The punctuation is stripped by trim_matches with a closure, the case is folded so The and the are one word, the HashSet does the duplicate removal, and the sort puts longest first with ties broken alphabetically by then. Each step is one line and none of them needs a temporary vector.

Exercise 7-1. Write a function that takes &[i32] and returns the second largest value as an Option<i32>. Decide what to do about duplicates and say so in a comment.

Exercise 7-2. Count the frequency of each character in the input and print the ten most common, highest first.

Exercise 7-3. Write fn is_palindrome(s: &str) -> bool that ignores case, spaces, and punctuation. Test it with something containing an accented letter.

Exercise 7-4. Rewrite longwords to keep only the five longest as it goes, rather than collecting and sorting everything. Which version is clearer, and at what input size does that stop mattering?

Exercise 7-5. words.sort_by(...) sorts by length descending, then alphabetically. Write the same comparison with sort_by_key and a tuple key. Why does the descending part make that awkward?