BTreeMap and BTreeSet: the APIs that matter

Published 13 October 2026

What they are¶

BTreeMap<K, V> is an ordered map. BTreeSet<T> is the same thing without values (internally it’s a BTreeMap<T, SetValZST>). Both live in std::collections.

Keys need Ord, not Hash + Eq.
Iteration is always in sorted key order.
Lookups, inserts and removes are \(O(\log n)\).

Under the hood it’s a B-tree, not a binary tree: each node holds up to 11 keys in a contiguous array, so a lookup does a short linear scan per node. Fewer allocations and better cache behaviour than a red-black tree like C++’s std::map.

BTreeMap or HashMap?¶

You need	Use
Just get/insert/remove, fastest possible	`HashMap`
Sorted iteration, or deterministic output	`BTreeMap`
min / max / “next key after x” / range queries	`BTreeMap`
Keys that implement `Ord` but not `Hash`	`BTreeMap`

The deterministic-order point matters more than it seems: printing a HashMap gives a different order on every run, which makes snapshot tests and debug output flaky.

The basics¶

use std::collections::BTreeMap;

let mut m = BTreeMap::new();
assert_eq!(m.insert("b", 2), None);       // new key
assert_eq!(m.insert("b", 20), Some(2));   // returns the old value
m.insert("a", 1);
m.insert("c", 3);

assert_eq!(m.get("a"), Some(&1));
if let Some(v) = m.get_mut("c") { *v += 10; }
assert_eq!(m["c"], 13);                   // Index panics if missing
assert!(m.contains_key("b"));

assert_eq!(m.remove("b"), Some(20));
assert_eq!(m.remove_entry("a"), Some(("a", 1)));   // key back too
assert_eq!(m.len(), 1);

Building one from literals or an iterator:

let m = BTreeMap::from([(3, "c"), (1, "a"), (2, "b")]);
let squares: BTreeMap<u32, u32> = (1..=5).map(|k| (k, k * k)).collect();

Looking up `String` keys with `&str`¶

get, remove, contains_key and range take &Q where K: Borrow<Q>, so you don’t have to allocate a String just to look something up:

let mut scores: BTreeMap<String, u32> = BTreeMap::new();
scores.insert("alice".to_string(), 90);
assert_eq!(scores.get("alice"), Some(&90)); // &str, no allocation

The Entry API¶

Same as HashMap. One lookup instead of a contains_key followed by an insert.

// counting
let mut counts: BTreeMap<char, usize> = BTreeMap::new();
for c in "hello".chars() {
    *counts.entry(c).or_insert(0) += 1;
}

// grouping: or_default() needs V: Default
let mut by_len: BTreeMap<usize, Vec<&str>> = BTreeMap::new();
for w in ["hi", "yo", "rust"] {
    by_len.entry(w.len()).or_default().push(w);
}
assert_eq!(by_len[&2], ["hi", "yo"]);

// update if present, insert otherwise
counts.entry('h').and_modify(|n| *n += 100).or_insert(1);

What `entry` actually is¶

map.entry(k) means: search the tree once for where k is, or would go, and hand back that slot. It’s an enum:

enum Entry<'a, K, V> {
    Occupied(OccupiedEntry<'a, K, V>), // k is there: read, modify or remove its value
    Vacant(VacantEntry<'a, K, V>),     // k isn't: insert at the slot already found
}

The chained methods are shortcuts for matching on it. or_insert is roughly:

match map.entry(k) {
    Entry::Occupied(e) => e.into_mut(),   // &mut V to the existing value
    Entry::Vacant(e)   => e.insert(v),    // insert, then &mut V to the new value
}

So *map.entry(c).or_insert(0) += 1 reads as “find c’s slot, put a 0 there if it’s empty, give me the value, add 1”. Think of it as a cursor to where k belongs, not a fancier get.

Why it exists¶

1. Searching once instead of twice. The obvious version walks the tree two or three times:

if !map.contains_key(&k) { map.insert(k, 0); }
*map.get_mut(&k).unwrap() += 1;

entry reuses the slot from the first search. Other languages have the same thing for the same reason: Java’s merge / computeIfAbsent, Python’s setdefault / defaultdict.

2. The borrow checker. Updating in place without entry compiles:

if let Some(v) = m.get_mut(&k) { *v += 1; } else { m.insert(k, 1); }

But returning the reference is rejected, even though the logic is correct:

fn get_or_insert(m: &mut BTreeMap<String, u32>, k: String) -> &mut u32 {
    if let Some(v) = m.get_mut(&k) { return v; } // this borrow may be returned...
    m.insert(k.clone(), 0);                      // E0499: cannot borrow `*m` as mutable more than once
    m.get_mut(&k).unwrap()
}

The current borrow checker can’t see that the first borrow is dead when the if fails (a known limitation that Polonius, the next-generation borrow checker, is meant to fix). entry sidesteps it: there’s one &mut borrow of the map, from the search to the result.

Why not map[k] += 1 like C++? C++’s operator[] quietly inserts a default when the key is missing. In Rust, indexing never mutates the map: map[&k] panics on a missing key and can’t insert. entry is the explicit, opt-in version.

entry takes the key by value

With String keys, map.entry(name.to_string()) allocates even when the key already exists, and the new String is thrown away. In a hot loop where the key is usually present, try get_mut first:

match m.get_mut(name) {
    Some(v) => *v += 1,
    None => { m.insert(name.to_string(), 1); }
}

`or_insert` vs `or_insert_with`¶

Rust evaluates arguments before the call, so

m.entry(k).or_insert(build());

runs build() every time, even when k is already there. or_insert sees the key exists and drops the value unused. Passing a closure instead makes it lazy:

m.entry(k).or_insert_with(|| build());   // build() runs only when k is missing

Side by side, inside:

fn or_insert(self, default: V) -> &mut V {
    match self {
        Occupied(e) => e.into_mut(),     // `default` was already built, now dropped
        Vacant(e)   => e.insert(default),
    }
}

fn or_insert_with<F: FnOnce() -> V>(self, f: F) -> &mut V {
    match self {
        Occupied(e) => e.into_mut(),     // f never called
        Vacant(e)   => e.insert(f()),
    }
}

Method	Use for
`or_insert(0)`, `or_insert(false)`	Cheap or already-computed values
`or_insert_with(\|\| expensive())`	Anything that allocates, computes, or does I/O
`or_default()`	`or_insert_with(Default::default)`: `Vec`, `String`, counters
`or_insert_with_key(\|k\| f(k))`	The default depends on the key (it’s moved into the entry already)

You can pass a function path instead of a closure: or_insert_with(build).

Clippy catches two versions of this:

or_insert(Vec::new()) warns by default (clippy::unwrap_or_default) and suggests or_default(). Vec::new() doesn’t allocate, so this is about style, not cost.
or_insert(build()) or or_insert(String::from("x")) is clippy::or_fun_call, which is in the nursery group and off by default. Turn it on with #![warn(clippy::or_fun_call)].

It’s the same eager-vs-lazy split as unwrap_or / unwrap_or_else and ok_or / ok_or_else.

Matching on `Entry` directly¶

When you need to branch, match on the Entry directly:

use std::collections::btree_map::Entry;

match counts.entry('z') {
    Entry::Vacant(e) => { e.insert(1); }
    Entry::Occupied(mut e) => { *e.get_mut() += 1; }
}

// remove the key when its count hits a value, in one lookup
if let Entry::Occupied(e) = counts.entry('l') {
    if *e.get() == 2 { e.remove(); }
}

Ordered iteration¶

let m = BTreeMap::from([(3, "c"), (1, "a"), (2, "b")]);

for (k, v) in &m { /* (1, "a"), (2, "b"), (3, "c") */ }

let keys: Vec<_> = m.keys().rev().copied().collect();
assert_eq!(keys, [3, 2, 1]);

Method	Yields
`iter()`	`(&K, &V)`
`iter_mut()`	`(&K, &mut V)`
`keys()`	`&K`
`values()`	`&V`
`values_mut()`	`&mut V`
`into_iter()`	`(K, V)`
`into_keys()`	`K`
`into_values()`	`V`

All of them are DoubleEndedIterator, so .rev() and .next_back() are free.

There is no keys_mut

Keys are never handed out mutably. Changing a key in place could break the sort order the tree depends on. To “rename” a key, remove it and insert again.

Min and max¶

let mut m = BTreeMap::from([(10, "x"), (20, "y"), (30, "z")]);

assert_eq!(m.first_key_value(), Some((&10, &"x")));
assert_eq!(m.last_key_value(),  Some((&30, &"z")));

assert_eq!(m.pop_first(), Some((10, "x")));   // remove and return
assert_eq!(m.pop_last(),  Some((30, "z")));

// an OccupiedEntry for the smallest key, to read/modify/remove it
if let Some(mut e) = m.first_entry() {
    *e.get_mut() = "Y";
}

pop_first / pop_last make a BTreeMap a priority queue you can pop from both ends, which BinaryHeap can’t do. They’re \(O(\log n)\), stable since Rust 1.66.

`range`: the reason to pick a BTreeMap¶

range takes anything that implements RangeBounds and returns a double-ended iterator over just that slice of keys, in \(O(\log n)\) to find the start.

let m = BTreeMap::from([(1, "a"), (5, "e"), (9, "i"), (12, "l")]);

let mid: Vec<_> = m.range(5..10).map(|(k, _)| *k).collect();
assert_eq!(mid, [5, 9]);

Floor, ceiling, predecessor, successor¶

These are the queries C++ gets from lower_bound / upper_bound and Java from TreeMap.floorKey / ceilingKey. In Rust they’re all range plus next or next_back:

use std::ops::Bound::{Excluded, Unbounded};

// largest key <= 7
assert_eq!(m.range(..=7).next_back(), Some((&5, &"e")));
// smallest key >= 7
assert_eq!(m.range(7..).next(),        Some((&9, &"i")));
// largest key < 5
assert_eq!(m.range(..5).next_back(),   Some((&1, &"a")));
// smallest key > 5: there's no `5<..` syntax, so use Bound
assert_eq!(m.range((Excluded(5), Unbounded)).next(), Some((&9, &"i")));

Query	Java	Rust
largest `<= x`	`floorKey(x)`	`range(..=x).next_back()`
largest `< x`	`lowerKey(x)`	`range(..x).next_back()`
smallest `>= x`	`ceilingKey(x)`	`range(x..).next()`
smallest `> x`	`higherKey(x)`	`range((Excluded(x), Unbounded)).next()`

range_mut is the same thing with &mut V:

for (_, v) in m.range_mut(..9) { *v = "-"; }

Prefix search on string keys¶

With String keys you can range with &str, but you have to spell the type out and use Bound explicitly ("ap".. won’t type-check against String keys as str):

use std::ops::Bound::{Included, Unbounded};

let words = BTreeMap::from([
    ("apple".to_string(), 1),
    ("apricot".to_string(), 2),
    ("banana".to_string(), 3),
]);

let ap: Vec<&str> = words
    .range::<str, _>((Included("ap"), Unbounded))
    .take_while(|(k, _)| k.starts_with("ap"))
    .map(|(k, _)| k.as_str())
    .collect();
assert_eq!(ap, ["apple", "apricot"]);

range panics on bad bounds

Both of these panic at runtime rather than returning an empty iterator:

m.range(5..2)                       // range start is greater than range end in BTreeMap
m.range((Excluded(3), Excluded(3))) // range start and end are equal and excluded in BTreeMap

If the bounds come from user input, check start <= end first.

Splitting, merging, filtering¶

let mut a = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c'), (4, 'd')]);

let mut b = a.split_off(&3);   // a = {1, 2}, b = {3, 4}; key 3 goes to the right half
a.append(&mut b);              // moves everything back; b is now empty

retain keeps entries matching a predicate. extract_if (stable since Rust 1.91) removes the matching ones and gives them back, over a key range:

let mut m: BTreeMap<u32, u32> = (1..=10).map(|k| (k, k * k)).collect();

m.retain(|k, _| k % 2 == 0);                       // {2, 4, 6, 8, 10}

let big: BTreeMap<u32, u32> = m.extract_if(.., |_, v| *v > 30).collect();
// big = {6: 36, 8: 64, 10: 100}, m = {2: 4, 4: 16}

The iterator is lazy: entries are only removed as you pull them, so drop it early and the rest stay.

BTreeSet¶

Everything above carries over, minus the values. insert returns a bool instead of the old value.

use std::collections::BTreeSet;

let mut s = BTreeSet::new();
assert!(s.insert(5));     // true: newly added
assert!(!s.insert(5));    // false: already there
s.extend([3, 8, 1]);

assert!(s.contains(&3));
assert!(s.remove(&3));

assert_eq!(s.first(), Some(&1));
assert_eq!(s.last(),  Some(&8));
assert_eq!(s.iter().copied().collect::<Vec<_>>(), [1, 5, 8]); // sorted

assert_eq!(s.range(2..).next(),       Some(&5));  // ceiling(2)
assert_eq!(s.range(..5).next_back(),  Some(&1));  // lower(5)

assert_eq!(s.pop_first(), Some(1));
assert_eq!(s.pop_last(),  Some(8));

A few set-only methods:

get(&q) returns the stored element itself, useful when equal-by-Ord values carry extra data.
take(&q) removes and returns the stored element.
replace(v) inserts v and returns the element it displaced, if any.
split_off, append, retain, extract_if work like the map versions.

Set operations¶

The methods return lazy iterators that walk both sets in order. The operators on references build a new BTreeSet (and need T: Clone).

let a = BTreeSet::from([1, 2, 3, 4]);
let b = BTreeSet::from([3, 4, 5]);

a.union(&b);                 // 1 2 3 4 5
a.intersection(&b);          // 3 4
a.difference(&b);            // 1 2
a.symmetric_difference(&b);  // 1 2 5

assert_eq!(&a & &b, BTreeSet::from([3, 4]));
assert_eq!(&a | &b, BTreeSet::from([1, 2, 3, 4, 5]));
assert_eq!(&a - &b, BTreeSet::from([1, 2]));
assert_eq!(&a ^ &b, BTreeSet::from([1, 2, 5]));

assert!(BTreeSet::from([3, 4]).is_subset(&a));
assert!(a.is_superset(&BTreeSet::from([1])));
assert!(a.is_disjoint(&BTreeSet::from([9])));

Patterns that come up¶

Multiset (sorted bag with duplicates)¶

Rust has no BTreeMultiSet. Use a map from value to count, and delete the key when the count hits zero so first_key_value / last_key_value stay correct:

fn add(ms: &mut BTreeMap<i32, usize>, x: i32) {
    *ms.entry(x).or_insert(0) += 1;
}

fn remove_one(ms: &mut BTreeMap<i32, usize>, x: i32) {
    if let Entry::Occupied(mut e) = ms.entry(x) {
        *e.get_mut() -= 1;
        if *e.get() == 0 { e.remove(); }
    }
}

This is the standard tool for “sliding window max/min” when you also need to remove arbitrary elements.

Sort descending, break ties another way¶

Put a tuple in a set and wrap the field you want reversed in std::cmp::Reverse:

use std::cmp::Reverse;

let mut board: BTreeSet<(Reverse<u32>, &str)> = BTreeSet::new();
board.insert((Reverse(90), "amy"));
board.insert((Reverse(95), "bob"));
board.insert((Reverse(90), "cat"));

let order: Vec<_> = board.iter().map(|(_, n)| *n).collect();
assert_eq!(order, ["bob", "amy", "cat"]); // score desc, then name asc

To update a score, remove the old tuple and insert the new one.

Interval booking¶

Store start -> end. A new [s, e) clashes only if the booking that starts closest before e hasn’t ended by s:

fn book(booked: &mut BTreeMap<u32, u32>, s: u32, e: u32) -> bool {
    if booked.range(..e).next_back().is_some_and(|(_, &end)| end > s) {
        return false;
    }
    booked.insert(s, e);
    true
}

(is_some_and is covered in its own post.)

Gotchas¶

No indexing by position. iter().nth(k) is \(O(k)\). There’s no order-statistic “k-th smallest in \(O(\log n)\)” in std.
No cursors on stable. lower_bound / upper_bound returning a movable cursor exist behind #![feature(btree_cursors)]; on stable, range covers the same queries.
Don’t mutate a key’s ordering through interior mutability (Cell, RefCell) while it’s in the tree. It won’t be UB, but lookups and iteration will give wrong answers.
Ord must agree with Eq. Two keys that compare Equal are the same key. If your Ord only looks at one field, inserting a second item with the same field replaces the first (map) or is rejected (set).
Floats aren’t Ord. Wrap them (ordered_float::OrderedFloat) or use f64::total_cmp in your own newtype’s Ord impl.

Cheat sheet¶

Operation	Complexity
`get`, `insert`, `remove`, `entry`	\(O(\log n)\)
`first_`, `last_`, `pop_*`	\(O(\log n)\)
`range(..)` to first item	\(O(\log n)\)
each further item in an iterator	amortised \(O(1)\)
`append`	\(O(n + m)\)
`len`, `is_empty`	\(O(1)\)