Learn/Rust/13. Maps and sets in depth
Lesson 13 of 15
Sign in

Rust, lesson 13

Maps and sets in depth

Lesson 7 introduced HashMap. This lesson digs into the patterns you will use again and again, plus Rust's set types and the ordered BTree collections.

The entry API

map.entry(key) looks up a key once and lets you decide what to do whether it is present or not. It is the idiomatic tool for counting and grouping.

Useful variations:

  • or_insert(v) inserts v if missing and returns &mut V.
  • or_default() inserts the type's default value (0, an empty Vec, an empty ).

2 exercises to try what you just read.

Exercise 1

Anagram groups

Press Ctrl Enter or Check to test your code.

Exercise 2

Club members

Press Ctrl Enter or Check to test your code.

String
  • or_insert_with(|| ...) only builds the default when it is needed.
  • and_modify(|v| ...) changes an existing value before falling back to an or_ call.
  • Grouping

    With or_default(), a map of vectors groups items in one line:

    Keys must implement Eq and Hash. Numbers, char, bool, String, &str and tuples of those all qualify, and you can #[derive(PartialEq, Eq, Hash)] on your own structs to use them as keys.

    Ordered maps: BTreeMap

    HashMap iterates in an unpredictable order. BTreeMap has the same core methods but keeps its keys sorted, so iteration comes out in order with no extra work:

    Choose HashMap for raw speed and BTreeMap when you need ordered output or range queries like stock.range("b".."p").

    Sets

    A set holds unique values with no associated data. HashSet is unordered; BTreeSet is sorted. insert returns false if the value was already there, which is a neat way to detect duplicates:

    You can also build a set straight from an iterator with collect():

    Set operations

    Sets come with the classic operations. Each returns an iterator of references:

    Add .copied() before collect() to get the values themselves instead of references (use .cloned() for types that are not Copy, such as String). With HashSet the results come out in arbitrary order; with BTreeSet they come out sorted. a.is_subset(&b) and a.is_disjoint(&b) answer yes/no questions.

    Further reading

    • std::collections overview
    • std::collections::hash_map::Entry
    • std::collections::BTreeMap
    • std::collections::HashSet

    Read words separated by whitespace. Group words that are anagrams of each other (same letters, like listen and silent): two words are anagrams when sorting their characters gives the same result. Ignore repeated copies of the same word.

    Print one group per line, the words in each group sorted alphabetically and separated by spaces. Order the lines alphabetically by their first word.

    Sample input:

    Sample output:

    The first input line lists the chess club's members and the second line the drama club's (names separated by spaces; a line may be empty). Print three lines, names sorted alphabetically and separated by single spaces:

    If a list is empty, print the label followed by -, for example both: -.

    Sample input:

    Sample output:

    use std::collections::HashMap;
    
    let mut counts: HashMap<&str, u32> = HashMap::new();
    for w in "to be or not to be".split_whitespace() {
        *counts.entry(w).or_insert(0) += 1;
    }
    let mut by_letter: HashMap<char, Vec<&str>> = HashMap::new();
    for name in ["ana", "bo", "al", "bea"] {
        let first = name.chars().next().unwrap();
        by_letter.entry(first).or_default().push(name);
    }
    // 'a' => ["ana", "al"], 'b' => ["bo", "bea"]
    use std::collections::BTreeMap;
    
    let mut stock = BTreeMap::new();
    stock.insert("pear", 2);
    stock.insert("apple", 5);
    for (fruit, qty) in &stock {
        println!("{fruit}: {qty}"); // apple first, then pear
    }
    use std::collections::HashSet;
    
    let mut seen = HashSet::new();
    for word in ["go", "rust", "go"] {
        if !seen.insert(word) {
            println!("duplicate: {word}");
        }
    }
    let a: HashSet<i32> = [1, 2, 3, 4].into_iter().collect();
    let b: HashSet<i32> = [3, 4, 5].into_iter().collect();
    let both: Vec<&i32> = a.intersection(&b).collect();          // 3, 4
    let either: Vec<&i32> = a.union(&b).collect();               // 1, 2, 3, 4, 5
    let only_a: Vec<&i32> = a.difference(&b).collect();          // 1, 2
    let one_side: Vec<&i32> = a.symmetric_difference(&b).collect(); // 1, 2, 5
    listen enlist google silent tinsel banana elgoog
    banana
    elgoog google
    enlist listen silent tinsel
    both: <members of both clubs>
    either: <members of at least one club>
    chess only: <chess members who are not in drama>
    ana ben cy dot
    cy eve ana
    both: ana cy
    either: ana ben cy dot eve
    chess only: ben dot