4.3 · BTreeMap, BTreeSet, and Ordered Collections

Domain 4 — Collections Deep Dive Duration: ~15 minutes Library components: std::collections::BTreeMap, std::collections::BTreeSet, std::collections::btree_map::Entry

Introduction

HashMap and HashSet are the default selections for key-value collections and membership collections. Their lookups are amortized O(1). But they cannot answer one simple query: "give me each entry between key X and key Y". When the order is important (range queries, sorted iteration, interval lookups), you need BTreeMap and BTreeSet.

These collections keep their entries in a B-Tree, a balanced tree structure that always keeps the keys sorted. Each operation (lookup, insertion, removal) is O(log n) in the worst case. There is no "amortized" qualifier, and no pathological hash collision can occur. The trade-off is that O(log n) is slower than O(1) for lookups only. But the sorted invariant makes possible a full class of operations that hash-based collections cannot do.

This tutorial shows:

• How to create a BTreeMap and a BTreeSet. The insertion order has no effect: the iteration order is always sorted.
• Range queries with range(), the primary advantage over hash-based collections.
• first_key_value, last_key_value, pop_first, and pop_last, which give access to the smallest and largest entries.
• The Entry API of BTreeMap, which has the same shape as the Entry API of HashMap.
• split_off, which divides a map at a threshold, and append, which merges maps.
• BTreeSet for ordered deduplication and sorted set operations.
• The Ord contract, and why floating-point types cannot be B-Tree keys.
• Performance characteristics: when to select a B-Tree and not a hash table.

Figure: B-Tree Node Structure (Conceptual)

BTreeMap Basics: Creation and Ordered Iteration

Insertion into a BTreeMap is the same as for HashMap. Call insert(key, value), or make the map from an array with BTreeMap::from(...). You see the difference only when you iterate: the entries always come in sorted key order.

use std::collections::BTreeMap;

let mut scores: BTreeMap<&str, u32> = BTreeMap::new();
scores.insert("charlie", 88);
scores.insert("alice", 95);   // inserted second, but iterates first
scores.insert("bob", 72);
scores.insert("diana", 91);

// `&scores` yields (&key, &value) pairs in ascending key order.
for (name, score) in &scores {
    println!("  {name}: {score}");
}
// Output: alice, bob, charlie, diana (lexicographic order)

With HashMap, the iteration order is arbitrary and changes between runs. With BTreeMap, the iteration order is deterministic and sorted. Thus the Debug output of a BTreeMap always shows the keys in order. This property is useful for snapshot tests and reproducible logs.

From arrays

// The compiler infers the type BTreeMap<&str, &str>.
let config = BTreeMap::from([
    ("host", "localhost"),
    ("port", "8080"),
    ("debug", "true"),
]);
// Debug output: {"debug": "true", "host": "localhost", "port": "8080"}

It is not necessary to sort the array elements. The B-Tree puts them in order internally.

Range Queries: The Primary Advantage

The range method is the primary difference between BTreeMap and HashMap. It accepts any range expression (.., start..end, start..=end, start.., ..end, ..=end). It returns an iterator that yields the key-value pairs in that range, in sorted order.

// The key is the hour (0 to 23). The value is the temperature in °C.
let mut temps: BTreeMap<u32, f64> = BTreeMap::new();
// (The example inserts one temperature for each hour here.)

// Query only 06:00 through 12:00 (inclusive).
// `hour` is &u32 and `temp` is &f64.
for (hour, temp) in temps.range(6..=12) {
    println!("  {hour:02}:00 → {temp:.1}°C");
}

This operation is O(log n + k), where k is the number of results. The B-Tree goes down to the start key in O(log n). Then it visits the subsequent entries in sequence. With a HashMap, you must iterate all the entries and filter them, which is O(n) each time.

Practical use cases for range

• Time-series data: select all the events between two timestamps.
• Leaderboards: find all the players with scores between 90 and 100.
• Configuration: get all the keys that start with a prefix. String order is lexicographic, so range("db.".."db/") gives all the db.* keys (/ is the character after .).
• Interval scheduling: find all the intervals that overlap a specified window.

Accessing Extremes

BTreeMap gives direct access to the smallest entry and the largest entry:

These methods are O(log n). pop_first and pop_last are useful for patterns that are almost a priority queue, where you consume the smallest or the largest entry:

// The key is the priority. A smaller number is a higher priority.
let mut priorities: BTreeMap<u32, &str> =
    BTreeMap::from([(1, "critical"), (2, "high"), (3, "medium"), (5, "low")]);

let highest = priorities.pop_first(); // Some((1, "critical")): the smallest key
let lowest  = priorities.pop_last();  // Some((5, "low")): the largest key
// priorities is now {2: "high", 3: "medium"}

The Ord Contract

BTreeMap keys must implement Ord, which is a total order. This requirement is stricter than the Hash + Eq requirement of HashMap. The Ord trait guarantees that you can compare any two values, and that the result is consistent, transitive, and antisymmetric.

Most standard types implement Ord: integers, strings, char, bool, Vec<T> (where T: Ord), and tuples. But floating-point types (f32, f64) do not implement Ord, because NaN != NaN breaks the requirement of a total order. If you need floating-point keys, put them in a newtype that handles NaN. For example, use ordered_float::OrderedFloat from the ecosystem, or write the comparison manually with std::cmp::Ordering.

For custom types, derive Ord together with PartialOrd, Eq, and PartialEq:

// The derived order compares `points` first. If the points are equal, it compares `name`.
#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
struct Score {
    points: u32,
    name: String,
}

The derived Ord compares the fields from top to bottom (lexicographic order on the struct fields). If you need a different order, implement Ord manually.

The Entry API

BTreeMap::entry operates the same as HashMap::entry. It returns an Entry enum. With it, you examine or change the value of a key with only one lookup:

use std::collections::BTreeMap;

let mut inventory: BTreeMap<&str, u32> = BTreeMap::new();
let items = ["apple", "banana", "apple", "cherry", "banana", "apple"];

for item in items {
    // If the key exists, add 1 to the count. If the key is absent, insert the count 1.
    inventory.entry(item).and_modify(|n| *n += 1).or_insert(1);
}
// inventory: {"apple": 3, "banana": 2, "cherry": 1}

The primary methods of Entry are:

Grouping with or_default

or_default is a clear method to make grouped collections:

let mut lists: BTreeMap<char, Vec<String>> = BTreeMap::new();
for name in ["Alice", "Ada", "Bob", "Clara", "Cleo"] {
    let initial = name.chars().next().unwrap();   // the first char is the group key
    // For a new initial, or_default inserts an empty Vec. Then push adds the name.
    lists.entry(initial).or_default().push(name.to_string());
}
// lists: {'A': ["Alice", "Ada"], 'B': ["Bob"], 'C': ["Clara", "Cleo"]}

The map is a BTreeMap, so the groups are in key order: 'A', then 'B', then 'C'.

split_off: Dividing a Map at a Threshold

split_off(&key) divides a BTreeMap into two maps. The entries with keys strictly less than key stay in the original map. The entries with keys greater than or equal to key move into the returned map.

let mut all_scores: BTreeMap<u32, &str> =
    BTreeMap::from([(10, "F"), (30, "D"), (50, "C"), (70, "B"), (90, "A")]);

let high = all_scores.split_off(&50);   // high: BTreeMap<u32, &str>
// all_scores: {10: "F", 30: "D"}          (keys < 50)
// high:       {50: "C", 70: "B", 90: "A"} (keys >= 50)

The division of the tree is O(log n). But the current implementation also counts the entries of one of the two maps, and that step is O(n) in the worst case. Use split_off when you must divide data at a boundary:

• grades that pass and grades that fail
• events before and after a cutoff time
• items below and above a price threshold

append: Merging Two Maps

append(&mut other) moves all the entries from other into self, and other becomes empty. If the two maps contain the same key, append keeps the value from other:

let mut base: BTreeMap<&str, i32> = BTreeMap::from([("a", 1), ("c", 3)]);
let mut extra: BTreeMap<&str, i32> = BTreeMap::from([("b", 2), ("d", 4)]);

base.append(&mut extra);   // moves "b" and "d" into `base`
// base:  {"a": 1, "b": 2, "c": 3, "d": 4}
// extra: {} (append emptied it)

The merged result is still sorted. append reads the two maps in key order and merges them in one pass. For two maps of similar size, this is faster than a separate insert call for each entry.

Conflict resolution

When the two maps have the same key, append keeps the value of the donor map:

let mut m1 = BTreeMap::from([("x", 1), ("y", 2)]);
let mut m2 = BTreeMap::from([("y", 99), ("z", 3)]);   // "y" is in the two maps
m1.append(&mut m2);
// m1["y"] == 99: the value from m2 replaces the value from m1
// m1 is now {"x": 1, "y": 99, "z": 3}

If you need a different merge rule (for example, the sum of the two values), iterate the donor map and use the Entry API.

BTreeSet: Ordered Deduplication and Set Operations

BTreeSet<T> has the same relation to BTreeMap<T, ()> as HashSet<T> has to HashMap<T, ()>. It is a collection of unique values with no associated data. The difference is that BTreeSet keeps its elements sorted.

Creation and ordering

use std::collections::BTreeSet;

// The array is not sorted, and it contains 1 and 5 two times.
let digits: BTreeSet<u8> = BTreeSet::from([5, 3, 1, 4, 1, 5, 9, 2, 6]);
// digits is {1, 2, 3, 4, 5, 6, 9}: sorted, with no duplicates

Iteration always yields the elements in ascending order.

Range queries on sets

As BTreeMap does, BTreeSet has a range method:

// `digits` is the BTreeSet<u8> from the previous snippet: {1, 2, 3, 4, 5, 6, 9}.
// range yields &u8. The pattern `&d` copies the value.
for &d in digits.range(3..=6) {
    print!("{d} ");
}
// 3 4 5 6

Set operations

BTreeSet has the four standard set operations. Each one returns a sorted iterator:

let evens: BTreeSet<i32> = (0..10).filter(|n| n % 2 == 0).collect();    // {0, 2, 4, 6, 8}
let threes: BTreeSet<i32> = (0..10).filter(|n| n % 3 == 0).collect();   // {0, 3, 6, 9}

// Each method yields &i32. `copied()` makes i32 values for the new set.
let union: BTreeSet<i32> = evens.union(&threes).copied().collect();
let intersection: BTreeSet<i32> = evens.intersection(&threes).copied().collect();
let difference: BTreeSet<i32> = evens.difference(&threes).copied().collect();
let sym_diff: BTreeSet<i32> = evens.symmetric_difference(&threes).copied().collect();
// union:        {0, 2, 3, 4, 6, 8, 9}
// intersection: {0, 6}
// difference:   {2, 4, 8}
// sym_diff:     {2, 3, 4, 8, 9}

The sets use a B-Tree, so the results are already sorted. With HashSet, the same operations give results in arbitrary order, and a sorted result needs a separate sort step.

Subset and superset checks

// `evens` is the set {0, 2, 4, 6, 8} from the previous snippet.
let small: BTreeSet<i32> = BTreeSet::from([2, 4]);
small.is_subset(&evens);    // true: 2 and 4 are in `evens`
evens.is_superset(&small);  // true: the same test from the other side

first, last, pop_first, pop_last

As BTreeMap does, BTreeSet gives direct O(log n) access to the smallest element and the largest element. pop_first and pop_last remove and return them.

Ordered Deduplication Pattern

A common pattern has two steps. Collect a Vec into a BTreeSet to remove the duplicates. Then collect the set into a Vec again to get sorted, unique elements:

let data = vec![5, 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];
let deduped_sorted: Vec<i32> = data
    .into_iter()
    .collect::<BTreeSet<_>>()   // removes the duplicates and sorts the values
    .into_iter()                // yields the values in ascending order
    .collect();
// deduped_sorted is [1, 2, 3, 4, 5, 6, 9]

This pattern is simpler than a manual sort and dedup, and the intent is clearer. The cost is O(n log n), the same asymptotic complexity as sort and dedup. But the constant factors are higher, because of the allocation overhead of the tree. For small to medium collections, prefer the clarity. For very large collections, sort and dedup on a Vec may be faster in practice.

Performance: B-Tree vs. Hash

Use BTreeMap when:

• You need range queries.
• You need sorted iteration.
• You need access to the minimum key or the maximum key.
• You want a deterministic iteration order for reproducible output.
• Your keys implement Ord but not Hash (rare, but possible with custom types).

Use HashMap when:

• You only do point lookups by exact key.
• You need the fastest possible lookups on large collections.
• The order is not important.

Figure: Choosing Between HashMap and BTreeMap

In practice, HashMap is the default. Use BTreeMap when order is a requirement, and not only a convenience.

Summary

Code Examples

Expected Output

04_09_btreemap_basics

leaderboard (sorted by name):
  alice: 95
  bob: 72
  charlie: 88
  diana: 91

config (sorted keys): {"debug": "true", "host": "localhost", "port": "8080"}

temperatures 06:00–12:00:
  06:00 → 30.0°C
  07:00 → 29.7°C
  08:00 → 29.0°C
  09:00 → 27.8°C
  10:00 → 26.3°C
  11:00 → 24.4°C
  12:00 → 22.5°C

afternoon max temp: 22.5°C

first key: alice, last key: diana

removed bob: Some(72)

pop_first (highest priority): Some((1, "critical"))
pop_last (lowest priority): Some((5, "low"))

All assertions passed.

04_10_btreemap_entry_split

inventory: {"apple": 3, "banana": 2, "cherry": 1}

grouped: {'A': ["Alice", "Ada"], 'B': ["Bob"], 'C': ["Clara", "Cleo"]}

before split_off(50): {10: "F", 30: "D", 50: "C", 70: "B", 90: "A"}
low  (<50):  {10: "F", 30: "D"}
high (>=50): {50: "C", 70: "B", 90: "A"}

before append:
  base:  {"a": 1, "c": 3}
  extra: {"b": 2, "d": 4}
after append:
  base:  {"a": 1, "b": 2, "c": 3, "d": 4}
  extra: {}

after conflicting append: m1 = {"x": 1, "y": 99, "z": 3}

All assertions passed.

04_11_btreeset

tags (sorted): {"collections", "rust", "tutorial"}
digits (sorted, deduped): {1, 2, 3, 4, 5, 6, 9}

digits in 3..=6:
3 4 5 6

after removing 'tutorial': {"collections", "rust"}
first digit: Some(1), last: Some(9)
after popping first and last: {2, 3, 4, 5, 6}

evens:  {0, 2, 4, 6, 8}
threes: {0, 3, 6, 9}
union:        {0, 2, 3, 4, 6, 8, 9}
intersection: {0, 6}
difference:   {2, 4, 8}
sym_diff:     {2, 3, 4, 8, 9}

{2,4} ⊂ evens: true

ordered dedup: [1, 2, 3, 4, 5, 6, 9]

All assertions passed.