Collections and Strings in Rust

A collection is a type that holds a variable number of values, stored on the heap so that it can grow and shrink while the program runs. Arrays and tuples from lesson 2 have a size fixed at compile time; collections do not. The standard library's std::collections module provides the usual data structures, and three of them carry most real Rust code: Vec<T> (a growable array), String (growable UTF-8 text) and HashMap<K, V> (a key-value table).

Collections are where ownership and borrowing meet everyday code. Pushing to a vector while holding a reference into it, looping over a vector and then using it again, inserting a String key into a map: each of these is a borrow-checker conversation you will have in your first week. Strings add a twist of their own, because Rust stores text as UTF-8 and refuses to let you index it by position. This lesson covers Vec (creating, reading with indexing versus get, iterating, changing, and the errors you hit), String and &str in depth, UTF-8, bytes versus chars, HashMap and its entry API, HashSet, BTreeMap and VecDeque briefly, and how to choose between them. Interviewers commonly ask why s[0] does not compile, how a Vec grows, and how to count words with a map; you will be able to answer all three.

Vec<T>: a growable array

A Vec<T> (pronounced "vector") stores values of one type T next to each other in memory, like a Java ArrayList or a Python list, except every element must have the same type.

fn main() {
    let mut scores: Vec<u32> = Vec::new();
    scores.push(72);
    scores.push(88);
    scores.push(95);

    let primes = vec![2, 3, 5, 7, 11];
    let zeros = vec![0; 4];

    println!("scores = {scores:?}, len = {}", scores.len());
    println!("primes = {primes:?}, zeros = {zeros:?}");

    println!("third score by index: {}", scores[2]);
    println!("tenth score with get: {:?}", scores.get(9));
    if let Some(first) = scores.first() {
        println!("first score: {first}");
    }

    let last = scores.pop();
    println!("popped {last:?}, now {scores:?}");

    scores.insert(0, 60);
    let removed = scores.remove(1);
    println!("after insert and remove({removed}): {scores:?}");

    println!("contains 88? {}", scores.contains(&88));
}

Output:

scores = [72, 88, 95], len = 3
primes = [2, 3, 5, 7, 11], zeros = [0, 0, 0, 0]
third score by index: 95
tenth score with get: None
first score: 72
popped Some(95), now [72, 88]
after insert and remove(72): [60, 88]
contains 88? true

Step by step:

1. Vec::new() creates an empty vector. The type annotation Vec<u32> is needed only because the compiler cannot guess the element type from nothing; after the first push, it usually can.
2. vec![...] is a macro that creates a vector with the listed values. vec![0; 4] means "four copies of 0".
3. scores[2] reads by index, starting from 0. scores.get(9) also reads by index, but returns an Option<&u32>: None when the index is out of range.
4. first() and last() return Option<&T> too, because the vector might be empty.
5. pop() removes and returns the last element as an Option<T>. insert(0, 60) shifts everything right to make room at the front; remove(1) takes out the element at index 1 (here 72) and shifts everything after it left.
6. contains(&88) takes a reference, because comparing does not need ownership of the value.

Indexing versus get

Indexing with [] assumes the index is valid and panics if it is not. A panic stops the thread with an error message; lesson 9 covers panics in depth. This program compiles but crashes:

fn main() {
    let mut scores = vec![72, 88];
    scores.push(95);
    let wanted: usize = "5".parse().unwrap();
    println!("score: {}", scores[wanted]);
}

Output (standard error):

thread 'main' (1740693) panicked at vec_oob.rs:5:33:
index out of bounds: the len is 3 but the index is 5
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

The index comes from parsing a string so that the compiler cannot see the mistake in advance; for a constant index into a fixed-size array it would reject the code at compile time. Rust always checks bounds, unlike C, where reading past the end of an array silently returns whatever memory is there. The check is cheap, and the optimiser often removes it when it can prove the index is in range, for example inside for i in 0..v.len().

How a Vec is laid out and how it grows

A Vec is three words on the stack, exactly like a String: a pointer to a heap buffer, a length (elements in use) and a capacity (elements the buffer can hold before it must grow).

let v = vec![10, 20, 30];  (with capacity 4)

stack                    heap
+-----+-----+-----+     +----+----+----+------+
| ptr | len | cap |---> | 10 | 20 | 30 | free |
|     |  3  |  4  |     +----+----+----+------+
+-----+-----+-----+

When you push into a full vector, it allocates a bigger buffer, copies the elements across, and frees the old one. Growing by a multiple each time, rather than by one, keeps push cheap on average:

fn main() {
    let mut v: Vec<i32> = Vec::new();
    println!("len {} cap {}", v.len(), v.capacity());
    for i in 0..9 {
        v.push(i);
        println!("len {} cap {}", v.len(), v.capacity());
    }

    let mut w: Vec<i32> = Vec::with_capacity(100);
    w.extend(0..10);
    println!("with_capacity: len {} cap {}", w.len(), w.capacity());
}

Output:

len 0 cap 0
len 1 cap 4
len 2 cap 4
len 3 cap 4
len 4 cap 4
len 5 cap 8
len 6 cap 8
len 7 cap 8
len 8 cap 8
len 9 cap 16
with_capacity: len 10 cap 100

With this compiler, an empty Vec allocates nothing (capacity 0), the first push allocates room for 4 small elements, and the capacity then doubles to 8 and 16. The exact growth strategy is an implementation detail that the documentation does not promise, so never rely on the numbers. What is guaranteed is the cost: because the capacity grows geometrically, n pushes cost O(n) in total, so a single push is amortised O(1), meaning constant on average even though an occasional push copies everything.

When you know roughly how many elements are coming, Vec::with_capacity(n) allocates once up front, and no reallocation happens until you exceed it.

Iterating over a Vec

There are three ways to loop over a vector, and they correspond to the three ways of passing a value: shared borrow, mutable borrow and move.

fn main() {
    let mut prices = vec![120, 45, 300];

    for p in &prices {
        print!("{p} ");
    }
    println!();

    for p in &mut prices {
        *p += *p / 10;
    }
    println!("after 10% increase: {prices:?}");

    for (i, p) in prices.iter().enumerate() {
        println!("item {i}: {p}");
    }

    let total: i32 = prices.iter().sum();
    println!("total = {total}");

    for p in prices {
        print!("[{p}] ");
    }
    println!();
}

Output:

120 45 300 
after 10% increase: [132, 49, 330]
item 0: 132
item 1: 49
item 2: 330
total = 511
[132] [49] [330] 

In the mutable loop, *p += *p / 10 adds 10% using integer division: 120 + 12 = 132, 45 + 4 = 49 and 300 + 30 = 330, which sum to 511.

Reading the compiler error: the for loop moved the vector

This does not compile:

fn main() {
    let names = vec![String::from("Asha"), String::from("Ravi")];
    for name in names {
        println!("hello {name}");
    }
    println!("{} names", names.len());
}

error[E0382]: borrow of moved value: `names`
 --> vec_moved_err.rs:6:26
  |
2 |     let names = vec![String::from("Asha"), String::from("Ravi")];
  |         ----- move occurs because `names` has type `Vec<String>`, which does not implement the `Copy` trait
3 |     for name in names {
  |                 ----- `names` moved due to this implicit call to `.into_iter()`
...
6 |     println!("{} names", names.len());
  |                          ^^^^^ value borrowed here after move
  |
note: the `for` loop is desugared into a call to `std::iter::IntoIterator::into_iter`, which takes ownership of the receiver `self`, which moves `names`
help: consider iterating over a slice of the `Vec<String>`'s content to avoid moving into the `for` loop
  |
3 |     for name in &names {
  |                 +

for name in names takes the vector by value: the loop calls into_iter(), which consumes names and hands you each String by value. After the loop the vector no longer exists. The note explains the desugaring, and the help gives the fix: loop over &names if you only need to read.

Reading the compiler error: holding a reference while pushing

This does not compile:

fn main() {
    let mut queue = vec![String::from("job-1"), String::from("job-2")];
    let newest = queue.last().unwrap();
    queue.push(String::from("job-3"));
    println!("newest was {newest}");
}

error[E0502]: cannot borrow `queue` as mutable because it is also borrowed as immutable
 --> vec_borrow_err.rs:4:5
  |
3 |     let newest = queue.last().unwrap();
  |                  ----- immutable borrow occurs here
4 |     queue.push(String::from("job-3"));
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ mutable borrow occurs here
5 |     println!("newest was {newest}");
  |                           ------ immutable borrow later used here

last() returns a reference into the buffer, and push may reallocate the buffer, so the two cannot overlap. You saw this error shape in lesson 5. The usual fixes: print newest before the push, or take an owned copy with queue.last().cloned(), which gives an Option<String> that does not borrow the vector.

Useful Vec methods

fn main() {
    let mut marks = vec![67, 92, 45, 92, 78, 30, 67];

    marks.sort();
    println!("sorted:    {marks:?}");
    marks.dedup();
    println!("dedup:     {marks:?}");
    marks.retain(|&m| m >= 40);
    println!("passed:    {marks:?}");
    marks.reverse();
    println!("reversed:  {marks:?}");

    let mut names = vec!["zoya", "Arun", "meena", "Bala"];
    names.sort_by_key(|n| n.to_lowercase());
    println!("names:     {names:?}");

    let mut v = vec!['a', 'b', 'c', 'd'];
    let taken = v.swap_remove(0);
    println!("swap_remove took {taken:?}, left {v:?}");

    let top_two: Vec<i32> = marks.iter().take(2).copied().collect();
    println!("top two:   {top_two:?}");
    println!(
        "max = {:?}, min = {:?}",
        marks.iter().max(),
        marks.iter().min()
    );
}

Output:

sorted:    [30, 45, 67, 67, 78, 92, 92]
dedup:     [30, 45, 67, 78, 92]
passed:    [45, 67, 78, 92]
reversed:  [92, 78, 67, 45]
names:     ["Arun", "Bala", "meena", "zoya"]
swap_remove took 'a', left ['d', 'b', 'c']
top two:   [92, 78]
max = Some(92), min = Some(45)

• sort sorts in place; it is a stable sort, which keeps equal elements in their original order. sort_unstable is usually faster and is fine when stability does not matter.
• dedup removes consecutive duplicates only, which is why it is normally used right after sorting.
• retain keeps the elements for which the closure returns true. It is the idiomatic way to delete elements while scanning, without fighting the borrow checker.
• sort_by_key sorts by a computed key; here, case-insensitively.
• swap_remove(0) removes an element in O(1) by moving the last element into its place. Use it when order does not matter; remove keeps order but shifts every later element, which is O(n).
• iter().max() returns Option<&T>, because an empty vector has no maximum.

String and &str

Rust has two main string types, and knowing which to use where is a core skill:

A String is essentially a Vec<u8> with a promise that the bytes are valid UTF-8. A &str is to a String what a &[T] is to a Vec<T>.

Building and changing strings

fn main() {
    let mut s = String::new();
    s.push_str("Namaste");
    s.push(',');
    s.push_str(" Rust");

    let from_literal = String::from("hello");
    let also = "hello".to_string();
    println!(
        "{s} | {from_literal} | {also} | equal: {}",
        from_literal == also
    );

    let first = String::from("tic");
    let second = String::from("tac");
    let joined = first + "-" + &second + "-toe";
    println!("{joined}");

    let formatted = format!("{}-{}-{}", "tic", second, "toe");
    println!("{formatted}");

    let words = ["ready", "steady", "go"];
    println!("{}", words.join(", "));

    let line = "  name = Priya  ";
    let trimmed = line.trim();
    if let Some((key, value)) = trimmed.split_once('=') {
        println!("key = {:?}, value = {:?}", key.trim(), value.trim());
    }
    println!("upper: {}", trimmed.to_uppercase());
    println!("replace: {}", trimmed.replace("Priya", "Anil"));
    println!("starts with name? {}", trimmed.starts_with("name"));
}

Output:

Namaste, Rust | hello | hello | equal: true
tic-tac-toe
tic-tac-toe
ready, steady, go
key = "name", value = "Priya"
upper: NAME = PRIYA
replace: name = Anil
starts with name? true

• push_str appends a &str and push appends one char.
• String::from("hello") and "hello".to_string() do the same thing. == compares contents, not addresses (unlike == on Java strings).
• first + "-" + &second + "-toe" uses the + operator, explained below.
• format! works like println! but returns a String. It borrows its arguments and never moves them, so it is usually the clearest way to combine several pieces.
• join concatenates a list with a separator.
• trim, split_once, to_uppercase, replace and starts_with are a few of the many text methods. Methods that return parts of the text, like trim and split_once, return &str slices borrowing the original, with no allocation. Methods that create new text, like to_uppercase and replace, return a new String.

Reading the compiler errors: what + does to a String

The + operator on strings calls a method with this signature:

fn add(self, s: &str) -> String

It takes the left-hand String by value (moving it), appends the right-hand &str to its buffer, and returns the same buffer. This is efficient, because it reuses the left string's allocation instead of copying both. But it has two consequences, and both produce errors.

First, the left operand is moved. This does not compile:

fn main() {
    let first = String::from("tic");
    let second = String::from("tac");
    let joined = first + &second;
    println!("{joined} came from {first}");
}

error[E0382]: borrow of moved value: `first`
 --> plus_err.rs:5:35
  |
2 |     let first = String::from("tic");
  |         ----- move occurs because `first` has type `String`, which does not implement the `Copy` trait
3 |     let second = String::from("tac");
4 |     let joined = first + &second;
  |                  ----- value moved here
5 |     println!("{joined} came from {first}");
  |                                   ^^^^^ value borrowed here after move
  |
help: consider cloning the value if the performance cost is acceptable
  |
4 |     let joined = first.clone() + &second;
  |                       ++++++++

Second, the right operand must be a &str, not a String. This does not compile:

fn main() {
    let first = String::from("tic");
    let second = String::from("tac");
    let joined = first + second;
    println!("{joined}");
}

error[E0308]: mismatched types
 --> plus_ref_err.rs:4:26
  |
4 |     let joined = first + second;
  |                          ^^^^^^ expected `&str`, found `String`
  |
help: consider borrowing here
  |
4 |     let joined = first + &second;
  |                          +

&second is a &String, which deref coercion turns into the &str that add wants. When you need both inputs afterwards, or are joining more than two pieces, use format!("{first}{second}") instead.

UTF-8: why strings are more complicated

Rust strings are always valid UTF-8, the dominant text encoding on the web. UTF-8 stores each Unicode character in 1 to 4 bytes: ASCII characters take 1 byte, most accented Latin, Greek and Cyrillic letters take 2, most Indian scripts, Chinese and Japanese take 3, and emoji take 4.

A Rust char is a Unicode scalar value: a single code point, always 4 bytes when stored on its own. Inside a String, characters are stored in their compact UTF-8 form, not as chars.

fn main() {
    for word in ["Rust", "café", "नमस्ते", "🦀"] {
        println!(
            "{word}: len() = {}, chars().count() = {}",
            word.len(),
            word.chars().count()
        );
    }

    let word = "café";
    println!("bytes: {:?}", word.as_bytes());
    println!("chars: {:?}", word.chars().collect::<Vec<char>>());
    for (i, c) in word.char_indices() {
        println!("char {c:?} starts at byte {i}");
    }

    let hindi = "नमस्ते";
    let chars: Vec<char> = hindi.chars().collect();
    println!("{} chars: {:?}", chars.len(), chars);
}

Output:

Rust: len() = 4, chars().count() = 4
café: len() = 5, chars().count() = 4
नमस्ते: len() = 18, chars().count() = 6
🦀: len() = 4, chars().count() = 1
bytes: [99, 97, 102, 195, 169]
chars: ['c', 'a', 'f', 'é']
char 'c' starts at byte 0
char 'a' starts at byte 1
char 'f' starts at byte 2
char 'é' starts at byte 3
6 chars: ['न', 'म', 'स', '\u{94d}', 'त', '\u{947}']

Reading the results:

• len() returns the length in bytes, not characters. "café" has 4 characters but 5 bytes, because é takes 2 bytes (195 and 169).
• "नमस्ते" (namaste) has 6 chars in 18 bytes: each Devanagari code point takes 3 bytes.
• The crab emoji is a single char taking 4 bytes.
• Not every char is what a reader would call a letter. Two of the six chars in "नमस्ते" are combining marks, shown as '\u{94d}' (the virama) and '\u{947}' (a vowel sign), which attach to the letter before them when displayed. What a reader perceives as one character is a grapheme cluster, and it can be several chars. The standard library does not split text into grapheme clusters; the unicode-segmentation crate does.

"café" as bytes:  0     1     2     3     4
                +-----+-----+-----+-----+-----+
                | 99  | 97  | 102 | 195 | 169 |
                +-----+-----+-----+-----+-----+
                  'c'   'a'   'f'   \___'é'___/
char_indices:     0     1     2     3

Reading the compiler error: you cannot index a string

In Python, "hello"[0] gives "h". In Rust, this does not compile:

fn main() {
    let word = String::from("hello");
    let first = word[0];
    println!("{first}");
}

error[E0277]: the type `str` cannot be indexed by `{integer}`
 --> index_err.rs:3:22
  |
3 |     let first = word[0];
  |                      ^ string indices are ranges of `usize`
  |
  = help: the trait `SliceIndex<str>` is not implemented for `{integer}`
  = note: you can use `.chars().nth()` or `.bytes().nth()`
          for more information, see chapter 8 in The Book: <https://doc.rust-lang.org/book/ch08-02-strings.html#indexing-into-strings>

The message says string indices must be ranges, and the note points to .chars().nth() and .bytes().nth(). Rust refuses s[0] for three reasons:

1. It is ambiguous. Should s[0] be the first byte, the first char, or the first grapheme cluster? For ASCII text they agree; for "नमस्ते" they are three different things.
2. A byte is often not a character. Returning the byte 195 for the first position of "éclair" would be meaningless to most callers.
3. It would not be O(1). Indexing is expected to take constant time. Finding the n-th char requires walking the UTF-8 bytes from the start, because characters have different widths, so it is O(n). Rust makes that cost visible by making you write .chars().nth(n).

Slicing with a byte range, &s[0..3], is allowed, but panics if a boundary falls inside a character, as lesson 5 showed.

Working with characters and bytes

fn main() {
    let word = String::from("café");

    let third = word.chars().nth(2);
    println!("third char: {third:?}");

    let first_two: String = word.chars().take(2).collect();
    println!("first two chars: {first_two}");

    let reversed: String = word.chars().rev().collect();
    println!("reversed: {reversed}");

    let b = word.as_bytes()[0];
    println!("first byte: {b} ({:?})", b as char);

    println!("byte 3 is a char boundary? {}", word.is_char_boundary(3));
    println!("byte 4 is a char boundary? {}", word.is_char_boundary(4));
}

Output:

third char: Some('f')
first two chars: ca
reversed: éfac
first byte: 99 ('c')
byte 3 is a char boundary? true
byte 4 is a char boundary? false

as_bytes()[0] is fine for ASCII work, and b as char converts a byte back to a char, which is only correct for ASCII bytes. Byte 4 of "café" is in the middle of é, so it is not a char boundary.

HashMap<K, V>

A HashMap<K, V> stores key-value pairs and finds the value for a key in O(1) time on average, using a hash function that turns each key into a number that picks a bucket. It is Rust's version of a Python dict or a Java HashMap. It is not in the prelude, so you import it with use std::collections::HashMap;.

use std::collections::HashMap;

fn main() {
    let mut stock: HashMap<String, u32> = HashMap::new();
    stock.insert(String::from("pens"), 40);
    stock.insert(String::from("notebooks"), 12);
    stock.insert(String::from("erasers"), 25);

    println!("pens: {:?}", stock.get("pens"));
    println!("staplers: {:?}", stock.get("staplers"));
    println!("notebooks: {}", stock["notebooks"]);

    let old = stock.insert(String::from("pens"), 35);
    println!("replaced pens, old value {old:?}");

    if let Some(n) = stock.get_mut("erasers") {
        *n -= 5;
    }

    let removed = stock.remove("notebooks");
    println!("removed notebooks: {removed:?}, {} keys left", stock.len());

    let mut items: Vec<(&String, &u32)> = stock.iter().collect();
    items.sort();
    for (name, count) in items {
        println!("{name}: {count}");
    }
}

Output:

pens: Some(40)
staplers: None
notebooks: 12
replaced pens, old value Some(40)
removed notebooks: Some(12), 2 keys left
erasers: 20
pens: 35

• insert(key, value) adds a pair. If the key was already present, the value is replaced and the old one is returned as Some(old).
• get(&key) returns Option<&V>. A HashMap<String, u32> can be queried with a plain &str (stock.get("pens")), so you do not need to build a String just to look something up.
• map[&key] returns the value directly, but panics if the key is missing, just like indexing a Vec.
• get_mut returns Option<&mut V>, for changing a value in place.
• remove takes the pair out and returns Option<V>.

Iteration order is not defined

The example above sorts the pairs before printing them. That is not decoration. A HashMap's iteration order depends on the hash values, and Rust's default hasher is seeded randomly for each map to resist HashDoS attacks, where an attacker sends keys chosen to collide and make every lookup slow. So the order can differ between runs of the same program:

use std::collections::HashMap;

fn main() {
    let mut m = HashMap::new();
    for (i, w) in ["one", "two", "three", "four", "five"].iter().enumerate() {
        m.insert(*w, i);
    }
    let keys: Vec<_> = m.keys().collect();
    println!("{keys:?}");
}

Output of three runs:

["four", "three", "five", "two", "one"]
["three", "two", "one", "five", "four"]
["five", "three", "two", "one", "four"]

If you need a stable order, sort the keys when you need them, or use a BTreeMap, which keeps keys sorted. Python programmers should note that this is different from Python 3.7+, where a dict remembers insertion order.

The entry API

A very common task is "update the value for this key, or insert a starting value if the key is new". Doing that with get followed by insert looks up the key twice and is awkward with borrowing. The entry API does it in one lookup: map.entry(key) returns an Entry, which is either occupied or vacant, and its methods handle both cases.

use std::collections::HashMap;

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

    let mut counts: HashMap<&str, u32> = HashMap::new();
    for word in text.split_whitespace() {
        *counts.entry(word).or_insert(0) += 1;
    }

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

    let mut groups: HashMap<usize, Vec<&str>> = HashMap::new();
    for word in ["go", "rust", "c", "java", "zig", "ruby"] {
        groups.entry(word.len()).or_default().push(word);
    }
    let mut lengths: Vec<_> = groups.keys().copied().collect();
    lengths.sort();
    for len in lengths {
        println!("{len} letters: {:?}", groups[&len]);
    }

    let mut visits: HashMap<&str, u32> = HashMap::new();
    for page in ["/home", "/about", "/home"] {
        visits.entry(page).and_modify(|n| *n += 1).or_insert(1);
    }
    println!("/home visited {} times", visits["/home"]);
}

Output:

top three: [("the", 3), ("brown", 1), ("dog", 1)]
1 letters: ["c"]
2 letters: ["go"]
3 letters: ["zig"]
4 letters: ["rust", "java", "ruby"]
/home visited 2 times

Three patterns to remember:

or_insert returns a mutable reference to the value inside the map, which is why the counting line needs * to add to it. In the word count, "the" appears 3 times; the other words appear once each, and the sort breaks ties alphabetically, so "brown" and "dog" come next.

Ownership of keys and values

Inserting into a map moves owned keys and values into it. This does not compile:

use std::collections::HashMap;

fn main() {
    let name = String::from("Asha");
    let mut ages = HashMap::new();
    ages.insert(name, 31);
    println!("{name} is {}", ages["Asha"]);
}

error[E0382]: borrow of moved value: `name`
 --> map_move_err.rs:7:16
  |
4 |     let name = String::from("Asha");
  |         ---- move occurs because `name` has type `String`, which does not implement the `Copy` trait
5 |     let mut ages = HashMap::new();
6 |     ages.insert(name, 31);
  |                 ---- value moved here
7 |     println!("{name} is {}", ages["Asha"]);
  |                ^^^^ value borrowed here after move
  |
help: consider cloning the value if the performance cost is acceptable
  |
6 |     ages.insert(name.clone(), 31);
  |                     ++++++++

The map now owns the String "Asha". Either clone it before inserting, or read it back from the map. Copy types like u32 are copied, so the value 31 is unaffected. You can also store references (HashMap<&str, u32>, as in the word count), but then the map cannot outlive the text it borrows from.

Other collections: HashSet, BTreeMap and VecDeque

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

fn main() {
    let python: HashSet<&str> = ["Asha", "Ravi", "Meena"].into_iter().collect();
    let rust: HashSet<&str> = ["Ravi", "Kabir", "Meena"].into_iter().collect();

    let mut both: Vec<_> = python.intersection(&rust).collect();
    both.sort();
    let mut either: Vec<_> = python.union(&rust).collect();
    either.sort();
    let mut only_python: Vec<_> = python.difference(&rust).collect();
    only_python.sort();
    println!("both: {both:?}");
    println!("either: {either:?}");
    println!("only python: {only_python:?}");

    let mut seen = HashSet::new();
    let ids = [4, 7, 4, 9, 7];
    let first_repeat = ids.iter().find(|id| !seen.insert(**id));
    println!("first repeated id: {first_repeat:?}");

    let mut marks = BTreeMap::new();
    marks.insert("Meena", 91);
    marks.insert("Asha", 78);
    marks.insert("Ravi", 85);
    println!("sorted by name: {marks:?}");
    let from_b: Vec<_> = marks.range("B"..).collect();
    println!("names from B onwards: {from_b:?}");

    let mut queue = VecDeque::new();
    queue.push_back("customer 1");
    queue.push_back("customer 2");
    queue.push_front("VIP");
    while let Some(next) = queue.pop_front() {
        println!("serving {next}");
    }
}

Output:

both: ["Meena", "Ravi"]
either: ["Asha", "Kabir", "Meena", "Ravi"]
only python: ["Asha"]
first repeated id: Some(4)
sorted by name: {"Asha": 78, "Meena": 91, "Ravi": 85}
names from B onwards: [("Meena", 91), ("Ravi", 85)]
serving VIP
serving customer 1
serving customer 2

HashSet<T> stores unique values with O(1) average membership checks; it is a HashMap with no values. It supports set operations: intersection, union and difference. Like HashMap, its order is unspecified, which is why the example sorts before printing. insert returns false if the value was already present, which makes "find the first duplicate" a one-liner.

BTreeMap<K, V> keeps its keys in sorted order, in a B-tree (a balanced tree whose nodes hold many keys each, which suits CPU caches well). Lookups are O(log n) rather than O(1), but iteration is always in key order, and you can ask for ranges: marks.range("B"..) gives every key from "B" onwards. BTreeSet<T> is the matching set.

VecDeque<T> is a double-ended queue: a ring buffer that supports O(1) push and pop at both ends. A Vec is fast only at the back; removing from its front is O(n). Use VecDeque for queues, breadth-first search and sliding windows.

There is also BinaryHeap<T>, a priority queue that always pops the largest element, and LinkedList<T>, which is rarely the right choice because of poor cache behaviour.

Choosing a collection

A quick decision guide:

Need key -> value lookups?
  yes: need keys in sorted order or range queries?
         yes -> BTreeMap      no -> HashMap
  no:  need uniqueness / membership checks?
         yes: sorted? -> BTreeSet, else HashSet
         no:  adding/removing at the front too?
                yes -> VecDeque
                no:  always need the largest first? -> BinaryHeap
                     otherwise                      -> Vec

When in doubt, start with Vec. For small collections, a linear scan over a Vec is often faster than hashing, because the elements sit together in memory.

Idioms and pitfalls

Exercises

Exercise 1: group anagrams

Group these words into anagram families and print the groups in a stable order: listen, silent, enlist, google, inlets, banana, gogole.

use std::collections::BTreeMap;

fn main() {
    let words = [
        "listen", "silent", "enlist", "google", "inlets", "banana", "gogole",
    ];
    let mut groups: BTreeMap<String, Vec<&str>> = BTreeMap::new();
    for word in words {
        let mut letters: Vec<char> = word.chars().collect();
        letters.sort_unstable();
        let key: String = letters.into_iter().collect();
        groups.entry(key).or_default().push(word);
    }
    for (key, group) in &groups {
        println!("{key}: {group:?}");
    }
}

aaabnn: ["banana"]
eggloo: ["google", "gogole"]
eilnst: ["listen", "silent", "enlist", "inlets"]

Exercise 2: first non-repeating character

Write fn first_unique(text: &str) -> Option<char> that works on any Unicode text, not just ASCII.

use std::collections::HashMap;

fn first_unique(text: &str) -> Option<char> {
    let mut counts: HashMap<char, usize> = HashMap::new();
    for c in text.chars() {
        *counts.entry(c).or_insert(0) += 1;
    }
    text.chars().find(|c| counts[c] == 1)
}

fn main() {
    for text in ["swiss", "aabbcc", "रामराम!", ""] {
        println!("{text:?} -> {:?}", first_unique(text));
    }
}

"swiss" -> Some('w')
"aabbcc" -> None
"रामराम!" -> Some('!')
"" -> None

Exercise 3: two sum

Given a slice of numbers and a target, return the indices of two numbers that add up to the target, in O(n) time.

use std::collections::HashMap;

fn two_sum(nums: &[i32], target: i32) -> Option<(usize, usize)> {
    let mut seen: HashMap<i32, usize> = HashMap::new();
    for (i, &n) in nums.iter().enumerate() {
        if let Some(&j) = seen.get(&(target - n)) {
            return Some((j, i));
        }
        seen.insert(n, i);
    }
    None
}

fn main() {
    println!("{:?}", two_sum(&[2, 7, 11, 15], 9));
    println!("{:?}", two_sum(&[3, 2, 4], 6));
    println!("{:?}", two_sum(&[1, 2, 3], 100));
}

Some((0, 1))
Some((1, 2))
None

Exercise 4: title case

Write fn title_case(text: &str) -> String that capitalises the first letter of each word, lowercases the rest, and collapses repeated spaces.

fn title_case(text: &str) -> String {
    let mut words: Vec<String> = Vec::new();
    for word in text.split_whitespace() {
        let mut chars = word.chars();
        let titled = match chars.next() {
            Some(first) => {
                first.to_uppercase().collect::<String>() + &chars.as_str().to_lowercase()
            }
            None => String::new(),
        };
        words.push(titled);
    }
    words.join(" ")
}

fn main() {
    println!("{}", title_case("the  rUST programming   LANGUAGE"));
    println!("{}", title_case("élan vital"));
}

The Rust Programming Language
Élan Vital

Exercise 5: recently visited pages

Keep the three most recently visited pages, newest first, without duplicates. Use a VecDeque.

use std::collections::VecDeque;

struct Recent {
    items: VecDeque<String>,
    limit: usize,
}

impl Recent {
    fn new(limit: usize) -> Self {
        Self {
            items: VecDeque::with_capacity(limit),
            limit,
        }
    }

    fn visit(&mut self, page: &str) {
        if let Some(pos) = self.items.iter().position(|p| p == page) {
            self.items.remove(pos);
        }
        self.items.push_front(page.to_string());
        if self.items.len() > self.limit {
            self.items.pop_back();
        }
    }
}

fn main() {
    let mut recent = Recent::new(3);
    for page in ["/home", "/jobs", "/learn", "/home", "/practice"] {
        recent.visit(page);
        println!("{page:<10} -> {:?}", recent.items);
    }
}

/home      -> ["/home"]
/jobs      -> ["/jobs", "/home"]
/learn     -> ["/learn", "/jobs", "/home"]
/home      -> ["/home", "/learn", "/jobs"]
/practice  -> ["/practice", "/home", "/learn"]

Interview questions

Q1. What is the difference between String and &str?

String is an owned, growable, heap-allocated UTF-8 buffer (pointer, length, capacity). &str is a borrowed slice of UTF-8 text (pointer and length) that can point into a String, into the program binary for literals, or anywhere else. Functions that only read text should take &str; use String when you need to own or change the text.

Q2. Why can you not index a String with s[0]?

Strings are UTF-8, so a byte position is not a character position, and it is unclear whether s[0] should mean a byte, a char or a grapheme cluster. Indexing is also expected to be O(1), but finding the n-th character requires scanning from the start. Rust makes you choose explicitly with s.chars().nth(0), s.as_bytes()[0] or a byte-range slice.

Q3. What does len() return for a String?

The number of bytes, not characters. "café" has len() 5 but 4 chars, and a Devanagari word can have three times as many bytes as chars. Use chars().count() for code points, and a grapheme segmentation crate for user-perceived characters.

Q4. How does Vec grow, and what is the cost of push?

A Vec keeps a capacity larger than its length; when a push finds no room, it allocates a larger buffer (growing geometrically, roughly doubling in the current implementation), moves the elements and frees the old buffer. That occasional O(n) copy is spread over many cheap pushes, so push is amortised O(1). with_capacity and reserve avoid repeated reallocations when the size is known.

Q5. What is the difference between v[i] and v.get(i)?

v[i] returns the element directly and panics if i is out of bounds. v.get(i) returns Option<&T>, with None for a bad index, so the caller must handle that case. Use indexing when an invalid index would be a bug, and get when the index comes from input.

Q6. Why does pushing to a Vec while holding a reference to an element fail to compile?

A push may reallocate the buffer, which would leave the reference pointing to freed memory. The reference is a shared borrow and push needs a mutable borrow, so the borrow checker reports E0502. Finish using the reference first, copy or clone the value, or store an index instead.

Q7. What is the entry API, and why use it?

map.entry(key) looks the key up once and returns an Entry that is either occupied or vacant, with methods such as or_insert, or_default, or_insert_with and and_modify. It replaces the get-then-insert pattern, which does two lookups and is awkward to write with borrowing. Word counting is the classic example: *counts.entry(word).or_insert(0) += 1.

Q8. Why is HashMap iteration order random, and what if you need order?

Rust's default hasher (SipHash 1-3 at present) is seeded with random keys per map to resist HashDoS attacks, so the bucket layout, and therefore the iteration order, varies between runs. Do not rely on it. Use BTreeMap for sorted keys, sort the keys yourself, or use a crate such as indexmap for insertion order.

Q9. When would you use BTreeMap instead of HashMap?

When you need keys in sorted order, range queries such as "all keys between A and M", the smallest or largest key, or deterministic output. BTreeMap operations are O(log n) instead of O(1) average, and keys need Ord rather than Hash and Eq. For small maps the difference in speed is often negligible.

Q10. Why does s1 + &s2 move s1?

The + operator for String is implemented as add(self, &str) -> String: it takes the left string by value, appends the right-hand slice into its existing buffer and returns it, avoiding a new allocation. That makes s1 unusable afterwards. Use format! when you want to keep all inputs.

Q11. How do you remove elements from a Vec that match a condition?

Use retain, which keeps only the elements for which a closure returns true, in one O(n) pass that preserves order. Removing inside a for loop over the vector does not compile, and removing by index in a forward loop is error-prone because indices shift. swap_remove is O(1) for a single element when order does not matter.

Key takeaways

• Vec<T> is a pointer, length and capacity over a heap buffer; push is amortised O(1) and may reallocate.
• v[i] panics on a bad index; v.get(i) returns Option<&T>.
• for x in &v borrows, for x in &mut v borrows mutably, and for x in v consumes the vector.
• You cannot hold a reference into a collection across a change that needs &mut (E0502).
• String owns UTF-8 text and &str borrows it; take &str parameters, and use format! to combine strings.
• len() counts bytes; strings cannot be indexed by integer; use chars(), char_indices() or bytes() explicitly.
• HashMap gives O(1) average lookups with no defined order; the entry API handles insert-or-update in one lookup.
• Reach for HashSet for uniqueness, BTreeMap for sorted keys and ranges, and VecDeque for queues; default to Vec.

Next lesson

Continue with Error handling in Rust.