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.
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`.
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.