Skip to content
Tutorials Center
My learning

Topics

Rust Reference ยท Collections

Rust BTreeMap range and first/last

Reference for ordered queries on Rust BTreeMap: range, range_mut, first_key_value, last_key_value, pop_first, pop_last and floor/ceiling lookups.

The reason to choose a BTreeMap over a HashMap is usually ordered access. range(a..b) returns an iterator over all entries whose key falls in the given range, in ascending order, without scanning the rest of the map. first_key_value and last_key_value peek at the smallest and largest entries, and pop_first and pop_last remove them, which makes a BTreeMap usable as a priority queue with updatable priorities.

BTreeSet offers the same methods with first, last, pop_first, pop_last and range over single values.

Rust
use std::collections::BTreeMap;

let m: BTreeMap<u32, &str> = BTreeMap::from([(10, "a"), (20, "b"), (30, "c")]);
let mid: Vec<_> = m.range(15..=30).collect(); // [(20, "b"), (30, "c")]

Try it

Rust Range queries

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

Rust first, last, pop and range_mut

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

Syntax

Rust
pub fn range<T: ?Sized, R>(&self, range: R) -> Range<'_, K, V>
    where T: Ord, K: Borrow<T> + Ord, R: RangeBounds<T>
pub fn range_mut<T: ?Sized, R>(&mut self, range: R) -> RangeMut<'_, K, V>
pub fn first_key_value(&self) -> Option<(&K, &V)>
pub fn last_key_value(&self) -> Option<(&K, &V)>
pub fn pop_first(&mut self) -> Option<(K, V)>
pub fn pop_last(&mut self) -> Option<(K, V)>
pub fn first_entry(&mut self) -> Option<OccupiedEntry<'_, K, V>>
pub fn last_entry(&mut self) -> Option<OccupiedEntry<'_, K, V>>
Name Description
range Any RangeBounds: a..b, a..=b, a.., ..b, ..=b, .., or a tuple of two Bound values.

Returns: range and range_mut give double-ended iterators over (&K, &V) and (&K, &mut V). The first_*/last_*/pop_* methods return None on an empty map.

Errors and panics: range panics if the start bound is greater than the end bound, or if both are equal and both excluded ((Excluded(3), Excluded(3))). An empty range such as 5..5 is fine.

Usage notes

  • Cost: finding the start of a range is O(log n); then each step is amortized O(1). Collecting k results is O(log n + k).
  • Floor and ceiling: "greatest key <= x" is range(..=x).next_back(); "smallest key >= x" is range(x..).next(). These are the standard idioms for interval tables, version lookups and time-line queries.
  • Borrowed bounds: with String keys, pass &str bounds using explicit Bound values, for example (Included("a"), Excluded("c")). A plain "a".."c" of &str also works because String: Borrow<str>.
  • first_entry and last_entry give an OccupiedEntry so you can inspect, modify or remove the extreme element without a second lookup.
  • Priority queue use: repeatedly pop_first() to process the smallest key. Unlike BinaryHeap you can also look up and remove by key.
  • Iterating while mutating the map is impossible; range_mut lets you change values only.
  • Same API on sets: BTreeSet::range, first, last, pop_first and pop_last.