Collections: Vec and HashMap

Arrays and tuples have a size fixed at compile time. Most programs don't know up front how many items they will deal with: lines in a file, players in a game, orders in a shop. For that, the standard library has collections, types that store any number of values on the heap and grow or shrink as the program runs.

This lesson covers the two you will use most:

• Vec<T>, a growable list of values of one type, kept in order.
• HashMap<K, V>, a set of key-value pairs where you look a value up by its key.

Both own their contents, so everything from the ownership lesson applies: putting a String in a collection moves it there, and a reference into a collection borrows the whole collection.

A Vec<T> (a "vector") holds values of type T next to each other in memory, like an array whose length can change. There are two common ways to make one:

fn main() {
    let mut scores: Vec<u32> = Vec::new();
    scores.push(40);
    scores.push(75);
 
    let primes = vec![2, 3, 5, 7];
    let zeros = vec![0.0; 4];
 
    println!("{scores:?}");
    println!("{primes:?}");
    println!("{zeros:?}");
}

[40, 75]
[2, 3, 5, 7]
[0.0, 0.0, 0.0, 0.0]

• Vec::new() makes an empty vector. With nothing in it yet, Rust can't infer the element type from the right-hand side, so it comes from the annotation or from how the vector is used later.
• The vec! macro builds a vector from a list of values, or from [value; count] like an array.
• push adds a value to the end. It changes the vector, so the variable has to be mut.

Every element must have the same type. To store "one of several kinds" of value, make a Vec of an enum.

You can read an element by index with [], or with the get method:

fn main() {
    let planets = vec!["Mercury", "Venus", "Earth", "Mars"];
 
    let third = planets[2];
    println!("third: {third}");
 
    match planets.get(10) {
        Some(name) => println!("found {name}"),
        None => println!("there is no planet at index 10"),
    }
 
    println!("{} planets, first is {:?}", planets.len(), planets.first());
    println!("has Mars? {}", planets.contains(&"Mars"));
}

third: Earth
there is no planet at index 10
4 planets, first is Some("Mercury")
has Mars? true

The difference is what happens when the index is past the end. planets[10] panics and stops the program, just like an array. planets.get(10) returns an Option: Some(&element) if the index exists and None if it doesn't, so the "missing" case is a normal value you handle with match or if let. Use [] when a bad index would be a bug, and get when the index comes from outside (user input, a file) and might not be there.

A Vec<T> can be used anywhere a slice &[T] is expected, so every slice method from the slices lesson (len, first, last, contains, iter, sort, split_at and the rest) works on a vector too. A function that only reads a list should take &[T], which accepts both arrays and vectors.

Besides push, a vector can remove from the end, insert and remove in the middle, and grow from another collection:

fn main() {
    let mut queue = vec!['b', 'c', 'd'];
 
    queue.insert(0, 'a');
    println!("after insert: {queue:?}");
 
    let last = queue.pop();
    println!("popped {last:?}, left {queue:?}");
 
    let removed = queue.remove(1);
    println!("removed {removed}, left {queue:?}");
 
    queue.extend(['x', 'y', 'z']);
    println!("after extend: {queue:?}");
 
    queue.retain(|letter| *letter != 'y');
    println!("after retain: {queue:?}");
 
    queue.truncate(2);
    println!("after truncate: {queue:?}");
 
    queue.clear();
    println!("empty? {}", queue.is_empty());
}

after insert: ['a', 'b', 'c', 'd']
popped Some('d'), left ['a', 'b', 'c']
removed b, left ['a', 'c']
after extend: ['a', 'c', 'x', 'y', 'z']
after retain: ['a', 'c', 'x', 'z']
after truncate: ['a', 'c']
empty? true

pop returns an Option because the vector may be empty. insert and remove panic if the index is out of range, so check it first when it could be. retain takes a closure, a small inline function written |parameter| body; closures get their own lesson later. insert and remove shift every element after the index, so on a long vector they are slower than push and pop, which only touch the end.

A for loop can walk a vector in three ways, depending on whether you want to read the elements, change them, or take them:

fn main() {
    let mut prices = vec![120, 80, 45];
 
    let mut total = 0;
    for price in &prices {
        total += price;
    }
    println!("total: {total}");
 
    for price in &mut prices {
        *price += 10;
    }
    println!("{prices:?}");
 
    for (position, price) in prices.iter().enumerate() {
        println!("#{position}: {price}");
    }
 
    let names = vec![String::from("tea"), String::from("cake")];
    for name in names {
        println!("{}", name.to_uppercase());
    }
    // `names` was moved into the loop and can't be used here.
}

total: 245
[130, 90, 55]
#0: 130
#1: 90
#2: 55
TEA
CAKE

• for x in &v borrows the vector and gives you a &T for each element.
• for x in &mut v borrows it mutably and gives you a &mut T; write through it with *x.
• for x in v consumes the vector: each element is moved out to you, and the vector is gone after the loop. Use it when you are done with the vector, for example to move its Strings somewhere else.

.iter().enumerate() pairs each element with its index, which is usually clearer than looping over 0..v.len() and indexing.

A vector owns what's in it. Pushing a String moves it into the vector, and reading an element out needs a reference or a clone:

fn main() {
    let mut guests = Vec::new();
    let host = String::from("Ada");
    guests.push(host);
    // `host` has moved into `guests`.
 
    let first: &String = &guests[0];
    println!("first guest: {first}");
 
    let copy: String = guests[0].clone();
    guests.push(String::from("Grace"));
    println!("{copy} and {guests:?}");
}

first guest: Ada
Ada and ["Ada", "Grace"]

let first = guests[0]; would not compile: it would move the String out of the vector and leave a hole. Integers and other Copy types are copied out instead, which is why planets[2] worked above.

When the vector is dropped, it drops every element with it.

A HashMap<K, V> maps keys of type K to values of type V. Each key appears at most once, and finding the value for a key is fast no matter how big the map gets. It isn't in the prelude, so bring it into scope with use:

use std::collections::HashMap;
 
fn main() {
    let mut capitals = HashMap::new();
    capitals.insert("France", "Paris");
    capitals.insert("Japan", "Tokyo");
    capitals.insert("Kenya", "Nairobi");
 
    println!("{} countries", capitals.len());
 
    if let Some(city) = capitals.get("Japan") {
        println!("the capital of Japan is {city}");
    }
 
    match capitals.get("Peru") {
        Some(city) => println!("the capital of Peru is {city}"),
        None => println!("no entry for Peru"),
    }
 
    println!("has Kenya? {}", capitals.contains_key("Kenya"));
 
    let removed = capitals.remove("France");
    println!("removed {removed:?}, {} left", capitals.len());
}

3 countries
the capital of Japan is Tokyo
no entry for Peru
has Kenya? true
removed Some("Paris"), 2 left

• HashMap::new() makes an empty map. The key and value types are inferred from the first insert, here HashMap<&str, &str>.
• get(&key) returns an Option<&V>, since the key may not be there.
• remove(&key) takes the entry out and returns its value as an Option<V>.

You can also build a map from an array of (key, value) tuples: HashMap::from([("France", "Paris"), ("Japan", "Tokyo")]).

A key can only appear once. Inserting a key that's already there replaces the old value, and insert hands the old value back:

use std::collections::HashMap;
 
fn main() {
    let mut stock = HashMap::new();
 
    let before = stock.insert("apples", 12);
    println!("first insert returned {before:?}");
 
    let before = stock.insert("apples", 30);
    println!("second insert returned {before:?}");
 
    println!("apples in stock: {}", stock["apples"]);
}

first insert returned None
second insert returned Some(12)
apples in stock: 30

map[key] reads a value directly, like indexing a vector, and panics if the key is missing. Prefer get unless the key is certain to be there.

get_mut gives you a mutable reference to a value, if the key exists:

use std::collections::HashMap;
 
fn main() {
    let mut lives = HashMap::from([("mario", 3), ("luigi", 2)]);
 
    if let Some(count) = lives.get_mut("luigi") {
        *count += 1;
    }
 
    println!("luigi has {} lives", lives["luigi"]);
}

luigi has 3 lives

A for loop over &map gives you (&key, &value) pairs. The order is not defined: it depends on the hashing and can differ from one run of the program to the next. If the order matters, collect the keys and sort them, or use BTreeMap, which has the same methods and always iterates in key order:

use std::collections::{BTreeMap, HashMap};
 
fn main() {
    let heights = HashMap::from([("oak", 28), ("birch", 19), ("pine", 35)]);
 
    let mut names: Vec<&str> = heights.keys().copied().collect();
    names.sort();
    for name in names {
        println!("{name}: {} m", heights[name]);
    }
 
    let sorted = BTreeMap::from([("oak", 28), ("birch", 19), ("pine", 35)]);
    for (name, height) in &sorted {
        println!("{name} is {height} m tall");
    }
}

birch: 19 m
oak: 28 m
pine: 35 m
birch is 19 m tall
oak is 28 m tall
pine is 35 m tall

keys() and values() iterate over just one side of the map, and values_mut() lets you change every value. .copied().collect() turns the &&str keys into a Vec<&str>; iterators get their own lesson later.

A HashMap<String, V> owns its keys. Inserting a String moves it into the map, just like pushing into a vector. To look one up you don't need to build a String: get accepts a &str for String keys.

use std::collections::HashMap;
 
fn main() {
    let mut emails: HashMap<String, String> = HashMap::new();
 
    let user = String::from("ferris");
    emails.insert(user, String::from("ferris@example.com"));
    // `user` has moved into the map.
 
    let address = emails.get("ferris");
    println!("{address:?}");
}

Some("ferris@example.com")

Structs and vectors make good values. A map from a name to a struct is a common way to keep a set of records you look up by id:

use std::collections::HashMap;
 
struct Account {
    owner: String,
    balance: i64,
}
 
fn main() {
    let mut accounts: HashMap<u32, Account> = HashMap::new();
    accounts.insert(
        7,
        Account {
            owner: String::from("Ada"),
            balance: 100,
        },
    );
 
    if let Some(account) = accounts.get_mut(&7) {
        account.balance -= 30;
    }
 
    let account = &accounts[&7];
    println!("{} has {}", account.owner, account.balance);
}

Ada has 70

With a non-string key like u32, get, get_mut and [] take a reference to the key: &7.

A very common job is "update the value for this key, or start it off if the key isn't there yet". With get_mut and insert that takes two lookups and an if. The entry API does it in one step. map.entry(key) returns an Entry for that key, which is either occupied or vacant, and its methods decide what to do:

use std::collections::HashMap;
 
fn main() {
    let rolls = [3, 6, 3, 1, 6, 3];
    let mut counts: HashMap<u8, u32> = HashMap::new();
 
    for roll in rolls {
        let count = counts.entry(roll).or_insert(0);
        *count += 1;
    }
 
    println!("three came up {} times", counts[&3]);
    println!("six came up {} times", counts[&6]);
    println!("one came up {} times", counts[&1]);
}

three came up 3 times
six came up 2 times
one came up 1 times

or_insert(0) inserts 0 if the key is missing, then returns a &mut to the value, whether it was just inserted or already there. *count += 1 then updates it in place.

The value can be a collection too. Here every word is filed under its first letter, and a missing letter starts with an empty vector:

use std::collections::HashMap;
 
fn main() {
    let words = ["apple", "banana", "avocado", "blueberry", "cherry"];
    let mut by_letter: HashMap<char, Vec<&str>> = HashMap::new();
 
    for word in words {
        let first = word.chars().next().unwrap_or('?');
        by_letter.entry(first).or_default().push(word);
    }
 
    println!("a: {:?}", by_letter[&'a']);
    println!("b: {:?}", by_letter[&'b']);
    println!("c: {:?}", by_letter[&'c']);
}

a: ["apple", "avocado"]
b: ["banana", "blueberry"]
c: ["cherry"]

and_modify chains with the others to say "change it if it's there, else insert this": map.entry(key).and_modify(|v| *v += 1).or_insert(1);.

std::collections has a few more. You will meet them less often, but it's worth knowing they exist:

• HashSet<T>: a set of unique values with fast "is this in the set?" checks. Like a HashMap with keys and no values.
• BTreeMap<K, V> and BTreeSet<T>: sorted versions of the map and set.
• VecDeque<T>: a queue you can push to and pop from at both ends efficiently.

See the std::collections docs for a guide to choosing between them. When in doubt, start with Vec or HashMap.

fn main() {
    let mut tasks = vec![String::from("write"), String::from("test")];
    let first = &tasks[0];
    tasks.push(String::from("ship"));
    println!("first task: {first}");
}

cargo run fails with E0502: cannot borrow tasks as mutable because it is also borrowed as immutable

first borrows tasks, and push needs to borrow it mutably while first is still used on the next line. This isn't the borrow checker being fussy: push may run out of room and move every element to a bigger block of memory, which would leave first pointing at freed memory. Use first before you push, or clone the element (tasks[0].clone()) if you need to keep it around.

fn main() {
    let mut ages = HashMap::new();
    ages.insert("Ada", 36);
    println!("{}", ages["Ada"]);
}

cargo run fails with E0433: cannot find type HashMap in this scope, suggesting use std::collections::HashMap

Vec and String are in the prelude, HashMap is not. Add use std::collections::HashMap; at the top of the file.

use std::collections::HashMap;
 
fn main() {
    let ages = HashMap::from([("Ada", 36), ("Grace", 45)]);
    println!("Alan is {}", ages["Alan"]);
}

cargo run panics: thread main panicked, no entry found for key

This compiles, then panics at run time because "Alan" isn't a key. [] is for keys you know are present. When a key might be missing, use get and handle the None, or get(...).copied().unwrap_or(0) for a fallback.

use std::collections::HashMap;
 
fn main() {
    let mut owners = HashMap::new();
    let pet = String::from("Biscuit");
    owners.insert(pet, String::from("Sam"));
    println!("{pet} belongs to {}", owners["Biscuit"]);
}

cargo run fails with E0382: borrow of moved value pet, value moved into the map by insert, suggesting pet.clone()

insert takes the String by value, so pet is moved into the map. Print it before the insert, insert pet.clone(), or read the key back out of the map.

• Vec<T> is a growable, ordered list. Make one with Vec::new() or vec![...], add with push, and remove with pop, remove, retain or clear.
• v[i] panics on a bad index; v.get(i) returns an Option instead. A Vec works anywhere a slice does, so take &[T] in functions that only read.
• Loop with &v to read, &mut v to change, and v to consume.
• HashMap<K, V> needs use std::collections::HashMap;. insert adds or overwrites, get returns an Option<&V>, get_mut lets you change a value, remove takes it out.
• A HashMap has no defined order. Sort the keys or use BTreeMap when order matters.
• Collections own their contents: inserting a String moves it in, and a reference into a collection blocks changes to it until the reference is last used.
• map.entry(key).or_insert(v) (and or_default, or_insert_with, and_modify) updates or initialises a value in one step.