Ordered maps in Rust

Open a paper dictionary and look up "maple". You do not read from page one. You flip to the M section, then narrow in, and there it is.

Now ask a different question: which words come between "map" and "mat"? That is easy too. Find "map", then keep reading until you pass "mat". The words you want are all side by side, because the dictionary keeps its words in alphabetical order.

An ordered map works like that. It stores pairs of a key and a value (as in lesson 6), but it keeps them sorted by key. Because of that, it can answer questions a hash map cannot:

• What is the smallest key? The largest?
• Which key is just below this one? Just above it?
• Which pairs have keys between two limits? This is a range query.

Reach for an ordered map when the order of the keys matters: a leaderboard, a timetable, grade boundaries, or anything where you ask "what is the closest one?" If you only ever look things up by exact key, a hash map is simpler and a bit faster.

Suppose the keys are 10, 20, 30, up to 80, in order. You want every key from 30 up to, but not including, 60.

You do not check all eight. First you find where the range starts: the slot holding 30. Then you step along, 30, 40, 50, until you reach 60, which is past the end, and stop. You never touch 10, 20, 70 or 80.

Two small pieces of vocabulary. In Rust, 30..60 is a half-open range: it includes the start but not the end. It is the same style as 0..n in a for loop. 30..=60 includes the end too.

How do you find the start without checking every key? With binary search. Look at the middle key. If it is too small, throw away the left half. If it is too big, throw away the right half. Repeat. Each look halves what is left, so even a million keys take only about twenty looks. This is the same halving trick as the search tree in lesson 7, and it works because the keys are sorted.

So a range query has two parts. Finding the start costs O(log n). Walking the results costs O(k), where k is how many you got back.

Remember: sorted keys put neighbours next to each other. Find the start once, then just walk.

Here is the simplest ordered map: a Vec of (key, value) pairs, always kept sorted by key.

/// An ordered map from `i32` to `i32`, kept as a `Vec` of pairs sorted by key.
pub struct SortedMap {
    pairs: Vec<(i32, i32)>,
}

impl SortedMap {
    pub fn new() -> Self {
        SortedMap { pairs: Vec::new() }
    }

    pub fn len(&self) -> usize {
        self.pairs.len()
    }

    pub fn is_empty(&self) -> bool {
        self.pairs.is_empty()
    }

    /// Binary search: `Ok(i)` if the key is at `i`, or `Err(i)` with the
    /// place it would have to go to keep the order.
    fn find(&self, key: i32) -> Result<usize, usize> {
        self.pairs.binary_search_by_key(&key, |&(k, _)| k)
    }

    pub fn get(&self, key: i32) -> Option<i32> {
        self.find(key).ok().map(|i| self.pairs[i].1)
    }

    /// Stores a pair. If the key was already there, its old value is returned.
    pub fn insert(&mut self, key: i32, value: i32) -> Option<i32> {
        match self.find(key) {
            Ok(i) => Some(std::mem::replace(&mut self.pairs[i].1, value)),
            Err(i) => {
                self.pairs.insert(i, (key, value)); // shifts everything after i
                None
            }
        }
    }

    pub fn remove(&mut self, key: i32) -> Option<i32> {
        let i = self.find(key).ok()?;
        Some(self.pairs.remove(i).1)
    }

    pub fn first(&self) -> Option<(i32, i32)> {
        self.pairs.first().copied()
    }

    pub fn last(&self) -> Option<(i32, i32)> {
        self.pairs.last().copied()
    }

    /// Every pair with `from <= key < to`, already in order.
    pub fn range(&self, from: i32, to: i32) -> &[(i32, i32)] {
        // `partition_point` is a binary search for the first key that fails the test.
        let start = self.pairs.partition_point(|&(k, _)| k < from);
        // `max(start)` keeps a backwards range (from > to) empty instead of a panic.
        let end = self.pairs.partition_point(|&(k, _)| k < to).max(start);
        &self.pairs[start..end]
    }
}

impl Default for SortedMap {
    fn default() -> Self {
        Self::new()
    }
}

Go through it in order.

• find does the binary search. binary_search_by_key returns a Result. Ok(i) means the key is at slot i. Err(i) means the key is missing, and i is the slot where it would have to go to keep the order. That one answer serves both get and insert.
• insert uses it. If the key is found, std::mem::replace swaps in the new value and hands back the old one. If not, Vec::insert puts the new pair in exactly the slot find suggested.
• remove finds the slot, then takes the pair out. The ? returns None early if the key was missing.
• range uses partition_point, a binary search for the first slot where a test stops being true. Slots before from fail k < from, so the first slot that passes is where the range starts. The same trick finds where it ends. The max(start) stops a backwards range, such as range(30, 10), from panicking.

Here it is in use.

let mut map = SortedMap::new();
for key in [50, 20, 40, 10, 30] {
    map.insert(key, key * 10); // they arrive in any order
}

println!("{:?}", map.range(20, 45));
assert_eq!(map.range(20, 45), [(20, 200), (30, 300), (40, 400)]);
assert_eq!(map.get(40), Some(400));
assert_eq!(map.get(45), None);
assert_eq!(map.first(), Some((10, 100)));
assert_eq!(map.last(), Some((50, 500)));

The keys went in as 50, 20, 40, 10, 30, and range(20, 45) still returned 20, 30, 40 in order. The Playground link on the code above runs this.

There is one cost to be honest about. Searching is quick, but insert and remove must shift every later pair along, as in lesson 1. That is O(n). For a big map with many changes, that hurts.

The standard library's BTreeMap keeps its keys sorted too, but it stores them in a balanced tree instead of one long Vec. Inserting and removing are O(log n), with no shifting. Lesson 7 met the same idea in BTreeSet, which is a BTreeMap with keys and no values.

use std::collections::BTreeMap;

let mut ages = BTreeMap::new();
ages.insert("maya", 21);
ages.insert("arun", 19);
ages.insert("zoya", 22);
ages.insert("ben", 20);

// Iteration is in key order, whatever order you inserted in.
let names: Vec<&str> = ages.keys().copied().collect();
println!("{:?}", names);
assert_eq!(names, ["arun", "ben", "maya", "zoya"]);
assert_eq!(ages.first_key_value(), Some((&"arun", &19)));
assert_eq!(ages.last_key_value(), Some((&"zoya", &22)));
assert_eq!(ages.get("maya"), Some(&21));

You did nothing to sort the names. Iterating a BTreeMap always visits the keys in order. first_key_value and last_key_value give the smallest and largest pair. The entry API from lesson 6 works here as well.

The star feature is range:

use std::collections::BTreeMap;

let mut map = BTreeMap::new();
for key in [10, 20, 30, 40, 50] {
    map.insert(key, key * 10);
}

// `a..b` is "from a up to, but not including, b".
let middle: Vec<i32> = map.range(20..45).map(|(&k, _)| k).collect();
println!("{:?}", middle);
assert_eq!(middle, [20, 30, 40]);

// `..=b` includes b. `a..` has no upper end.
assert_eq!(map.range(..=20).count(), 2);
assert_eq!(map.range(40..).count(), 2);

20..45 includes 20 but not 45. ..=20 means "everything up to and including 20", and 40.. means "from 40 onwards". Each call returns an iterator, so you can .map, .count, or .collect it like any other.

A range query can also answer "what is the nearest key?" Add next_back(), which takes the last item of an iterator, or next(), which takes the first. Here is a grade lookup, where each key is the lowest score that earns a grade:

use std::collections::BTreeMap;

// Each key is the lowest score that earns that grade.
let mut grades = BTreeMap::new();
grades.insert(0, "F");
grades.insert(40, "D");
grades.insert(55, "C");
grades.insert(70, "B");
grades.insert(85, "A");

let score = 72;
// The last key at or below the score: look backwards from `..=score`.
let grade = grades.range(..=score).next_back().map(|(_, g)| *g);
println!("{:?}", grade);
assert_eq!(grade, Some("B"));

// The first key at or above 60: look forwards from `60..`.
let next = grades.range(60..).next().map(|(&k, _)| k);
assert_eq!(next, Some(70));

range(..=score) is every boundary at or below 72. The last of those, found by next_back(), is the closest one below: 70, which is a B. Going the other way, range(60..).next() is the first boundary at or above 60.

Remember: range(..=x).next_back() is the closest key at or below x, and range(x..).next() is the closest at or above.

Two cautions. Keys must have a total order, so an f64 cannot be a key. And range panics if the start is bigger than the end, so check the bounds first if they come from outside.

How does that compare with the others? A HashMap gets and inserts in O(1) on average, but it has no order, so it cannot do a range query at all. The sorted Vec you built also gets in O(log n) and does ranges in O(log n + k), but its insert and remove are O(n). BTreeMap is the one that is good at everything, for a little more than O(1).

Each starter has a signature and a todo!(), which is a placeholder that panics if it runs. Replace it with your code. The Playground link on each starter runs a tiny demo.

use std::collections::BTreeSet;

pub fn floor_and_ceiling(set: &BTreeSet<i32>, x: i32) -> (Option<i32>, Option<i32>) {
    todo!("the biggest value <= x, and the smallest value >= x")
}

use std::collections::BTreeSet;

pub fn floor_and_ceiling(set: &BTreeSet<i32>, x: i32) -> (Option<i32>, Option<i32>) {
    // `..=x` ends at x, so its last item is the floor. `x..` starts at x,
    // so its first item is the ceiling.
    let floor = set.range(..=x).next_back().copied();
    let ceiling = set.range(x..).next().copied();
    (floor, ceiling)
}

pub fn letter_counts(text: &str) -> Vec<(char, usize)> {
    todo!("count each letter, ignoring case, and list them a to z")
}

pub fn letter_counts(text: &str) -> Vec<(char, usize)> {
    use std::collections::BTreeMap;

    let mut counts = BTreeMap::new();
    for c in text.chars().filter(|c| c.is_alphabetic()) {
        *counts.entry(c.to_ascii_lowercase()).or_insert(0) += 1;
    }
    // A BTreeMap iterates in key order, so the sorting is already done.
    counts.into_iter().collect()
}

pub struct TimeMap {
    // choose your own fields
}

impl TimeMap {
    pub fn new() -> Self {
        todo!()
    }

    /// Remembers that `key` had `value` at time `time`.
    pub fn set(&mut self, key: &str, value: &str, time: u32) {
        todo!()
    }

    /// The value `key` had at `time`: the latest one set at or before it.
    pub fn get(&self, key: &str, time: u32) -> Option<&str> {
        todo!()
    }
}

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

/// Each key has its own history: a map from time to value.
pub struct TimeMap {
    history: HashMap<String, BTreeMap<u32, String>>,
}

impl TimeMap {
    pub fn new() -> Self {
        TimeMap {
            history: HashMap::new(),
        }
    }

    pub fn set(&mut self, key: &str, value: &str, time: u32) {
        self.history
            .entry(key.to_string())
            .or_default()
            .insert(time, value.to_string());
    }

    pub fn get(&self, key: &str, time: u32) -> Option<&str> {
        let past = self.history.get(key)?;
        // The latest entry at or before `time`.
        let (_, value) = past.range(..=time).next_back()?;
        Some(value.as_str())
    }
}

Ordered maps solve a family of questions that a hash map cannot. A few habits help.

• Spot the signals. "The closest", "the next larger", "at or before", "between a and b", and "in sorted order" all point to an ordered map or set.
• Know the four words. The floor of x is the biggest key at or below x. The ceiling is the smallest key at or above it. The predecessor is the key just before x, and the successor is the key just after. Using the right word makes your answer clear.
• Explain why not a hash map. A hash map scatters its keys on purpose, so it cannot find neighbours or ranges. That one sentence shows you understand both structures.
• Explain why not a sorted Vec. Searching is just as quick, but every insert shifts the items after it, which is O(n). That is the cost the tree removes.
• Ask about the range ends. Is the end included? Rust's a..b leaves it out, and a..=b keeps it. Guessing wrong is an easy way to be off by one.
• Say the cost. "Get, insert and remove are O(log n), and a range query is O(log n + k)" is a complete answer.

Made by VeraStack Labs