Btreemap

Vec::extract_if was great. The BTreeMap version, stable since Rust 1.91, adds a trick the slice variant can’t pull off — a range bound that scopes the scan to part of the keyspace.

The collect-keys-then-remove dance

You want to remove every entry matching a predicate from a BTreeMap, and keep the removed entries. The borrow checker won’t let you mutate the map while you’re iterating it, so the textbook workaround is a two-pass clone-the-keys shuffle:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

use std::collections::BTreeMap;

let mut events: BTreeMap<u64, String> = BTreeMap::from([
    (1, "boot".into()),
    (2, "login".into()),
    (3, "click".into()),
    (4, "logout".into()),
]);

let cutoff = 3;

let to_remove: Vec<u64> = events
    .iter()
    .filter(|(k, _)| **k < cutoff)
    .map(|(k, _)| *k)            // requires K: Copy or Clone
    .collect();

let mut expired = Vec::new();
for k in to_remove {
    if let Some(v) = events.remove(&k) {
        expired.push((k, v));
    }
}

assert_eq!(expired.len(), 2);

It works, but the costs add up. You walk the map twice, you require K: Clone (or Copy), and you allocate a throwaway Vec<K> just to break the self-borrow.

extract_if is one pass — and it takes a range

BTreeMap::extract_if(range, pred) returns an iterator that visits keys in ascending order inside the given range, and yields (K, V) for every entry whose predicate returns true. The map’s structure is updated as the iterator advances:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

use std::collections::BTreeMap;

let mut events: BTreeMap<u64, &str> = BTreeMap::from([
    (1, "boot"),
    (2, "login"),
    (3, "click"),
    (4, "logout"),
    (5, "shutdown"),
]);

let expired: BTreeMap<u64, &str> =
    events.extract_if(..3, |_k, _v| true).collect();

assert_eq!(expired.into_iter().collect::<Vec<_>>(), [(1, "boot"), (2, "login")]);
assert_eq!(events.keys().copied().collect::<Vec<_>>(), [3, 4, 5]);

No Clone bound. No second pass. No temp Vec<K>. The range ..3 does double duty as a prune — keys outside it aren’t even visited, which matters when the map is large and the range is small.

The closure can mutate survivors too

The predicate signature is FnMut(&K, &mut V) -> bool. Returning true removes and yields; returning false keeps the entry in the map — but you’ve still got &mut V, so you can edit it on the way past:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

use std::collections::BTreeMap;

let mut scores: BTreeMap<&str, i32> = BTreeMap::from([
    ("alice", 85),
    ("bob",   42),
    ("carol", 91),
    ("dan",   30),
]);

let failing: Vec<(&str, i32)> = scores
    .extract_if(.., |_k, v| {
        if *v < 50 {
            true            // pull this one out
        } else {
            *v += 5;        // bump the survivors by 5
            false           // keep it
        }
    })
    .collect();

assert_eq!(failing, [("bob", 42), ("dan", 30)]);
assert_eq!(scores[&"alice"], 90);
assert_eq!(scores[&"carol"], 96);

One traversal, three behaviors at once: filter, remove, and update.

Constraints

The range is RangeBounds<K>, so anything from .. to start..=end works. extract_if panics if start > end or if the bounds collapse to an empty exclusive range. BTreeSet::extract_if is the same idea minus the value — predicate signature is FnMut(&T) -> bool.

When to reach for it

Whenever the operation is “walk a sorted map, peel off the entries matching a condition, optionally bounded to a key range”. Expiring old timestamped events. Draining tasks below a priority watermark. Splitting a map at a tenant boundary into “keep” and “ship”. The range bound is the part the Vec::extract_if (bite 43) can’t give you — and on a large map, scoping the scan is the whole point.

BinaryHeap only goes one way — biggest first. When you want to pull the smallest or the largest from the same collection, reach for BTreeMap and let pop_first / pop_last do the work.

The classic shape: a queue of jobs keyed by priority where you sometimes need the most-urgent job and sometimes the least-urgent one. With BinaryHeap you’d pick a direction and stick with it (or wrap things in Reverse to flip it). With BTreeMap you get both ends for free, because the keys are already sorted:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

use std::collections::BTreeMap;

let mut jobs: BTreeMap<u32, &str> = BTreeMap::new();
jobs.insert(5, "rebuild index");
jobs.insert(1, "send heartbeat");
jobs.insert(9, "page oncall");
jobs.insert(3, "rotate logs");

// Smallest key first — drain by priority.
assert_eq!(jobs.pop_first(), Some((1, "send heartbeat")));
assert_eq!(jobs.pop_first(), Some((3, "rotate logs")));

// Or grab the most urgent from the other end.
assert_eq!(jobs.pop_last(), Some((9, "page oncall")));

// Empty? You get None — same shape as Vec::pop.
let mut empty: BTreeMap<u32, &str> = BTreeMap::new();
assert_eq!(empty.pop_first(), None);

Both methods return Option<(K, V)> and remove the entry from the map. No second lookup, no .remove(key) follow-up after .first_key_value().

Where this really earns its keep is the “drain-in-order” loop — the kind of thing you’d otherwise write with a heap plus a sidecar map:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

use std::collections::BTreeMap;

let mut tasks: BTreeMap<u32, String> = BTreeMap::new();
tasks.insert(20, "compact".into());
tasks.insert(10, "vacuum".into());
tasks.insert(30, "snapshot".into());

let mut order = Vec::new();
while let Some((priority, name)) = tasks.pop_first() {
    order.push((priority, name));
}

assert_eq!(
    order,
    vec![
        (10, "vacuum".into()),
        (20, "compact".into()),
        (30, "snapshot".into()),
    ],
);

Same loop, swap pop_first for pop_last and you drain in reverse order — no Reverse wrapper, no second collection.

BTreeSet got the same pair (pop_first / pop_last) at the same time, so a sorted set behaves like a deque you can pop from either end:

1
2
3
4
5
6

use std::collections::BTreeSet;

let mut ids: BTreeSet<u32> = BTreeSet::from([7, 2, 9, 4]);
assert_eq!(ids.pop_first(), Some(2));
assert_eq!(ids.pop_last(),  Some(9));
assert_eq!(ids.len(), 2);

A few things worth knowing. BTreeMap insertion is O(log n) — heavier than a BinaryHeap push, which amortises to O(1). If you genuinely only ever pop from one side and throughput matters, a heap still wins. The moment you need ordered iteration, range queries, or popping from both ends, BTreeMap is the better fit and pop_first / pop_last make that fit feel native.

Stable since Rust 1.66 — and one of those methods that quietly replaces a fistful of match arms once you remember it exists.