Choose a data structure from the operation that must be cheap, not from its
name or theoretical reputation.
| Need | Start with |
|---|
| Indexed sequence, stack, contiguous slice | Vec |
| Queue or active operations at both ends | VecDeque |
| Fixed-capacity streaming | Ring buffer |
| Node-based links or whole-list joining | LinkedList |
| Rolling minimum or maximum | Monotonic deque |
| Need | Start with |
|---|
| Key to value, order irrelevant | HashMap |
| Unique membership, order irrelevant | HashSet |
| Key to value with ranges and sorting | BTreeMap |
| Unique membership with ranges and sorting | BTreeSet |
| Dense bounded integer membership | Bit set |
| Compact negative membership filter | Bloom filter |
| Prefix lookup | Trie |
| Need | Start with |
|---|
| Repeated greatest or smallest item | BinaryHeap |
| Change arbitrary priorities | Indexed priority queue |
| Stable IDs with slot reuse | Generational arena |
| Arbitrary relationships | Adjacency-list graph |
| Connectivity under edge additions | Union-find |
| Lookup plus recency | LRU composition |
| Dynamic overlap queries | Interval tree |
- Is access by position, key, priority, range, prefix, identity, or recency?
- Which operations dominate, and what are their required bounds?
- Is order semantic or merely convenient for display?
- Is the domain dense or sparse?
- Are identities stable across removal and reuse?
- Must memory be bounded?
- Does contiguous layout outweigh asymptotic differences?
- What invariant must every mutation preserve?
- Can a simpler structure meet the measured workload?
Prefer the simplest representation whose invariants make the required
operations cheap enough—and verify the decision with realistic measurements.