Collections

What the standard library packs in your lunchbox

Rust’s standard library ships a handful of collection types. You’ll spend most of your career using three: Vec, HashMap, and HashSet. The rest are there when you need them.

Type	What it is	When to reach for it
`Vec<T>`	growable array, contiguous in memory	the default list
`VecDeque<T>`	double-ended queue	push/pop from both ends
`LinkedList<T>`	doubly-linked list	almost never
`HashMap<K, V>`	unordered key→value map	the default map
`BTreeMap<K, V>`	ordered key→value map	when you want sorted iteration
`HashSet<T>`	unordered unique-value set	the default set
`BTreeSet<T>`	ordered unique-value set	when you want sorted iteration
`BinaryHeap<T>`	priority queue (max-heap by default)	top-k stuff, schedulers

LinkedList exists for completeness but you should almost never use it. Modern CPUs hate pointer chasing; a Vec will beat a linked list at almost every game you can think of.

Vec — the workhorse

You’ve met Vec already in Starting Out. Let’s get cosier:

v.len() is the number of items currently stored. v.capacity() is how many the vec could hold before it has to reallocate. When you push past capacity, Vec allocates a larger buffer (typically doubling) and copies the old contents over. This is amortized O(1) push — the same trick std::vector and Python lists pull.

Iterating

That trio (&xs, &mut xs, xs) is the same trio you see everywhere in Rust. Once it clicks, the same instincts work for every type that owns a heap allocation.

Sorting, searching, and friends

HashMap — keys to values

A HashMap is a hash table. Average O(1) insertion, lookup, and removal.

The `entry` API — the secret weapon

How many times have you written “increment this counter, or initialise it to 1 if it’s not there”? In Python it’s a defaultdict. In Rust it’s entry:

counts.entry(word) gives you an Entry — basically “a handle to the slot where this key would live.” You can then call:

.or_insert(default) — fills it with default if missing, returns &mut V
.or_insert_with(|| expensive_default()) — same, but lazy
.and_modify(|v| *v += 1) — runs the closure if present

One lookup, one mutation, no double-hashing.

What can be a key?

A type can be a HashMap key if it implements Eq + Hash. That covers strings, integers, tuples of hashable things, and anything you’ve derived Eq + Hash on. Floats can’t (because NaN != NaN). That’s a feature, not a bug.

HashSet — just the keys, please

HashSet<T> is HashMap<T, ()> with nicer methods. You use it when you care whether you’ve seen something, not what it maps to.

BTreeMap and BTreeSet — when order matters

The BTree* variants are sorted by key. They’re O(log n) instead of O(1), but iteration comes out in sorted order without you having to ask. Same API as their Hash* cousins.

A worked example — word histogram

Putting iterators and collections together:

That then_with is a nice little trick — sort primarily by count descending, then by word ascending as a tiebreaker. Makes the output deterministic when two words appear the same number of times.

Next chapter: lifetimes. Where we make the borrow checker into a friend instead of a coworker.