Ordered Collections

Range Queries

One of the defining advantages of BTreeMap<K, V> and BTreeSet<T> over hash-based collections is the ability to perform ordered range queries in $O(\log n + k)$ time (where $k$ is the number of matching elements in the range), jumping directly to the lower bound in the B-Tree and walking leaf/internal nodes sequentially until the upper bound.

Expressing Interval Endpoints with std::ops::RangeBounds

Range queries accept any type implementing std::ops::RangeBounds<Q>, which includes all built-in range syntaxes as well as custom (Bound<Q>, Bound<Q>) pairs:

pub enum Bound<T> {
    Included(T),
    Excluded(T),
    Unbounded,
}
Range Syntax Lower Bound Upper Bound Mathematical Interval
a..b Included(&a) Excluded(&b) $[a, b)$
a..=b Included(&a) Included(&b) $[a, b]$
a.. Included(&a) Unbounded $[a, +\infty)$
..b Unbounded Excluded(&b) $(-\infty, b)$
..=b Unbounded Included(&b) $(-\infty, b]$
.. Unbounded Unbounded $(-\infty, +\infty)$
(Bound::Excluded(a), Bound::Included(b)) Excluded(a) Included(b) $(a, b]$ (open lower bound!)

Querying Half-Open, Closed, and Open-Lower Intervals

Because Rust does not have a dedicated built-in syntax for an exclusive lower bound $(a, b]$, passing a 2-tuple (Bound::Excluded(a), Bound::Included(b)) lets you express any combination of open and closed endpoints:

use std::collections::BTreeSet;
use std::ops::Bound::{Excluded, Included};

fn main() {
    let scores = BTreeSet::from([10, 20, 30, 40, 50]);

    // 1. Closed interval [20, 40] (`20..=40`):
    let closed: Vec<i32> = scores.range(20..=40).copied().collect();

    // 2. Half-open interval (20, 40] (strictly > 20 and <= 40):
    let open_left: Vec<i32> = scores
        .range((Excluded(&20), Included(&40)))
        .copied()
        .collect();

    println!("[20, 40]: {closed:?}");
    println!("(20, 40]: {open_left:?}");
}

[20, 40]: [20, 30, 40]
(20, 40]: [30, 40]

Predecessor (<= x) and Successor (>= x) Lookups in $O(\log n)$

Combining .range() with .next() or .next_back() implements C++-style lower_bound, upper_bound, floor, and ceiling queries in $O(\log n)$ time:

Query Idiomatic BTreeMap / BTreeSet Expression
Smallest key $\ge x$ (ceiling / lower_bound) map.range(x..).next()
Smallest key $> x$ (strict successor / upper_bound) map.range((Excluded(x), Unbounded)).next()
Largest key $\le x$ (floor) map.range(..=x).next_back()
Largest key $< x$ (strict predecessor) map.range(..x).next_back() 
use std::collections::BTreeMap;

fn main() {
    let versions = BTreeMap::from([(100, "v1.0"), (200, "v2.0"), (300, "v3.0")]);

    let floor_250 = versions.range(..=250).next_back();
    let ceil_250 = versions.range(250..).next();

    println!("Floor of 250 (<= 250):   {floor_250:?}");
    println!("Ceiling of 250 (>= 250): {ceil_250:?}");
}

Floor of 250 (<= 250):   Some((&200, &"v2.0"))
Ceiling of 250 (>= 250): Some((&300, &"v3.0"))