1027 Intermediate

1027-btreemap-sorted — BTreeMap: Sorted Key Iteration

Functional Programming

Tutorial

The Problem

Hash maps provide O(1) average lookup but iterate in arbitrary order, making them unsuitable for tasks that require processing keys in sorted order — leaderboards, time-series data, range queries, and sorted output. B-trees, invented by Bayer and McCreight in 1972 for database indexes, maintain sorted order while keeping operations O(log n). Rust's BTreeMap is a cache-friendly B-tree optimized for modern hardware.

This is the data structure behind database indexes, std::map in C++, and OCaml's Map.Make module.

🎯 Learning Outcomes

• Understand when to choose BTreeMap over HashMap

• Iterate over a BTreeMap in guaranteed sorted key order

• Use the range method for efficient range queries without scanning all entries

• Use first_key_value and last_key_value for O(log n) min/max access

• Implement a sorted frequency counter

Code Example

#![allow(clippy::all)]
// 1027: BTreeMap — Sorted Key Iteration
// Rust's BTreeMap keeps keys in sorted order (B-tree internally)

use std::collections::BTreeMap;

/// Build a BTreeMap and iterate — keys come out sorted
fn sorted_iteration() {
    let mut m = BTreeMap::new();
    m.insert(5, "five");
    m.insert(1, "one");
    m.insert(3, "three");
    m.insert(7, "seven");
    m.insert(2, "two");

    let keys: Vec<_> = m.keys().collect();
    assert_eq!(keys, vec![&1, &2, &3, &5, &7]);

    let values: Vec<_> = m.values().collect();
    assert_eq!(values, vec![&"one", &"two", &"three", &"five", &"seven"]);
}

/// Range queries using the `range` method
fn range_query() {
    let mut m = BTreeMap::new();
    for (k, v) in [(1, "a"), (2, "b"), (3, "c"), (4, "d"), (5, "e")] {
        m.insert(k, v);
    }

    // Get elements with keys in [2, 4]
    let range_keys: Vec<_> = m.range(2..=4).map(|(&k, _)| k).collect();
    assert_eq!(range_keys, vec![2, 3, 4]);

    // Half-open range [3, ∞)
    let tail: Vec<_> = m.range(3..).map(|(&k, _)| k).collect();
    assert_eq!(tail, vec![3, 4, 5]);
}

/// First and last key (min/max)
fn min_max() {
    let m: BTreeMap<i32, &str> = [(10, "ten"), (3, "three"), (7, "seven")]
        .into_iter()
        .collect();

    let (&min_k, _) = m.iter().next().unwrap();
    let (&max_k, _) = m.iter().next_back().unwrap();
    assert_eq!(min_k, 3);
    assert_eq!(max_k, 10);
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_sorted_iteration() {
        sorted_iteration();
    }

    #[test]
    fn test_range_query() {
        range_query();
    }

    #[test]
    fn test_min_max() {
        min_max();
    }

    #[test]
    fn test_from_iterator() {
        let pairs = vec![(3, "c"), (1, "a"), (2, "b")];
        let m: BTreeMap<_, _> = pairs.into_iter().collect();
        let keys: Vec<_> = m.keys().copied().collect();
        assert_eq!(keys, vec![1, 2, 3]);
    }
}

(* 1027: BTreeMap — Sorted Key Iteration *)
(* OCaml's Map module is tree-based and always sorted *)

module IntMap = Map.Make(Int)

(* Approach 1: Build and iterate in sorted order *)
let sorted_iteration () =
  let m = IntMap.empty
    |> IntMap.add 5 "five"
    |> IntMap.add 1 "one"
    |> IntMap.add 3 "three"
    |> IntMap.add 7 "seven"
    |> IntMap.add 2 "two"
  in
  let keys = IntMap.fold (fun k _v acc -> k :: acc) m [] |> List.rev in
  assert (keys = [1; 2; 3; 5; 7]);
  let values = IntMap.fold (fun _k v acc -> v :: acc) m [] |> List.rev in
  assert (values = ["one"; "two"; "three"; "five"; "seven"])

(* Approach 2: Range queries using split *)
let range_query () =
  let m = IntMap.empty
    |> IntMap.add 1 "a"
    |> IntMap.add 2 "b"
    |> IntMap.add 3 "c"
    |> IntMap.add 4 "d"
    |> IntMap.add 5 "e"
  in
  (* Get elements with keys in [2, 4] *)
  let (_, _, right) = IntMap.split 1 m in
  let (left, _, _) = IntMap.split 5 right in
  let range_keys = IntMap.fold (fun k _v acc -> k :: acc) left [] |> List.rev in
  assert (range_keys = [2; 3; 4])

(* Approach 3: Min/max binding *)
let min_max () =
  let m = IntMap.empty
    |> IntMap.add 10 "ten"
    |> IntMap.add 3 "three"
    |> IntMap.add 7 "seven"
  in
  let (min_k, _) = IntMap.min_binding m in
  let (max_k, _) = IntMap.max_binding m in
  assert (min_k = 3);
  assert (max_k = 10)

let () =
  sorted_iteration ();
  range_query ();
  min_max ();
  Printf.printf "✓ All tests passed\n"

Key Differences

Default sort: OCaml's Map.Make is always sorted by key — there is no unsorted alternative; Rust has both HashMap (unsorted) and BTreeMap (sorted).

Range API: Rust has an explicit .range(lo..=hi) method; OCaml uses to_seq_from plus take_while for the equivalent.

Cache efficiency: Rust's B-tree stores multiple keys per node (cache-friendly); OCaml's balanced binary tree stores one key per node.

Persistence: OCaml's Map is persistent (update returns a new version sharing structure); Rust's BTreeMap is mutable.

OCaml Approach

OCaml's Map.Make(Ord) is always a sorted tree map. It has no hash map variant in the standard library, so range queries are natural:

module IntMap = Map.Make(Int)

let range_query m lo hi =
  IntMap.to_seq_from lo m
  |> Seq.take_while (fun (k, _) -> k <= hi)
  |> List.of_seq

Map.to_seq_from starts iteration at a given key, enabling efficient range scans without the explicit range API.

Full Source

#![allow(clippy::all)]
// 1027: BTreeMap — Sorted Key Iteration
// Rust's BTreeMap keeps keys in sorted order (B-tree internally)

use std::collections::BTreeMap;

/// Build a BTreeMap and iterate — keys come out sorted
fn sorted_iteration() {
    let mut m = BTreeMap::new();
    m.insert(5, "five");
    m.insert(1, "one");
    m.insert(3, "three");
    m.insert(7, "seven");
    m.insert(2, "two");

    let keys: Vec<_> = m.keys().collect();
    assert_eq!(keys, vec![&1, &2, &3, &5, &7]);

    let values: Vec<_> = m.values().collect();
    assert_eq!(values, vec![&"one", &"two", &"three", &"five", &"seven"]);
}

/// Range queries using the `range` method
fn range_query() {
    let mut m = BTreeMap::new();
    for (k, v) in [(1, "a"), (2, "b"), (3, "c"), (4, "d"), (5, "e")] {
        m.insert(k, v);
    }

    // Get elements with keys in [2, 4]
    let range_keys: Vec<_> = m.range(2..=4).map(|(&k, _)| k).collect();
    assert_eq!(range_keys, vec![2, 3, 4]);

    // Half-open range [3, ∞)
    let tail: Vec<_> = m.range(3..).map(|(&k, _)| k).collect();
    assert_eq!(tail, vec![3, 4, 5]);
}

/// First and last key (min/max)
fn min_max() {
    let m: BTreeMap<i32, &str> = [(10, "ten"), (3, "three"), (7, "seven")]
        .into_iter()
        .collect();

    let (&min_k, _) = m.iter().next().unwrap();
    let (&max_k, _) = m.iter().next_back().unwrap();
    assert_eq!(min_k, 3);
    assert_eq!(max_k, 10);
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_sorted_iteration() {
        sorted_iteration();
    }

    #[test]
    fn test_range_query() {
        range_query();
    }

    #[test]
    fn test_min_max() {
        min_max();
    }

    #[test]
    fn test_from_iterator() {
        let pairs = vec![(3, "c"), (1, "a"), (2, "b")];
        let m: BTreeMap<_, _> = pairs.into_iter().collect();
        let keys: Vec<_> = m.keys().copied().collect();
        assert_eq!(keys, vec![1, 2, 3]);
    }
}

(* 1027: BTreeMap — Sorted Key Iteration *)
(* OCaml's Map module is tree-based and always sorted *)

module IntMap = Map.Make(Int)

(* Approach 1: Build and iterate in sorted order *)
let sorted_iteration () =
  let m = IntMap.empty
    |> IntMap.add 5 "five"
    |> IntMap.add 1 "one"
    |> IntMap.add 3 "three"
    |> IntMap.add 7 "seven"
    |> IntMap.add 2 "two"
  in
  let keys = IntMap.fold (fun k _v acc -> k :: acc) m [] |> List.rev in
  assert (keys = [1; 2; 3; 5; 7]);
  let values = IntMap.fold (fun _k v acc -> v :: acc) m [] |> List.rev in
  assert (values = ["one"; "two"; "three"; "five"; "seven"])

(* Approach 2: Range queries using split *)
let range_query () =
  let m = IntMap.empty
    |> IntMap.add 1 "a"
    |> IntMap.add 2 "b"
    |> IntMap.add 3 "c"
    |> IntMap.add 4 "d"
    |> IntMap.add 5 "e"
  in
  (* Get elements with keys in [2, 4] *)
  let (_, _, right) = IntMap.split 1 m in
  let (left, _, _) = IntMap.split 5 right in
  let range_keys = IntMap.fold (fun k _v acc -> k :: acc) left [] |> List.rev in
  assert (range_keys = [2; 3; 4])

(* Approach 3: Min/max binding *)
let min_max () =
  let m = IntMap.empty
    |> IntMap.add 10 "ten"
    |> IntMap.add 3 "three"
    |> IntMap.add 7 "seven"
  in
  let (min_k, _) = IntMap.min_binding m in
  let (max_k, _) = IntMap.max_binding m in
  assert (min_k = 3);
  assert (max_k = 10)

let () =
  sorted_iteration ();
  range_query ();
  min_max ();
  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_sorted_iteration() {
        sorted_iteration();
    }

    #[test]
    fn test_range_query() {
        range_query();
    }

    #[test]
    fn test_min_max() {
        min_max();
    }

    #[test]
    fn test_from_iterator() {
        let pairs = vec![(3, "c"), (1, "a"), (2, "b")];
        let m: BTreeMap<_, _> = pairs.into_iter().collect();
        let keys: Vec<_> = m.keys().copied().collect();
        assert_eq!(keys, vec![1, 2, 3]);
    }
}

Deep Comparison

BTreeMap: Sorted Key Iteration — Comparison

Core Insight

Both languages provide tree-based sorted maps. OCaml's Map uses a balanced binary tree (AVL); Rust's BTreeMap uses a B-tree optimized for cache locality. Both guarantee sorted iteration.

OCaml Approach

• Functor-based: Map.Make(Ord) creates a map module for a given key type

• Immutable by default — add returns a new map

• split for range queries: splits map into (below, at, above)

• min_binding / max_binding for extremes

• fold for ordered traversal

Rust Approach

• Generic: BTreeMap<K: Ord, V> — no functor needed

• Mutable with insert, or built from iterators via collect()

• range() accepts RangeBounds for efficient sub-range iteration

• iter().next() / iter().next_back() for min/max

• B-tree layout means better cache performance than binary trees

Comparison Table

Feature	OCaml (`Map`)	Rust (`BTreeMap`)
Structure	AVL tree	B-tree
Mutability	Immutable	Mutable
Key constraint	`Ord` module (functor)	`Ord` trait (generic)
Sorted iteration	`fold` / `iter`	`iter()` / `keys()` / `values()`
Range query	`split` (returns 3 parts)	`range(a..=b)` (lazy iterator)
Min/Max	`min_binding` / `max_binding`	`first_key_value()` / `last_key_value()`
Cache locality	Poor (pointer-heavy)	Good (B-tree nodes)

Exercises

Build a time-series store using BTreeMap<u64, f64> (timestamp -> value) and write a window_average(start: u64, end: u64) function using range.

Implement a ranked_top_k(map: &BTreeMap<String, usize>, k: usize) -> Vec<(&str, usize)> that returns the k most frequent items in alphabetical order.

Write a function that splits a BTreeMap at a given key into two maps using split_off.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust