🎓 A1Learner
🔍

Rust Sorted Maps

BTreeMap is a map that keeps its keys sorted at all times. A HashMap keeps no order, and its order can even change between runs.

Keys always come out sorted

Insert in chaos. Iterate in order.

use std::collections::BTreeMap;

let mut temps: BTreeMap<&str, i32> = BTreeMap::new();
temps.insert("Wed", 18);
temps.insert("Mon", 21);
temps.insert("Fri", 16);
for (day, t) in &temps {
    println!("{day} = {t}");
}

A slice of the keys (range)

range(4..=8) visits only days 4 through 8 — it walks straight to 4 instead of scanning from the start.

use std::collections::BTreeMap;

let mut diary: BTreeMap<u32, &str> = BTreeMap::new();
diary.insert(2, "gym");
diary.insert(4, "exam");
diary.insert(6, "trip");
diary.insert(8, "party");
diary.insert(10, "rest");
for (day, plan) in diary.range(4..=8) {
    println!("day {day}: {plan}");
}

The ends of the map

first_key_value and last_key_value read the smallest and largest pair without removing them.

println!("{:?}", diary.first_key_value());
println!("{:?}", diary.last_key_value());

BTreeSet: the sorted HashSet

The same idea without values — tags come out alphabetically and stay unique.

use std::collections::BTreeSet;

let mut tags = BTreeSet::new();
tags.insert("rust");
tags.insert("cargo");
tags.insert("rust");
println!("{:?}", tags);

Example

use std::collections::BTreeMap;

fn main() {
    let mut week: BTreeMap<u32, &str> = BTreeMap::new();
    week.insert(5, "concert");
    week.insert(1, "gym");
    week.insert(3, "dentist");
    week.insert(7, "rest");
    week.insert(2, "market");
    println!("the week in order:");
    for (day, plan) in &week {
        println!("day {day}: {plan}");
    }
    println!("busy days 2 to 5:");
    for (day, plan) in week.range(2..=5) {
        println!("day {day}: {plan}");
    }
    println!("first plan = {:?}", week.first_key_value());
    println!("last plan = {:?}", week.last_key_value());
}

Key points

  • Sorted order is the whole difference: a BTreeMap sorts its keys as it stores them.
  • BTreeMap and BTreeSet live in std::collections and need keys with a total order (Ord) — text and numbers qualify.
  • Every read and write costs a little more than a HashMap: the tree re-balances behind the scenes.
  • That extra cost is the price of order.
  • BTreeMap carries the same entry API as HashMap: count with entry(key).or_insert(0) and the tally is already in sorted order (Rust BTreeMap In Depth, in the Intermediate course)
  • Use range_mut(range) to change the values inside a window of keys in one loop — the keys never move
  • Use split_off(&key) to divide the map in two.
  • This map keeps the keys below the split key.
  • The returned map takes the key and everything above it.
  • Sorted keys suit a diary, a leaderboard, or a range of days.

The days are inserted as 5, 1, 3, 7, 2. But every iteration walks them in order. The map stores them sorted. range(2..=5) visits only the days in that window. first_key_value and last_key_value read the ends without removing them. There are also pop_first and pop_last. Those two take the ends out.

Note

Choose HashMap for pure lookup speed.

Choose BTreeMap the moment order, ranges, or smallest/largest matter.

Sorted output from a HashMap is a sort() that must not be forgotten.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Rust Playground

Exercise

You need every diary entry from day 4 to day 8, in order. Which map and call fit?