Using and Choosing std::collections in Rust: BTreeMap, HashSet, BinaryHeap, and VecDeque

Introduction

#

Most of the time in Rust, Vec<T> and HashMap<K, V> are all you need. But when you hit message queues, specialized queries, or task schedulers, the default containers start falling short.

The standard std::collections module covers most application needs without third-party crates. Still, it is worth looking beyond just O(1) or O(log N) complexity ratings and paying attention to how data actually sits in memory. Modern CPUs love contiguous memory: good data placement and L1/L2 cache hits often outweigh theoretical algorithmic bounds in practice.

Let’s walk through four key structures from the standard library: VecDeque, BTreeMap, BTreeSet, and BinaryHeap.

1. Collections: VecDeque vs Vec vs LinkedList

#

Dynamic Array (Vec<T>)

#

Vec<T> stores elements as a contiguous array on the heap. Because of this, iterating over a vector runs very fast, and indexing is rated at O(1).

The vector’s weak spot is inserting or removing elements at the front or middle: you have to shift the entire tail for O(N).

Double-Ended Queue (VecDeque<T>)

#

If you need a queue (FIFO) or a ring buffer of recent events, reach for VecDeque<T>.

Under the hood, it is a dynamic ring buffer:

• Push and pop at the back (push_back / pop_back) — O(1).
• Push and pop at the front (push_front / pop_front) — O(1) without shifting the entire array.

Linked List (LinkedList<T>)

#

Doubly linked LinkedList<T> is almost never seen in real-world Rust code. Each node lives in its own heap allocation. Traversing the list forces the CPU to jump across memory and constantly hit cache misses.

2. Maps: BTreeMap vs HashMap

#

For working with key-value pairs, the standard library offers two tools.

Hash Tables (HashMap<K, V> and HashSet<T>)

#

• Under the hood: SwissTable algorithm.
• Complexity: lookup, insertion, and deletion run in average O(1).
• Characteristics: element order is arbitrary. Keys must implement Hash + Eq.

B-Trees (BTreeMap<K, V> and BTreeSet<T>)

#

• Under the hood: a B-Tree where each node holds a small array of elements. This packs keys tightly into CPU cache lines.
• Complexity: lookup, insertion, and deletion guarantee O(log N) time.
• Characteristics: keys are always sorted. Keys must implement Ord.

use std::collections::BTreeMap;

let mut map = BTreeMap::new();
map.insert(3, "Third");
map.insert(1, "First");

// Iterates in ascending key order: 1, then 3
for (key, val) in &map {
    println!("{key}: {val}");
}

3. Priority Queue: BinaryHeap

#

BinaryHeap<T> is a binary Max-Heap implemented on top of a vector. The collection is built for task schedulers and event queues where you need to process the highest-priority item first.

• Adding an item via .push(item) takes O(log N).
• Extracting the maximum item via .pop() takes O(log N).
• Peeking at the top item via .peek() takes O(1).

4. Complexity Cheatsheet

#

Below are interactive slides for each collection:

 1use std::collections::VecDeque;
 2
 3fn main() {
 4    // Double-ended queue (Ring Buffer)
 5    let mut queue = VecDeque::with_capacity(5);
 6
 7    // Appending to the back:
 8    queue.push_back("Task 1");
 9    queue.push_back("Task 2");
10
11    // Urgent push to the front:
12    queue.push_front("Priority task!");
13
14    println!("Queue elements: {:?}", queue);
15
16    // Pop from opposite ends in O(1):
17    if let Some(first) = queue.pop_front() {
18        println!("Popped from front: {first}");
19    }
20
21    if let Some(last) = queue.pop_back() {
22        println!("Popped from back: {last}");
23    }
24}
25

 1use std::collections::BTreeMap;
 2
 3fn main() {
 4    let mut sensor_data = BTreeMap::new();
 5
 6    // Inserting keys in arbitrary order
 7    sensor_data.insert(104, "Server Room");
 8    sensor_data.insert(101, "Hallway");
 9    sensor_data.insert(103, "Kitchen");
10    sensor_data.insert(102, "Living Room");
11
12    println!("--- Iteration is always strictly sorted by key ---");
13    for (id, room) in &sensor_data {
14        println!("Sensor ID {id}: {room}");
15    }
16
17    println!("\n--- Key range query (Range query 102..=103) ---");
18    for (id, room) in sensor_data.range(102..=103) {
19        println!("Range: ID {id} -> {room}");
20    }
21}
22

 1use std::cmp::Ordering;
 2use std::collections::BinaryHeap;
 3
 4#[derive(Eq, PartialEq)]
 5struct Job {
 6    priority: u32,
 7    name: String,
 8}
 9
10// Implement Ord for sorting the heap by priority
11impl Ord for Job {
12    fn cmp(&self, other: &Self) -> Ordering {
13        self.priority.cmp(&other.priority)
14    }
15}
16
17impl PartialOrd for Job {
18    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
19        Some(self.cmp(other))
20    }
21}
22
23fn main() {
24    let mut heap = BinaryHeap::new();
25
26    heap.push(Job { priority: 10, name: "Background log flush".to_string() });
27    heap.push(Job { priority: 90, name: "Emergency power cutoff".to_string() });
28    heap.push(Job { priority: 50, name: "Config update".to_string() });
29
30    println!("--- Fetching jobs by priority (Max-Heap) ---");
31    while let Some(job) = heap.pop() {
32        println!("Executing [Priority {}]: {}", job.priority, job.name);
33    }
34}
35

Quick Quiz

#

A short test to check your understanding of Rust collections: