Sorted Collections: BTreeMap and BTreeSet

20 min read

Rust’s standard library ships two collections whose superpower is order: BTreeMap<K, V> and BTreeSet<T>. Where a HashMap gives you the fastest possible lookup but throws away ordering, a BTreeMap keeps its keys permanently sorted — which makes “give me everything between X and Y” and “iterate in order” cheap, built-in operations rather than something you reconstruct by sorting on every read.

Quick Overview

In JavaScript, both plain objects and Map iterate in insertion order, and there is no built-in sorted collection at all — if you want sorted keys or a range query, you sort an array yourself, every single time. Rust’s BTreeMap stores its entries sorted by key, so iteration is always in ascending key order and you get O(log n) range queries for free. BTreeSet is the same idea without values: a sorted set of unique elements. The trade-off is that BTreeMap/BTreeSet are slightly slower per lookup than their hashing cousins, and their keys must be orderable (Ord) rather than merely hashable.

TypeScript/JavaScript Example

1
// TypeScript - a Map preserves INSERTION order, never sorted order.
2
const scores = new Map<string, number>();
3
scores.set("charlie", 90);
4
scores.set("alice", 85);
5
scores.set("bob", 95);
6

7
console.log([...scores.keys()]); // [ 'charlie', 'alice', 'bob' ]  <- insertion order!
8

9
// To display in sorted order, you must sort explicitly EVERY time you read.
10
const sortedByName = [...scores.entries()].sort(([a], [b]) => a.localeCompare(b));
11
console.log(sortedByName); // [ [ 'alice', 85 ], [ 'bob', 95 ], [ 'charlie', 90 ] ]
12

13
// A "range query" — events between 10:00 and 15:00 — is a manual filter + sort.
14
const events = new Map<number, string>([
15
  [900, "standup"],
16
  [1030, "design review"],
17
  [1200, "lunch"],
18
  [1400, "1:1"],
19
  [1630, "retro"],
20
]);
21

22
const between = [...events.entries()]
23
  .filter(([time]) => time >= 1000 && time <= 1500)
24
  .sort(([a], [b]) => a - b);
25
console.log(between);
26
// [ [ 1030, 'design review' ], [ 1200, 'lunch' ], [ 1400, '1:1' ] ]

Key points:

A JavaScript Map (and a plain object) iterates in insertion order, not key order.
There is no native sorted map or sorted set; you rebuild a sorted view with [...map].sort(...) on every read, which is O(n log n) each time.
A range query is “spread to an array, filter, then sort” — correct, but linear in the whole collection regardless of how small the window is.

Rust Equivalent

1
use std::collections::BTreeMap;
2

3
fn main() {
4
    // Insert in scrambled order; BTreeMap keeps the keys sorted automatically.
5
    let mut scores: BTreeMap<String, u32> = BTreeMap::new();
6
    scores.insert("charlie".to_string(), 90);
7
    scores.insert("alice".to_string(), 85);
8
    scores.insert("bob".to_string(), 95);
9

10
    // Iteration is ALWAYS in ascending key order — no sorting step needed.
11
    for (name, score) in &scores {
12
        println!("{name}: {score}");
13
    }
14

15
    // The smallest and largest keys are O(log n) lookups.
16
    println!("first: {:?}", scores.first_key_value());
17
    println!("last: {:?}", scores.last_key_value());
18
}

Verified output:

1
alice: 85
2
bob: 95
3
charlie: 90
4
first: Some(("alice", 85))
5
last: Some(("charlie", 90))

The range query becomes a single, efficient .range(..) call that touches only the entries inside the window:

1
use std::collections::BTreeMap;
2

3
fn main() {
4
    let mut events: BTreeMap<u32, &str> = BTreeMap::new();
5
    events.insert(900, "standup");
6
    events.insert(1030, "design review");
7
    events.insert(1200, "lunch");
8
    events.insert(1400, "1:1");
9
    events.insert(1630, "retro");
10

11
    // Inclusive range 1000..=1500 — returns entries in key order, no filter/sort.
12
    println!("between 10:00 and 15:00:");
13
    for (time, name) in events.range(1000..=1500) {
14
        println!("  {time}: {name}");
15
    }
16
}

Verified output:

1
between 10:00 and 15:00:
2
  1030: design review
3
  1200: lunch
4
  1400: 1:1

Key points:

BTreeMap keeps entries sorted by key at all times; iteration order is guaranteed and free.
.range(start..=end) walks only the matching slice of the tree, in order — no full scan, no per-read sort.
The API mirrors HashMap (insert, get, remove, the entry API), so most code reads the same; you swap the type and gain ordering.

Detailed Explanation

What “B-Tree” means and why you don’t care (much)

A BTreeMap is implemented as a B-Tree — a balanced search tree where each node holds many keys, chosen to be cache-friendly on modern CPUs. You never interact with the tree structure directly; what matters is the behavior it buys you:

Keys are kept in sorted order as you insert.
get, insert, and remove are O(log n) (versus HashMap’s amortized O(1)).
Iteration visits keys smallest-to-largest.
Finding a range of keys is O(log n + k), where k is the number of items in the range.

Note: The name is “B-Tree”, not “Binary Tree”. Each node stores a block of keys, which keeps the tree shallow and the memory accesses local. You will not implement or tune it — std does that for you.

Keys must be `Ord`, not `Hash`

The defining requirement is right there in the method signatures: a BTreeMap key must implement the Ord trait (total ordering), because the collection sorts by comparing keys. A HashMap instead needs Hash + Eq. All the obvious primitives — integers, char, bool, &str/String, and tuples/Vecs of orderable things — implement Ord already. (Ord and its companions PartialOrd/Eq are part of the trait system covered in Section 09.)

1
use std::collections::BTreeSet;
2

3
// Deriving Ord (plus the traits it builds on) makes a struct usable as a key.
4
// Ordering is field-by-field, top to bottom — major, then minor, then patch.
5
#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
6
struct Version {
7
    major: u32,
8
    minor: u32,
9
    patch: u32,
10
}
11

12
fn main() {
13
    let mut releases: BTreeSet<Version> = BTreeSet::new();
14
    releases.insert(Version { major: 1, minor: 2, patch: 0 });
15
    releases.insert(Version { major: 1, minor: 0, patch: 5 });
16
    releases.insert(Version { major: 2, minor: 0, patch: 0 });
17
    releases.insert(Version { major: 1, minor: 2, patch: 0 }); // duplicate ignored
18

19
    for v in &releases {
20
        println!("{}.{}.{}", v.major, v.minor, v.patch);
21
    }
22
    println!("latest: {:?}", releases.last());
23
}

Verified output:

1
1.0.5
2
1.2.0
3
2.0.0
4
latest: Some(Version { major: 2, minor: 0, patch: 0 })

The four derives matter: #[derive(PartialEq, Eq, PartialOrd, Ord)] generates a lexicographic comparison in field declaration order. Reorder the fields and you reorder the sort. This is more honest than JavaScript’s Array.prototype.sort, whose default coerces everything to strings (so [2, 10].sort() famously yields [10, 2]).

`BTreeSet` is a `BTreeMap` with no values

BTreeSet<T> is the sorted analogue of HashSet<T> (see hashsets.md): a collection of unique, ordered elements. Duplicate inserts are silently ignored, membership tests are O(log n), and iteration is in sorted order.

1
use std::collections::BTreeSet;
2

3
fn main() {
4
    let mut tags: BTreeSet<&str> = BTreeSet::new();
5
    tags.insert("rust");
6
    tags.insert("async");
7
    tags.insert("rust"); // duplicate ignored
8
    tags.insert("web");
9

10
    let listed: Vec<&&str> = tags.iter().collect();
11
    println!("{listed:?}");                       // sorted, deduped
12
    println!("contains async: {}", tags.contains("async"));
13
}

Verified output:

1
["async", "rust", "web"]
2
contains async: true

Range queries in depth

.range(..) accepts any of Rust’s range syntaxes, and the bounds follow the same inclusive/exclusive rules as slicing:

Range expression	Meaning
`start..end`	`start` inclusive, `end` exclusive
`start..=end`	both ends inclusive
`start..`	from `start` (inclusive) to the largest key
`..end`	from the smallest key up to (excluding) `end`
`..`	the whole map, in order (same as iterating)

1
use std::collections::BTreeMap;
2
use std::ops::Bound::{Excluded, Unbounded};
3

4
fn main() {
5
    let mut events: BTreeMap<u32, &str> = BTreeMap::new();
6
    events.insert(900, "standup");
7
    events.insert(1030, "design review");
8
    events.insert(1200, "lunch");
9
    events.insert(1400, "1:1");
10
    events.insert(1630, "retro");
11

12
    // Everything from 1200 onward.
13
    println!("from 12:00 onward:");
14
    for (time, name) in events.range(1200..) {
15
        println!("  {time}: {name}");
16
    }
17

18
    // For full control, pass an explicit (start, end) pair of Bound values.
19
    // Here: strictly after 1200, no upper limit.
20
    println!("strictly after 12:00:");
21
    for (time, name) in events.range((Excluded(1200), Unbounded)) {
22
        println!("  {time}: {name}");
23
    }
24
}

Verified output:

1
from 12:00 onward:
2
  1200: lunch
3
  1400: 1:1
4
  1630: retro
5
strictly after 12:00:
6
  1400: 1:1
7
  1630: retro

The Bound enum (Included, Excluded, Unbounded) is the escape hatch when the .. syntaxes are not expressive enough — most commonly when you need an exclusive lower bound, which the range operators cannot express on their own.

BTreeSet has the same .range(..):

1
use std::collections::BTreeSet;
2

3
fn main() {
4
    let primes: BTreeSet<u32> = [2, 3, 5, 7, 11, 13, 17, 19].into_iter().collect();
5
    let in_range: Vec<&u32> = primes.range(5..15).collect();
6
    println!("{in_range:?}"); // 5 inclusive, 15 exclusive
7
}

Verified output:

1
[5, 7, 11, 13]

The familiar map operations still apply

Everything you know from hashmaps.md carries over — the entry API, get_mut, remove, set operations on sets — because both maps implement the same conceptual interface. Here is the classic word-count, which now prints alphabetically with no extra sorting:

1
use std::collections::BTreeMap;
2

3
fn main() {
4
    let text = "the quick brown fox the lazy dog the end";
5
    let mut counts: BTreeMap<&str, u32> = BTreeMap::new();
6
    for word in text.split_whitespace() {
7
        // entry().or_insert() works identically to HashMap.
8
        *counts.entry(word).or_insert(0) += 1;
9
    }
10
    for (word, count) in &counts {
11
        println!("{word}: {count}");
12
    }
13
}

Verified output:

1
brown: 1
2
dog: 1
3
end: 1
4
fox: 1
5
lazy: 1
6
quick: 1
7
the: 3

BTreeSet also supports the same union, intersection, and difference as HashSet, but here the results come out sorted:

1
use std::collections::BTreeSet;
2

3
fn main() {
4
    let a: BTreeSet<i32> = [1, 2, 3, 4].into_iter().collect();
5
    let b: BTreeSet<i32> = [3, 4, 5, 6].into_iter().collect();
6

7
    let union: Vec<&i32> = a.union(&b).collect();
8
    let inter: Vec<&i32> = a.intersection(&b).collect();
9
    let diff: Vec<&i32> = a.difference(&b).collect();
10

11
    println!("union: {union:?}");
12
    println!("intersection: {inter:?}");
13
    println!("difference: {diff:?}");
14
}

Verified output:

1
union: [1, 2, 3, 4, 5, 6]
2
intersection: [3, 4]
3
difference: [1, 2]

Ordered-specific extras

Because the data is sorted, BTreeMap/BTreeSet offer methods that have no HashMap equivalent. pop_first/pop_last remove and return the smallest/largest entry, turning a BTreeMap into a serviceable ordered queue or simple priority queue:

1
use std::collections::BTreeMap;
2

3
fn main() {
4
    let mut tasks: BTreeMap<u8, &str> = BTreeMap::new();
5
    tasks.insert(3, "medium");
6
    tasks.insert(1, "urgent");
7
    tasks.insert(5, "low");
8

9
    // Always pull the smallest key first.
10
    while let Some((priority, name)) = tasks.pop_first() {
11
        println!("handling p{priority}: {name}");
12
    }
13
}

Verified output:

1
handling p1: urgent
2
handling p3: medium
3
handling p5: low

Tip: For a heavy-duty priority queue, reach for std::collections::BinaryHeap instead — it is purpose-built for “always give me the max” with O(log n) push/pop and O(1) peek. Use BTreeMap::pop_first/pop_last when you also need ordered iteration, range queries, or keyed lookup on the same data.

split_off cuts the map in two at a key, keeping the lower part and returning the upper part as a new map:

1
use std::collections::BTreeMap;
2

3
fn main() {
4
    let mut map: BTreeMap<i32, &str> = BTreeMap::new();
5
    for i in 1..=5 {
6
        map.insert(i, "x");
7
    }
8
    // Keys >= 3 move into `high`; `map` retains keys < 3.
9
    let high = map.split_off(&3);
10
    let low_keys: Vec<&i32> = map.keys().collect();
11
    let high_keys: Vec<&i32> = high.keys().collect();
12
    println!("low: {low_keys:?}");
13
    println!("high: {high_keys:?}");
14
}

Verified output:

1
low: [1, 2]
2
high: [3, 4, 5]

Key Differences

Aspect	JS `Map` / object	Rust `HashMap`	Rust `BTreeMap`
Iteration order	Insertion order	Unspecified (randomized)	Sorted by key
Lookup / insert / remove	`O(1)` average	`O(1)` amortized	`O(log n)`
Range query	Manual `filter` + `sort`	Not supported	`O(log n + k)` via `.range(..)`
Min / max key	Manual scan / sort	Manual scan (`O(n)`)	`O(log n)` (`first/last_key_value`)
Key requirement	Any value (SameValueZero)	`Hash` + `Eq`	`Ord`
Floats as keys	Allowed	Allowed (via `Eq` workarounds)	Not allowed (`f64` is not `Ord`)

Why iteration order differs from HashMap

A HashMap’s order is not just “different” — it is deliberately randomized per execution (its default hasher is seeded from a random value at startup) to defend against hash-flooding denial-of-service attacks. So you must never rely on HashMap iteration order. A BTreeMap makes the opposite promise: order is part of the contract. If your output must be deterministic — config files, serialized snapshots, anything diffed in tests — BTreeMap removes a whole class of flaky behavior.

When to choose which

Reach for HashMap/HashSet when you only do point lookups and inserts and never need order. They are faster per operation.
Reach for BTreeMap/BTreeSet when you need any of: sorted iteration, range queries, smallest/largest by key, or deterministic output.

A detailed Big-O comparison across all the collections lives in collection-performance.md.

Common Pitfalls

Pitfall 1: Trying to use a type that isn’t `Ord` as a key

If you forget to derive Ord on a struct (or try to derive it on a type containing a non-Ord field), the error appears at the insert call:

1
use std::collections::BTreeMap;
2

3
#[derive(Debug)] // only Debug — no Ord
4
struct Point {
5
    x: i32,
6
    y: i32,
7
}
8

9
fn main() {
10
    let mut m: BTreeMap<Point, &str> = BTreeMap::new();
11
    m.insert(Point { x: 1, y: 2 }, "origin-ish"); // does not compile (error[E0277])
12
    println!("{m:?}");
13
}

Real compiler output:

1
error[E0277]: the trait bound `Point: Ord` is not satisfied
2
  --> src/main.rs:12:7
3
   |
4
12 |     m.insert(Point { x: 1, y: 2 }, "origin-ish");
5
   |       ^^^^^^ the trait `Ord` is not implemented for `Point`
6
   |
7
note: required by a bound in `BTreeMap::<K, V, A>::insert`
8
...
9
help: consider annotating `Point` with `#[derive(Ord)]`
10
   |
11
 5 + #[derive(Ord)]
12
 6 | struct Point {
13
   |

The fix is exactly what the compiler suggests, except you need the full set: #[derive(PartialEq, Eq, PartialOrd, Ord)] (deriving Ord requires PartialOrd, Eq, and PartialEq too).

Pitfall 2: Floating-point keys

Coming from JavaScript, where new Map().set(1.5, "x") is fine, you may try a BTreeMap<f64, _>. It will not compile, because f64 deliberately does not implement Ord (the NaN != NaN rule makes a total ordering impossible):

1
use std::collections::BTreeMap;
2

3
fn main() {
4
    let mut m: BTreeMap<f64, &str> = BTreeMap::new();
5
    m.insert(1.5, "one and a half"); // does not compile (error[E0277])
6
    println!("{m:?}");
7
}

Real compiler output (abridged):

1
error[E0277]: the trait bound `f64: Ord` is not satisfied
2
  --> src/main.rs:5:7
3
   |
4
5  |     m.insert(1.5, "one and a half");
5
   |       ^^^^^^ the trait `Ord` is not implemented for `f64`
6
   |
7
   = help: the following other types implement trait `Ord`:
8
             i128
9
             i16
10
             i32
11
             ...

Workarounds: scale to an integer key (e.g. store millis or cents as u64/i64), or wrap floats in a crate like ordered-float’s OrderedFloat, which provides a total order by defining where NaN sorts.

Pitfall 3: A backwards range panics at runtime

Unlike a JavaScript filter that silently returns an empty array, calling .range(start..end) with start > end is a programming error and panics:

1
use std::collections::BTreeMap;
2

3
fn main() {
4
    let mut m: BTreeMap<i32, &str> = BTreeMap::new();
5
    m.insert(1, "a");
6
    m.insert(2, "b");
7
    m.insert(3, "c");
8
    let r: Vec<_> = m.range(3..1).collect(); // start > end
9
    println!("{r:?}");
10
}

Real runtime output:

1
thread 'main' panicked at .../alloc/src/collections/btree/search.rs:121:21:
2
range start is greater than range end in BTreeMap
3
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Validate or min/max-clamp user-supplied bounds before passing them to .range(..). (An empty equal range like 3..3 is fine — it just yields nothing.)

Pitfall 4: Expecting `HashMap`-level speed

BTreeMap operations are O(log n), not O(1). For a million-entry hot path doing nothing but point lookups, a HashMap will measurably win. Choose BTreeMap for what it gives you (order, ranges), not as a drop-in faster map.

Best Practices

Use BTreeMap/BTreeSet for deterministic output. Anything serialized, logged, snapshot-tested, or diffed benefits from stable key order. Many teams collect into a BTreeMap purely so their test fixtures and config dumps stop reordering between runs.

Build with a HashMap, present with a BTreeMap when ordering only matters at the end. Do the hot inserts in a HashMap, then .collect() into a BTreeMap once for display:

1
use std::collections::{BTreeMap, HashMap};
2

3
fn main() {
4
    let mut counts: HashMap<&str, u32> = HashMap::new();
5
    for w in "b a c a b a".split_whitespace() {
6
        *counts.entry(w).or_insert(0) += 1;
7
    }
8
    // One conversion at the end yields a sorted view.
9
    let sorted: BTreeMap<_, _> = counts.into_iter().collect();
10
    for (word, count) in &sorted {
11
        println!("{word}: {count}");
12
    }
13
}

Verified output:

1
a: 3
2
b: 2
3
c: 1

Prefer .range(..) over .iter().filter(..) for windowed queries. filter walks the entire map; .range(..) jumps straight to the start of the window and stops at the end.
Use first_key_value/last_key_value (peek) and pop_first/pop_last (remove) instead of .iter().next() gymnastics when you want the min/max entry.
Order keys by deriving in field order. Put the most significant field first in a key struct so the derived Ord sorts the way you want.

Note: Need a custom comparison that the derived field order can’t express — for example, “sort users by score descending, then name ascending”? Implement Ord/PartialOrd by hand on the key type, or store a transformed key (e.g. std::cmp::Reverse(score)). Hand-written Ord is covered alongside the other comparison traits in Section 09.

Real-World Example

A time-series metric store, the kind you’d find behind a monitoring dashboard. Samples arrive keyed by timestamp; the consumer asks for windowed averages and “the latest value as of time T”. A BTreeMap makes every one of those a sorted range query.

1
use std::collections::BTreeMap;
2

3
/// A time-series store keyed by Unix-millisecond timestamps. Because a
4
/// `BTreeMap` keeps keys sorted, range queries ("everything in this window")
5
/// are cheap and the results come back in chronological order.
6
#[derive(Debug, Default)]
7
struct MetricSeries {
8
    samples: BTreeMap<u64, f64>,
9
}
10

11
impl MetricSeries {
12
    fn record(&mut self, timestamp_ms: u64, value: f64) {
13
        self.samples.insert(timestamp_ms, value);
14
    }
15

16
    /// Average of all samples in the half-open window `[start, end)`.
17
    fn average(&self, start: u64, end: u64) -> Option<f64> {
18
        let window: Vec<f64> = self.samples.range(start..end).map(|(_, &v)| v).collect();
19
        if window.is_empty() {
20
            return None;
21
        }
22
        Some(window.iter().sum::<f64>() / window.len() as f64)
23
    }
24

25
    /// The most recent sample at or before `timestamp_ms`.
26
    /// `range(..=t).next_back()` walks to the end of the window and grabs the last entry.
27
    fn latest_at(&self, timestamp_ms: u64) -> Option<(u64, f64)> {
28
        self.samples
29
            .range(..=timestamp_ms)
30
            .next_back()
31
            .map(|(&t, &v)| (t, v))
32
    }
33
}
34

35
fn main() {
36
    let mut cpu = MetricSeries::default();
37
    cpu.record(1_000, 12.5);
38
    cpu.record(2_000, 30.0);
39
    cpu.record(3_000, 45.5);
40
    cpu.record(4_000, 22.0);
41
    cpu.record(5_000, 60.0);
42

43
    // Average over [2000, 5000): samples at 2000, 3000, 4000.
44
    println!("avg 2s..5s: {:?}", cpu.average(2_000, 5_000));
45

46
    // What was the reading as of t=3500? -> the sample at 3000.
47
    println!("latest at 3500: {:?}", cpu.latest_at(3_500));
48

49
    // No samples in this window -> None, not a crash.
50
    println!("avg 6s..9s: {:?}", cpu.average(6_000, 9_000));
51

52
    // Iterating yields chronological order for free.
53
    println!("all samples:");
54
    for (t, v) in &cpu.samples {
55
        println!("  t={t}: {v}");
56
    }
57
}

Verified output:

1
avg 2s..5s: Some(32.5)
2
latest at 3500: Some((3000, 45.5))
3
avg 6s..9s: None
4
all samples:
5
  t=1000: 12.5
6
  t=2000: 30
7
  t=3000: 45.5
8
  t=4000: 22
9
  t=5000: 60

Note the design choices a JavaScript version would make harder: latest_at uses range(..=t).next_back() — an O(log n) “floor” lookup — instead of scanning; values are floats but the key is an integer (u64 millis), sidestepping the f64: Ord pitfall entirely; and the chronological iteration at the end needs no sort.

Exercises

Exercise 1: First repeated word, alphabetically

Difficulty: Easy

Objective: Use a BTreeMap to find the alphabetically-first word that appears two or more times in a sentence.

Instructions:

Split the input on whitespace and count occurrences with the entry API.
Because a BTreeMap iterates in sorted key order, iterate the counts and return the first word whose count is >= 2.
Return Option<String> so the “no repeats” case is None.

1
use std::collections::BTreeMap;
2

3
fn first_repeated(text: &str) -> Option<String> {
4
    // TODO: count words, then find the first (alphabetically) with count >= 2
5
    todo!()
6
}
7

8
fn main() {
9
    println!("{:?}", first_repeated("zebra apple mango apple zebra"));
10
    println!("{:?}", first_repeated("one two three"));
11
}

Solution

1
use std::collections::BTreeMap;
2

3
fn first_repeated(text: &str) -> Option<String> {
4
    let mut counts: BTreeMap<&str, u32> = BTreeMap::new();
5
    for word in text.split_whitespace() {
6
        *counts.entry(word).or_insert(0) += 1;
7
    }
8
    // Iteration is alphabetical, so `find` returns the first qualifying word.
9
    counts
10
        .into_iter()
11
        .find(|&(_, count)| count >= 2)
12
        .map(|(word, _)| word.to_string())
13
}
14

15
fn main() {
16
    println!("{:?}", first_repeated("zebra apple mango apple zebra"));
17
    println!("{:?}", first_repeated("one two three"));
18
}

Verified output:

1
Some("apple")
2
None

apple and zebra both repeat, but because the BTreeMap is sorted, find reaches apple first.

Exercise 2: Score range report

Difficulty: Medium

Objective: Given a BTreeMap<u32, Vec<&str>> mapping a score to the students who earned it, list everyone whose score falls in an inclusive [lo, hi] band, in ascending score order.

Instructions:

Use .range(lo..=hi) to select only the scores in the band — do not iterate the whole map.
For each (score, names) entry, produce one "name: score" line per student.
Return a Vec<String> of those lines.

1
use std::collections::BTreeMap;
2

3
fn report(scores: &BTreeMap<u32, Vec<&str>>, lo: u32, hi: u32) -> Vec<String> {
4
    // TODO: range over [lo, hi] and flatten into "name: score" lines
5
    todo!()
6
}
7

8
fn main() {
9
    let mut scores: BTreeMap<u32, Vec<&str>> = BTreeMap::new();
10
    scores.insert(72, vec!["Dana"]);
11
    scores.insert(85, vec!["Alice", "Eve"]);
12
    scores.insert(91, vec!["Bob"]);
13
    scores.insert(60, vec!["Frank"]);
14
    for line in report(&scores, 70, 90) {
15
        println!("{line}");
16
    }
17
}

Solution

1
use std::collections::BTreeMap;
2

3
fn report(scores: &BTreeMap<u32, Vec<&str>>, lo: u32, hi: u32) -> Vec<String> {
4
    scores
5
        .range(lo..=hi)
6
        // `move` lets the inner closure capture `score` by copy for each entry.
7
        .flat_map(|(score, names)| names.iter().map(move |n| format!("{n}: {score}")))
8
        .collect()
9
}
10

11
fn main() {
12
    let mut scores: BTreeMap<u32, Vec<&str>> = BTreeMap::new();
13
    scores.insert(72, vec!["Dana"]);
14
    scores.insert(85, vec!["Alice", "Eve"]);
15
    scores.insert(91, vec!["Bob"]);
16
    scores.insert(60, vec!["Frank"]);
17
    for line in report(&scores, 70, 90) {
18
        println!("{line}");
19
    }
20
}

Verified output:

1
Dana: 72
2
Alice: 85
3
Eve: 85

60 (Frank) and 91 (Bob) fall outside [70, 90], so .range(..) skips them entirely. flat_map is covered in iterators.md.

Exercise 3: Merge two leaderboards

Difficulty: Medium

Objective: Combine two BTreeMap<String, u32> leaderboards into one, summing the scores of players who appear in both.

Instructions:

Start from a clone of the first map.
For each (name, score) in the second map, add the score into the merged map using the entry API (insert 0 if the player is new).
Return the merged BTreeMap, which is automatically sorted by player name.

1
use std::collections::BTreeMap;
2

3
fn merge(
4
    a: &BTreeMap<String, u32>,
5
    b: &BTreeMap<String, u32>,
6
) -> BTreeMap<String, u32> {
7
    // TODO: clone `a`, then fold `b`'s scores in with entry().or_insert(0)
8
    todo!()
9
}
10

11
fn main() {
12
    let mut q1: BTreeMap<String, u32> = BTreeMap::new();
13
    q1.insert("alice".into(), 10);
14
    q1.insert("bob".into(), 5);
15
    let mut q2: BTreeMap<String, u32> = BTreeMap::new();
16
    q2.insert("bob".into(), 7);
17
    q2.insert("carol".into(), 3);
18
    for (name, total) in merge(&q1, &q2) {
19
        println!("{name}: {total}");
20
    }
21
}

Solution

1
use std::collections::BTreeMap;
2

3
fn merge(
4
    a: &BTreeMap<String, u32>,
5
    b: &BTreeMap<String, u32>,
6
) -> BTreeMap<String, u32> {
7
    let mut merged = a.clone();
8
    for (name, score) in b {
9
        // entry() returns a mutable handle; or_insert(0) seeds new players.
10
        *merged.entry(name.clone()).or_insert(0) += score;
11
    }
12
    merged
13
}
14

15
fn main() {
16
    let mut q1: BTreeMap<String, u32> = BTreeMap::new();
17
    q1.insert("alice".into(), 10);
18
    q1.insert("bob".into(), 5);
19
    let mut q2: BTreeMap<String, u32> = BTreeMap::new();
20
    q2.insert("bob".into(), 7);
21
    q2.insert("carol".into(), 3);
22
    for (name, total) in merge(&q1, &q2) {
23
        println!("{name}: {total}");
24
    }
25
}

Verified output:

1
alice: 10
2
bob: 12
3
carol: 3

bob appears in both leaderboards, so his 5 + 7 = 12 is summed; the result iterates alphabetically because it is a BTreeMap.

Previous: HashSets · Next: Iterators · Up: Section 07 Overview

Sorted Collections: BTreeMap and BTreeSet

Quick Overview

TypeScript/JavaScript Example

Rust Equivalent

Detailed Explanation

What “B-Tree” means and why you don’t care (much)

Keys must be Ord, not Hash

BTreeSet is a BTreeMap with no values

Range queries in depth

The familiar map operations still apply

Ordered-specific extras

Key Differences

Why iteration order differs from HashMap

When to choose which

Common Pitfalls

Pitfall 1: Trying to use a type that isn’t Ord as a key

Pitfall 2: Floating-point keys

Pitfall 3: A backwards range panics at runtime

Pitfall 4: Expecting HashMap-level speed

Best Practices

Real-World Example

Further Reading

Exercises

Exercise 1: First repeated word, alphabetically

Exercise 2: Score range report

Exercise 3: Merge two leaderboards

Keys must be `Ord`, not `Hash`

`BTreeSet` is a `BTreeMap` with no values

Pitfall 1: Trying to use a type that isn’t `Ord` as a key

Pitfall 4: Expecting `HashMap`-level speed