Choosing the Container: The std Complexity Table, Annotated

Most people choose a collection by which name they recognise from their last language. A Python programmer reaches for HashMap because dict was the answer to everything; a Java programmer reaches for LinkedList because a data-structures course said insertion was O(1). Both instincts are wrong often enough to be worth replacing with one table and four rules.

The table

This is the standard library’s own complexity table, from std::collections, with the columns that matter in practice. A * means amortised.

Sequences

	get(i)	insert(i)	remove(i)	append	push/pop back
Vec	O(1)	O(n − i)*	O(n − i)	O(m)*	O(1)*
VecDeque	O(1)	O(min(i, n − i))*	O(min(i, n − i))	O(m)*	O(1)*
LinkedList	O(min(i, n − i))	O(min(i, n − i))	O(min(i, n − i))	O(1)	O(1)

Maps and sets

	get	insert	remove	range query	ordered iteration
HashMap	O(1)~	O(1)~	O(1)~	none	none
BTreeMap	O(log n)	O(log n)	O(log n)	O(log n)	free

HashSet and BTreeSet are the same structures with () values, so their rows are identical. BinaryHeap is its own thing: push O(log n)*, pop O(log n), peek O(1), and no lookup of anything except the maximum.

Three things in that table are worth saying out loud.

Vec::insert at the front is O(n). So is remove(0). Every element after the insertion point moves. This is the single most common accidental quadratic loop in Rust: a Vec used as a queue with push and remove(0). Use a VecDeque.

LinkedList::get is O(min(i, n − i)), not O(n). It is doubly linked and walks from whichever end is closer. That is the best row in its column, and it is still almost never the right choice — see below.

BTreeMap has a column HashMap cannot have at any price. Range queries and ordered iteration are not a bonus feature; they are the reason the type exists. Hashing deliberately destroys adjacency, so “every key between a and b” in a HashMap means visiting all n entries.

Rule 1: default to Vec

Not as a slogan — because of memory layout. A Vec is one contiguous allocation. Iterating it is a linear walk the prefetcher predicts perfectly; every cache line you pull in contains several elements you are about to use. A LinkedList is one allocation per element, scattered across the heap, each visit a dependent load that cannot start until the previous one finished.

The asymptotics say LinkedList inserts in the middle in O(1) once you have a cursor there. Getting the cursor there costs O(n) of the worst kind of memory traffic. In practice, for anything under tens of thousands of elements, “walk a Vec and memmove the tail” beats “chase pointers to the right place” — and memmove is one of the most optimised routines on your machine.

clippy ships a lint called linkedlist whose help text says “you seem to be using a LinkedList! Perhaps you meant some other data structure?” It is a pedantic lint, off by default, and its existence is a fair summary of the community’s position. Use LinkedList when you genuinely need O(1) splice/append of large sublists, or stable element addresses. That is a real requirement. It is just rarer than you think.

💡If Vec is so good, why does VecDeque exist at all? click to reveal

Because one operation on a Vec is genuinely, unfixably O(n): removing from the front. A ring buffer keeps contiguity and cache friendliness — it is still one allocation, still elements packed side by side — while making both ends O(1). You give up exactly one thing: the elements may wrap, so as_slices() returns two slices instead of one, and anything that needs a single &[T] has to call make_contiguous() first.

So the choice between Vec and VecDeque is nearly free, and it is decided by one question: do you take from the front? If yes, VecDeque. Everything else about them is the same.

Rule 2: HashMap for lookups, BTreeMap for order

If all you ever do is get, insert and contains_key, HashMap wins on large data. The moment any of these appears in your requirements, switch:

• the output must be sorted, or reproducible across runs
• you need “all keys between a and b”, or “the next key after x”
• the keys are Ord but not Hash (or hashing them is expensive)
• the map is small and you would rather not pay for hashing at all

And remember from earlier in this track: HashMap iteration order is randomised per map per process. A BTreeMap is often chosen not for speed but because it makes tests, logs and serialised output deterministic. That is a legitimate reason to pick a structure and you do not need to apologise for it.

Rule 3: measure, because big-O hides a constant

Here is the classic “obviously use a set” case: deduplicating values by membership test. Measured on one machine, Vec::contains versus HashSet::insert, time per full dedup pass:

n =      4    Vec 0.00004 ms   HashSet 0.00015 ms    Vec 3.8x faster
n =     16    Vec 0.00011 ms   HashSet 0.00030 ms    Vec 2.7x faster
n =    128    Vec 0.00068 ms   HashSet 0.00213 ms    Vec 3.1x faster
n =   1024    Vec 0.0189  ms   HashSet 0.0165  ms    about even
n =  30000    Vec 14.44   ms   HashSet 0.52    ms    HashSet 27.7x faster

Both halves of that table are important.

The bottom row is the one people quote: linear scan is quadratic overall, so at thirty thousand elements the hash set wins by more than an order of magnitude, and the gap grows without limit. (An independent run on different hardware measured the same comparison at 2.64 ms versus 0.176 ms — a 15× gap rather than 28×. The constant is machine-specific; the shape is not.)

The top rows are the ones people forget: below roughly a thousand elements a Vec scan is faster, by about 3×, because comparing u32s in a cache-hot array is nearly free while hashing every key is not. “Always use a HashSet” overcorrects, and it is why a “tags” field or a “flags” list is very reasonably a Vec<String> with a linear contains.

The honest rule is not a threshold, it is a question: can n grow? If the collection is bounded by something small and structural — the fields of a record, the days of the week, the arguments to a command — a Vec is simpler, faster and allocates once. If n is driven by input you do not control, use the structure with the good asymptotics, because the constant factor stops mattering the moment somebody uploads a big file.

💡You are writing a function that takes a list of allowed names and checks each incoming request against it. Vec<String> or HashSet<String>? click to reveal

It depends on where the list comes from, and the answer is a genuine engineering judgement rather than a lookup.

If the allow-list is a compile-time constant of a dozen names, Vec — or better, a const array with contains — is faster, allocates nothing, and reads better. If it is loaded from configuration that some deployment will eventually populate with fifty thousand entries, HashSet, because the quadratic version will work fine for a year and then fall over on someone else’s Tuesday.

The tell is whether you can name an upper bound. If you can, and it is small, take the simple structure. If your answer is “however many they configure”, you have no bound and you should assume the worst.

Rule 4: pick by operation, not by name

A short lookup table for the question “what am I actually doing?”:

The operation you keep doing	The type
index by position, append, iterate	Vec
take from the front, add at the back	VecDeque
“have I seen this?” over unbounded data	HashSet
“have I seen this?” over a handful	Vec + contains
key → value, order irrelevant	HashMap
key → value, ordered or ranged	BTreeMap
“what is the largest / smallest right now?”	BinaryHeap
splice large sublists in O(1)	LinkedList, honestly

And one last note on effort: changing collection type in Rust is usually a one-line change plus whatever the compiler then complains about, and the compiler will complain about all of it. That is a real advantage. You are allowed to start with the obvious Vec, discover it is the bottleneck, and swap it — safe in the knowledge that nothing silently keeps working while meaning something different.