Rust’s standard library provides several general-purpose collection types. Unlike arrays and tuples (which live on the stack with fixed sizes), collections store their data on the heap and grow or shrink at runtime. Choosing the right collection for the job is one of the most impactful performance decisions you can make.
Vec<T> — The Workhorse
Vec<T> is a contiguous, growable array. It’s the most commonly used collection in Rust — use it whenever you need an ordered list of homogeneous values.
Creating and Populating
fn main() {
// Empty vec with explicit type
let mut v: Vec<i32> = Vec::new();
v.push(1);
v.push(2);
v.push(3);
// From literal with macro
let v2 = vec![10, 20, 30, 40, 50];
// Pre-allocate capacity (avoids reallocations)
let mut v3: Vec<String> = Vec::with_capacity(100);
for i in 0..100 {
v3.push(format!("item {}", i));
}
println!("len={}, capacity={}", v3.len(), v3.capacity()); // 100, 100
// From iterator
let squares: Vec<u32> = (1..=5).map(|x| x * x).collect();
println!("{:?}", squares); // [1, 4, 9, 16, 25]
}
Reading Elements
fn main() {
let v = vec![10, 20, 30, 40, 50];
// Index — panics if out of bounds
println!("{}", v[2]); // 30
// get() — returns Option<&T>
match v.get(2) {
Some(&val) => println!("{}", val),
None => println!("out of bounds"),
}
// First and last
println!("{:?}", v.first()); // Some(10)
println!("{:?}", v.last()); // Some(50)
// Slices
let middle = &v[1..4];
println!("{:?}", middle); // [20, 30, 40]
}
Modifying
fn main() {
let mut v = vec![3, 1, 4, 1, 5, 9, 2, 6];
// Insert/remove at position
v.insert(2, 99); // [3, 1, 99, 4, 1, 5, 9, 2, 6]
v.remove(2); // back to [3, 1, 4, 1, 5, 9, 2, 6]
// Remove and return last
println!("{:?}", v.pop()); // Some(6)
// Retain only elements matching predicate
v.retain(|&x| x % 2 != 0); // keep odds
println!("{:?}", v); // [3, 1, 1, 5, 9]
// Sort
let mut nums = vec![3, 1, 4, 1, 5, 9];
nums.sort();
println!("{:?}", nums); // [1, 1, 3, 4, 5, 9]
// Sort by key (descending)
nums.sort_by(|a, b| b.cmp(a));
println!("{:?}", nums); // [9, 5, 4, 3, 1, 1]
// Dedup (requires sorted)
nums.sort();
nums.dedup();
println!("{:?}", nums); // [1, 3, 4, 5, 9]
}
Iterating
fn main() {
let mut v = vec![1, 2, 3, 4, 5];
// Immutable iteration
for x in &v {
print!("{} ", x);
}
println!();
// Mutable iteration
for x in &mut v {
*x *= 2;
}
println!("{:?}", v); // [2, 4, 6, 8, 10]
// Consuming iteration (v is moved)
let sum: i32 = v.into_iter().sum();
println!("Sum: {}", sum); // 30
}
Vec as a Stack
fn main() {
let mut stack: Vec<String> = Vec::new();
stack.push("first".to_string());
stack.push("second".to_string());
stack.push("third".to_string());
while let Some(top) = stack.pop() {
println!("{}", top); // third, second, first
}
}
String — UTF-8 Text
String is a growable, heap-allocated, UTF-8 encoded string. It owns its data.
fn main() {
let mut s = String::new();
s.push_str("Hello");
s.push(',');
s.push_str(" world!");
println!("{}", s); // Hello, world!
// Concatenation with + (takes ownership of left side)
let s1 = String::from("Hello, ");
let s2 = String::from("Rust!");
let s3 = s1 + &s2; // s1 is moved, s2 borrowed
println!("{}", s3);
// format! — doesn't take ownership
let a = String::from("tic");
let b = String::from("tac");
let c = String::from("toe");
let combined = format!("{}-{}-{}", a, b, c);
println!("{} (a={}, b={}, c={})", combined, a, b, c); // all still valid
// Slicing — must be on char boundaries
let hello = "Здравствуйте"; // Cyrillic
let s = &hello[0..4]; // First 4 bytes = 2 Cyrillic chars
println!("{}", s);
// Safe character iteration
for c in "नमस्ते".chars() {
print!("{} ", c); // न म स ् त े
}
println!();
// String operations
let mixed = " hello world ";
println!("{}", mixed.trim()); // "hello world"
println!("{}", mixed.trim().to_uppercase()); // "HELLO WORLD"
println!("{}", "hello".replace("l", "r")); // "herro"
println!("{:?}", "a,b,c".split(',').collect::<Vec<_>>()); // ["a", "b", "c"]
}
HashMap<K, V> — Key-Value Lookup
HashMap provides O(1) average-case insert and lookup. Keys must implement Hash + Eq.
use std::collections::HashMap;
fn main() {
let mut scores: HashMap<String, u32> = HashMap::new();
// Insert
scores.insert("Alice".to_string(), 92);
scores.insert("Bob".to_string(), 85);
scores.insert("Carol".to_string(), 97);
// Lookup
if let Some(&score) = scores.get("Alice") {
println!("Alice: {}", score); // 92
}
// Entry API — insert only if absent
scores.entry("Dave".to_string()).or_insert(70);
scores.entry("Alice".to_string()).or_insert(0); // No-op, Alice exists
// Modify existing value
let alice_score = scores.entry("Alice".to_string()).or_insert(0);
*alice_score += 5; // Alice is now 97
// Iterate (unordered)
for (name, score) in &scores {
println!("{}: {}", name, score);
}
// Contains key
println!("{}", scores.contains_key("Eve")); // false
// Remove
scores.remove("Bob");
println!("{:?}", scores.keys().collect::<Vec<_>>());
}
Word Frequency Counter
The classic HashMap pattern:
use std::collections::HashMap;
fn word_count(text: &str) -> HashMap<&str, usize> {
let mut counts = HashMap::new();
for word in text.split_whitespace() {
*counts.entry(word).or_insert(0) += 1;
}
counts
}
fn main() {
let text = "hello world hello rust world hello";
let counts = word_count(text);
// Sort by count descending
let mut pairs: Vec<(&&str, &usize)> = counts.iter().collect();
pairs.sort_by(|a, b| b.1.cmp(a.1));
for (word, count) in pairs {
println!("{}: {}", word, count);
}
// hello: 3, world: 2, rust: 1
}
Building from Iterators
use std::collections::HashMap;
fn main() {
// From Vec of tuples
let map: HashMap<&str, i32> = vec![("a", 1), ("b", 2), ("c", 3)]
.into_iter()
.collect();
println!("{:?}", map);
// Group by first character
let words = vec!["apple", "ant", "bear", "avocado", "cat"];
let grouped: HashMap<char, Vec<&str>> = words.iter()
.fold(HashMap::new(), |mut acc, &w| {
acc.entry(w.chars().next().unwrap()).or_default().push(w);
acc
});
println!("{:?}", grouped);
}
HashSet<T> — Unique Values
HashSet stores unique values with O(1) insert and lookup. Useful for deduplication and membership tests:
use std::collections::HashSet;
fn main() {
let mut set: HashSet<i32> = HashSet::new();
set.insert(1);
set.insert(2);
set.insert(3);
set.insert(2); // Duplicate — ignored
println!("{}", set.contains(&2)); // true
println!("{}", set.len()); // 3
// Set operations
let a: HashSet<i32> = [1, 2, 3, 4].iter().copied().collect();
let b: HashSet<i32> = [3, 4, 5, 6].iter().copied().collect();
let union: HashSet<&i32> = a.union(&b).collect();
let intersection: HashSet<&i32> = a.intersection(&b).collect();
let difference: HashSet<&i32> = a.difference(&b).collect();
println!("union: {:?}", union); // {1, 2, 3, 4, 5, 6}
println!("intersection: {:?}", intersection); // {3, 4}
println!("difference a-b: {:?}", difference); // {1, 2}
// Deduplication
let with_dupes = vec![1, 2, 2, 3, 3, 3, 4];
let unique: HashSet<_> = with_dupes.into_iter().collect();
let mut sorted: Vec<_> = unique.into_iter().collect();
sorted.sort();
println!("{:?}", sorted); // [1, 2, 3, 4]
}
BTreeMap<K, V> — Sorted Key-Value
BTreeMap keeps keys in sorted order. Use it when you need ordered iteration or range queries. O(log n) operations:
use std::collections::BTreeMap;
fn main() {
let mut map = BTreeMap::new();
map.insert("banana", 3);
map.insert("apple", 5);
map.insert("cherry", 1);
map.insert("date", 4);
// Always iterates in sorted key order
for (fruit, qty) in &map {
println!("{}: {}", fruit, qty);
}
// apple: 5, banana: 3, cherry: 1, date: 4
// Range query
for (fruit, qty) in map.range("b"..="c") {
println!("range: {}: {}", fruit, qty);
}
// banana: 3, cherry: 1
// First and last
println!("{:?}", map.iter().next()); // Some(("apple", 5))
println!("{:?}", map.iter().next_back()); // Some(("date", 4))
}
VecDeque<T> — Double-Ended Queue
VecDeque supports O(1) push/pop from both ends. Use it as a queue or deque:
use std::collections::VecDeque;
fn main() {
let mut deque: VecDeque<i32> = VecDeque::new();
// Push front and back
deque.push_back(1);
deque.push_back(2);
deque.push_front(0);
deque.push_front(-1);
println!("{:?}", deque); // [-1, 0, 1, 2]
// FIFO queue: push_back + pop_front
while let Some(val) = deque.pop_front() {
print!("{} ", val); // -1 0 1 2
}
// Sliding window simulation
let data = vec![1, 3, 5, 7, 9, 11, 13];
let window_size = 3;
let mut window: VecDeque<i32> = VecDeque::new();
for &val in &data {
window.push_back(val);
if window.len() > window_size {
window.pop_front();
}
if window.len() == window_size {
let avg: f64 = window.iter().sum::<i32>() as f64 / window_size as f64;
println!("{:?} avg={:.1}", window, avg);
}
}
}
BinaryHeap<T> — Priority Queue
BinaryHeap is a max-heap. The largest element is always at the top:
use std::collections::BinaryHeap;
use std::cmp::Reverse;
fn main() {
// Max-heap (default)
let mut heap = BinaryHeap::new();
heap.push(5);
heap.push(1);
heap.push(8);
heap.push(3);
println!("{:?}", heap.peek()); // Some(8) — max
while let Some(val) = heap.pop() {
print!("{} ", val); // 8 5 3 1 (descending)
}
println!();
// Min-heap using Reverse wrapper
let mut min_heap: BinaryHeap<Reverse<i32>> = BinaryHeap::new();
min_heap.push(Reverse(5));
min_heap.push(Reverse(1));
min_heap.push(Reverse(8));
while let Some(Reverse(val)) = min_heap.pop() {
print!("{} ", val); // 1 5 8 (ascending)
}
}
Dijkstra’s Algorithm with BinaryHeap
use std::collections::{BinaryHeap, HashMap};
use std::cmp::Reverse;
fn shortest_paths(graph: &HashMap<&str, Vec<(&str, u32)>>, start: &str) -> HashMap<String, u32> {
let mut dist: HashMap<String, u32> = HashMap::new();
let mut heap: BinaryHeap<Reverse<(u32, String)>> = BinaryHeap::new();
heap.push(Reverse((0, start.to_string())));
dist.insert(start.to_string(), 0);
while let Some(Reverse((cost, node))) = heap.pop() {
if dist.get(&node).map_or(false, |&d| d < cost) {
continue; // Already found a shorter path
}
if let Some(neighbors) = graph.get(node.as_str()) {
for &(neighbor, weight) in neighbors {
let new_cost = cost + weight;
if new_cost < *dist.get(neighbor).unwrap_or(&u32::MAX) {
dist.insert(neighbor.to_string(), new_cost);
heap.push(Reverse((new_cost, neighbor.to_string())));
}
}
}
}
dist
}
Choosing the Right Collection
| Collection | Ordering | Duplicate keys/values | Lookup | Insert/Delete | Use when |
|---|---|---|---|---|---|
Vec<T> |
Insertion order | Yes | O(n) | O(1) end, O(n) middle | Ordered list, stack |
VecDeque<T> |
Insertion order | Yes | O(n) | O(1) both ends | Queue, deque |
HashMap<K,V> |
None | No (keys) | O(1) avg | O(1) avg | Key lookup |
BTreeMap<K,V> |
Sorted by key | No (keys) | O(log n) | O(log n) | Sorted map, range queries |
HashSet<T> |
None | No | O(1) avg | O(1) avg | Membership test, dedup |
BinaryHeap<T> |
Max first | Yes | O(1) peek | O(log n) | Priority queue |
Summary
Vec<T>is the default — use it unless you have a specific reason for another collectionHashMapfor key-value lookup when ordering doesn’t matterBTreeMapwhen keys must stay sorted or you need range queriesHashSetfor deduplication and membership testsVecDequewhen you push/pop from both endsBinaryHeapfor priority queues (e.g., Dijkstra, job scheduling)- Pre-allocate with
with_capacity()when you know the approximate size — it avoids repeated reallocations
Comments