Ordered Collections

BTreeMap.Entry

The std::collections::btree_map::Entry<'a, K, V> API mirrors hash_map::Entry, traversing the B-Tree once in $O(\log n)$ time and returning a cursor-like handle to either the existing key-value slot (Entry::Occupied) or the exact node position where a missing key belongs (Entry::Vacant).

Types and Methods in std::collections::btree_map

pub enum Entry<'a, K: 'a, V: 'a> {
    Vacant(VacantEntry<'a, K, V>),
    Occupied(OccupiedEntry<'a, K, V>),
}
Method Defined On Return Type Behavior
e.or_insert(default) Entry &'a mut V Inserts default at the searched B-Tree position if vacant
e.or_insert_with(f) Entry &'a mut V Calls f() lazily if vacant
e.or_insert_with_key(f) Entry &'a mut V Calls f(&key) lazily if vacant
e.or_default() Entry (V: Default) &'a mut V Inserts V::default() if vacant
e.and_modify(f) Entry Entry<'a, K, V> Mutates &mut V in place if occupied before chaining
occ.get() / occ.get_mut() OccupiedEntry &V / &mut V Borrows value while keeping occ alive
occ.into_mut() OccupiedEntry &'a mut V Consumes occ to return a map-lifetime mutable reference
occ.insert(new_v) OccupiedEntry V Replaces value and returns old value
occ.remove() / occ.remove_entry() OccupiedEntry V / (K, V) Removes the entry from the B-Tree without re-searching

Grouping Items into Sorted Buckets with BTreeMap::entry

Using BTreeMap::entry instead of HashMap::entry groups items in a single pass while keeping the group keys automatically sorted:

use std::collections::BTreeMap;

fn main() {
    let words = ["pear", "apple", "apricot", "banana", "blueberry", "peach"];
    let mut by_first_char: BTreeMap<char, Vec<&str>> = BTreeMap::new();

    for word in words {
        let first_ch = word.chars().next().unwrap();
        by_first_char.entry(first_ch).or_default().push(word);
    }

    // Keys ('a', 'b', 'p') are automatically visited in alphabetical order:
    for (letter, group) in &by_first_char {
        println!("'{letter}' -> {group:?}");
    }
}

'a' -> ["apple", "apricot"]
'b' -> ["banana", "blueberry"]
'p' -> ["pear", "peach"]

Conditional Removal via OccupiedEntry

Matching on btree_map::Entry::Occupied lets you inspect a key's current value, mutate it, and remove the node from the B-Tree if a condition is met—all with a single $O(\log n)$ tree descent:

use std::collections::BTreeMap;
use std::collections::btree_map::Entry;

fn apply_delta(ledger: &mut BTreeMap<&str, i64>, account: &str, delta: i64) {
    match ledger.entry(account) {
        Entry::Occupied(mut occ) => {
            *occ.get_mut() += delta;
            if *occ.get() == 0 {
                occ.remove(); // Prune zero-balance accounts immediately
            }
        }
        Entry::Vacant(vac) if delta != 0 => {
            vac.insert(delta);
        }
        Entry::Vacant(_) => {}
    }
}

fn main() {
    let mut ledger = BTreeMap::new();
    apply_delta(&mut ledger, "acct_1", 100);
    apply_delta(&mut ledger, "acct_2", 50);
    apply_delta(&mut ledger, "acct_1", -100); // Reaches 0 -> removed

    println!("Active non-zero accounts: {ledger:?}");
}

Active non-zero accounts: {"acct_2": 50}