Collections and Strings

The standard collections

Rust's standard library has a small set of collections, all generic over the element type and all owning their elements: when the collection is dropped, everything in it is dropped too (see Ownership). The general ideas behind them are on Data Structures; this page is about how they behave in Rust.

Vec and String are always available; the others are imported from std::collections, for example use std::collections::BTreeMap;.

Vec: the growable list

A Vec (vector) stores elements of one type next to each other on the heap and grows as you push more: Rust's dynamic array. The vec![…] macro creates one with initial contents.

fn main() {
    let mut readings: Vec<u32> = Vec::new();
    readings.push(350);
    readings.push(412);
    readings.push(120);
    readings.extend([95, 401]);

    println!("{} readings: {readings:?}", readings.len());
    println!("first: {}, last: {:?}", readings[0], readings.last());
    println!("total: {} kWh", readings.iter().sum::<u32>());
    println!("contains 120: {}", readings.contains(&120));

    readings.sort();
    println!("sorted: {readings:?}");
    let removed = readings.remove(0); // shifts the rest one place left
    println!("removed {removed}, now {readings:?}");
}

5 readings: [350, 412, 120, 95, 401]
first: 350, last: Some(401)
total: 1378 kWh
contains 120: true
sorted: [95, 120, 350, 401, 412]
removed 95, now [120, 350, 401, 412]

readings[0] is checked at run time: an index past the end panics instead of reading other memory (see panics), and readings.get(i) returns None instead when a missing element is a normal case. last() is an Option for the same reason: an empty vector has no last element.

Like a String, a Vec is a small header (a pointer to the heap buffer, the length and the capacity, 24 bytes on a 64-bit Linux machine (ARM64)) plus the buffer itself. When the buffer is full, push allocates a larger one and moves the elements over. If you know the size in advance, reserve it once:

fn main() {
    // 96 quarter-hours in a normal day: reserve room for all of them at once.
    let mut quarter_hours: Vec<u16> = Vec::with_capacity(96);
    let reserved = quarter_hours.capacity();
    for q in 0..96 {
        quarter_hours.push(q * 10);
    }
    println!("len {}, room for 96: {}", quarter_hours.len(), reserved >= 96);
    println!("no reallocation needed: {}", quarter_hours.capacity() == reserved);
    let zeros = vec![0u32; 4];
    println!("{zeros:?}");
}

len 96, room for 96: true
no reallocation needed: true
[0, 0, 0, 0]

The example only prints whether there is at least enough room: the standard library promises that, not an exact capacity. (And a day in October with the clock change has 100 quarter-hours, which is why the vector grows rather than refusing the 97th.)

Slices: a view of part of a list

A slice, &[T], borrows a run of elements from a vector, an array or another slice without copying them. It is a pointer plus a length (16 bytes on a 64-bit Linux machine (ARM64)), so it always knows where it ends. Functions that only read a list should take a slice rather than &Vec<T>: then they accept a whole vector, an array and part of either.

// Takes a slice: works for a Vec, an array, or part of either.
fn average(readings: &[u32]) -> Option<u32> {
    if readings.is_empty() {
        return None;
    }
    Some(readings.iter().sum::<u32>() / readings.len() as u32)
}

fn main() {
    let week = vec![350, 412, 120, 95, 401, 388, 290];
    let weekend = [388, 290];
    println!("whole week: {:?}", average(&week));
    println!("first three days: {:?}", average(&week[0..3]));
    println!("weekend array: {:?}", average(&weekend));
    println!("nothing: {:?}", average(&week[7..]));
}

whole week: Some(293)
first three days: Some(294)
weekend array: Some(339)
nothing: None

&week turns into a slice of the whole vector by itself. Ranges are half-open: 0..3 is elements 0, 1 and 2, and 7.. on a seven-element vector is an empty slice, not an error. A range past the end, such as &week[5..9], panics. Clippy, Rust's linter, flags a &Vec<u32> parameter and suggests &[u32] (see Testing, Docs and Tooling). How long a slice may be kept is the subject of Borrowing and References: for example, you cannot push to a vector while a slice of it is still in use, because the push may move the buffer.

HashMap: fast lookup by key

A HashMap maps keys to values with a hash table: looking a key up takes about the same time whether the map holds ten entries or ten million. In this example it keeps the last power value seen per pilot home:

use std::collections::HashMap;

fn main() {
    let mut last_seen: HashMap<&str, u32> = HashMap::new();
    last_seen.insert("h0017", 412);
    last_seen.insert("h0042", 350);
    last_seen.insert("h0101", 120);
    last_seen.insert("h0017", 415); // same key: replaces the old value

    println!("{} homes", last_seen.len());
    println!("h0017: {:?}", last_seen.get("h0017"));
    println!("h0999: {:?}", last_seen.get("h0999"));
    if let Some(watts) = last_seen.get_mut("h0042") {
        *watts += 10;
    }
    println!("h0042: {}", last_seen["h0042"]);
    println!("removed h0101: {:?}", last_seen.remove("h0101"));
    println!("has h0101: {}", last_seen.contains_key("h0101"));
}

3 homes
h0017: Some(415)
h0999: None
h0042: 360
removed h0101: Some(120)
has h0101: false

get returns an Option, because the key may be missing; map["h0042"] panics for a missing key. get_mut gives a mutable reference to change a value in place.

Why the order changes on every run

The example above never prints the whole map, and that is deliberate. A HashMap visits its entries in an order that depends on a random key that each map gets when it is created. This program prints the keys of a map with four entries:

use std::collections::HashMap;

fn main() {
    let mut watts: HashMap<&str, u32> = HashMap::new();
    for (home, w) in [("h0017", 412), ("h0042", 350), ("h0101", 120), ("h0007", 95)] {
        watts.insert(home, w);
    }
    let homes: Vec<_> = watts.keys().collect();
    println!("{homes:?}");
}

$ ./h2
["h0017", "h0007", "h0101", "h0042"]
$ ./h2
["h0007", "h0042", "h0101", "h0017"]
$ ./h2
["h0101", "h0007", "h0017", "h0042"]

The reason is security. If the hash function were fixed, an attacker who can choose keys (field names in a web request, for example) could pick thousands that all land in the same bucket and make every lookup slow, a denial-of-service attack called HashDoS. Rust's default hasher, currently SipHash 1-3, is seeded randomly, so nobody can predict the buckets. The price is that the iteration order is meaningless, and that applies to integer keys too.

The entry API: count and sum per key

"Add this amount to the total for this key, starting at zero if the key is new" is so common that maps have a dedicated entry API. map.entry(key) looks the key up once and returns a handle to its slot, occupied or empty; .or_insert(0) fills an empty slot and returns a mutable reference to the value either way:

use std::collections::BTreeMap;

fn main() {
    let readings = [
        ("fixed", 350), ("dynamic", 120), ("fixed", 95),
        ("day_night", 412), ("dynamic", 64), ("fixed", 401),
    ];

    let mut kwh_per_tariff: BTreeMap<&str, u32> = BTreeMap::new();
    let mut count_per_tariff: BTreeMap<&str, usize> = BTreeMap::new();
    for (tariff, kwh) in readings {
        *kwh_per_tariff.entry(tariff).or_insert(0) += kwh;
        *count_per_tariff.entry(tariff).or_default() += 1;
    }
    for (tariff, kwh) in &kwh_per_tariff {
        println!("{tariff:10} {:>4} kWh in {} readings", kwh, count_per_tariff[tariff]);
    }
}

day_night   412 kWh in 1 readings
dynamic     184 kWh in 2 readings
fixed       846 kWh in 3 readings

The * in front writes through the returned reference. or_default() does the same with the type's default value (0 for numbers, an empty Vec for vectors). Without the entry API you would look the key up twice, once to check and once to insert or change. The example uses a BTreeMap, so the totals come out in alphabetical order; the entry API works identically on a HashMap.

BTreeMap: always sorted

A BTreeMap keeps its entries in a B-tree, sorted by key. Lookups take a little longer than in a HashMap (they grow with the logarithm of the size), but iteration is always in key order, the same on every run and every machine, and you can ask for the first, last or a range of keys:

use std::collections::BTreeMap;

fn main() {
    let mut watts: BTreeMap<&str, u32> = BTreeMap::new();
    for (home, w) in [("h0017", 412), ("h0042", 350), ("h0101", 120), ("h0007", 95)] {
        watts.insert(home, w);
    }
    println!("{watts:?}");
    for (home, w) in &watts {
        println!("{home}: {w} W");
    }
    println!("first: {:?}", watts.first_key_value());
    let middle: Vec<_> = watts.range("h0010".."h0100").collect();
    println!("h0010 to h0100: {middle:?}");
}

{"h0007": 95, "h0017": 412, "h0042": 350, "h0101": 120}
h0007: 95 W
h0017: 412 W
h0042: 350 W
h0101: 120 W
first: Some(("h0007", 95))
h0010 to h0100: [("h0017", 412), ("h0042", 350)]

The keys need an order (the Ord trait), where a HashMap needs Hash and Eq; for your own types you derive them (see deriving common behavior). A good rule: use BTreeMap for anything a person reads (reports, totals per tariff, configuration dumps) and for tests; use HashMap for large lookup tables where speed matters and order does not.

Sets: unique values

HashSet<T> and BTreeSet<T> are maps without values: they store each value once and answer "is it in there?" quickly. Set operations such as difference, intersection and union answer questions like "which homes did not report":

use std::collections::{BTreeSet, HashSet};

fn main() {
    let reports = ["h0042", "h0017", "h0042", "h0101", "h0017", "h0042"];

    let distinct: BTreeSet<&str> = reports.iter().copied().collect();
    println!("{} reports from {} homes: {distinct:?}", reports.len(), distinct.len());

    let expected: HashSet<&str> = ["h0017", "h0042", "h0101", "h0200"].into_iter().collect();
    let seen: HashSet<&str> = reports.iter().copied().collect();
    let mut silent: Vec<_> = expected.difference(&seen).collect();
    silent.sort();
    println!("no report from: {silent:?}");
    println!("h0200 reported: {}", seen.contains("h0200"));
}

6 reports from 3 homes: {"h0017", "h0042", "h0101"}
no report from: ["h0200"]
h0200 reported: false

collect() builds any collection from an iterator; the type annotation on the left says which one (see Iterators and Closures). The difference of two HashSets comes out in hash order, so it is sorted before printing.

String and &str

Rust has two main string types, and the difference is ownership. A String owns its text in a heap buffer and can grow, like a Vec<u8> that is guaranteed to hold valid UTF-8. A string slice, &str, borrows text that someone else owns: part of a String, or a string literal compiled into the program. Neither has a terminating zero byte; both store their length.

fn main() {
    let label: &str = "Kestrel Home";          // a string literal: &str, fixed text
    let mut status = String::from("dongle");   // an owned, growable String
    status.push(' ');
    status.push_str("KHP1-000231");
    status += " online";

    let line = format!("{label}: {status} ({} bytes)", status.len());
    println!("{line}");

    let first_word: &str = &status[0..6];      // a borrowed view into status
    println!("first word: {first_word}");
    println!("upper: {}", status.to_uppercase());
}

Kestrel Home: dongle KHP1-000231 online (25 bytes)
first word: dongle
upper: DONGLE KHP1-000231 ONLINE

Which one to use is mostly about ownership. Store a String in a struct that must keep the text (see Structs, Enums and Methods); take &str as a parameter when a function only reads text, because then it accepts both:

fn shout(text: &str) -> String {
    text.to_uppercase() + "!"
}

fn main() {
    let owned = String::from("meter offline");
    let literal = "meter online";
    println!("{}", shout(&owned));   // &String works where &str is expected
    println!("{}", shout(literal));
    println!("{}", shout(&owned[6..]));
}

METER OFFLINE!
METER ONLINE!
OFFLINE!

Ways to build strings: String::from("…") or "…".to_string() to get an owned copy, push for one character, push_str for text, and format! for anything with values in it. The + operator has a surprise: it takes the left-hand String by value, appends to its buffer and returns it, so the left side is gone afterward:

fn main() {
    let a = String::from("KHP1");
    let b = String::from("-000231");
    let serial = a + &b; // + takes a by value and borrows b
    println!("{serial}");
    println!("{a}");
}

example.rs:6:16: error[E0382]: borrow of moved value: `a`: value borrowed here after move

format!("{a}{b}") borrows both and is usually the clearer choice.

UTF-8: bytes are not characters

Every String and &str holds valid UTF-8, checked when the text is created. In UTF-8 a character takes one to four bytes, so the length in bytes and the number of characters differ as soon as the text is not plain ASCII:

fn main() {
    for text in ["kWh", "Größe", "€0.27", "Zoë"] {
        println!("{text:8} bytes {:2}  chars {}", text.len(), text.chars().count());
    }
    let name = "Größe";
    println!("bytes: {:?}", name.as_bytes());
    println!("chars: {:?}", name.chars().collect::<Vec<char>>());
    println!("reversed: {}", name.chars().rev().collect::<String>());
    println!("upper: {}", name.to_uppercase());
    println!("size of a char: {} bytes", size_of::<char>());
}

kWh      bytes  3  chars 3
Größe    bytes  7  chars 5
€0.27    bytes  7  chars 5
Zoë      bytes  4  chars 3
bytes: [71, 114, 195, 182, 195, 159, 101]
chars: ['G', 'r', 'ö', 'ß', 'e']
reversed: eßörG
upper: GRÖSSE
size of a char: 4 bytes

.len() is the number of bytes, which is what memory, files and network protocols care about. .chars() walks the Unicode code points; a char is one code point and always 4 bytes, unlike C's one-byte char. to_uppercase follows Unicode's rules, so ß becomes SS and the string gets longer. Even .chars() is not always "what a person sees as one letter": an emoji with a skin-tone modifier is several code points. Counting those visible characters needs a crate such as unicode-segmentation.

No indexing by number

Because a character can be several bytes, "the character at index 2" cannot be found without walking the string from the start, and "byte 2" might be half a character. Rust refuses to guess which one you mean:

fn main() {
    let name = String::from("Größe");
    let first = name[0];
    println!("{first}");
}

example.rs:3:22: error[E0277]: the type `str` cannot be indexed by `{integer}`: string indices are ranges of `usize`

error[E0277]: the type `str` cannot be indexed by `{integer}`
 --> example.rs:3:22
  |
3 |     let first = name[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 note names both ways out: .chars().nth(0) for the first character, .bytes().nth(0) or .as_bytes()[0] for the first byte. For text you parse, the string methods are usually better than any index: split, split_once, trim, strip_prefix, starts_with, find.

Slicing at a char boundary

Ranges are allowed, &name[0..2], but they count bytes, and both ends must fall on a char boundary: the first byte of a character, or the end of the string. A range that cuts a character in half would produce text that is not valid UTF-8, so it panics. .get(range) asks first and returns None instead:

fn main() {
    let name = "Größe";
    println!("{:?}", name.get(0..2));
    println!("{:?}", name.get(0..3));
    println!("{:?}", name.char_indices().nth(2));
    println!("{:?}", name.chars().next());
    println!("{}", &name[0..3]);
}

Some("Gr")
None
Some((2, 'ö'))
Some('G')
thread 'main' (48213) panicked at example.rs:7:25:
end byte index 3 is not a char boundary; it is inside 'ö' (bytes 2..4 of string)

char_indices() gives each character with the byte position where it starts, which is the safe way to find a place to cut. Byte positions returned by find and split_once are always on a boundary, so slicing with them is safe.

No silent buffer overflows

On Strings and Buffer Overflows in C, the serial number KHP1-000231 (11 characters) is copied into an 8-byte buffer and silently overwrites the memory next to it. In Rust, every string, vector and slice knows its own length, and every copy checks it. The same mistake stops with a clear message:

fn main() {
    let serial = String::from("KHP1-000231");
    let mut buffer = [0u8; 8]; // room for 8 bytes, as in the C example
    buffer.copy_from_slice(serial.as_bytes());
    println!("{buffer:?}");
}

thread 'main' (48213) panicked at example.rs:4:12:
copy_from_slice: source slice length (11) does not match destination slice length (8)

A panic is still a failure, but a safe one: nothing outside the buffer was touched, and the message says exactly what was wrong. Usually the better answer is not to use a fixed-size buffer at all: a String grows to fit. This is what "memory-safe language" means in practice (see memory-safe languages): the bug can still be written, but it can no longer corrupt memory.

Putting it together: totals per tariff

In this example, the reading tool from the previous pages reads meter;kwh;tariff lines from standard input, sums the kWh per tariff in a BTreeMap (so the report is in the same order every time), counts distinct meters in a BTreeSet and keeps the lines it could not use:

use std::collections::{BTreeMap, BTreeSet};
use std::io;

fn main() {
    let mut kwh_per_tariff: BTreeMap<String, u64> = BTreeMap::new();
    let mut meters: BTreeSet<String> = BTreeSet::new();
    let mut rejected: Vec<String> = Vec::new();

    for line in io::stdin().lines() {
        let line = line.expect("stdin is readable");
        let fields: Vec<&str> = line.split(';').map(str::trim).collect();
        let [meter, kwh, tariff] = fields[..] else {
            rejected.push(line);
            continue;
        };
        let Ok(kwh) = kwh.parse::<u64>() else {
            rejected.push(line);
            continue;
        };
        meters.insert(meter.to_string());
        *kwh_per_tariff.entry(tariff.to_lowercase()).or_insert(0) += kwh;
    }

    for (tariff, kwh) in &kwh_per_tariff {
        println!("{tariff:10} {kwh:>5} kWh");
    }
    println!("meters: {}", meters.len());
    println!("rejected: {rejected:?}");
}

day_night    412 kWh
dynamic      184 kWh
fixed        445 kWh
meters: 4
rejected: ["M-30010;abc;fixed", "M-30011;80"]

Two details make the tool tolerant about format while staying strict about content: map(str::trim) removes stray spaces around fields (" 412 " is accepted), and to_lowercase() treats Dynamic and dynamic as the same tariff. A line with the wrong number of fields or a kWh value that is not a number is rejected, not guessed at. let [meter, kwh, tariff] = fields[..] else { … } is a let-else with a slice pattern: it matches only a slice of exactly three elements (see Control Flow and Pattern Matching).