Start with the operations your program needs. A queue removes its oldest item; a lookup table finds a value by key; a priority queue takes the highest priority item. These access patterns matter more than which collection name is familiar from another language.
Sequences: indexing, queues and joining lists
| Collection | Read by index | Remove the front | Append another collection |
|---|---|---|---|
Vec |
O(1) | O(n) | O(m) amortised |
VecDeque |
O(1) | O(1) | O(m) amortised |
LinkedList |
Traverse nodes | O(1) | O(1) |
Here n is the current length and m is the number of appended elements.
Appending means transferring the contents of another collection of the same
type, leaving that source empty. The table treats moving an element as a
constant-cost operation; large payloads and user-defined destructors can add
work beyond these structural costs.
Amortised costs average over a sequence of operations: one call that grows an allocation can be much more expensive. See the standard library's collection cost table for more operations.
Use Vec for indexed data and stacks. Its contiguous storage makes
iteration straightforward. Pushing is amortised O(1), but repeatedly calling
remove(0) shifts the remaining elements and can turn draining a queue into
quadratic work.
Use VecDeque for queues. A ring buffer supports removing from either
end in O(1) and adding at either end in amortised O(1). Its elements can wrap
within the allocation: as_slices() exposes up to two slices, while
make_contiguous() may rearrange elements to provide one. It is not identical
to Vec in API or performance; choose it when operations at both ends help.
use std::collections::VecDeque;
fn main() {
let mut jobs = VecDeque::from(["parse", "check"]);
jobs.push_back("report");
assert_eq!(jobs.pop_front(), Some("parse"));
assert_eq!(jobs.front(), Some(&"check"));
}
Use LinkedList for a specific list operation. Stable Rust has no
LinkedList::get(i) method. list.iter().nth(i) walks forward; it does not
automatically choose the nearer end. For a known index you can explicitly
traverse backwards with iter().rev(). The conceptual indexed-access cost
in a complexity table is not a promise about a method named get.
LinkedList::append joins two existing lists without moving each element.
Locating an interior split point requires traversal. Its cursor APIs are
currently nightly-only, so an algorithm built around editable cursors needs
a separate API/toolchain decision. The
LinkedList documentation
recommends considering array-based collections first because of their memory
and cache advantages. There is no universal list length at which one wins.
Check your understanding Why can a queue become quadratic when it uses a Vec? Show answer Hide answer
Removing the first item shifts all remaining elements. Draining n items with
repeated remove(0) performs roughly (n − 1) + (n − 2) + ... + 1 moves.
VecDeque::pop_front advances the front of the ring instead. If you only
need to consume every item once, consuming a Vec through its iterator is
another option: the queue operation itself may be unnecessary. These are
algorithmic move counts, not a prediction of elapsed time for every element
type or optimized build.
Maps and sets: lookup or order
| Collection | Find a key | Insert a key | Traversal order |
|---|---|---|---|
HashMap / HashSet |
Expected O(1) | Expected amortised O(1) | Unspecified |
BTreeMap / BTreeSet |
O(log n) | O(log n) | Sorted by key |
These costs treat a key comparison or hash as a unit of work. Long strings and expensive user-defined keys add their own costs. Expected constant time for a hash table is not a worst-case guarantee.
Choose a map when each key has a value; choose a set for membership alone. A hash table is a useful starting point for lookup-heavy work. A B-tree provides ordered traversal and efficient access to a key range. Finding the range start is not the whole cost: consuming k matching entries also takes work proportional to k.
Sorted output from a hash map is still possible: collect its entries and sort them. Compare that occasional sorting cost with maintaining order in a B-tree. Hash-map traversal has no stable order guarantee, even when a run happens to produce the same order twice. A B-tree gives reproducible key order, provided the keys and their ordering are themselves reproducible.
use std::collections::BTreeMap;
fn main() {
let scores = BTreeMap::from([
("Ada", 8), ("Grace", 9), ("Linus", 7),
]);
let names: Vec<_> = scores
.range("Ada".."Linus")
.map(|(name, _)| *name)
.collect();
assert_eq!(names, ["Ada", "Grace"]);
}
Small collections: measure the real operation
A short linear scan can beat hashing because it avoids hash computation and table overhead. That is a possibility to measure, not a fixed threshold: element type, duplicates, hit rate, allocation and hardware all affect it.
Separate two workloads that are easy to confuse:
- Build a deduplicated collection: checking every incoming item against an ever-growing Vec can require O(n²) comparisons when values are distinct. A hash set offers expected linear total insertion work under the usual constant-cost hashing model.
- Check requests against an existing allow-list: a Vec scan costs O(n) per request, or O(qn) for q requests. Building the list is a separate cost; this is not automatically a quadratic operation in the list length.
To compare implementations, first check that they produce the required result, including any ordering requirement. Benchmark optimised builds with representative keys, small and large inputs, and both hits and misses. Decide whether construction belongs inside the timed operation, keep results observable, repeat measurements, and record the environment. A timing table without that setup cannot tell you which implementation will win here.
Check your understanding An allow-list has twelve fixed names. Does it need a HashSet? Show answer Hide answer
Not necessarily. A fixed array or slice with contains is simple and needs
no heap allocation for the collection itself. Whether its lookup is faster
needs measurement. If the list can grow substantially, a hash set becomes
a stronger starting point for repeated membership checks. Consider how often
the list changes and how many requests reuse it, not only its current size.
Priority queues and the final choice
BinaryHeap is a max-heap: peek sees the greatest item, and pop removes
it. Iteration is not sorted. Wrap values in Reverse when the next item
should instead be the smallest:
use std::cmp::Reverse;
use std::collections::BinaryHeap;
fn main() {
let mut deadlines = BinaryHeap::from([
Reverse(30), Reverse(10), Reverse(20),
]);
assert_eq!(deadlines.pop(), Some(Reverse(10)));
}
Start with the collection whose operations match the job. Then check the consequences of changing it: traversal order, duplicate handling, trait bounds and borrowing behaviour can change even when the compiler accepts the new code. Keep tests for those requirements and measure any performance claim you rely on.