Other Collections — Rust

Other Collections in Rust

Rust's standard library ships several specialised collections beyond Vec and HashMap. Choosing the right one for your problem avoids unnecessary copies, unlocks better algorithmic complexity, and makes your intent clear to other readers.

HashSet<T> — Unique Values

A HashSet is essentially a HashMap<T, ()>. It stores unique values and provides O(1) average membership testing, insertion, and removal. It also supports the classical set operations: union, intersection, difference, and symmetric difference.

RUST

use std::collections::HashSet;

let mut set: HashSet<i32> = HashSet::new();

// Insertion — returns false if the value was already present
set.insert(1);
set.insert(2);
set.insert(3);
let inserted = set.insert(2); // duplicate — returns false
println!("inserted duplicate: {}", inserted); // false

// Membership
println!("{}", set.contains(&3)); // true
println!("{}", set.contains(&9)); // false

// Remove
set.remove(&1);
println!("{:?}", set); // {2, 3}  (order is not guaranteed)

Set Operations

RUST

use std::collections::HashSet;

let a: HashSet<i32> = [1, 2, 3, 4].iter().cloned().collect();
let b: HashSet<i32> = [3, 4, 5, 6].iter().cloned().collect();

// Union — all elements from both sets
let union: HashSet<&i32> = a.union(&b).collect();
println!("union: {:?}", union); // {1, 2, 3, 4, 5, 6}

// Intersection — only elements in both
let inter: HashSet<&i32> = a.intersection(&b).collect();
println!("intersection: {:?}", inter); // {3, 4}

// Difference — elements in a but not in b
let diff: HashSet<&i32> = a.difference(&b).collect();
println!("difference: {:?}", diff); // {1, 2}

// Symmetric difference — elements in either but not both
let sym: HashSet<&i32> = a.symmetric_difference(&b).collect();
println!("symmetric diff: {:?}", sym); // {1, 2, 5, 6}

// Subset / superset checks
let small: HashSet<i32> = [3, 4].iter().cloned().collect();
println!("small ⊆ a: {}", small.is_subset(&a)); // true
println!("a ⊇ small: {}", a.is_superset(&small)); // true

Tip

HashSet is perfect for deduplication: let unique: HashSet<_> = vec.into_iter().collect();

BTreeMap<K, V> — Sorted Key-Value Store

BTreeMap<K, V> is a sorted map backed by a B-tree. Keys must implement Ord. All operations are O(log n). Use it when you need the map's keys in a defined order, or when you need range queries.

RUST

use std::collections::BTreeMap;

let mut scores: BTreeMap<String, u32> = BTreeMap::new();
scores.insert("Charlie".into(), 70);
scores.insert("Alice".into(),   95);
scores.insert("Bob".into(),     88);

// Iteration is always in sorted key order
for (name, score) in &scores {
    println!("{}: {}", name, score);
}
// Alice: 95
// Bob:   88
// Charlie: 70

// Range queries — unique to BTreeMap (not available on HashMap)
for (name, score) in scores.range("Alice".to_string()..="Bob".to_string()) {
    println!("range: {}: {}", name, score);
}
// Alice: 95
// Bob:   88

// First and last key
println!("first: {:?}", scores.keys().next());
println!("last:  {:?}", scores.keys().next_back());

BTreeSet<T> — Sorted Unique Values

BTreeSet is to BTreeMap what HashSet is to HashMap — a sorted set. All set operations from HashSet are available, and iteration is always in ascending order.

RUST

use std::collections::BTreeSet;

let mut set: BTreeSet<i32> = BTreeSet::new();
set.insert(5);
set.insert(1);
set.insert(3);
set.insert(1); // duplicate, ignored

// Always iterates in sorted order
for x in &set {
    print!("{} ", x); // 1 3 5
}

// Range iteration
for x in set.range(1..4) {
    print!("{} ", x); // 1 3
}

// First and last in O(log n)
println!("min: {:?}", set.iter().next());
println!("max: {:?}", set.iter().next_back());

VecDeque<T> — Double-Ended Queue

VecDeque is a ring-buffer backed double-ended queue. It provides O(1) push and pop from both the front and the back, unlike Vec which is only O(1) at the back. Use it when you need queue (FIFO) or deque semantics.

RUST

use std::collections::VecDeque;

let mut deque: VecDeque<i32> = VecDeque::new();

// Push to both ends
deque.push_back(1);
deque.push_back(2);
deque.push_front(0);
println!("{:?}", deque); // [0, 1, 2]

// Pop from both ends
let front = deque.pop_front();
let back  = deque.pop_back();
println!("front={:?} back={:?}", front, back); // Some(0) Some(2)
println!("{:?}", deque); // [1]

// Create from a Vec
let mut dq: VecDeque<i32> = vec![1, 2, 3, 4, 5].into();

// Rotate — efficient circular shift
dq.rotate_left(2);
println!("{:?}", dq); // [3, 4, 5, 1, 2]

Tip

VecDeque supports indexing (dq[i]) and most Vec-like operations, so it is often a drop-in replacement when you realise you need front-insertion.

LinkedList<T> — Doubly-Linked List

LinkedList is a doubly-linked list. Each element is separately heap-allocated, so it has poor cache locality. It is rarely the right choice in Rust.

RUST

use std::collections::LinkedList;

let mut list: LinkedList<i32> = LinkedList::new();
list.push_back(1);
list.push_back(2);
list.push_front(0);
println!("{:?}", list); // [0, 1, 2]

// Splice two lists — O(1) because it just re-links pointers
let mut other = LinkedList::from([3, 4, 5]);
list.append(&mut other);
println!("{:?}", list); // [0, 1, 2, 3, 4, 5]

Warning

In practice, VecDeque beats LinkedList for almost every use case. LinkedList allocates each node separately, leading to heap fragmentation and cache misses. Only reach for it when you need O(1) splitting and splicing of large lists, and only after benchmarking.

BinaryHeap<T> — Priority Queue

BinaryHeap implements a max-heap. The largest element is always at the top and can be retrieved in O(1). Insertion and removal are O(log n). It is the standard choice for priority queues in Rust.

RUST

use std::collections::BinaryHeap;

let mut heap: BinaryHeap<i32> = BinaryHeap::new();

heap.push(3);
heap.push(1);
heap.push(4);
heap.push(1);
heap.push(5);

// peek — O(1), returns the maximum without removing it
println!("max: {:?}", heap.peek()); // Some(5)

// pop — O(log n), removes and returns the maximum
while let Some(val) = heap.pop() {
    print!("{} ", val); // 5 4 3 1 1
}

// Build from a Vec — O(n) heapify
let heap: BinaryHeap<i32> = vec![3, 1, 4, 1, 5, 9].into();
println!("top: {:?}", heap.peek()); // Some(9)

Min-Heap with Reverse

RUST

use std::collections::BinaryHeap;
use std::cmp::Reverse;

// Wrap values in Reverse<T> to turn the max-heap into a min-heap
let mut min_heap: BinaryHeap<Reverse<i32>> = BinaryHeap::new();
min_heap.push(Reverse(5));
min_heap.push(Reverse(1));
min_heap.push(Reverse(3));

while let Some(Reverse(val)) = min_heap.pop() {
    print!("{} ", val); // 1 3 5
}

Choosing the Right Collection

Need	Use	Why
Dynamic array	Vec<T>	Cache-friendly, O(1) amortised push, most versatile
Key-value, fast lookup	HashMap<K, V>	O(1) average get/insert/remove
Key-value, sorted keys	BTreeMap<K, V>	O(log n), sorted iteration and range queries
Unique values, fast test	HashSet<T>	O(1) contains, set algebra methods
Unique values, sorted	BTreeSet<T>	O(log n), always iterates in order
Queue / deque (both ends)	VecDeque<T>	O(1) push/pop at front and back
Priority queue	BinaryHeap<T>	O(1) peek-max, O(log n) pop-max
Splicing large sequences	LinkedList<T>	O(1) splice — but cache-unfriendly

HashMap vs BTreeMap — Trade-offs

Property	HashMap	BTreeMap
Lookup	O(1) average	O(log n)
Insert	O(1) amortised	O(log n)
Delete	O(1) average	O(log n)
Iteration order	Random	Sorted by key
Range queries	No	Yes (.range())
Key requirement	Hash + Eq	Ord
Memory layout	Flat array	Tree nodes (pointer-heavy)
Best for	Fast lookup, unordered data	Sorted output, range scans

Small Collections — Arrays and Tuples

When you have a fixed, small number of items (2–5), reach for a plain array or tuple instead of allocating a Vec.

RUST

// Fixed-size array — lives on the stack, zero heap allocation
let rgb: [u8; 3] = [255, 128, 0];
println!("{:?}", rgb);

// Tuple — heterogeneous, stack-allocated
let point: (f64, f64) = (1.0, 2.0);
println!("x={} y={}", point.0, point.1);

// Named tuple struct for clarity
struct Color(u8, u8, u8);
let red = Color(255, 0, 0);
println!("r={} g={} b={}", red.0, red.1, red.2);

// Destructure
let [r, g, b] = rgb;
let (x, y) = point;

Tip

Arrays and tuples avoid heap allocation entirely. If your collection size is known at compile time and small, prefer them over Vec for performance and clarity.

External Crates Worth Knowing

indexmap — HashMap that remembers insertion order; useful when iteration order matters
dashmap — thread-safe concurrent HashMap with fine-grained locking
ahash — fast non-cryptographic hasher, drop-in replacement for the standard SipHash
smallvec — Vec-like collection that stores up to N elements on the stack before spilling to the heap
tinyvec — similar to smallvec but 100% safe Rust
slotmap — stable key-value store where keys remain valid after removals (useful for ECS or graph nodes)

Note

These crates exist because the standard library deliberately stays conservative. The std collections are excellent defaults; only reach for external ones after profiling or when you need a capability the std types genuinely lack.

Complete Example — Using Several Collections Together

RUST

use std::collections::{HashMap, HashSet, BinaryHeap, VecDeque};
use std::cmp::Reverse;

// Task scheduler: tasks have a priority and unique names
#[derive(Debug, Eq, PartialEq)]
struct Task { priority: u32, name: String }

impl Ord for Task {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        self.priority.cmp(&other.priority)
    }
}
impl PartialOrd for Task { fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> { Some(self.cmp(other)) } }

let mut queue: BinaryHeap<Task> = BinaryHeap::new();
let mut completed: HashSet<String> = HashSet::new();
let mut results: HashMap<String, String> = HashMap::new();
let mut history: VecDeque<String> = VecDeque::with_capacity(10);

queue.push(Task { priority: 1, name: "low".into() });
queue.push(Task { priority: 5, name: "high".into() });
queue.push(Task { priority: 3, name: "medium".into() });

while let Some(task) = queue.pop() {
    if completed.contains(&task.name) { continue; }

    let result = format!("done:{}", task.priority);
    results.insert(task.name.clone(), result);
    completed.insert(task.name.clone());

    history.push_back(task.name.clone());
    if history.len() > 5 { history.pop_front(); } // keep only last 5
}

println!("results: {:?}", results);
println!("history: {:?}", history);

Success

You now have a solid grasp of Rust's standard collection types — when to choose each one, how their performance characteristics differ, and how to combine them to solve real problems.