Standard Collections

BTreeSet<T>

BTreeSet<T> (std::collections::BTreeSet) is an ordered set of unique elements backed by a BTreeMap<T, ()>, maintaining elements in ascending T: Ord order and supporting $O(\log n)$ membership checks, min/max extraction, range queries, and linear-time ordered set algebra.

Key Capabilities of BTreeSet<T>

Operation Method Time Complexity
Insert / remove / contains set.insert(x) / set.remove(&q) / set.contains(&q) $O(\log n)$
Inspect minimum / maximum set.first() -> Option<&T> / set.last() -> Option<&T> $O(\log n)$
Pop minimum / maximum set.pop_first() -> Option<T> / set.pop_last() -> Option<T> $O(\log n)$
Subrange iteration set.range(min..=max) $O(\log n + k)$
Set algebra (union, intersection, difference) a.union(&b) / a.intersection(&b) $O(n + m)$ sorted merge

Sorted Deduplication, Min/Max Extraction, and Range Queries

use std::collections::BTreeSet;

fn main() {
    let mut versions = BTreeSet::from([3, 1, 4, 1, 5, 9, 2, 6]);

    println!("Sorted unique: {versions:?}");
    println!("Min: {:?}, Max: {:?}", versions.first(), versions.last());

    // Query all elements in the inclusive range `3..=6`:
    let mid_range: Vec<i32> = versions.range(3..=6).copied().collect();
    println!("Range 3..=6:   {mid_range:?}");

    let smallest = versions.pop_first();
    let largest = versions.pop_last();
    println!("Popped min={smallest:?}, max={largest:?}");
}

Sorted unique: {1, 2, 3, 4, 5, 6, 9}
Min: Some(&1), Max: Some(&9)
Range 3..=6:   [3, 4, 5, 6]
Popped min=Some(1), max=Some(9)

Using BTreeSet<T> as a Key in Another Set or Map

Unlike HashSet<T>, which does not implement Hash or Ord (because its iteration order is arbitrary), BTreeSet<T> implements both Hash and Ord whenever T implements them. This makes BTreeSet<T> the standard choice when you need a set of sets (BTreeSet<BTreeSet<T>> or HashMap<BTreeSet<T>, V>), such as in DFA state construction or graph algorithms:

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

fn main() {
    let mut state_transitions = HashMap::new();

    let nfa_state_set = BTreeSet::from([1_u32, 4, 2]);
    state_transitions.insert(nfa_state_set, "accepting");

    let lookup = BTreeSet::from([2_u32, 1, 4]);
    println!("DFA state lookup: {:?}", state_transitions.get(&lookup));
}

DFA state lookup: Some(&"accepting")