11. Advanced Collections
📋 Jump to Takeaways🎁 You know Vec and HashMap. But what if you need guaranteed uniqueness, sorted keys, a priority queue, or a double-ended buffer? Picking the right collection is the difference between clean code and fighting the standard library.
HashSet
A HashSet is a HashMap without values. It stores unique keys and gives you O(1) membership checks. If you've used Go, this is what you'd hack together with map[string]bool, except it's a real type with set operations built in.
use std::collections::HashSet;
fn main() {
let mut languages = HashSet::new();
languages.insert("Rust");
languages.insert("Go");
languages.insert("Rust"); // duplicate, ignored
println!("Count: {}", languages.len()); // Count: 2
println!("Has Rust: {}", languages.contains("Rust")); // Has Rust: true
println!("Has Python: {}", languages.contains("Python")); // Has Python: false
}Inserting a duplicate returns false (the value was already there). Inserting a new value returns true. This makes deduplication trivial.
If you already know the values upfront, use HashSet::from:
use std::collections::HashSet;
fn main() {
let allowed = HashSet::from(["admin", "editor", "viewer"]);
println!("{}", allowed.contains("admin")); // true
}Deduplication with HashSet
The most common use case: removing duplicates from a Vec while preserving only unique items.
use std::collections::HashSet;
fn main() {
let words = vec!["apple", "banana", "apple", "cherry", "banana"];
let unique: HashSet<&str> = words.into_iter().collect();
println!("{:?}", unique); // {"cherry", "banana", "apple"} (order varies)
}Collecting into a HashSet loses the original order. If you need to keep items in the order they first appeared, use a HashSet as a "have I seen this?" tracker while building a Vec:
use std::collections::HashSet;
fn main() {
let items = vec![3, 1, 4, 1, 5, 9, 2, 6, 5, 3];
let mut seen = HashSet::new();
let mut unique = Vec::new();
for item in items {
if seen.insert(item) {
// insert() returns true if the value was NEW
// insert() returns false if it was already in the set
unique.push(item);
}
}
println!("{:?}", unique); // [3, 1, 4, 5, 9, 2, 6] — first-seen order preserved
// Same thing as a one-liner using filter + collect:
let mut seen2 = HashSet::new();
let unique2: Vec<i32> = vec![3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
.into_iter()
.filter(|x| seen2.insert(*x))
.collect();
println!("{:?}", unique2); // [3, 1, 4, 5, 9, 2, 6]
}seen.insert(*x) returns true the first time it sees a value. That's why the filter keeps exactly the first occurrence.
Set Operations
HashSet supports the classic set operations: union, intersection, difference, and symmetric difference. Each returns an iterator.
use std::collections::HashSet;
fn main() {
let backend: HashSet<&str> = ["Rust", "Go", "Python"].into_iter().collect();
let frontend: HashSet<&str> = ["TypeScript", "Rust", "Python"].into_iter().collect();
let both: Vec<&str> = backend.intersection(&frontend).copied().collect();
println!("Both: {:?}", both); // Both: ["Rust", "Python"] (order varies)
let all: Vec<&str> = backend.union(&frontend).copied().collect();
println!("All: {:?}", all); // All: ["Rust", "Go", "Python", "TypeScript"] (order varies)
let only_backend: Vec<&str> = backend.difference(&frontend).copied().collect();
println!("Only backend: {:?}", only_backend); // Only backend: ["Go"] (order varies)
}These operations return iterators over references. .copied() converts &&str to &str (removes the extra reference layer). You can also chain .filter(), .map(), or .count() without allocating intermediate collections.
BTreeMap
BTreeMap is like HashMap but keeps keys sorted. Lookups are O(log n) instead of O(1), but you get ordered iteration and range queries for free.
use std::collections::BTreeMap;
fn main() {
let mut versions = BTreeMap::new();
versions.insert("1.0", "initial release");
versions.insert("2.1", "bug fixes");
versions.insert("1.5", "new features");
versions.insert("3.0", "breaking changes");
// Iteration is always sorted by key — ver and desc are references
for (ver, desc) in &versions {
println!("{}: {}", ver, desc);
}
// 1.0: initial release
// 1.5: new features
// 2.1: bug fixes
// 3.0: breaking changes
}When to pick BTreeMap over HashMap: you need sorted iteration, you need range queries, or your keys don't implement Hash (BTreeMap only requires Ord). Ord itself requires PartialOrd and Eq as supertraits, so in practice your key type needs all three. You typically #[derive(PartialEq, Eq, PartialOrd, Ord)] and move on.
Range Queries with BTreeMap
The killer feature of BTreeMap is .range(). It returns an iterator over a subset of entries defined by bounds.
use std::collections::BTreeMap;
fn main() {
let mut temps = BTreeMap::new();
temps.insert(6, 15); // 6am: 15C
temps.insert(9, 18); // 9am: 18C
temps.insert(12, 24); // noon: 24C
temps.insert(15, 27); // 3pm: 27C
temps.insert(18, 22); // 6pm: 22C
temps.insert(21, 17); // 9pm: 17C
// Temperatures between 9am and 6pm (inclusive)
println!("Daytime temps:");
for (hour, temp) in temps.range(9..=18) {
println!(" {}:00 -> {}C", hour, temp);
}
// 9:00 -> 18C
// 12:00 -> 24C
// 15:00 -> 27C
// 18:00 -> 22C
}HashMap can't do this. You'd have to iterate everything and filter, which is O(n). BTreeMap's .range() is O(log n + k) where k is the number of results.
BTreeSet
Same story as HashSet vs HashMap: BTreeSet is a BTreeMap without values. Sorted, deduplicated, with range queries.
use std::collections::BTreeSet;
fn main() {
let mut scores = BTreeSet::new();
scores.insert(85);
scores.insert(92);
scores.insert(78);
scores.insert(95);
scores.insert(88);
// Always iterated in sorted order
println!("All scores: {:?}", scores); // All scores: {78, 85, 88, 92, 95}
// Scores above 90 — range() returns references into the set
let high: Vec<&i32> = scores.range(90..).collect();
println!("High scores: {:?}", high); // High scores: [92, 95]
}Use BTreeSet when you need a sorted set or range queries over unique values. Use HashSet when you just need fast membership checks and don't care about order.
BinaryHeap
BinaryHeap is a max-heap: the largest element is always at the top. Pop gives you elements in descending order. This is your priority queue.
use std::collections::BinaryHeap;
fn main() {
let mut tasks = BinaryHeap::new();
tasks.push(3); // low priority
tasks.push(10); // high priority
tasks.push(1); // lowest
tasks.push(7); // medium
// Always pops the largest
println!("{:?}", tasks.pop()); // Some(10)
println!("{:?}", tasks.pop()); // Some(7)
println!("{:?}", tasks.pop()); // Some(3)
println!("{:?}", tasks.pop()); // Some(1)
}.peek() looks at the top without removing it. .push() and .pop() are both O(log n).
Min-Heap with Reverse
BinaryHeap is a max-heap by default. For a min-heap (smallest first), wrap values in std::cmp::Reverse.
use std::collections::BinaryHeap;
use std::cmp::Reverse;
fn main() {
let mut queue = BinaryHeap::new();
queue.push(Reverse(5));
queue.push(Reverse(1));
queue.push(Reverse(8));
queue.push(Reverse(3));
// Now pops smallest first
while let Some(Reverse(val)) = queue.pop() {
print!("{} ", val);
}
println!(); // 1 3 5 8
}Reverse flips the ordering. Reverse(1) > Reverse(8) because the inner comparison is reversed. The heap doesn't know or care, it just sees "larger" values at the top.
Priority Queue with Structs
For real priority queues, you typically push structs with a priority field. This example implements Ord manually to control the ordering. Don't worry if the trait implementations look unfamiliar — you'll learn traits in the next lesson. The key idea is that you tell the heap how to compare your structs.
use std::collections::BinaryHeap;
use std::cmp::Ordering;
#[derive(Eq, PartialEq)]
struct Task {
priority: u8,
name: String,
}
impl Ord for Task {
fn cmp(&self, other: &Self) -> Ordering {
self.priority.cmp(&other.priority)
}
}
impl PartialOrd for Task {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
fn main() {
let mut queue = BinaryHeap::new();
queue.push(Task { priority: 2, name: "send email".into() });
queue.push(Task { priority: 5, name: "fix crash".into() });
queue.push(Task { priority: 1, name: "update docs".into() });
while let Some(task) = queue.pop() {
println!("[{}] {}", task.priority, task.name);
}
// [5] fix crash
// [2] send email
// [1] update docs
}The highest priority number pops first. If you want lowest-first, flip the comparison in cmp or wrap the priority in Reverse.
VecDeque
VecDeque is a double-ended queue backed by a ring buffer. It gives you O(1) push and pop at both ends, unlike Vec which is O(n) for insert(0, x) or remove(0).
use std::collections::VecDeque;
fn main() {
let mut buf = VecDeque::new();
// Push to both ends
buf.push_back(1);
buf.push_back(2);
buf.push_front(0);
println!("{:?}", buf); // [0, 1, 2]
// Pop from both ends
println!("{:?}", buf.pop_front()); // Some(0)
println!("{:?}", buf.pop_back()); // Some(2)
println!("{:?}", buf); // [1]
}Internally, VecDeque uses a ring buffer. When elements are popped from the front, the space wraps around and gets reused. No shifting, no copying.
VecDeque as Queue and Stack
VecDeque works as both a FIFO queue and a LIFO stack, depending on which end you push and pop.
use std::collections::VecDeque;
fn main() {
// FIFO queue: push_back, pop_front
let mut queue = VecDeque::new();
queue.push_back("first");
queue.push_back("second");
queue.push_back("third");
println!("Queue (FIFO):");
while let Some(item) = queue.pop_front() {
println!(" {}", item);
}
// first, second, third
// Stack: push_back, pop_back (same as Vec)
let mut stack = VecDeque::new();
stack.push_back("first");
stack.push_back("second");
stack.push_back("third");
println!("Stack (LIFO):");
while let Some(item) = stack.pop_back() {
println!(" {}", item);
}
// third, second, first
}For a pure stack, Vec is fine (push/pop at the back is O(1)). VecDeque shines when you need efficient operations at the front, like a work queue or sliding window.
Choosing the Right Collection
Here's a quick decision guide:
| Need | Collection |
|---|---|
| Ordered list, index access | Vec |
| Key-value, fast lookup | HashMap |
| Unique values, membership check | HashSet |
| Key-value, sorted keys | BTreeMap |
| Unique values, sorted | BTreeSet |
| Priority queue (largest first) | BinaryHeap |
| Queue or double-ended ops | VecDeque |
All of these live in std::collections (except Vec and String, which are in the prelude).
Key Takeaways
- HashSet stores unique values with O(1) lookup.
insert()returnsfalsefor duplicates. - Set operations (union, intersection, difference) are built-in and return lazy iterators
- BTreeMap keeps keys sorted and supports
.range()queries in O(log n + k) - BTreeSet is a sorted set, use it when you need range queries over unique values
- BinaryHeap is a max-heap. Wrap values in
Reversefor a min-heap. - For custom priority queues, implement
Ordon your struct - VecDeque gives O(1) push/pop at both ends via a ring buffer
- Use VecDeque for queues (FIFO). Vec is fine for stacks (LIFO at the back).
- Pick HashMap/HashSet for speed, BTreeMap/BTreeSet for ordering
🎁 Your collections can hold any type, but what if you want to define shared behavior that works across different types without inheritance? Traits let you describe what a type can do, so completely unrelated types can share one interface.