Collections

The Rust standard library provides general-purpose, efficient data structures tailored for safe, high-performance memory management [562]. These collections are grouped into four major categories: Sequences, Maps, Sets, and Miscellaneous [562, 563, 564, 565].

Quick Selection Cheat Sheet

1. Sequences

Sequence collections store elements sequentially in dynamic memory [562].

Vec<T> (Vector)

The Vec is Rust's default array-like collection [562, 565]. It stores elements contiguously on the heap [562].

• Memory Footprint: On 64-bit systems, a Vec header occupies exactly 24 bytes on the stack [24, 25]. This is split across three 8-byte fields: a pointer to the heap buffer, capacity (usize), and length (usize) [25].
• The Cost of Dynamic Growth: When you initialize an empty vector using Vec::new() and push elements onto it, it starts with zero capacity or a very small default [18, 19]. As elements exceed capacity:
  1. Heap Reallocations: Rust requests a larger block of memory from the OS allocator, copies all existing items to the new address, and frees the old block [19].
  2. Checks: Every .push() triggers a CPU check (len == capacity) to determine if a reallocation is required [19].
  3. Cache Invalidation: Moving data to a new memory address invalidates CPU cache lines [19].
• Optimization Best Practices:
  • If the maximum size is known at compile-time and strictly capped, a stack-allocated fixed-size array (e.g., [u8; 100]) is the fastest option, as stack allocation takes virtually 0 CPU cycles and stays hot in L1/L2 caches [20, 22].
  • If a heap-allocated vector is necessary, initialize it with Vec::with_capacity(capacity) to pre-allocate memory [21, 23]. This eliminates intermediate reallocations and turns pushes into simple pointer increments [21].

VecDeque<T> (Double-Ended Queue)

A VecDeque uses a growable ring buffer [562]. It is ideal for FIFO (First-In, First-Out) or double-ended queues [565].

• Performance: It offers $O(1)$ push and pop operations at both the front and back of the sequence [562].
• Contrast with Vec: While Vec is optimized for push and pop at the end, pushing to the front of a Vec is an $O(n)$ operation because all downstream elements must be shifted in memory.

LinkedList<T> (Doubly-Linked List)

A doubly-linked list where each node has owned allocations [562].

• The Cache Locality Penalty: LinkedList is rarely used in systems programming [562]. Because nodes are scattered across the heap rather than stored contiguously like a Vec or VecDeque, they suffer from poor CPU cache locality [562].
• Appropriate Use Cases: Use only when you have large datasets where you must perform constant-time $O(1)$ list splitting and appending operations without triggering memory reallocations [562].

2. Maps

Maps store unique keys associated with values [563].

HashMap<K, V>

The HashMap is Rust's default key-value collection [565]. It uses a hash table layout implemented with linear probing and Robin Hood bucket stealing [563].

• Performance: On average, it provides $O(1)$ time complexity for lookups, insertions, and removals [563].
• Requirements: The key type K must implement the Hash and Eq traits [563].
• Contrast with Sequence Lookups: Using a vector for key lookups forces $O(n)$ linear searches [30]. For example, managing active background jobs or data registries by ID using a HashMap is vastly superior to iterating over a dynamic vector because it permits direct, constant-time $O(1)$ retrieval [30].

BTreeMap<K, V>

A map based on a self-balancing B-Tree structure [563].

• Guaranteed Bounds: While HashMap has average $O(1)$ performance, a bad hashing function can degrade performance. BTreeMap provides strict $O(\log n)$ performance bounds regardless of hashing quality [563].
• Sorted Order: Keys are maintained in sorted order according to their Ord implementation [563].
• Range Queries: It provides powerful range-based lookups using the .range() method (e.g., retrieving all entries within a specific key boundary) [563].

3. Sets

Sets store unique individual keys without associated values [564].

• Under the Hood: Standard library sets are lightweight wrappers around their corresponding Map implementations [564]:
  • HashSet<T> is a wrapper around HashMap<T, ()> [564].
  • BTreeSet<T> is a wrapper around BTreeMap<T, ()> [564].
• HashSet<T>: Offers unordered storage with average $O(1)$ deduplication and membership checks [564]. It supports standard mathematical set operations such as union, intersection, and difference [564].
• BTreeSet<T>: Maintains its elements in sorted order based on the B-Tree structure, making it ideal for range queries on unique elements [564].

4. Miscellaneous

BinaryHeap<T>

A priority queue implemented as a max-binary heap [565].

• Ordering: The queue always prioritizes the "greatest" element based on the Ord trait implementation of the elements [565].
• Complexity:
  • Popping the greatest element takes $O(\log n)$ time [565].
  • Peeking at the maximum element without removing it is a constant-time $O(1)$ operation [565].