Module collections/btree_map
Sorted map backed by a sorted array with O(log n) lookup via binary search.
The name is Rust's, the shape is Rust's — key-ordered iteration, range,
first_entry/last_entry, pop_first/pop_last — but the storage is
not: entries live in one ArrayList kept in key order, so get and
contains_key are O(log n) while insert and remove are O(n) (they
shift the tail), where Rust's B-tree gives all four O(log n). That trade
wins for the small, read-mostly maps this is used for and costs on
insert-heavy ones; use HashMap when the order is not needed.
Example
{ BTreeMap } :: import "std/collections/btree_map";
m := BTreeMap(String, i32).new();
m.insert(String.from("b"), 2);
m.insert(String.from("a"), 1);
// Iteration order: a, b
Stability
stable — the surface mirrors std::collections::BTreeMap (insert
returning the replaced value since 2026-09-06, contains_key, range
over a Range(K), pop_first/pop_last, FromIterator), and
plans/STD_API_STABILIZATION.md §4 lists nothing open against it. The
sorted-array backing is an implementation choice, not part of the
contract: replacing it with a real B-tree would change complexity, not
any signature.
Types
A single key/value entry in a map.
Type Parameters
| Name | Type | Notes |
|---|---|---|
K | Type | comptime |
V | Type | comptime |
Sorted map maintaining entries in key order. Provides ordered iteration and O(log n) lookup via binary search. Insert is O(n).
Type Parameters
| Name | Type | Notes |
|---|---|---|
K | Type | comptime |
V | Type | comptime |
Trait Implementations
impl(generic(K : Type, V : Type), BTreeMap(K, V), ...)
new : (fn() -> Self)Empty map.
Returns: Self
len : (fn(self : Self) -> usize)Number of entries. O(1).
Returns: usize
is_empty : (fn(self : Self) -> bool)True when the map holds no entries.
Returns: bool
_find : (fn(self : Self, k : K, where(K <: Ord(K))) -> _FindResult)Returns: _FindResult
get : (fn(self : Self, k : K, where(K <: Ord(K))) -> Option(V))Copy of the value stored under k, or .None — O(log n) binary
search. self(k) (the Index impl) asserts the key is present
instead.
Returns: Option(V)
insert : (fn(self : Self, k : K, v : V, where(K <: Ord(K))) -> Option(V))Insert or update the value for key k, returning the value it REPLACED
(.None for a new key) — Rust's BTreeMap::insert. Until 2026-09-06
this returned unit, dropping the old value silently, and discarded
push's Result before computing len() - 1
(issues/fixed/btree-map-insert-dropped-the-old-value-and-push-results-were-ignored.md).
For new keys: append at end then shift-left to the sorted position.
Returns: Option(V)
remove : (fn(self : Self, k : K, where(K <: Ord(K))) -> Option(V))Remove the entry for k and return its value, or .None — O(log n)
to find it, O(n) to close the gap, and the key order is preserved.
Returns: Option(V)
contains_key : (fn(self : Self, k : K, where(K <: Ord(K))) -> bool)Whether k is present — Rust's contains_key. O(log n), and it does
not touch the value.
Returns: bool
pop_first : (fn(self : Self, where(K <: Ord(K))) -> Option(MapEntry(K, V)))pop_last : (fn(self : Self, where(K <: Ord(K))) -> Option(MapEntry(K, V)))first_entry : (fn(self : Self) -> Option(MapEntry(K, V)))The entry with the smallest key, or .None — O(1), since the backing
array is kept in key order.
Named first_entry/last_entry rather than min/max because this is
a MAP: it returns a whole MapEntry, not a key. Sets keep min/max,
which do return the element (plans/archive/STD_API_AUDIT.md §5).
impl(generic(K : Type, V : Type), BTreeMap(K, V), IntoIterator(...))
Item : MapEntry(K, V)IntoIter : BTreeMapIter(K, V)into_iter : (fn(self : Self) -> BTreeMapIter(K, V))Returns: BTreeMapIter(K, V)
impl(generic(K : Type, V : Type), BTreeMap(K, V), ...)
iter : (fn(self : Self) -> BTreeMapIterPtr(K, V))Borrowing walk in key order: yields a *(MapEntry(K, V)) into the
backing array and leaves the map intact (D14).
Returns: BTreeMapIterPtr(K, V)
impl(generic(K : Type, V : Type), BTreeMap(K, V), ...)
keys : (fn(self : Self) -> BTreeMapKeys(K, V))Walk the keys in ascending order — Rust's keys.
Returns: BTreeMapKeys(K, V)
impl(generic(K : Type, V : Type), BTreeMap(K, V), ...)
values : (fn(self : Self) -> BTreeMapValues(K, V))Walk the values in key order — Rust's values.
Returns: BTreeMapValues(K, V)
impl(generic(K : Type, V : Type), BTreeMap(K, V), ...)
range : (fn(self : Self, r : Range(K), where(K <: Ord(K))) -> BTreeMapRange(K, V))The entries whose keys lie in [start, end), in key order — Rust's
range.
The window is a Range(K) — write it with ..: m.range(k1 .. k2). It is
half-open, like every other range in the language, so a .. b and b .. c
partition [a, c) with nothing counted twice, and the .. at the call
site says so without the reader having to remember.
An inverted window yields NOTHING rather than erroring — unlike
Rng.range / random_range, which panic. The difference is what each
returns: an empty iterator is a real answer, whereas a sampler asked for
a value from an empty range has none to give.
The bounds do NOT have to be present in the map: _find reports the
insertion point for an absent key, which is exactly the first entry at or
past it.
Returns: BTreeMapRange(K, V)
impl(generic(K : Type, V : Type), where(K <: Ord(K)), BTreeMap(K, V), FromIterator(...))
Elem : MapEntry(K, V)from_iter_new : (fn() -> Self)The empty collection collect starts from.
Returns: Self
from_iter_add : (fn(acc : Self, item : MapEntry(K, V)) -> Self)Add one element to a partially-built collection and return it.
Parameters
| Name | Type | Notes |
|---|---|---|
acc | Self | |
item | MapEntry(K, V) |
Returns: Self
impl(generic(K : Type, V : Type), BTreeMap(K, V), Index(K)(...))
Output : Vindex : (fn(inout(self) : Self, idx : K, where(K <: Ord(K))) -> *Self.Output)impl(generic(K : Type, V : Type), BTreeMap(K, V), Default(...))
default : (fn() -> Self)The default value of the type.
Returns: Self
Value iterator over a BTreeMap — yields each MapEntry(K, V) BY VALUE in
KEY ORDER. This is what into_iter(), and therefore for(map, ...),
returns; iter() yields pointers.
It holds the backing entry list by handle, so the walk sees the array as it was when the iterator was made plus any in-place value updates; inserting or removing during the walk shifts entries under it.
Type Parameters
| Name | Type | Notes |
|---|---|---|
K | Type | comptime |
V | Type | comptime |
Trait Implementations
Pointer iterator over a BTreeMap — yields *(MapEntry(K, V)) into the
backing array, in key order. This is what iter() returns (D14): nothing
is dup'd, and p.*.value can be written in place.
An insert or remove during the walk shifts or reallocates that array
and invalidates every pointer already yielded.
Type Parameters
| Name | Type | Notes |
|---|---|---|
K | Type | comptime |
V | Type | comptime |
Trait Implementations
Iterator over the entries of one key window, in key order — what
range(k1 .. k2) returns.
The window is resolved to array INDICES once, when the iterator is made, so an insertion during the walk moves entries in or out of it. Yields entries by value.
Type Parameters
| Name | Type | Notes |
|---|---|---|
K | Type | comptime |
V | Type | comptime |
Trait Implementations
Iterator over a BTreeMap's keys in ascending order — what keys()
returns. Keys are yielded by value.
Type Parameters
| Name | Type | Notes |
|---|---|---|
K | Type | comptime |
V | Type | comptime |
Trait Implementations
impl(generic(K : Type, V : Type), BTreeMapKeys(K, V), Iterator(...))
Item : Knext : (fn(inout(self) : Self) -> Option(K))Advance the iterator and return the next value, or None when exhausted.
Returns: Option(K)
Iterator over a BTreeMap's values, ordered by their KEYS — what
values() returns. Values are yielded by value.
Type Parameters
| Name | Type | Notes |
|---|---|---|
K | Type | comptime |
V | Type | comptime |
Trait Implementations
impl(generic(K : Type, V : Type), BTreeMapValues(K, V), Iterator(...))
Item : Vnext : (fn(inout(self) : Self) -> Option(V))Advance the iterator and return the next value, or None when exhausted.
Returns: Option(V)