BTreeMap range queries

Answer a time-window query over a log of timestamped events.

pub fn events_between(events: Vec<(i64, String)>, from: i64, to: i64) -> Vec<String>

Index the events by timestamp in a BTreeMap<i64, Vec<String>>, then return the names of every event whose timestamp is in the half-open interval [from, to) — from included, to excluded. Timestamps ascending; events sharing a timestamp keep their input order.

Two cases you must handle rather than assume away: from > to, and a window entirely past the end of the data. Both return an empty Vec. Neither may panic.

What a BTreeMap is actually for

Beginners often file BTreeMap under “the sorted HashMap” and then never use it, because sorting at the end is easy. That misses the point. Ordered iteration is a side effect; the reason BTreeMap exists is range:

map.range(from..to)      // every entry with from <= key < to

This is O(log n) to find the start plus O(k) to walk the k matches. Not O(n). The tree descends to the first key at or after from and then walks the leaves in order. A HashMap cannot do this at any price: hashing destroys adjacency by design, so “all keys between two values” means visiting every entry.

That single operation is why BTreeMap is the right index for time series, version numbers, sorted IDs, priority tiers, and anything where you routinely ask “what is in this window?” or “what is the next one after X?”

range accepts anything implementing RangeBounds<K>:

map.range(a..b)      // [a, b)
map.range(a..=b)     // [a, b]
map.range(a..)       // [a, infinity)
map.range(..b)       // (-infinity, b)
map.range(..)        // everything, same as iter()

For a range that excludes its start there is no operator, so you spell it with Bound directly:

use std::ops::Bound;
map.range((Bound::Excluded(a), Bound::Unbounded))   // (a, infinity)

The panic

range panics if the start is greater than the end:

thread 'main' panicked at library/alloc/src/collections/btree/search.rs:
range start is greater than range end in BTreeMap

Note what this is not: it is not a Result, not an empty iterator, not a clamp. std made a judgement — range(9..4) is almost certainly a bug in the caller, and silently returning nothing would hide it. So it is your job to decide what a reversed window means in your domain, and this problem says it means “no events”. Guard before you call.

You will meet this design a lot in std: slice::windows(0) panics, slice[a..b] panics if b > len, integer division by zero panics. The rule of thumb is that std panics for programmer errors and returns Option/Result for situations the program is expected to encounter. Whether a reversed range is one or the other is a question about your program, and the compiler cannot answer it for you.

The compile error in the starter

error[E0277]: a value of type `Vec<String>` cannot be built from an iterator
              over elements of type `&String`

range yields (&K, &V) — the map still owns everything. So flat_map(|(_, v)| v) iterates a &Vec<String> and produces &String, and a Vec<String> cannot be collected from references. This is the same borrowed-versus-owned distinction from the ownership track, met through a trait bound instead of a move error, and E0277 (“the trait bound is not satisfied”) is how it will usually reach you from now on.

.cloned() is the fix — and it is honest about the cost: you asked for owned Strings in the return type, so somebody has to allocate them.

::: question Why does BTreeMap require K: Ord while HashMap requires K: Hash + Eq? Because they answer different questions. A hash map only needs to know whether two keys are the same (Eq) and how to scatter them into buckets (Hash). A B-tree needs to know which of two keys comes first, at every node, on every descent — that is Ord.

The practical consequence bites early: f64 is not Ord, because NaN is not equal to itself and is not ordered against anything. So BTreeMap<f64, _> does not compile. The escape hatches are to store a wrapper type that defines a total order, or to store the bits, or to use a fixed-point integer key. There is a whole item on this later in the course — for now, just recognise the error when you meet it. :::

range is not filter

It is worth being explicit that

map.iter().filter(|(k, _)| **k >= from && **k < to)

produces the same answer and is O(n). It looks similar, reads similarly, and is asymptotically worse for the entire reason the data structure was chosen. If you find yourself filtering a BTreeMap by a key comparison, that is almost always a range you have not spotted. (clippy’s manual_range_contains is a cousin of this observation, for the x >= a && x < b shape itself.)

Remember the grade is compile + tests + clippy -D warnings.