351: BTreeMap Ordered
Functional Programming
Tutorial
The Problem
HashMap gives O(1) average lookup but no ordering guarantees — iterating a HashMap yields keys in unpredictable order, and range queries are impossible. BTreeMap solves this by storing key-value pairs in a B-tree (Bayer & McCreight, 1972) — a self-balancing tree optimized for block-access patterns. All operations are O(log n) in the worst case, and keys are always iterated in sorted order. BTreeMap is the right tool when you need sorted output, range queries, min_key/max_key in O(log n), or when the number of entries is small enough that cache-friendly sorted data beats hash table overhead.
🎯 Learning Outcomes
BTreeMap<K, V> from an iterator of pairs.range(from..=to) for efficient range queries without scanning all keys.keys().next() and maximum with .keys().next_back()BTreeMap requires K: Ord (total ordering), unlike HashMap's K: Hash + EqBTreeMap over HashMap based on access patternsentry() API for conditional insertion with ordered keysCode Example
#![allow(clippy::all)]
//! # BTreeMap Ordered
//! Sorted key-value map with efficient range queries.
use std::collections::BTreeMap;
pub fn sorted_map<K: Ord, V>(pairs: Vec<(K, V)>) -> BTreeMap<K, V> {
pairs.into_iter().collect()
}
pub fn range_query<K: Ord + Clone, V: Clone>(
map: &BTreeMap<K, V>,
from: &K,
to: &K,
) -> Vec<(K, V)> {
map.range(from..=to)
.map(|(k, v)| (k.clone(), v.clone()))
.collect()
}
pub fn min_key<K: Clone, V>(map: &BTreeMap<K, V>) -> Option<K> {
map.keys().next().cloned()
}
pub fn max_key<K: Clone, V>(map: &BTreeMap<K, V>) -> Option<K> {
map.keys().next_back().cloned()
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn sorted_iteration() {
let m = sorted_map(vec![(3, 'c'), (1, 'a'), (2, 'b')]);
let keys: Vec<_> = m.keys().cloned().collect();
assert_eq!(keys, vec![1, 2, 3]);
}
#[test]
fn range_works() {
let m: BTreeMap<i32, i32> = (0..10).map(|i| (i, i * i)).collect();
let r = range_query(&m, &3, &5);
assert_eq!(r, vec![(3, 9), (4, 16), (5, 25)]);
}
#[test]
fn min_max_keys() {
let m = sorted_map(vec![(5, 'e'), (1, 'a'), (9, 'i')]);
assert_eq!(min_key(&m), Some(1));
assert_eq!(max_key(&m), Some(9));
}
}Key Differences
| Aspect | Rust BTreeMap | OCaml Map.Make |
|---|---|---|
| Underlying structure | B-tree (cache-friendly) | AVL tree (balanced binary tree) |
| Mutability | In-place mutation | Persistent (immutable, functional) |
| Range query | O(log n + k) with .range() | O(n) with filter |
| Ordering requirement | K: Ord | compare function via functor |
| Min/max | O(log n) via next()/next_back() | O(log n) via min_binding/max_binding |
OCaml Approach
OCaml's Map.Make functor creates ordered maps parameterized by a comparison module:
module IntMap = Map.Make(Int)
let sorted_map pairs =
List.fold_left (fun m (k, v) -> IntMap.add k v m) IntMap.empty pairs
(* Range query: filter (no built-in range iterator) *)
let range_query m lo hi =
IntMap.filter (fun k _ -> k >= lo && k <= hi) m
|> IntMap.to_seq |> List.of_seq
let min_key m = fst (IntMap.min_binding m)
let max_key m = fst (IntMap.max_binding m)
OCaml's Map is a purely functional AVL tree — all operations return new maps (persistent). Rust's BTreeMap is imperative with in-place modification. OCaml lacks a built-in range query iterator; Map.filter scans all entries (O(n)) unless you use a custom fold.
Full Source
#![allow(clippy::all)]
//! # BTreeMap Ordered
//! Sorted key-value map with efficient range queries.
use std::collections::BTreeMap;
pub fn sorted_map<K: Ord, V>(pairs: Vec<(K, V)>) -> BTreeMap<K, V> {
pairs.into_iter().collect()
}
pub fn range_query<K: Ord + Clone, V: Clone>(
map: &BTreeMap<K, V>,
from: &K,
to: &K,
) -> Vec<(K, V)> {
map.range(from..=to)
.map(|(k, v)| (k.clone(), v.clone()))
.collect()
}
pub fn min_key<K: Clone, V>(map: &BTreeMap<K, V>) -> Option<K> {
map.keys().next().cloned()
}
pub fn max_key<K: Clone, V>(map: &BTreeMap<K, V>) -> Option<K> {
map.keys().next_back().cloned()
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn sorted_iteration() {
let m = sorted_map(vec![(3, 'c'), (1, 'a'), (2, 'b')]);
let keys: Vec<_> = m.keys().cloned().collect();
assert_eq!(keys, vec![1, 2, 3]);
}
#[test]
fn range_works() {
let m: BTreeMap<i32, i32> = (0..10).map(|i| (i, i * i)).collect();
let r = range_query(&m, &3, &5);
assert_eq!(r, vec![(3, 9), (4, 16), (5, 25)]);
}
#[test]
fn min_max_keys() {
let m = sorted_map(vec![(5, 'e'), (1, 'a'), (9, 'i')]);
assert_eq!(min_key(&m), Some(1));
assert_eq!(max_key(&m), Some(9));
}
}
✓ Tests
Rust test suite
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn sorted_iteration() {
let m = sorted_map(vec![(3, 'c'), (1, 'a'), (2, 'b')]);
let keys: Vec<_> = m.keys().cloned().collect();
assert_eq!(keys, vec![1, 2, 3]);
}
#[test]
fn range_works() {
let m: BTreeMap<i32, i32> = (0..10).map(|i| (i, i * i)).collect();
let r = range_query(&m, &3, &5);
assert_eq!(r, vec![(3, 9), (4, 16), (5, 25)]);
}
#[test]
fn min_max_keys() {
let m = sorted_map(vec![(5, 'e'), (1, 'a'), (9, 'i')]);
assert_eq!(min_key(&m), Some(1));
assert_eq!(max_key(&m), Some(9));
}
}Deep Comparison
OCaml vs Rust: Btreemap Ordered
Overview
See the example.rs and example.ml files for detailed implementations.
Key Differences
| Aspect | OCaml | Rust |
|---|---|---|
| Type system | Hindley-Milner | Ownership + traits |
| Memory | GC | Zero-cost abstractions |
| Mutability | Explicit ref | mut keyword |
| Error handling | Option/Result | Result<T, E> |
See README.md for detailed comparison.
Exercises
BTreeMap<&str, usize>; print the top 5 words sorted alphabetically, then resort by frequency using a BinaryHeap.BTreeMap<i32, i32> (key → value), implement range_sum(map, lo, hi) that returns the sum of values for all keys in [lo, hi] using .range().BTreeMap<i32, i32> where keys are interval starts and values are interval ends; implement a query that finds all intervals overlapping a given point using .range(..=point).