Collection Types

When choosing a collection, first list the operations: how you look up, where you add/remove, whether ordering is required, whether range scans are needed, and the size and distribution of keys and values. Comparing O(1) against O(log n) in isolation misses the costs of hashing, string comparison, allocation, and cache access.

Quick Reference by Operation

The following complexities isolate the cost of a single key comparison or hash for specific types; amortized does not mean every operation is equally fast.

HashSet/BTreeSet correspond to key-only storage needs; arrays can be used for fixed counts. Whether to use inline small containers depends on actual capacity distribution and library rules; there is no universal threshold like "zero heap allocation for fewer than 20 items". Standard Library Collections Overview

Vec: Capacity is Not Length

Vec contains pointer, length, and capacity information, but field order is not a stable C layout promise. It can reside on the stack, heap, or inside other objects; it cannot be universally called a "24-byte stack object." Zero-sized elements and zero capacity have special allocation behaviors.

with_capacity(n) requests at least n items of capacity but does not create n initialized T values. reserve(additional) calculates the requirement based on current length plus additional, rather than directly setting the final capacity. Ordinary push does not need to grow if capacity is sufficient; growth strategy and multiplier are not permanent formulas that applications can rely on. Vec Guarantees

fn main() {
    let mut values = Vec::with_capacity(8);
    assert_eq!(values.len(), 0);
    assert!(values.capacity() >= 8);
    values.extend([10, 20, 30]);
    values.clear();
    assert!(values.is_empty());
    assert!(values.capacity() >= 8); // clear does not require returning the buffer
}

Operations that may cause growth invalidate raw pointers, and safe borrowing rules restrict conflicting access. Even without growth, operations like insert, remove, and sort may change the objects corresponding to indices; "address hasn't changed" and "still the same logical element" are not the same thing.

swap_remove replaces the deleted position with the last item, avoiding the move required to maintain order, at the cost of changing the order. When long-term stable identifiers are needed, design IDs, generation indices, or appropriate indirection; do not treat current indices as permanent identities.

Separate Order from Identity on Deletion

fn main() {
    let original = vec![(10, "a"), (20, "b"), (30, "c"), (40, "d")];
    let mut ordered = original.clone();
    assert_eq!(ordered.remove(1), (20, "b"));
    assert_eq!(ordered, [(10, "a"), (30, "c"), (40, "d")]);

    let mut unordered = original;
    assert_eq!(unordered.swap_remove(1), (20, "b"));
    assert_eq!(unordered, [(10, "a"), (40, "d"), (30, "c")]);
    assert_eq!(unordered[1].0, 40); // Index 1 now belongs to another ID
}

If another HashMap<ID, usize> maintains positions, you must update the index of the item moved to the end after swap_remove, otherwise queries will locate the wrong object. IDs resolve logical identity, and mappings maintain storage locations; both are indispensable. Simply changing Vec elements to Box only makes the addresses of un-moved heap objects more stable; it does not prevent objects from being deleted or old IDs from being reused.

HashMap: Hash, Equality, and Random Seed Form the Contract

Equal keys must produce equal hash results. Custom Hash and Eq implementations must be consistent; once a key is inserted, you cannot change parts involved in hashing or equality comparison via interior mutability, as this breaks collection contracts.

The standard library's current implementation is based on SwissTable and uses a default hasher with random state; the default algorithm and details may evolve. The random state is not simply "a single fixed seed shared by all tables on each process start." When choosing an alternative hasher, consider input threat models, key lengths, and measurements; do not promise a fixed 10% or 30% speedup. HashMap

The Entry API combines lookup and insertion intent into a single operation:

use std::collections::HashMap;
fn main() {
    let mut counts = HashMap::new();
    for word in ["red", "blue", "red"] {
        *counts.entry(word).or_insert(0_u32) += 1;
    }
    assert_eq!(counts.get("red"), Some(&2));
}

Do not rely on HashMap iteration order to generate stable snapshots or test expectations. The current implementation may scan by capacity rather than just length; tables that were once large but later became sparse deserve separate measurement. For stable order, explicitly sort the output or choose an ordered structure.

Borrowed Queries Avoid Allocation for Lookup

use std::collections::HashMap;
fn main() {
    let mut values: HashMap<String, Vec<u32>> = HashMap::new();
    values.insert(String::from("red"), vec![1]);
    assert_eq!(values.get("red").map(Vec::len), Some(1));

    let mut constructed = 0;
    values.entry(String::from("red")).or_insert_with(|| {
        constructed += 1;
        vec![99]
    }).push(2);
    assert_eq!(constructed, 0);
    assert_eq!(values.get("red").unwrap(), &[1, 2]);
}

String keys can be queried by borrowing str because the corresponding Borrow contract ensures consistent equality and hashing for both representations. This capability does not mean any custom type "convertible to string" is suitable for Borrow<str>: if keys compare case-insensitively while standard str compares case-sensitively, they do not share the same key semantics.

or_insert_with constructs the value only when absent, but the String passed to entry is still created before the call. If the hot path is primarily hits, measure the path of checking get_mut first and creating the key if missing; it reduces key allocation on hits but may add an extra lookup on misses. Do not understand Entry as automatically lazily creating both key and value. HashMap Borrowed Queries

BTreeMap: Ordering is an Interface Capability, Not a Performance Byproduct

BTreeMap sorts based on Ord, making it suitable for range queries, finding boundaries, and ordered output. Nodes store multiple items, providing some locality, but the entire tree is not a contiguous array. A sorted Vec also provides contiguous layout and ordered reads, so the notion that "cache locality and ordering are mutually exclusive" is incorrect.

use std::collections::BTreeMap;
fn main() {
    let values = BTreeMap::from([(10, "a"), (20, "b"), (30, "c")]);
    let selected: Vec<_> = values.range(15..=30)
        .map(|(&key, &value)| (key, value)).collect();
    assert_eq!(selected, [(20, "b"), (30, "c")]);
}

Choosing between a tree and a sorted Vec requires comparing update frequency and range reads: if data is built in batches and read-only for a long time, a sorted Vec is often worth measuring; frequent online insertions and deletions may be better suited for a tree. If key comparison involves long strings, the cost of comparison itself should be factored in.

Nearest Boundary Queries Require Explicit Inclusion

use std::collections::BTreeMap;
fn main() {
    let changes = BTreeMap::from([(10, "v1"), (20, "v2"), (30, "v3")]);
    let at = |time| changes.range(..=time).next_back().map(|(_, v)| *v);
    assert_eq!(at(9), None);
    assert_eq!(at(20), Some("v2"));
    assert_eq!(at(25), Some("v2"));

    let sorted = [(10, "v1"), (20, "v2"), (30, "v3")];
    let end = sorted.partition_point(|(time, _)| *time <= 25);
    let predecessor = end.checked_sub(1).map(|i| sorted[i].1);
    assert_eq!(predecessor, Some("v2"));
}

Here, the query is for the "last change not later than time." The tree uses an ordered range followed by next_back, while the sorted slice uses partition_point to find the first position greater than time. The slice returns 0 for times before the earliest, so checked_sub is needed to handle the absence of a predecessor. If duplicate times are allowed, Map insertion with the same key replaces the value, while Vec can retain multiple items; a tie-breaking order must be defined separately. BTreeMap Range

VecDeque: Logical Continuity Does Not Equal Physical Continuity

Ring buffers allow efficient operations at both ends, but growth may still occur. as_slices returns two segments; concatenating them in order yields the logical content. make_contiguous can consolidate them into a single contiguous slice, but consolidation itself may require moving elements. VecDeque

use std::collections::VecDeque;
fn main() {
    let mut queue = VecDeque::from([1, 2, 3]);
    assert_eq!(queue.pop_front(), Some(1));
    queue.push_back(4);
    let (a, b) = queue.as_slices();
    let logical: Vec<_> = a.iter().chain(b).copied().collect();
    assert_eq!(logical, [2, 3, 4]);
}

Do not constantly call remove(0) to use Vec as a FIFO: each call moves remaining elements, accumulating significant work for long queues. If the business logic only requires batch reading followed by a complete clear, Vec may still be appropriate; the operation pattern is more important than the container name.

How does a logical queue cross the buffer end?

Treat A,B,C as logical identities and slot numbers as physical positions. Near the buffer end, queue order stays A,B,C while storage splits into two regions. Modulo explains wrapping; it does not make arbitrary out-of-bounds Rust indexing valid.

$$p(i)=(h+i)\mathrm{mod}C,0\le i<\mathrm{len}\le C$$

BinaryHeap: Scheduling Order is a Result of Ord

The standard BinaryHeap is a max-heap; to execute earliest deadlines first, wrap the comparison key with Reverse. If tied tasks require FIFO, include a sequence number assigned by enqueue order in the key; do not rely on internal permutation order.

use std::{cmp::Reverse, collections::BinaryHeap};
fn main() {
    let mut pending = BinaryHeap::from([
        Reverse((20u64, 0u64)),
        Reverse((10, 2)),
        Reverse((10, 1)),
    ]);
    assert_eq!(pending.pop(), Some(Reverse((10, 1))));
    assert_eq!(pending.pop(), Some(Reverse((10, 2))));
    assert_eq!(pending.pop(), Some(Reverse((20, 0))));
    assert_eq!(pending.pop(), None);

    let mut scores = BinaryHeap::from([9, 5, 3]);
    {
        let mut top = scores.peek_mut().unwrap();
        *top = 1;
    } // guard drops normally, maintaining new heap order
    assert_eq!(scores.peek(), Some(&5));
}

Sequence number allocation and wrapping are the scheduler's responsibility; long-lived systems should handle overflow before it occurs, rather than letting duplicate sequence numbers silently change order. Real tasks can store only deadline, sequence number, and task ID in the heap, keeping large objects in a separate table, so the task body does not participate in Ord.

Ordinary iter does not provide sorted traversal; continuous pop retrieves items according to heap priority. Do not secretly modify sorting fields of heap elements via interior mutability; updating the heap top can use peek_mut, while arbitrary task rescheduling requires explicit delete/re-insert or versioned invalidation strategies. The latter allows old entries to remain in the heap, checking the version upon pop and skipping if stale, but accumulation of stale entries must be controlled. BinaryHeap Contract

Measure Real Costs

Record element count, key distribution, insert/delete ratio, peak capacity, and whether output order is required, then test both the construction and steady-state phases. Pre-allocation reduces growth frequency but may increase long-term memory usage; shrink_to_fit does not guarantee an immediate drop in RSS, as there are allocators and the OS in between.

Using safe APIs for collections does not mean all logical conditions are proven by the compiler: index validity, business ID lifetimes, hash consistency, and sorting rules remain part of the design.