std::collections::BTreeMap — Rust struct

What `BTreeMap` does

An ordered map based on a B-Tree, with O(log n) operations and ordered iteration.

As a struct, BTreeMap bundles related fields into a single named record with a known layout. Each field has a fixed type and offset, so the size of an instance is the sum of its field sizes plus alignment padding. Construction follows ordinary Rust ownership rules: each owned field must itself be constructed or moved before the struct is well-formed, and the compiler will refuse to leave any field uninitialised. The full canonical path is std::collections::BTreeMap; bring it into scope with use std::collections::BTreeMap; or refer to it by its full path.

When to use it

Use BTreeMap when you need keys to be visited in sorted order, when you need range queries (`range(a..b)`), or when memory locality and predictable comparator-based ordering matter more than raw single-lookup speed.

Annotated examples

Range query: every key between two bounds

use std::collections::BTreeMap;
use std::ops::Bound::Included;

fn timeline_slice(events: &BTreeMap<u64, String>, from: u64, to: u64) -> Vec<&String> {
    events
        .range((Included(from), Included(to)))
        .map(|(_ts, msg)| msg)
        .collect()
}

BTreeMap::range returns an in-order iterator over a half-open or closed bound — impossible with HashMap, which is the main reason to choose BTreeMap.

For deeper background, see the canonical Rust patterns reference for the broader context behind this section.

Removing the smallest entry with pop_first

use std::collections::BTreeMap;

fn drain_lowest_priority(queue: &mut BTreeMap<u32, String>) -> Option<String> {
    // pop_first removes and returns the entry with the smallest key.
    // This makes BTreeMap a passable priority queue when keys = priority.
    queue.pop_first().map(|(_priority, payload)| payload)
}

BTreeMap exposes pop_first / pop_last for cheap min/max removal in O(log n), which is hard to beat without bringing in a separate priority-queue crate.

Common pitfalls

BTreeMap requires its key type to implement `Ord`. Floating-point keys (`f32`, `f64`) only implement `PartialOrd` and will not compile — wrap them in a custom newtype with a total order if you need that. Iteration order is by key, not by insertion order; use `IndexMap` from the indexmap crate if you need both.

For deeper background, see an in-depth Rust idioms cheat sheet for the broader context behind this section.

Performance & threading notes

Stack-allocated by default. Heap allocation only happens if a field is itself heap-allocated (Vec, String, Box). Cloning copies every field; for read access pass by reference. Send / Sync are automatically derived if every field is Send / Sync.

What BTreeMap does