Standard Collections

Choosing the Right Collection

In Rust, Vec<T> and HashMap<K, V> cover the vast majority of workloads because of their cache-friendly contiguous memory layouts. Specialized collections are chosen when your access pattern requires double-ended queue operations, sorted range queries, set algebra, or priority scheduling.

Decision Matrix by Workload

Primary Requirement Recommended Collection Why?
Sequential storage, stack (LIFO), or index access Vec<T> Contiguous memory, $O(1)$ indexing and push/pop, lowest memory overhead
FIFO queue or pushing/popping at both ends VecDeque<T> Ring buffer gives $O(1)$ push_front/pop_front and push_back/pop_back
Fast key-value lookup without ordering HashMap<K, V> $O(1)$ average lookup, insertion, and removal
Key-value lookup plus sorted order, min/max, or key range queries (range(a..b)) BTreeMap<K, V> Keys stayed sorted ($O(\log n)$ ops); supports .range(), .first_key_value(), .last_key_value()
Fast membership testing (contains) and deduplication HashSet<T> $O(1)$ average membership test and insertion
Sorted unique elements or ordered range queries BTreeSet<T> Elements kept in Ord order; works as a map key itself (BTreeSet<T>: Ord + Hash)
Always popping the largest (or smallest via Reverse<T>) element next BinaryHeap<T> $O(1)$ .peek(), $O(\log n)$ .push() and .pop()
$O(1)$ splitting/appending two lists at known cursor positions LinkedList<T> Rarely needed; Vec<T> or VecDeque<T> is faster for almost all other operations

Decision Flowchart

What is your primary access pattern?
  │
  ├── Ordered sequence by position (0, 1, 2, ...)?
  │     ├── Append/pop at back only + random indexing  ──> Vec<T>
  │     └── Push/pop at both front and back (FIFO)     ──> VecDeque<T>
  │
  ├── Associate keys K with values V?
  │     ├── Need sorted keys or range queries (a..=b)? ──> BTreeMap<K, V>
  │     └── Only need fast exact-key lookup?           ──> HashMap<K, V>
  │
  ├── Store unique items T with fast membership checks?
  │     ├── Need sorted order or set as a map key?     ──> BTreeSet<T>
  │     └── Only need fast .contains() / set algebra?  ──> HashSet<T>
  │
  └── Repeatedly extract the highest-priority item?    ──> BinaryHeap<T>

Example: Selecting VecDeque, HashSet, and BinaryHeap Together

use std::collections::{BinaryHeap, HashSet, VecDeque};

fn main() {
    // 1. FIFO work queue (VecDeque):
    let mut work_queue = VecDeque::from(["task-1", "task-2"]);
    work_queue.push_back("task-3");
    let next_fifo = work_queue.pop_front();

    // 2. Deduplicating seen IDs (HashSet):
    let mut seen_ids = HashSet::new();
    let is_first_time = seen_ids.insert(1042_u64);

    // 3. Priority scheduling — highest score first (BinaryHeap):
    let mut urgent = BinaryHeap::from([10_u32, 95, 40]);
    let highest = urgent.pop();

    println!(
        "FIFO next: {next_fifo:?}, new ID: {is_first_time}, highest prio: {highest:?}"
    );
}

FIFO next: Some("task-1"), new ID: true, highest prio: Some(95)