🎓 A1Learner
🔍

Rust Choosing a Collection

Choosing a collection means matching the job to the collection's strength. Vec and HashMap cover most jobs.

The default answer: Vec

For a plain list, collected now and processed later, the std docs give blunt advice. You should probably just use Vec or HashMap:

let readings = vec![21, 19, 23];
let total: i32 = readings.iter().sum();
println!("{} readings, total {}", readings.len(), total);

A queue: VecDeque

Items leaving from the front as well as joining at the back — that is VecDeque. A Vec pays for remove(0) by shifting every item behind it:

use std::collections::VecDeque;

let mut queue: VecDeque<&str> = VecDeque::new();
queue.push_back("first");
queue.push_back("second");
println!("serving {:?}", queue.pop_front());

Sorted output: BTreeMap

Same style of inserts as a HashMap — but this one walks in key order when you print it:

use std::collections::BTreeMap;

let mut diary: BTreeMap<u32, &str> = BTreeMap::new();
diary.insert(9, "exam");
diary.insert(2, "gym");
for (day, plan) in &diary {
    println!("day {day}: {plan}");
}

Have I seen this? HashSet answers

insert returns false for a repeat — the duplicate test is the insert itself:

use std::collections::HashSet;

let mut seen: HashSet<i32> = HashSet::new();
println!("7 new = {}", seen.insert(7));
println!("7 again = {}", seen.insert(7));

Example

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

fn main() {
    let signups = ["ana@oslo", "bo@oslo", "ana@oslo", "cy@bergen", "di@oslo"];
    let mut seen: HashSet<&str> = HashSet::new();
    let mut unique: Vec<&str> = Vec::new();
    let mut by_city: BTreeMap<&str, u32> = BTreeMap::new();
    for s in signups {
        if seen.insert(s) {
            unique.push(s);
            let city = s.split('@').nth(1).unwrap();
            *by_city.entry(city).or_insert(0) += 1;
        }
    }
    println!("unique = {:?}", unique);
    for (city, n) in &by_city {
        println!("{city}: {n}");
    }
}

Key points

  • The choice starts from the job: order, lookup, queue, or membership picks the collection.
  • Vec vs VecDeque: pick VecDeque only when the front of the list is a door too — queues and buffers.
  • For everything else, Vec is simpler and scans faster.
  • LinkedList honesty: the std docs steer you to it only in narrow cases.
  • One narrow case is splitting and joining whole lists cheaply.
  • Another narrow case is a list that cannot tolerate a Vec pausing to grow now and then.
  • Its items live scattered in memory, so plain walking is slow.
  • In practice, Vec or VecDeque wins almost every contest.
  • That holds even for inserts in the middle.
  • HashMap vs BTreeMap: pick HashMap for the fastest plain lookup.
  • Pick BTreeMap the moment sorted order is needed.
  • BTreeMap also wins when a range of keys, or the smallest and largest entries, is needed.
  • A set is a map with the values thrown away.
  • Pick the Set twin (HashSet, BTreeSet) when only "have I seen this?" matters.
  • BinaryHeap when only the biggest item is ever needed next — or the smallest, wrapped in Reverse (Rust Priority Queues)

In this example, three collections each do the one job they fit. The HashSet spots the repeat. ana@oslo signs up twice. But the second insert returns false. So the duplicate is skipped entirely. The Vec keeps the survivors in arrival order — that is the order guarantee only a sequence gives. The BTreeMap counts signups per city through the entry pattern. Its keys stay sorted. So the report prints bergen before oslo, with no sorting step. No collection here is fancy. Each is simply the right shape for its question.

Note

When two collections tie on paper, the std docs rank them in a fixed order.

Vec comes first, then VecDeque, then LinkedList.

Items stored side by side are simply quick for the machine to walk.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Rust Playground

Exercise

A sensor log must print every reading sorted by timestamp, and new readings arrive all day. Which map fits?