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.
use std::collections::BTreeMap; let mut m = BTreeMap::new(); m.insert(3, "c"); m.insert(1, "a"); // iterates 1, 3
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 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,removeare O(log n); iteration is O(n) and visits in key order;first_key_valueandlast_key_valueare O(log n). - Deterministic output: unlike
HashMap, printing aBTreeMapwith{:?}is stable, which makes it good for tests and reports. - Key requirement:
Ord, notHash. Floats are notOrd; wrap them (for example withf64::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
rangewithnext_back(). - Edit while iterating? Not allowed; use
retainor collect keys first.iter_mutandvalues_mutchange values only. - Merge:
appendis faster than inserting one by one when the second map is large. - Small maps are often faster in a
BTreeMapthan in aHashMapthanks to contiguous nodes, and no hashing is needed. pop_firstandpop_lastare stable since Rust 1.66;first_key_valueandlast_key_valuesince 1.66 as well.