Ordered Collections

range()

The .range(range) method on BTreeMap<K, V> and BTreeSet<T> returns a lazy, double-ended iterator over all entries whose keys fall within the specified bounds.

Signatures on BTreeMap and BTreeSet

// On BTreeMap<K, V>:
pub fn range<T, R>(&self, range: R) -> std::collections::btree_map::Range<'_, K, V>
where
    T: Ord + ?Sized,
    K: Borrow<T> + Ord,
    R: RangeBounds<T>;

// On BTreeSet<T>:
pub fn range<K, R>(&self, range: R) -> std::collections::btree_set::Range<'_, T>
where
    K: Ord + ?Sized,
    T: Borrow<K> + Ord,
    R: RangeBounds<K>;

Because K: Borrow<T> and T: Ord + ?Sized, you can pass a range of borrowed &str slices (map.range("a".."m")) to a BTreeMap<String, V> without allocating String endpoints!

Querying BTreeMap<String, V> with &str Range Endpoints

Note a subtle Rust syntax rule with unsized str: when querying a BTreeMap<String, V> with &str literals, either pass String references or specify (Bound<&str>, Bound<&str>) / .range::<str, _>(...) when the compiler needs to know whether T is str or &str:

use std::collections::BTreeMap;

fn main() {
    let directory = BTreeMap::from([
        (String::from("alice"), "eng"),
        (String::from("bob"), "sales"),
        (String::from("carol"), "eng"),
        (String::from("dave"), "ops"),
        (String::from("erin"), "sec"),
    ]);

    // Zero-allocation range query on `BTreeMap<String, &str>` using `T = str`:
    println!("Names from 'b' through 'd':");
    for (name, dept) in directory.range::<str, _>("b"..="d") {
        println!("  {name:<6} ({dept})");
    }
}

Names from 'b' through 'd':
  bob    (sales)
  carol  (eng)
  dave   (ops)

Reverse Iteration Over a Subrange (.range(...).rev())

Because btree_map::Range and btree_set::Range implement DoubleEndedIterator, calling .rev() walks the subrange from the upper bound down to the lower bound in $O(\log n + k)$ time:

use std::collections::BTreeMap;

fn main() {
    let events = BTreeMap::from([
        (10, "init"),
        (20, "connect"),
        (30, "query"),
        (40, "close"),
    ]);

    let recent_first: Vec<(&i32, &&str)> = events.range(15..=35).rev().collect();
    println!("Events in 15..=35 (newest first): {recent_first:?}");
}

Events in 15..=35 (newest first): [(30, &"query"), (20, &"connect")]

Runtime Panic Conditions of .range()

.range(start..end) panics at runtime if the lower bound is greater than the upper bound (start > end), or if both bounds are Bound::Excluded(x) with the exact same value (Excluded(x), Excluded(x)) (which represents an impossible empty open interval $(x, x)$):

// Panics at runtime: `range start is greater than range end in BTreeMap`
// map.range(50..10);