Collections

use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};

let v1: Vec<i32> = Vec::new();             // empty, type annotated
let mut v2 = Vec::new();                    // empty, type inferred later
v2.push(1);

let v3 = vec![1, 2, 3];                     // macro with elements
let v4 = vec![0; 10];                       // ten zeros
let v5 = Vec::from([1, 2, 3]);              // from an array
let v6: Vec<i32> = (1..=5).collect();       // from an iterator
let v7 = vec!["a"; 3];                      // ["a", "a", "a"]
let v8: Vec<char> = "abc".chars().collect();
let v9 = [1, 2].to_vec();                   // copy of a slice

let mut v = Vec::with_capacity(100);   // reserves room for 100 elements, length 0
println!("{} {}", v.len(), v.capacity());  // 0 100
for i in 0..100 {
    v.push(i);                          // no reallocation
}
v.reserve(50);                          // guarantees room for 50 more
v.shrink_to_fit();                      // gives back unused memory

• len(): number of elements.
• capacity(): allocated space.

When len reaches capacity, push allocates a block about twice as large and copies everything into it. What with_capacity is for: when you know the final size, it avoids these successive copies. collect does it on its own when the iterator knows its size.

let rows = vec![Vec::<i32>::new(); 3];   // three independent Vecs (each one cloned)

vec![x; n] clones x: the type must implement Clone.

let mut v = vec![1, 2, 3];
v.push(4);                     // [1, 2, 3, 4]
let last = v.pop();            // Some(4); None if empty

let mut v = vec![1, 2, 3];
v.insert(1, 10);               // [1, 10, 2, 3]
let removed = v.remove(0);     // 1; [10, 2, 3] — panics if the index does not exist

let mut v = vec![1, 2, 3, 4];
let x = v.swap_remove(0);      // 1; the last one takes its place: [4, 2, 3]

remove shifts all the following elements (cost proportional to the size), swap_remove moves only one. Use it when the order does not matter.

let mut v = vec![1, 2, 3];
v.extend([4, 5]);                        // adds from any iterator
v.extend_from_slice(&[6, 7]);            // copies from a slice

let mut other = vec![8, 9];
v.append(&mut other);                    // moves everything: other becomes empty

let tail = v.split_off(5);               // v keeps [0..5), tail receives the rest
v.truncate(2);                           // keeps the first 2
let extracted: Vec<i32> = v.drain(..1).collect();   // removes a range and returns it
v.clear();                               // empties (keeps the capacity)

let mut v = vec![1, 2, 3, 4, 5, 6];

// 1. retain: keeps those that satisfy the condition (in place)
v.retain(|&x| x % 2 == 0);              // [2, 4, 6]

// 2. filter + collect: new collection, the original is untouched
let v = vec![1, 2, 3, 4];
let evens: Vec<i32> = v.iter().copied().filter(|x| x % 2 == 0).collect();

// 3. extract_if (Rust 1.87+): removes AND returns what is removed
let mut v = vec![1, 2, 3, 4];
let odds: Vec<i32> = v.extract_if(.., |x| *x % 2 == 1).collect();   // v = [2, 4]

Never remove elements by index in a for i in 0..v.len() loop: the indexes shift and the end of the loop goes out of bounds.

let v = vec![10, 20, 30];

let a = v[0];                 // 10 — panics if the index does not exist
let b = v.get(0);             // Some(&10)
let c = v.get(10);            // None, no panic

match v.get(5) {
    Some(x) => println!("{x}"),
    None => println!("no element"),
}
let x = v.get(5).copied().unwrap_or(0);

let v = vec![1, 2, 3, 4];
v.first();               // Some(&1)
v.last();                // Some(&4)
v.split_first();         // Some((&1, &[2, 3, 4]))
v.get(1..3);             // Some(&[2, 3])
v.is_empty();
v.len();

let mut v = vec![1, 2, 3];
v[0] = 10;

if let Some(x) = v.get_mut(1) {
    *x += 5;
}

if let Some(last) = v.last_mut() {
    *last = 0;
}

v.swap(0, 2);            // swaps two elements
v.fill(7);               // replaces everything

let mut v = vec![1, 2, 3];
let first = &v[0];
// v.push(4);            // ERROR: v is borrowed by `first`
println!("{first}");
v.push(4);               // OK: `first` is no longer used

push may reallocate the memory block, which would make first invalid: the compiler therefore forbids modifying the Vec while a reference to an element is in use.

let mut v = vec![3, 1, 2];
v.sort();                                  // [1, 2, 3], stable
v.sort_unstable();                         // faster, does not preserve the order of equal elements
v.reverse();                               // [3, 2, 1]
v.sort_by(|a, b| b.cmp(a));                // descending

struct P { name: String, age: u32 }
let mut people = vec![P { name: "B".into(), age: 30 }, P { name: "A".into(), age: 20 }];
people.sort_by_key(|p| p.age);                          // by age
people.sort_by(|a, b| a.name.cmp(&b.name));             // by name
people.sort_by(|a, b| b.age.cmp(&a.age).then_with(|| a.name.cmp(&b.name))); // age descending then name
people.sort_by_key(|p| std::cmp::Reverse(p.age));       // descending, other syntax

let mut f = vec![2.5, 1.0, 3.2];
f.sort_by(|a, b| a.total_cmp(b));          // floats do not have Ord

sort_by_key with an expensive key (a String created at each comparison): prefer sort_by_cached_key, which computes it once per element.

let v = vec![10, 20, 30, 40];

v.contains(&20);                          // true
v.iter().position(|&x| x == 30);          // Some(2)
v.iter().find(|&&x| x > 15);              // Some(&20)
v.iter().any(|&x| x > 35);                // true
v.binary_search(&30);                     // Ok(2) — v must be SORTED
v.binary_search(&25);                     // Err(2): position where to insert it to keep the order

contains and position go through everything (cost proportional to the size). binary_search halves the range at each step (1,000,000 elements: 20 comparisons), but requires a sorted Vec.

let mut v = vec![1, 1, 2, 3, 3, 3, 1];
v.dedup();                     // [1, 2, 3, 1]: removes CONSECUTIVE duplicates

let mut v = vec![3, 1, 3, 2, 1];
v.sort();
v.dedup();                     // [1, 2, 3]: sort first to deduplicate everything

// Keeping the original order
use std::collections::HashSet;
let v = vec![3, 1, 3, 2, 1];
let mut seen = HashSet::new();
let uniques: Vec<i32> = v.into_iter().filter(|x| seen.insert(*x)).collect();   // [3, 1, 2]

let mut v = vec![1, 2, 3];

for x in &v { }              // &i32: read
for x in &mut v { *x += 1; } // &mut i32: modify
for x in v { }               // i32: consumes v

The details of these three forms are in the structures-et-controle course.

let v = vec![1, 2, 3];

let doubled: Vec<i32> = v.iter().map(|x| x * 2).collect();
let texts: Vec<String> = v.iter().map(|x| x.to_string()).collect();
let total: i32 = v.iter().sum();
let joined = v.iter().map(|x| x.to_string()).collect::<Vec<_>>().join(", ");   // "1, 2, 3"
let (evens, odds): (Vec<i32>, Vec<i32>) = v.iter().copied().partition(|x| x % 2 == 0);

Iterators are covered in the closures-iterateurs course.

let matrix = vec![vec![1, 2], vec![3]];
let flat: Vec<i32> = matrix.concat();                          // [1, 2, 3]
let flat2: Vec<i32> = matrix.into_iter().flatten().collect();  // same result

let words = vec!["a", "b", "c"];
let sentence = words.join("-");                                // "a-b-c"

// Version 1: &Vec<i32> — only accepts a Vec
fn sum_vec(v: &Vec<i32>) -> i32 { v.iter().sum() }

// Version 2: &[i32] — accepts Vec, array, part of either
fn sum(v: &[i32]) -> i32 { v.iter().sum() }

fn main() {
    let v = vec![1, 2, 3];
    let t = [4, 5];
    sum(&v);           // &Vec<i32> becomes &[i32] automatically
    sum(&t);
    sum(&v[1..]);
}

clippy flags &Vec<T> as a parameter (ptr_arg): &[T] does the same thing while accepting more types. Likewise, prefer &str to &String.

use std::collections::VecDeque;

let mut queue = VecDeque::new();
queue.push_back(1);            // at the end
queue.push_back(2);
queue.push_front(0);           // at the start
let first = queue.pop_front();    // Some(0)
let last = queue.pop_back();      // Some(2)
queue.front();                 // Some(&1)

// Task queue limited to the last 3 entries
let mut history = VecDeque::with_capacity(3);
for event in ["a", "b", "c", "d"] {
    if history.len() == 3 {
        history.pop_front();
    }
    history.push_back(event);
}
// ["b", "c", "d"]

use std::collections::HashMap;

let mut scores: HashMap<String, u32> = HashMap::new();
let scores2 = HashMap::from([("Alice", 10), ("Bob", 7)]);
let scores3: HashMap<&str, u32> = vec![("Alice", 10), ("Bob", 7)].into_iter().collect();
let names = ["a", "b"];
let lengths: HashMap<&str, usize> = names.iter().map(|n| (*n, n.len())).collect();
let reserved: HashMap<u32, String> = HashMap::with_capacity(1000);

let mut scores = HashMap::new();
let old = scores.insert("Alice", 10);   // None: new key
let old = scores.insert("Alice", 15);   // Some(10): the value is replaced

insert always replaces. To insert only if the key is absent: entry(...).or_insert(...) (section 11).

let mut scores = HashMap::from([("Alice".to_string(), 10)]);

let s = scores.get("Alice");                 // Some(&10) — a &str is enough for a String key
let s = scores.get("Zoe").copied().unwrap_or(0);
let exists = scores.contains_key("Alice");
let s = scores["Alice"];                     // panics if the key is absent

get accepts a borrowed form of the key: with String keys, you search with a &str, without creating a String.

if let Some(s) = scores.get_mut("Alice") {
    *s += 5;
}

let removed = scores.remove("Alice");                // Some(15)
let pair = scores.remove_entry("Bob");               // Some(("Bob", v)) or None
scores.retain(|_name, score| *score > 5);            // keeps based on a condition

let scores = HashMap::from([("Alice", 10), ("Bob", 7)]);

for (name, score) in &scores { }         // (&K, &V)
for name in scores.keys() { }
for score in scores.values() { }

let mut scores = scores;
for score in scores.values_mut() {
    *score *= 2;
}
for (name, score) in scores { }          // consumes the map

// In a stable order
let mut pairs: Vec<_> = HashMap::from([("b", 2), ("a", 1)]).into_iter().collect();
pairs.sort();

use std::collections::HashMap;

let text = "the cat and the dog";

// 1. get then insert: two lookups, longer
let mut c1: HashMap<&str, u32> = HashMap::new();
for word in text.split_whitespace() {
    let n = c1.get(word).copied().unwrap_or(0);
    c1.insert(word, n + 1);
}

// 2. match on get_mut
let mut c2: HashMap<&str, u32> = HashMap::new();
for word in text.split_whitespace() {
    match c2.get_mut(word) {
        Some(n) => *n += 1,
        None => { c2.insert(word, 1); }
    }
}

// 3. entry + or_insert: a single lookup (idiomatic form)
let mut c3: HashMap<&str, u32> = HashMap::new();
for word in text.split_whitespace() {
    *c3.entry(word).or_insert(0) += 1;
}

// 4. entry + or_default
let mut c4: HashMap<&str, u32> = HashMap::new();
for word in text.split_whitespace() {
    *c4.entry(word).or_default() += 1;
}

let mut m: HashMap<&str, Vec<u32>> = HashMap::new();

m.entry("a").or_insert(Vec::new());          // value created even if the key exists
m.entry("b").or_insert_with(Vec::new);       // created only if absent
m.entry("c").or_default();                   // Default of the type
m.entry("a").or_default().push(1);           // group: returns &mut V

m.entry("a")
    .and_modify(|v| v.push(2))               // if present: modify
    .or_insert_with(|| vec![2]);             // if absent: insert

let key = "d";
m.entry(key).or_insert_with_key(|k| vec![k.len() as u32]);   // the value depends on the key

let words = ["tree", "tent", "boat", "bus", "car"];
let mut by_initial: HashMap<char, Vec<&str>> = HashMap::new();
for word in words {
    let initial = word.chars().next().unwrap();
    by_initial.entry(initial).or_default().push(word);
}
// {'t': ["tree", "tent"], 'b': ["boat", "bus"], 'c': ["car"]}

use std::collections::hash_map::Entry;

let mut stock: HashMap<&str, u32> = HashMap::new();
match stock.entry("apple") {
    Entry::Occupied(mut e) => { *e.get_mut() += 1; }
    Entry::Vacant(e) => { e.insert(1); }
}

What it is for: when the two cases need different and lengthy handling, or to remove the entry (e.remove()) depending on its value.

use std::collections::BTreeMap;

let mut grades = BTreeMap::new();
grades.insert("Charlie", 12);
grades.insert("Alice", 15);
grades.insert("Bob", 9);

for (name, grade) in &grades {
    println!("{name}: {grade}");         // Alice, Bob, Charlie: always in order
}

grades.first_key_value();                // Some((&"Alice", &15))
grades.last_key_value();                 // Some((&"Charlie", &12))

let mut events = BTreeMap::new();
events.insert(1990, "a");
events.insert(2005, "b");
events.insert(2020, "c");
for (year, e) in events.range(2000..2021) {
    println!("{year} {e}");              // 2005, 2020
}

use std::collections::HashSet;

let mut s = HashSet::new();
let is_new = s.insert("rust");       // true
let is_new = s.insert("rust");       // false: already present, nothing changes
s.remove("rust");

let s2: HashSet<i32> = [1, 2, 2, 3].into_iter().collect();   // {1, 2, 3}
let s3 = HashSet::from([1, 2, 3]);

insert returns false for a duplicate: handy for detecting duplicates along the way.

let forbidden_vec = vec!["admin", "root", "system"];
let forbidden_set: HashSet<&str> = forbidden_vec.iter().copied().collect();

let name = "root";
forbidden_vec.contains(&name);     // goes through the whole Vec
forbidden_set.contains(name);      // one hash lookup

For a few elements, there is no difference. For thousands of checks on thousands of elements, the HashSet is vastly faster.

let a: HashSet<i32> = [1, 2, 3, 4].into();
let b: HashSet<i32> = [3, 4, 5].into();

let union: HashSet<_> = a.union(&b).copied().collect();                 // {1, 2, 3, 4, 5}
let inter: HashSet<_> = a.intersection(&b).copied().collect();          // {3, 4}
let diff: HashSet<_> = a.difference(&b).copied().collect();             // {1, 2}
let sym: HashSet<_> = a.symmetric_difference(&b).copied().collect();    // {1, 2, 5}

let inter2 = &a & &b;      // same operations with operators
let union2 = &a | &b;
let diff2 = &a - &b;

a.is_subset(&b);           // false
a.is_disjoint(&b);         // false

use std::collections::BTreeSet;

let s: BTreeSet<i32> = [5, 1, 3].into();
for x in &s { }            // 1, 3, 5
s.first();                 // Some(&1)
s.range(2..).next();       // Some(&3): smallest value >= 2

use std::collections::BinaryHeap;
use std::cmp::Reverse;

let mut heap = BinaryHeap::new();
heap.push(3);
heap.push(10);
heap.push(1);
heap.pop();            // Some(10)
heap.peek();           // Some(&3)

// The SMALLEST first: wrap in Reverse
let mut min_heap = BinaryHeap::new();
min_heap.push(Reverse(3));
min_heap.push(Reverse(1));
let Some(Reverse(smallest)) = min_heap.pop() else { return };   // 1

// Priority + data: the tuple is compared element by element
let mut tasks = BinaryHeap::new();
tasks.push((2, "medium"));
tasks.push((9, "urgent"));
tasks.pop();           // Some((9, "urgent"))

let name = String::from("Alice");
let mut names = Vec::new();
names.push(name);
// println!("{name}");    // ERROR: name was moved into the Vec

let key = String::from("k");
let mut m = std::collections::HashMap::new();
m.insert(key, 1);
// println!("{key}");     // ERROR too

Three solutions depending on the need:

let name = String::from("Alice");
let mut a = Vec::new();
a.push(name.clone());     // 1. copy: name stays usable

let mut b: Vec<&str> = Vec::new();
b.push(&name);            // 2. store a reference: b must not outlive name

let mut c = Vec::new();
c.push(name);             // 3. move, and access the value through the collection afterwards
println!("{}", c[0]);

let mut v = vec![String::from("a"), String::from("b")];

// let s = v[0];                    // ERROR: cannot move out of index
let s = &v[0];                      // borrow
let s = v[0].clone();               // copy
let s = v.remove(0);                // remove (and shift)
let s = std::mem::take(&mut v[0]);  // take the value, leave String::new() in its place
let s = std::mem::replace(&mut v[0], String::from("z"));   // swap

fn stats_loop(v: &[f64]) -> Option<(f64, f64, f64)> {
    if v.is_empty() {
        return None;
    }
    let mut min = v[0];
    let mut max = v[0];
    let mut total = 0.0;
    for &x in v {
        if x < min { min = x; }
        if x > max { max = x; }
        total += x;
    }
    Some((min, max, total / v.len() as f64))
}

fn stats_iter(v: &[f64]) -> Option<(f64, f64, f64)> {
    let first = *v.first()?;
    let min = v.iter().copied().fold(first, f64::min);
    let max = v.iter().copied().fold(first, f64::max);
    let average = v.iter().sum::<f64>() / v.len() as f64;
    Some((min, max, average))
}

f64 does not have Ord, so there is no .min() on the iterator: use fold with f64::min.

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

let v = vec![3, 1, 3, 2, 1];

// 1. Sort + dedup: sorted order
let mut a = v.clone();
a.sort();
a.dedup();                                             // [1, 2, 3]

// 2. Go through a BTreeSet: sorted order
let b: Vec<i32> = v.iter().copied().collect::<BTreeSet<_>>().into_iter().collect();

// 3. HashSet as a filter: original order kept
let mut seen = HashSet::new();
let c: Vec<i32> = v.iter().copied().filter(|x| seen.insert(*x)).collect();   // [3, 1, 2]

use std::collections::HashMap;

fn most_frequent(text: &str) -> Option<(&str, u32)> {
    let mut count: HashMap<&str, u32> = HashMap::new();
    for word in text.split_whitespace() {
        *count.entry(word).or_default() += 1;
    }
    count.into_iter().max_by_key(|&(_, n)| n)
}

In case of a tie, the result depends on the order of the HashMap, so it can change from one run to the next. For a stable result, use a BTreeMap or break the tie on the word: max_by(|a, b| a.1.cmp(&b.1).then(b.0.cmp(a.0))).

vec![1, 2]   Vec::with_capacity(n)   iter.collect::<Vec<_>>()
v.push(x)   v.pop()   v.insert(i, x)   v.remove(i)   v.swap_remove(i)
v.extend(it)   v.append(&mut w)   v.truncate(n)   v.clear()   v.drain(a..b)
v.retain(|x| ..)   v.dedup()   v.sort()   v.sort_by_key(|x| ..)   v.reverse()
v[i]   v.get(i)   v.first()   v.last()   v.get_mut(i)   v.contains(&x)
v.binary_search(&x)   v.iter().position(|x| ..)   v.windows(2)   v.chunks(n)

HashMap::from([(k, v)])   m.insert(k, v)   m.get(&k)   m.get_mut(&k)
m.remove(&k)   m.contains_key(&k)   m.keys()   m.values()   m.values_mut()
*m.entry(k).or_insert(0) += 1
m.entry(k).or_default().push(x)
m.entry(k).and_modify(|v| ..).or_insert(v)

s.insert(x)  // false if already present
s.contains(&x)   a.union(&b)   a.intersection(&b)   a.difference(&b)
&a | &b   &a & &b   &a - &b