Collections and Ownership-Aware Data Structures

Start with the operations that must remain cheap

A scheduler needs to accept runnable jobs, pop the next job, cancel by identity, and inspect job state. A cache needs fast key lookup and an eviction policy. A graph needs edges that survive storage growth without becoming dangling references. A protocol table needs reproducible output and range queries. Calling all four requirements “store some values” conceals the design.

Collection choice is an ownership decision before it is an asymptotic-complexity decision. The collection owns elements or keys, decides when their storage may move, lends references only while a borrow remains valid, and exposes a particular mutation vocabulary. Its layout affects allocation, cache behavior, and iteration cost. Its order may leak into snapshots, hashes, logs, or wire output even when the API never promised that order.

Write an operation profile before selecting a type:

• which operations dominate, and on what distributions;
• whether order is semantic, merely useful for reproducibility, or irrelevant;
• whether callers need references, opaque identities, or removable ownership;
• whether insertion and removal may invalidate positions or identities;
• how large the collection becomes and whether it is bounded;
• whether memory locality or allocation count is on a measured hot path.

Big-O notation then filters candidates. It does not choose one. Two nominally constant-time designs can differ by hashing, pointer chasing, cache misses, allocator traffic, and adversarial input behavior.

Vec<T> is the default when sequence and locality agree

Vec<T> owns a contiguous, growable sequence described by a pointer, length, and capacity at the API-model level. Elements in 0..len are initialized. Capacity is reserved storage, not additional elements. Indexing is constant time, iteration is linear and cache-friendly, and appending is amortized constant time. Insertion or removal near the front shifts elements.

When growth exceeds capacity, the vector may allocate another buffer and move its elements. Numeric positions still describe sequence order after an append, but previously observed addresses must not be treated as persistent identities. Rust’s borrow rules prevent safe code from holding an element reference while mutating the same vector in a way that needs &mut Vec<T>:

let mut jobs = vec!["parse", "index"];
let first = &jobs[0];
jobs.push("compact");
println!("{first}");

The rejected program is useful evidence: the API does not let a reference outlive the exclusive mutation that might reallocate. Replacing the reference with index 0 compiles, but an index is only an identity if insertions, removals, sorting, and swapping preserve the intended association. swap_remove deliberately changes which element occupies a position.

Use with_capacity or reserve when a defensible upper or next-batch size is known. Capacity planning can reduce repeated allocation and copying, but aggressive reservation increases resident memory and may amplify attacker-declared sizes. Check external lengths before reserving. shrink_to_fit is a request, not a guaranteed exact compaction policy, and repeated shrinking can create allocator churn.

Box<[T]> is often a better final form for an owned sequence whose length is fixed after construction. It drops spare-capacity and growth semantics. An array [T; N] additionally carries its length in the type. A small fixed-capacity design can keep storage inline, but the standard library does not provide a universal small-vector type; introducing a third-party or custom implementation changes MSRV, unsafe-review, layout, and worst-case-cost obligations.

VecDeque<T> makes both ends first-class

VecDeque<T> is a growable ring buffer. It supports efficient push and pop at both ends and is a natural starting point for FIFO queues and work-stealing building blocks. Its logical sequence may occupy two physical slices after wrapping, so code that requires one contiguous slice may call make_contiguous, potentially moving elements. Do not choose it merely because it sounds like a more flexible vector; middle indexing and split storage can make ordinary sequential work less direct.

A scheduler queue also needs a policy. VecDeque<JobId> can express FIFO order, but it does not provide cancellation lookup by itself. Adding a HashMap<JobId, Position> is delicate because positions change when the deque rotates or items are removed. Alternatives include lazy cancellation checked on pop, a separate authoritative job store plus queue handles, or a purpose-built intrusive structure. The right choice follows cancellation frequency, latency bounds, and complexity tolerance.

Linked structures pay for properties Rust APIs may not expose

Linked lists make local link changes cheap once a node is located. They also allocate nodes separately, add pointer fields, weaken spatial locality, and make traversal dependent on pointer chasing. Finding a position remains linear. In safe Rust, ownership and cursor APIs determine whether the theoretical splice advantage is actually available to the caller.

std::collections::LinkedList is therefore a specialized option, not the default queue. VecDeque usually gives a simpler ownership model and better locality for end operations. A custom intrusive list can eliminate separate ownership of nodes, but it commonly requires pinning, raw pointers, and an unsafe safety case covering node lifetime, exclusivity, unlinking, and destruction. Chapter 31 treats pinning; later unsafe chapters treat the proof boundary. A benchmark that excludes allocation and traversal is not evidence for a production list.

Maps separate key semantics from storage strategy

HashMap<K, V> is designed for expected constant-time key operations under its hashing policy. BTreeMap<K, V> provides ordered iteration and range queries with logarithmic operations. The meaningful choice is not simply O(1) versus O(log n):

Hash-map iteration order must not become a persistent or protocol contract accidentally. It can differ with implementation, hasher state, capacity, and mutation history. If deterministic snapshots matter, sort explicitly or choose an ordered structure and document the ordering. Sorting at output time keeps faster updates but concentrates latency and allocation in the output path; an ordered map spreads cost across updates.

Hashing untrusted keys is also a security decision. The standard map’s default hasher is intended to resist collision attacks, but no application should infer a fixed algorithm or stable serialized ordering from it. Custom fast hashers require a threat model. Measure realistic key size and distribution, not just integer microbenchmarks.

Borrow keys instead of allocating lookup probes

An owned String key does not require every lookup to construct another String. Standard map lookup uses borrowed forms where the key’s Borrow implementation and ordering or hashing are compatible:

use std::collections::HashMap;

let mut routes = HashMap::from([(String::from("/health"), 200)]);
assert_eq!(routes.get("/health"), Some(&200));

The borrowed form must behave consistently with the owned key for equality, ordering, and hashing. A case-folded or normalized key newtype should encode that rule once. Implementing Borrow<str> is valid only when the borrowed str has exactly the same key semantics; a view that compares differently breaks the collection contract.

Entry APIs combine lookup with mutation

Avoid contains_key followed by insert when one lookup and an atomic-looking local decision will do:

let count = routes.entry(String::from("/ready")).or_insert(0);
*count += 1;

The entry holds an exclusive borrow into the map, so unrelated access to the map waits until that borrow ends. That static restriction prevents invalidation and aliasing mistakes, but it is not thread synchronization. A concurrent map or a lock around a standard map adds a separate concurrency contract.

Sets and heaps expose deliberately narrower views

HashSet<T> and BTreeSet<T> apply the corresponding map strategies when only membership is stored. A set can state domain intent better than HashMap<T, ()>. As with maps, deterministic order belongs to a tree set or an explicit sorting step, not an assumption about a hash set.

BinaryHeap<T> represents a priority queue, not a sorted vector. Peeking and removing the greatest item follow heap order; iterating the heap does not promise globally sorted output. For a minimum queue, reverse the ordering deliberately, usually through Reverse. If priority changes after insertion, mutating ordering fields behind interior mutability can violate heap logic even if memory safety remains intact. Remove/reinsert, use supported guard APIs where applicable, or store immutable priority records and tolerate stale entries that are checked on pop.

Heaps are strong scheduler candidates when urgency, deadline, or cost determines the next job. They are weak candidates when arbitrary cancellation must be immediate unless paired with an identity store or index. Again, the operation profile controls the design.

Drain, retain, and extraction operations encode ownership transitions

Collections offer more than insert and remove:

• retain visits elements and keeps those accepted by a predicate; it is useful when the collection remains authoritative.
• draining operations yield ownership of removed elements while borrowing the collection mutably for the drain’s lifetime.
• extraction APIs can conditionally remove and yield values where available on the declared toolchain.
• split_off transfers a suffix or key range into another owner for supported collections.

These operations can avoid temporary collections, but their drop behavior matters. If a drain-like iterator is dropped early, consult that API’s documentation rather than guessing what remains. A predicate that panics can leave a collection partially processed while maintaining memory safety. Production code should decide whether partial mutation is an acceptable panic boundary.

Retaining a vector preserves relative order of retained elements but moves them to close gaps. HashMap::retain currently scans empty buckets too, so its work is proportional to capacity rather than length; removal also leaves spare capacity allocated for reuse. Never keep raw addresses into a collection across these operations unless a documented unsafe contract proves validity.

Stable indices are not stable identities

The scheduler fixture separates storage from identity with a generational handle:

#[derive(Clone, Copy, Debug, Eq, PartialEq)]
struct JobId { slot: usize, generation: u32 }

The slot selects storage; the generation prevents an old handle from naming a new job after reuse. A bare index cannot detect that ABA-style substitution. The full collections-dst-lab tests removal, slot reuse, and stale-handle rejection without unsafe code.

Generational handles trade a lookup and metadata for movable storage, compact edges, and explicit invalidation. Generation wraparound needs a policy in long-lived or adversarial systems. Deletion may also leave fragmented slots; compaction requires a remapping step or an indirection table. Arena crates can provide richer implementations, but their exact invalidation, thread-safety, and serialization contracts must be reviewed.

Stable address and stable identity solve different problems. A boxed node may retain an allocation address while its logical identity is deleted and replaced. A generational handle may retain identity while the underlying value moves during compaction. APIs should expose the property callers need, not an incidental pointer.

Newtype collections preserve domain invariants

A public Vec<Job> permits every vector operation, including arbitrary reordering, duplicate insertion, and indexing that may not fit the domain. A newtype can expose a smaller vocabulary:

struct Scheduler {
    runnable: std::collections::VecDeque<JobId>,
}

impl Scheduler {
    fn enqueue(&mut self, id: JobId) { self.runnable.push_back(id); }
    fn pop_next(&mut self) -> Option<JobId> { self.runnable.pop_front() }
}

The wrapper can enforce uniqueness, capacity, admission, metrics, and cancellation policy. Do not automatically implement Deref<Target = VecDeque<_>>; doing so re-exports the representation and bypasses the invariant. Implement iteration intentionally, with an ownership mode that matches the API. Expose bulk operations only after defining partial failure and ordering.

Allocation and locality are workload facts

Contiguous collections usually reduce allocation count and exploit prefetching. Tree and linked structures buy different mutation or ordering properties with nodes, pointers, and less predictable access. Hash maps reserve spare buckets and compute hashes. Small collections can make linear search surprisingly competitive because branch, hash, and allocation costs dominate at low cardinalities.

Measure:

• representative sizes, including empty, median, p95, and maximum;
• lookup hit/miss ratios and key distributions;
• update versus iteration frequency;
• allocations, retained capacity, and bytes per logical element;
• end-to-end latency and cache behavior where tools support it;
• worst-case input and collision behavior for exposed boundaries.

Do not bake benchmark-specific implementation observations into a public compatibility promise. Collection implementation details may evolve within the standard library while documented semantics remain stable.

Work the decision through four production shapes

The same menu produces different answers once the ownership and operational constraints are concrete.

Scheduler: queue order plus authoritative storage

Suppose jobs are submitted by one thread, executed by a worker pool, cancelled rarely, and addressed by an ID in logs and control requests. A VecDeque<JobId> can own the runnable order while a slot store owns Job values. The queue may contain a handle for a job cancelled since enqueue; the pop path validates the generation and state, discards stale work, and continues. This lazy strategy makes cancellation cheap and adds bounded cleanup work to dequeue.

If cancellation is frequent or queue delay is large, stale entries can consume memory and latency. A second index can support eager removal, but then every rotation and deletion must maintain two structures consistently. A heap replaces FIFO when deadline or priority is authoritative, yet priority updates commonly use new records plus stale-record detection rather than mutation through a hidden alias. Put a sequence number beside priority when equal-priority determinism matters.

Capacity is an admission contract. A bounded scheduler should reject, shed, or backpressure before unbounded allocation. Observability should report runnable count, stale-pop count, queue residence, rejected submissions, and retained capacity. The choice of collection does not supply fairness, cancellation semantics, or overload behavior; the wrapper does.

Cache: lookup is only half the data structure

A HashMap<Key, Entry> handles point lookup, but a cache also needs eviction order, expiry, weight accounting, and concurrency. A second structure may order candidates by recency or deadline. That makes updates transactional at the design level: replacing a value must update byte accounting and the eviction index exactly once, including error and panic paths.

Storing direct references from one collection into another is the wrong connection because map growth, removal, and mutable access invalidate the borrowing story. Store owned keys, shared owners where justified, or opaque IDs. Owned duplicate keys cost memory; an ID table adds lookup; shared ownership changes destruction and retention. Measure key size before optimizing.

Untrusted key cardinality needs both hashing resistance and a capacity limit. An LRU label does not prove bounded memory if entries have variable weight or if dead metadata accumulates. Export low-cardinality hit, miss, eviction-reason, entry-count, and byte gauges rather than keys themselves. Decide whether deterministic dump order is an operator feature and sort only that diagnostic path if so.

Graph: identity must survive movement, not deletion

An adjacency-list graph can store nodes in a slot vector and edges as generational node IDs. Vector growth may relocate node values, but IDs remain resolvable through the store. Deleting a node increments its generation, so old edges fail validation instead of silently targeting a replacement. The graph must decide whether deletion eagerly removes inbound edges, leaves tombstones for later cleanup, or rejects deletion while edges exist.

Each policy shifts cost. Eager cleanup needs an inbound index or a full scan. Tombstones make reads and memory use pay for deferred work. Rejecting deletion simplifies invariants but may not fit the domain. Compacting storage requires either preserving slot numbers, rewriting every edge under exclusive access, or adding an indirection layer.

For immutable or batch-built graphs, compressed contiguous adjacency arrays can beat node-heavy structures through locality and lower overhead. Mutation then becomes a rebuild or delta-layer operation. The senior decision compares read/write ratio and snapshot lifecycle instead of choosing a textbook “graph collection.”

Protocol table: reproducibility can be semantic

A protocol table keyed by route or numeric code may need exact lookup, prefix/range queries, deterministic diagnostics, and reproducible generated artifacts. BTreeMap gives key order and ranges directly. HashMap plus sorting can be better when updates and point lookups dominate and generation is infrequent. A dense numeric table may be a vector when the valid domain is bounded and holes are affordable.

Do not serialize any collection’s internal representation. Define an explicit schema, key ordering, duplicate policy, and version. Even a BTreeMap’s useful iteration order is not a license to treat memory layout as wire layout. During loading, bound entry count and aggregate bytes before allocation, reject duplicate or noncanonical keys according to policy, then construct the internal index.

The RouteTable newtype in the fixture accepts an owned String, supports lookup by &str, and exposes a range operation. A production version would additionally validate route syntax and prevent callers from mutating keys in ways that violate ordering. The newtype keeps a future HashMap-plus-sort migration possible because callers depend on domain operations rather than BTreeMap methods.

The four decisions can now be compressed into a retrieval aid. Read its center panel narrowly: vector growth can preserve a logical position while changing an address, but neither property by itself creates durable identity.

The visual is not an ABI or reference-validity specification. In particular, “stable address” is not a blanket API promise for a standard collection: safe mutation requires exclusive access and can end outstanding borrows. Prefer documented handles and operation contracts over inferred node addresses.

Small collections deserve a measured path

At low cardinalities, Vec<(K, V)> with linear search may outperform a hash map and occupy less memory. It also gives deterministic insertion order and simple serialization. The crossover depends on key comparison cost, hit distribution, update frequency, target cache, compiler, and hasher. “Small” must therefore be a measured workload range, not an intuition.

An inline-capacity collection can avoid a heap allocation for common cases and spill for larger ones. That optimization complicates moves, increases the containing value’s size, and may duplicate code or introduce unsafe internals through a dependency. It is especially risky in enums or arrays where every instance pays the inline capacity. Record the expected distribution and benchmark the containing structure, not an isolated push loop.

For a hard maximum, an array plus length or bitset can encode the budget without fallback allocation. The implementation must maintain initialized-prefix invariants, and ergonomic removal may still shift elements. In constrained or real-time systems, predictable worst-case cost may matter more than average throughput. Chapter 32 expands allocation-free and arena strategies; this chapter’s rule is to make the capacity and overflow policy part of the collection API now.

Exercise: choose four data structures

Produce a design note for these workloads:

1. A bounded FIFO scheduler with frequent enqueue/dequeue, rare cancellation, and opaque job IDs.
2. A 100,000-entry cache with untrusted string keys, frequent point lookup, a memory ceiling, and a separate eviction policy.
3. A mutable graph whose edges must reject deleted-and-reused vertices and whose nodes may be compacted.
4. A protocol table requiring point lookup, prefix/range queries, deterministic diagnostics, and versioned serialization.

For each, define the authoritative owner, identity representation, dominant operations, order contract, invalidation rules, capacity policy, panic/partial-mutation behavior, and observability. Compare at least two credible structures. Benchmark the decision whose cost is uncertain. Reject any answer that relies on references surviving collection mutation or hash iteration remaining stable.

Collection review card

• Is the workload a sequence, deque, priority queue, membership set, key map, graph, or multi-index structure?
• Which operations dominate at realistic cardinalities?
• Is order semantic, deterministic for operations, or irrelevant?
• Are callers holding references, positions, keys, or opaque handles?
• What invalidates each identity form?
• Can growth or compaction relocate elements?
• Are external sizes bounded before reserve or insert?
• Can lookup borrow an existing key view?
• Would an entry API avoid duplicate lookup or inconsistent mutation?
• Do drain, retain, or panic paths permit partial changes?
• Does a newtype need to hide dangerous representation operations?
• Have allocation, retained capacity, locality, hashing, and worst-case inputs been measured?

What engineers may rely on

Vec provides contiguous sequence storage and may reallocate as capacity grows. VecDeque makes both ends efficient but may store its logical sequence in two slices. Hash collections provide key-based operations without deterministic iteration promises; B-tree collections provide key order and range operations. A binary heap provides priority access, not sorted iteration. Linked structures exchange locality and allocation simplicity for node-based operations whose usefulness depends on the safe API.

References into a collection are scoped borrows, not persistent IDs. Positions survive only the mutations that preserve their meaning. Opaque generational handles make reuse detectable and allow storage to move. Newtype collections can turn these rules into a domain API. Chapter 30 now explains the pointer metadata that makes slices and trait-object views possible even though their pointee size is not known from the type alone.

Sources and version notes

• Standard library collections overview
• Vec and VecDeque
• HashMap, BTreeMap, and Borrow
• HashSet, BTreeSet, and BinaryHeap
• LinkedList
• The dependency-free collections-dst-lab uses Rust 2024, pinned Rust 1.97.0, and MSRV 1.85. It demonstrates design contracts, not stable standard-collection layout or ABI.