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/archive/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
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 : &mut 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 : &mut 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 : &mut Self, where(K <: Ord(K))) -> Option(MapEntry(K, V)))pop_last : (fn(self : &mut 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), where(V <: Clone), BTreeMap(K, V), ...)
get_cloned : (fn(self : &Self, k : &K, where(K <: Ord(K))) -> Option(V))A clone of the value stored under k, or .None — O(log n).
Returns: Option(V)
impl(generic(K : Type, V : Type), where(K <: Clone, V <: Clone), BTreeMap(K, V), ...)
first_entry_cloned : (fn(self : &Self) -> Option(MapEntry(K, V)))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))Raw walk in key order: yields a *(MapEntry(K, V)) into the backing
array and leaves the map intact (D14). Safe code reads entries with
for(&map, (k, v) => ...); this is the pragma(Pragma.AllowUnsafe)
form, whose iterator holds the array's buffer, not the map (B7b).
Returns: BTreeMapIterPtr(K, V)
impl(generic(K : Type, V : Type), BTreeMap(K, V), BorrowedWalk(...))
WalkCursor : usizeWalkElem : MapEntry(K, V)walk_start : (fn(self : &Self) -> usize)The first position (equal to the end for an empty collection).
Returns: usize
walk_valid : (fn(self : &Self, cur : &usize) -> bool)Whether cur names an element.
Parameters
| Name | Type | Notes |
|---|---|---|
cur | &usize |
Returns: bool
walk_ref : (fn(self : &Self, cur : &usize) -> &MapEntry(K, V))The element at cur, read in place (a read projection). Panics if cur
names no element.
Parameters
| Name | Type | Notes |
|---|---|---|
cur | &usize |
Returns: &MapEntry(K, V)
walk_next : (fn(self : &Self, cur : &usize) -> usize)The position after cur.
Parameters
| Name | Type | Notes |
|---|---|---|
cur | &usize |
Returns: usize
impl(generic(K : Type, V : Type), BTreeMap(K, V), BorrowedWalkMut(...))
walk_elem : (fn(self : &mut Self, cur : &usize) -> &mut MapEntry(K, V))The element at cur, written in place (a mutable projection). Panics
if cur names no element.
Parameters
| Name | Type | Notes |
|---|---|---|
cur | &usize |
Returns: &mut MapEntry(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. Consumes the map
(lookahead D20).
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. Consumes the map
(lookahead D20).
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(sink(acc) : Self, item : &MapEntry(K, V)) -> Self)Add one element to a partially-built collection and return it.
Parameters
| Name | Type | Notes |
|---|---|---|
item | &MapEntry(K, V) |
Returns: Self
impl(generic(K : Type, V : Type), BTreeMap(K, V), Index(K)(...))
Output : Vindex : (fn(self : &Self, idx : K, where(K <: Ord(K))) -> &Self.Output)impl(generic(K : Type, V : Type), BTreeMap(K, V), IndexMut(K)(...))
Output : Vindex_mut : (fn(self : &mut Self, idx : K, where(K <: Ord(K))) -> &mut 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.
A raw view (decision 39, B7b): it holds the entry array's buffer pointer
and the length iter() saw, NOT the map, so it keeps nothing alive and is
meant for pragma(Pragma.AllowUnsafe) code. The map must outlive the
walk; an insert or remove during it 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(self : &mut 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(self : &mut Self) -> Option(V))Advance the iterator and return the next value, or None when exhausted.
Returns: Option(V)