🎓 A1Learner
🔍

Rust BTreeMap In Depth

BTreeMap is a sorted map with tools for counting, ranges, and splitting.

Counting with entry — sorted for free

BTreeMap has the same entry API as HashMap. The difference shows when you print: the pairs come out in key order:

use std::collections::BTreeMap;

let mut count: BTreeMap<char, u32> = BTreeMap::new();
for c in "abcaab".chars() {
    *count.entry(c).or_insert(0) += 1;
}
println!("{:?}", count);

range_mut: change values inside a window

range_mut works like range, but hands you &mut values — a whole slice of the map updated in one loop:

use std::collections::BTreeMap;

let mut prices: BTreeMap<&str, i32> = BTreeMap::new();
prices.insert("apple", 30);
prices.insert("banana", 12);
prices.insert("cherry", 45);
prices.insert("date", 20);
for (_, price) in prices.range_mut("b".."d") {
    *price += 5;
}
println!("{:?}", prices);

split_off: cut the map at a key

split_off(&key) moves the key and everything above it into a new map. This map keeps what is below:

use std::collections::BTreeMap;

let mut first: BTreeMap<u32, &str> = BTreeMap::new();
first.insert(1, "gym");
first.insert(3, "dentist");
first.insert(5, "concert");
first.insert(7, "rest");
let second = first.split_off(&5);
println!("first = {:?}", first);
println!("second = {:?}", second);

The window need not start on a key

range accepts bounds that are not in the map at all — it starts at the first key inside the window:

use std::collections::BTreeMap;

let mut map: BTreeMap<u32, &str> = BTreeMap::new();
map.insert(2, "b");
map.insert(5, "e");
map.insert(8, "h");
println!("first from 3 = {:?}", map.range(3..).next());

Example

use std::collections::BTreeMap;

fn main() {
    let mut temps: BTreeMap<u32, i32> = BTreeMap::new();
    for (day, t) in [(3, 18), (1, 15), (5, 21), (2, 16), (4, 19), (6, 22)] {
        temps.insert(day, t);
    }
    for (_, t) in temps.range_mut(2..=3) { *t += 1; }
    println!("after fix: {:?}", temps);
    let second = temps.split_off(&4);
    println!("first half: {:?}", temps);
    println!("second half: {:?}", second);
    let next = temps.range(3..).next();
    println!("first day from 3 = {:?}", next);
}

Key points

  • A BTreeMap keeps order through every tool: counting, ranging, and splitting all leave the keys sorted.
  • The Entry type lives at std::collections::btree_map::Entry.
  • The verbs match HashMap: or_insert, or_insert_with, or_insert_with_key, and_modify.
  • The entry verbs were verified on this machine with rustc 1.99.1.
  • range and range_mut panic when the start bound is after the end bound — the window must face the right way
  • range_mut changes values only: the keys stay fixed, so the map never needs re-sorting mid-loop
  • If the split key is missing, split_off splits at the next greater key.
  • split_off returns an empty map when no greater key exists.
  • Use get_key_value(&key) when the stored key itself is needed back, not just the value.
  • The stored key helps when the lookup used an equal-but-not-identical key.

In this example, six days of temperatures arrive out of order. The BTreeMap stores them sorted. The first print shows this. A sensor fault is fixed with range_mut(2..=3): days 2 and 3 each gain a degree, and no key moves. split_off(&4) then archives the back half. The first map keeps days 1 to 3. The returned map takes day 4 and everything above. Last, range(3..).next() asks for the first entry from day 3 onward and finds day 3 itself, with its corrected 19.

Note

A HashMap count must be sorted by hand afterwards.

When the report is the point, counting straight into a BTreeMap skips that step entirely.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Rust Playground

Exercise

What does temps.split_off(&4) return?