Skip to content
Tutorials Center
My learning

Topics

Rust Reference ยท Collections

Rust BTreeMap<K, V> type

Reference for Rust BTreeMap<K, V>: a map sorted by key, with O(log n) operations, ordered iteration, entry API, range queries and the Ord requirement.

BTreeMap<K, V> in std::collections is an ordered map built on a B-tree. Keys are kept sorted according to Ord, so iteration always visits them in ascending order and you can ask ordered questions such as "the smallest key", "everything between 10 and 20" or "the first key at or after x".

Compared with HashMap, lookups cost O(log n) instead of O(1) on average, but the order is deterministic, the key type needs only Ord (not Hash), and there are no hasher settings. Because B-tree nodes hold many keys in a small array, a BTreeMap is much more cache friendly than a binary search tree.

Rust
use std::collections::BTreeMap;

let mut m = BTreeMap::new();
m.insert(3, "c");
m.insert(1, "a");
// iterates 1, 3

Try it

Rust Always sorted

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 Keys need Ord and pop_first

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 struct BTreeMap<K, V, A = Global> { /* private */ }

impl<K, V> BTreeMap<K, V> {
    pub const fn new() -> BTreeMap<K, V>;
}

impl<K: Ord, V> BTreeMap<K, V> {
    pub fn insert(&mut self, key: K, value: V) -> Option<V>;
    pub fn get<Q>(&self, key: &Q) -> Option<&V> where K: Borrow<Q>, Q: Ord + ?Sized;
    pub fn remove<Q>(&mut self, key: &Q) -> Option<V> where K: Borrow<Q>, Q: Ord + ?Sized;
    pub fn entry(&mut self, key: K) -> Entry<'_, 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 range<T, R>(&self, range: R) -> Range<'_, K, V> where R: RangeBounds<T>;
    pub fn append(&mut self, other: &mut BTreeMap<K, V>);
    pub fn split_off<Q>(&mut self, key: &Q) -> BTreeMap<K, V>;
}
Name Description
K Key type; must implement Ord (a total order).
key, value The pair. insert moves both into the map.
range Any range expression such as 3..7, ..=9 or (Bound, Bound).
other Map to merge in with append; it is left empty.

Returns: insert returns the previous value if the key existed. Lookups return Option. pop_first and pop_last return the owned pair.

Errors and panics: behavior is unspecified (but memory-safe) if Ord is inconsistent or a key's ordering changes while stored. range panics if the start is greater than the end, or if both bounds are equal and excluded. Indexing with map[&k] panics for a missing key.

Usage notes

  • Complexity: insert, get, remove are O(log n); iteration is O(n) and visits in key order; first_key_value and last_key_value are O(log n).
  • Deterministic output: unlike HashMap, printing a BTreeMap with {:?} is stable, which makes it good for tests and reports.
  • Key requirement: Ord, not Hash. Floats are not Ord; wrap them (for example with f64::total_cmp) or use integers.
  • Both iterators are double ended, so .rev() walks from the largest key down.
  • Ordered queries such as "greatest key below x" use range with next_back().
  • Edit while iterating? Not allowed; use retain or collect keys first. iter_mut and values_mut change values only.
  • Merge: append is faster than inserting one by one when the second map is large.
  • Small maps are often faster in a BTreeMap than in a HashMap thanks to contiguous nodes, and no hashing is needed.
  • pop_first and pop_last are stable since Rust 1.66; first_key_value and last_key_value since 1.66 as well.