Choosing the right collection
Rust's `std::collections` module exposes six concrete types: `Vec`, `VecDeque`, `LinkedList`, `HashMap`, `BTreeMap`, `HashSet`, `BTreeSet`, and `BinaryHeap`. The single best rule of thumb is: start with `Vec` for sequences and `HashMap` for keyed lookups, and only reach for the others when their specific algorithmic shape matters. `Vec` is contiguous, cache-friendly, and grows in O(1) amortised. `HashMap` is the unordered keyed store with O(1) average operations. The other types each trade something — ordering, priority, two-ended access, lock-free push — for a different cost curve.
Sequence containers
`Vec<T>` is a heap-allocated growable array. It is the workhorse of Rust code and you should default to it for almost any sequence. `VecDeque<T>` is a ring buffer optimised for push/pop on both ends — use it for BFS frontiers, sliding-window buffers, and producer-consumer queues that don't need cross-thread coordination. `LinkedList<T>` exists for completeness but is almost never the right answer in practice; cache-friendly contiguous storage in `Vec` beats pointer-chasing for nearly every realistic workload.
For deeper background, see a complete cheat-sheet of std collection complexities for the broader context behind this section.
Keyed containers
`HashMap<K, V>` and `HashSet<T>` use the SipHash 1-3 family by default, which is randomised per process to defeat HashDoS attacks. They give average-case O(1) on insert, lookup, and delete. `BTreeMap<K, V>` and `BTreeSet<T>` use a B-Tree internally — they are O(log n) but iterate in sorted order and support range queries via `range()`. Reach for the BTree variants whenever you need sorted iteration, range queries, or a small predictable memory footprint at moderate sizes.
Priority and heap
`BinaryHeap<T>` is a max-heap built on top of a `Vec`. It supports O(log n) push and pop, and is the right structure for Dijkstra-style algorithms, top-k problems, and any priority-driven scheduling where you only care about the next-largest element. To get a min-heap, wrap your items in `Reverse` from `std::cmp`.
For deeper background, see the official Rust API guidelines for module-level design for the broader context behind this section.
Capacity, allocation, and amortisation
All resizable collections double their capacity on grow, giving O(1) amortised insertion. If you know the final size up front, pre-allocate with `with_capacity` to avoid the doubling chain. `shrink_to_fit` reclaims excess memory after a long-lived collection has shrunk significantly. Note that capacity is rarely returned to the OS automatically — long-running programs that grow and shrink large collections will see high steady-state memory unless they explicitly shrink.
When to look beyond std
If you need insertion-order preservation in a HashMap, use the `indexmap` crate. For lock-free concurrent maps, look at `dashmap` or `evmap`. For copy-on-write and persistent data structures, the `im` and `rpds` crates implement the standard functional collections. For specialised numeric or bit data, `smallvec`, `bitvec`, and `ndarray` each fill specific niches.