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.
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
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.
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
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
kresults is O(log n + k). - Floor and ceiling: "greatest key <= x" is
range(..=x).next_back(); "smallest key >= x" isrange(x..).next(). These are the standard idioms for interval tables, version lookups and time-line queries. - Borrowed bounds: with
Stringkeys, pass&strbounds using explicitBoundvalues, for example(Included("a"), Excluded("c")). A plain"a".."c"of&stralso works becauseString: Borrow<str>. first_entryandlast_entrygive anOccupiedEntryso you can inspect, modify or remove the extreme element without a second lookup.- Priority queue use: repeatedly
pop_first()to process the smallest key. UnlikeBinaryHeapyou can also look up and remove by key. - Iterating while mutating the map is impossible;
range_mutlets you change values only. - Same API on sets:
BTreeSet::range,first,last,pop_firstandpop_last.