Ordered Collections

BTreeSet

BTreeSet<T> (std::collections::BTreeSet) is an ordered set of unique elements implemented as a thin wrapper around BTreeMap<T, ()>, keeping all elements sorted by T: Ord and supporting $O(\log n)$ membership checks, min/max extraction, and range queries.

Memory Layout and Zero-Sized Value Optimization

Because () occupies 0 bytes, the vals: [(); 11] array inside each BTreeMap<T, ()> node compiles away to zero bytes of storage. Each B-Tree node in a BTreeSet<T> stores only the contiguous array of up to 11 sorted elements T (plus child pointers on internal nodes).

Essential BTreeSet<T> Methods

Method Signature Return Type Behavior
set.insert(val) fn insert(&mut self, value: T) -> bool bool Inserts val if absent (true); keeps existing equal element and returns false if present
set.replace(val) fn replace(&mut self, value: T) -> Option<T> Option<T> Inserts val, replacing and returning any existing equal element Some(old)
set.contains(&q) fn contains<Q>(&self, value: &Q) -> bool bool $O(\log n)$ binary search down the B-Tree
set.get(&q) fn get<Q>(&self, value: &Q) -> Option<&T> Option<&T> Returns a reference to the stored element matching q
set.remove(&q) fn remove<Q>(&mut self, value: &Q) -> bool bool Removes matching element and returns true if present
set.take(&q) fn take<Q>(&mut self, value: &Q) -> Option<T> Option<T> Removes and returns ownership of the matching element Some(T)
set.first() / set.last() fn first(&self) -> Option<&T> Option<&T> Returns smallest or largest element in $O(\log n)$
set.pop_first() / set.pop_last() fn pop_first(&mut self) -> Option<T> Option<T> Removes and returns smallest or largest element in $O(\log n)$ 
use std::collections::BTreeSet;

fn main() {
    let mut ports = BTreeSet::from([8080_u16, 80, 443, 80]);

    ports.insert(22);
    println!("Sorted unique ports: {ports:?}");
    println!("Smallest port:       {:?}", ports.first());
    println!("Largest port:        {:?}", ports.last());

    // Bidirectional sorted iteration (`.iter().rev()`):
    let descending: Vec<u16> = ports.iter().copied().rev().collect();
    println!("Descending order:    {descending:?}");
}

Sorted unique ports: {22, 80, 443, 8080}
Smallest port:       Some(&22)
Largest port:        Some(&8080)
Descending order:    [8080, 443, 80, 22]

Bidirectional Iteration (DoubleEndedIterator)

Unlike HashSet<T>, all BTreeSet<T> and BTreeMap<K, V> iterators (.iter(), .into_iter(), .range()) implement DoubleEndedIterator, so calling .rev() iterates from the largest element down to the smallest in $O(n)$ time without allocating or sorting a separate vector.