Collections · about 45 min

Sets, VecDeque and Choosing a Collection

Why this matters

Vec and the maps cover most needs, but two other shapes come up constantly: "is this value in my collection?" (a set) and "first in, first out" (a queue). Using the right one turns a slow, awkward program into a fast, obvious one. This lesson covers HashSet, BTreeSet and VecDeque, mentions BinaryHeap, and ends with a guide to choosing among all the standard collections.

Sets: membership without values

A set stores distinct values and answers "is it there?" quickly. A HashSet<T> is literally a HashMap<T, ()>: keys with no values.

use std::collections::HashSet;

fn main() {
    let mut seen = HashSet::new();
    for word in "to be or not to be".split(' ') {
        let new = seen.insert(word);
        println!("{word:4} new: {new}");
    }
    println!("{} distinct, contains \"or\": {}", seen.len(), seen.contains("or"));
}

to   new: true
be   new: true
or   new: true
not  new: true
to   new: false
be   new: false
4 distinct, contains "or": true

insert returns true if the value was not already present, which makes "first time seeing this?" a single call. Removing duplicates, tracking visited states in a search, and checking membership against a list of allowed values are all set jobs. A Vec with contains gives the same answers but scans the whole list on each call: O(n) versus O(1). For thousands of checks against thousands of values, that is the difference between instant and minutes.

BTreeSet and set operations

BTreeSet<T> keeps values sorted, iterates in order, and supports ranges. Both set types support the operations from mathematics:

use std::collections::BTreeSet;

fn main() {
    let a: BTreeSet<i32> = [1, 2, 3, 4].into_iter().collect();
    let b: BTreeSet<i32> = [3, 4, 5].into_iter().collect();
    println!("union        {:?}", a.union(&b).collect::<Vec<_>>());
    println!("intersection {:?}", a.intersection(&b).collect::<Vec<_>>());
    println!("difference   {:?}", a.difference(&b).collect::<Vec<_>>());
    println!("symmetric    {:?}", a.symmetric_difference(&b).collect::<Vec<_>>());
    println!("subset: {}", [3, 4].into_iter().collect::<BTreeSet<_>>().is_subset(&a));
    println!("smallest {:?}, range {:?}", a.first(), a.range(2..4).collect::<Vec<_>>());
}

union        [1, 2, 3, 4, 5]
intersection [3, 4]
difference   [1, 2]
symmetric    [1, 2, 5]
subset: true
smallest Some(1), range [2, 3]

The operations return iterators of references; collect gathers them. With BTreeSet, results come out sorted; with HashSet, in arbitrary order (sort before printing). Values in a HashSet need Hash + Eq, in a BTreeSet they need Ord.

VecDeque: a double-ended queue

VecDeque<T> ("vec-deck") is a growable ring buffer: a Vec whose contents may wrap around the end of the allocation, so both ends can grow and shrink in O(1):

 capacity 8, holding [c, d, e, f] with head at slot 6:

 slots:   0   1   2   3   4   5   6   7
        [ e | f |   |   |   |   | c | d ]
                  ^ tail          ^ head

 push_front(b) -> slot 5;   push_back(g) -> slot 2;   pop_front() -> c

use std::collections::VecDeque;

fn main() {
    let mut q: VecDeque<&str> = VecDeque::new();
    q.push_back("job1");
    q.push_back("job2");
    q.push_front("urgent");
    println!("{:?} front={:?} back={:?}", q, q.front(), q.back());
    while let Some(job) = q.pop_front() {
        println!("processing {job}");
    }
}

["urgent", "job1", "job2"] front=Some("urgent") back=Some("job2")
processing urgent
processing job1
processing job2

Use it for queues (breadth-first search, task scheduling, buffering the last N items). It supports indexing and iteration like a Vec, though its elements are not guaranteed to be one contiguous slice.

BinaryHeap<T> is the other specialized collection: a priority queue where pop always returns the largest element (wrap values in std::cmp::Reverse for smallest first). It suits "always process the most urgent item next" and algorithms like Dijkstra's shortest paths.

Choosing a collection

need	collection	key costs
a list in order, index by position	`Vec<T>`	push/pop end O(1), index O(1), insert/remove front O(n), contains O(n)
queue or deque (both ends)	`VecDeque<T>`	push/pop both ends O(1), index O(1)
lookup by key	`HashMap<K, V>`	insert/get/remove O(1) average; no order
lookup by key, sorted, ranges	`BTreeMap<K, V>`	O(log n); sorted iteration
membership, uniqueness	`HashSet<T>`	O(1) average; no order
sorted unique values, ranges	`BTreeSet<T>`	O(log n); sorted
always take the largest	`BinaryHeap<T>`	push/pop O(log n), peek O(1)

Some practical guidance:

Start with Vec. It is compact, cache-friendly and fast for small sizes, often beating "better" structures below a few dozen elements. Switch when profiling or the access pattern says so.
Need lookups by something other than position? A map or set.
Need deterministic output? BTree versions, or sort at the end.
Repeatedly removing from the front? VecDeque.
LinkedList exists, but it is rarely the right choice: Vec and VecDeque are almost always faster in practice.

The "O(...)" notation describes how cost grows with size n: O(1) is constant, O(log n) grows very slowly (20 steps for a million items), O(n) grows in proportion. An O(n) operation inside a loop over n items is O(n^2): fine for a hundred items, painful for a million.

Common mistakes

Vec::contains inside a loop over many items: quadratic. Build a HashSet once.
Printing a HashSet where the output must be stable: sort or use BTreeSet.
Vec::remove(0) as a queue: use VecDeque::pop_front.
Sets of floats: E0277 (f64 is not Hash/Eq/Ord).

Recap

HashSet and BTreeSet store distinct values; insert returns whether the value was new.
Set operations: union, intersection, difference, symmetric_difference, is_subset.
VecDeque is a ring buffer with O(1) operations at both ends; BinaryHeap pops the largest first.
Choose by access pattern: position (Vec), both ends (VecDeque), key (maps), membership (sets), priority (heap).
Start with Vec; prefer BTree types when order or determinism matters.

Going further: implement breadth-first search over a small grid using a VecDeque for the frontier and a HashSet<(i32, i32)> for visited cells. Read the std::collections module docs, which include a performance table.

Exercises

Exercise 1 · write code

First repeat and unique words

Read words from stdin (whitespace separated, case-sensitive). Print the first word that appears for the second time (first repeat: WORD, or first repeat: none), then all distinct words in sorted order on one line separated by spaces:

first repeat: b
a b c d

for the input d b a b c a. Use a HashSet to detect the repeat (insert returns false when the value was already present) and a BTreeSet for the sorted list.

File: main.rs

Starting point

use std::collections::{BTreeSet, HashSet};
use std::io::{self, Read};

fn main() {
    let mut input = String::new();
    io::stdin().read_to_string(&mut input).unwrap();
}

Example

input

d b a b c a

expected output

first repeat: b
a b c d

Example

input

x y z

expected output

first repeat: none
x y z

Hint 1

if !seen.insert(w) && first_repeat.is_none() { first_repeat = Some(w); }

Hint 2

Collect the BTreeSet into a Vec<&str> and join(" ").

Reference solution

use std::collections::{BTreeSet, HashSet};
use std::io::{self, Read};

fn main() {
    let mut input = String::new();
    io::stdin().read_to_string(&mut input).unwrap();
    let mut seen = HashSet::new();
    let mut first_repeat = None;
    let mut all = BTreeSet::new();
    for w in input.split_whitespace() {
        if !seen.insert(w) && first_repeat.is_none() {
            first_repeat = Some(w);
        }
        all.insert(w);
    }
    println!("first repeat: {}", first_repeat.unwrap_or("none"));
    let list: Vec<&str> = all.into_iter().collect();
    println!("{}", list.join(" "));
}

Exercise 2 · write code

Set operations

The first line of stdin lists the languages Ada knows, the second line those Bob knows (space separated). Using two BTreeSet<&str>, print the intersection, the union, and the languages only Ada knows, each sorted and space separated:

both: c rust
either: c go python rust
only ada: python

for the lines rust python c and c go rust. Print an empty list as nothing after the colon and space, e.g. only ada:.

File: main.rs

Starting point

use std::collections::BTreeSet;
use std::io::{self, Read};

fn main() {
    let mut input = String::new();
    io::stdin().read_to_string(&mut input).unwrap();
    let mut lines = input.lines();
    let ada: BTreeSet<&str> = lines.next().unwrap_or("").split_whitespace().collect();
    let bob: BTreeSet<&str> = lines.next().unwrap_or("").split_whitespace().collect();
}

Example

input

rust python c
c go rust

expected output

both: c rust
either: c go python rust
only ada: python

Example

input

a
b

expected output

both: 
either: a b
only ada: a

Hint 1

ada.intersection(&bob), ada.union(&bob) and ada.difference(&bob) iterate in sorted order.

Hint 2

They yield &&str; .copied() or .map(|s| *s) gives &str to collect into a Vec<&str> for join.

Reference solution

use std::collections::BTreeSet;
use std::io::{self, Read};

fn show(label: &str, items: Vec<&&str>) {
    let words: Vec<&str> = items.into_iter().copied().collect();
    println!("{label}: {}", words.join(" "));
}

fn main() {
    let mut input = String::new();
    io::stdin().read_to_string(&mut input).unwrap();
    let mut lines = input.lines();
    let ada: BTreeSet<&str> = lines.next().unwrap_or("").split_whitespace().collect();
    let bob: BTreeSet<&str> = lines.next().unwrap_or("").split_whitespace().collect();
    show("both", ada.intersection(&bob).collect());
    show("either", ada.union(&bob).collect());
    show("only ada", ada.difference(&bob).collect());
}

Exercise 3 · write code

Keep the last N lines

Implement a tiny tail: the first line of stdin is a number n; print the last n of the remaining lines, in order. Use a VecDeque<String> as a bounded buffer: push each line at the back and pop from the front whenever it holds more than n, so memory stays bounded however long the input is. For 2, a, b, c:

b
c

File: main.rs

Starting point

use std::collections::VecDeque;
use std::io;

fn main() {
    let mut lines = io::stdin().lines();
    let n: usize = lines.next().unwrap().unwrap().trim().parse().unwrap();
}

Example

input

2
a
b
c

expected output

b
c

Example

input

5
only

expected output

only

Hint 1

buf.push_back(line) then if buf.len() > n { buf.pop_front(); }.

Hint 2

With n = 0 the buffer is emptied after every push, which correctly prints nothing.

Reference solution

use std::collections::VecDeque;
use std::io;

fn main() {
    let mut lines = io::stdin().lines();
    let n: usize = lines.next().unwrap().unwrap().trim().parse().unwrap();
    let mut buf: VecDeque<String> = VecDeque::with_capacity(n + 1);
    for line in lines {
        buf.push_back(line.unwrap());
        if buf.len() > n {
            buf.pop_front();
        }
    }
    for line in &buf {
        println!("{line}");
    }
}

Exercise 4 · quiz

Pick the collection

A program must process print jobs in arrival order, adding new jobs at one end and taking the next job from the other, thousands of times per second. Which collection fits best?

Vec, using push and remove(0)
VecDeque, using push_back and pop_front
HashSet
BTreeMap keyed by arrival time

Answer

VecDeque, using push_back and pop_front

A first-in first-out queue needs cheap operations at both ends. Vec::remove(0) shifts every remaining element, O(n) per job. VecDeque is a ring buffer with O(1) push and pop at both ends. A BTreeMap would work but costs O(log n) and more memory for no benefit here.