Collections in Rust

Vec<T> — Dynamic Array

Vec<T> is Rust’s workhorse collection — a heap-allocated, contiguous, growable array. It is the right default choice whenever you need to store a variable number of values of the same type. Because elements are stored contiguously in memory, iteration and random access are cache-friendly and fast. Pre-allocating with Vec::with_capacity avoids repeated reallocations when the final size is known in advance.

fn main() {
    // Create
    let mut v: Vec<i32> = Vec::new();
    let v2 = vec![1, 2, 3, 4, 5];
    let _v3: Vec<i32> = Vec::with_capacity(100); // pre-allocate to avoid reallocations

    // Add elements
    v.push(10);
    v.push(20);
    v.push(30);

    // Access — indexing panics on out of bounds; .get() returns Option
    println!("{}", v[0]);              // panics if out of bounds
    println!("{:?}", v.get(1));        // safe access
    println!("{:?}", v.get(99));       // no panic

    // Modify
    v[0] = 100;

    // Remove
    let last = v.pop();                // removes from the end
    v.remove(0);                       // removes index 0, shifts remaining elements
    println!("popped {:?}, left with {:?}", last, v);

    // Length and capacity
    println!("len: {}", v2.len());
    println!("is_empty: {}", v.is_empty());

    // Iterate by reference (v2 is not consumed)
    for n in &v2 {
        print!("{} ", n);
    }
    println!();

    // Slice operations
    println!("{:?}", &v2[1..4]);
    println!("{:?}", v2.first());
    println!("{:?}", v2.last());
}

$ rustc collections_vec_t_dynamic_array.rs && ./collections_vec_t_dynamic_array
10
Some(20)
None
popped Some(30), left with [20]
len: 5
is_empty: false
1 2 3 4 5 
[2, 3, 4]
Some(1)
Some(5)

v[0] prints 10 but v.get(99) prints None rather than crashing — the same out-of-range index with v[99] would panic. After v[0] = 100, pop takes 30 off the end and remove(0) drops the 100, leaving [20]. &v2[1..4] is a slice: indices 1, 2 and 3, end-exclusive.

Common Vec Operations

fn main() {
    let mut v = vec![3, 1, 4, 1, 5, 9, 2, 6];

    // Sort then deduplicate consecutive duplicates
    v.sort();
    println!("{:?}", v);
    v.dedup();           // dedup only removes consecutive duplicates — sort first
    println!("{:?}", v);

    // retain keeps only elements satisfying the predicate
    v.retain(|&x| x % 2 == 0);
    println!("{:?}", v);

    // Extend appends elements from any iterable
    let mut a = vec![1, 2, 3];
    a.extend([4, 5, 6]);
    println!("{:?}", a);

    // chain + collect concatenates without mutating either source
    let b = vec![7, 8, 9];
    let c: Vec<i32> = a.iter().chain(b.iter()).copied().collect();
    println!("{:?}", c);

    // flatten removes one level of nesting from a Vec<Vec<T>>
    let nested = vec![vec![1, 2], vec![3, 4], vec![5, 6]];
    let flat: Vec<i32> = nested.into_iter().flatten().collect();
    println!("{:?}", flat);
}

$ rustc collections_common_vec_operations.rs && ./collections_common_vec_operations
[1, 1, 2, 3, 4, 5, 6, 9]
[1, 2, 3, 4, 5, 6, 9]
[2, 4, 6]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6]

HashMap<K, V> — Hash Map

HashMap maps keys to values with O(1) average-case lookup, insert, and remove. It is the right choice when you need to associate data with arbitrary keys and access it by key later. The standard library’s HashMap uses a high-quality hash function by default that is resistant to hash-flooding attacks — if raw speed matters more than security you can swap in a faster hasher.

use std::collections::HashMap;

fn main() {
    let mut scores: HashMap<String, i32> = HashMap::new();

    // Insert key-value pairs
    scores.insert(String::from("Alice"), 95);
    scores.insert(String::from("Bob"), 87);
    scores.insert(String::from("Charlie"), 92);

    // Access — .get() returns Option, indexing panics on missing key
    println!("{:?}", scores.get("Alice"));
    println!("{:?}", scores.get("Dave"));
    println!("{}", scores["Alice"]);            // panics if the key is missing

    // Membership test
    println!("{}", scores.contains_key("Bob"));

    // Remove
    scores.remove("Bob");

    // Iterate — order is not guaranteed
    for (name, score) in &scores {
        println!("{}: {}", name, score);
    }

    // Overwrite an existing entry
    scores.insert(String::from("Alice"), 100);
    println!("{}", scores["Alice"]);
}

$ rustc collections_hashmap_k_v_hash_map.rs && ./collections_hashmap_k_v_hash_map
Some(95)
None
95
true
Alice: 95
Charlie: 92
100

Run it a few times and the Alice/Charlie lines swap places between runs: HashMap seeds its hasher randomly per process (that’s the hash-flooding protection), so iteration order is not just unspecified, it genuinely changes. Never rely on it — sort, or use BTreeMap.

The Entry API

The entry API solves a common pattern — insert a value if the key is absent, or update it if present — without a separate lookup. It avoids the double-hash and the clone that a contains_key + insert pair would require, making it both cleaner and faster for accumulation patterns like word counting.

use std::collections::HashMap;

fn word_count(text: &str) -> HashMap<&str, usize> {
    let mut map = HashMap::new();

    for word in text.split_whitespace() {
        // or_insert returns a mutable reference to the value, inserting 0 if absent
        *map.entry(word).or_insert(0) += 1;
    }

    map
}

fn main() {
    let counts = word_count("the quick brown fox jumps over the lazy fox");
    let mut pairs: Vec<_> = counts.iter().collect();
    // Highest count first; ties broken alphabetically so the output is stable
    pairs.sort_by_key(|&(word, count)| (std::cmp::Reverse(*count), *word));

    for (word, count) in pairs.iter().take(3) {
        println!("{}: {}", word, count);
    }
}

$ rustc collections_the_entry_api.rs && ./collections_the_entry_api
fox: 2
the: 2
brown: 1

use std::collections::HashMap;

fn main() {
    let mut map: HashMap<&str, Vec<i32>> = HashMap::new();

    // or_insert_with creates the Vec lazily only when the key is absent
    map.entry("evens").or_insert_with(Vec::new).push(2);
    map.entry("evens").or_insert_with(Vec::new).push(4);
    map.entry("odds").or_insert_with(Vec::new).push(1);

    println!("evens: {:?}", map["evens"]);
    println!("odds:  {:?}", map["odds"]);
}

$ rustc collections_the_entry_api_2.rs && ./collections_the_entry_api_2
evens: [2, 4]
odds:  [1]

The second entry("evens") found the existing Vec and pushed onto it; Vec::new only ran twice, once per distinct key. Printing keys explicitly (rather than {:?} on the whole map) keeps the output in a fixed order.

HashSet<T> — Unique Elements

HashSet is a collection of unique values backed by a hash table. It is ideal when you care about membership rather than order — checking whether an element exists, deduplicating a list, or computing set operations like union and intersection. The underlying hash mechanism is the same as HashMap, so lookup is O(1) average.

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 — silently ignored

    println!("{}", set.contains(&2));
    println!("{}", set.len());        // the duplicate 2 was not added

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

    // Set algebra — all return iterators over references
    let union: HashSet<_>        = a.union(&b).collect();
    let intersection: HashSet<_> = a.intersection(&b).collect();
    let difference: HashSet<_>   = a.difference(&b).collect();

    // HashSet order changes from run to run — sort before printing
    let sorted = |s: &HashSet<&i32>| { let mut v: Vec<i32> = s.iter().map(|&&x| x).collect(); v.sort(); v };
    println!("union: {:?}", sorted(&union));
    println!("intersection: {:?}", sorted(&intersection));
    println!("a - b: {:?}", sorted(&difference));

    println!("a subset of union: {}", a.is_subset(&union.into_iter().copied().collect()));
}

$ rustc collections_hashset_t_unique_elements.rs && ./collections_hashset_t_unique_elements
true
3
union: [1, 2, 3, 4, 5, 6]
intersection: [3, 4]
a - b: [1, 2]
a subset of union: true

union, intersection and difference yield &i32 references into a and b, which is why the sets are HashSet<&i32>; the copied() in the last line turns them back into owned i32s so is_subset can compare against a.

BTreeMap<K, V> — Sorted Map

BTreeMap is like HashMap but keys are always stored in sorted order, which means iteration visits keys in ascending order and you can efficiently query ranges. The trade-off is O(log n) operations instead of O(1). Use it when you need sorted output, need to find the minimum or maximum key, or need to query a range of keys.

use std::collections::BTreeMap;

fn main() {
    let mut scores: BTreeMap<&str, i32> = BTreeMap::new();
    scores.insert("Charlie", 92);
    scores.insert("Alice", 95);
    scores.insert("Bob", 87);

    // Iteration always visits keys in sorted (alphabetical) order
    for (name, score) in &scores {
        println!("{}: {}", name, score);
    }

    // Range queries — only possible with BTreeMap, not HashMap
    for (name, score) in scores.range("Alice"..="Bob") {
        println!("{}: {}", name, score);
    }
}

$ rustc collections_btreemap_k_v_sorted_map.rs && ./collections_btreemap_k_v_sorted_map
Alice: 95
Bob: 87
Charlie: 92
Alice: 95
Bob: 87

VecDeque<T> — Double-Ended Queue

VecDeque is a ring buffer that supports efficient push and pop from both ends. It is the right choice when you need a queue (FIFO) or deque — pushing to the back and popping from the front is O(1), unlike Vec where removing from the front is O(n) because it shifts all elements.

use std::collections::VecDeque;

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

    // O(1) push to either end
    deque.push_back(1);
    deque.push_back(2);
    deque.push_front(0);

    println!("{:?}", deque);

    // O(1) pop from either end
    println!("{:?}", deque.pop_front());
    println!("{:?}", deque.pop_back());
}

$ rustc collections_vecdeque_t_double_ended_queue.rs && ./collections_vecdeque_t_double_ended_queue
[0, 1, 2]
Some(0)
Some(2)

Collecting into Collections

The .collect() method is how you materialize an iterator into a concrete collection. Because collect is generic, Rust can build any collection type as long as you tell it which one — either through a type annotation or the turbofish syntax. This makes iterator pipelines compose naturally with any collection you need.

use std::collections::{HashMap, HashSet};

fn main() {
    // Vec — most common collect target
    let squares: Vec<i32> = (1..=5).map(|x| x * x).collect();
    println!("{:?}", squares);

    // HashSet — automatically deduplicates
    let unique: HashSet<i32> = vec![1, 2, 2, 3, 3, 3].into_iter().collect();
    println!("{}", unique.len());

    // HashMap — collect from an iterator of (key, value) tuples
    let map: HashMap<&str, i32> = vec![("one", 1), ("two", 2), ("three", 3)]
        .into_iter()
        .collect();
    println!("{}", map["two"]);

    // partition — split one iterator into two Vecs based on a predicate
    let (evens, odds): (Vec<_>, Vec<_>) = (0..10).partition(|&x| x % 2 == 0);
    println!("{:?}", evens);
    println!("{:?}", odds);
}

$ rustc collections_collecting_into_collections.rs && ./collections_collecting_into_collections
[1, 4, 9, 16, 25]
3
2
[0, 2, 4, 6, 8]
[1, 3, 5, 7, 9]

Practice

1. With let v = vec![10, 20, 30];, print v.get(99) and then v[99]. What happens on each line?

   Solution

   None
   
   thread 'main' (29260) panicked at collections_oob.rs:4:21:
   index out of bounds: the len is 3 but the index is 99

   get reports absence as a value; indexing treats it as a bug and panics. Both compile — the difference only shows at runtime.

2. Rewrite word_count to return a BTreeMap<&str, usize> and print the whole map with {:?}.

   Solution

   Change HashMap to BTreeMap in the use line, the return type and ::new() — the entry API is identical. Printing the map gives keys in sorted order, the same on every run:

   {"brown": 1, "fox": 2, "jumps": 1, "lazy": 1, "over": 1, "quick": 1, "the": 2}

3. Predict what dedup() does to vec![1, 2, 1, 2, 2, 3], then what sort() followed by dedup() does.

   Solution

   [1, 2, 1, 2, 3]
   [1, 2, 3]

   dedup only removes consecutive duplicates — the 2, 2 pair collapses, but the scattered 1s and 2s survive. Sorting first makes every duplicate consecutive. (To keep the original order instead, filter through a HashSet.)

4. Use a VecDeque as a sliding window of the last 3 readings from [5, 7, 9, 11, 13], printing the window and its average after each reading.

   Solution

   use std::collections::VecDeque;
   
   fn main() {
       let mut window: VecDeque<i32> = VecDeque::new();
       for reading in [5, 7, 9, 11, 13] {
           window.push_back(reading);
           if window.len() > 3 {
               window.pop_front();
           }
           let avg: f64 = window.iter().sum::<i32>() as f64 / window.len() as f64;
           println!("{:?} avg {:.1}", window, avg);
       }
   }

   [5] avg 5.0
   [5, 7] avg 6.0
   [5, 7, 9] avg 7.0
   [7, 9, 11] avg 9.0
   [9, 11, 13] avg 11.0

   pop_front is O(1) on a VecDeque; Vec::remove(0) would shift every element.