Module collections/ordered_map
Insertion-ordered map.
OrderedMap(K, V) preserves the order in which keys were first inserted,
similar to JavaScript's Map or Python's dict (≥ 3.7). The entries live
in one ArrayList(MapEntry(K, V)) in insertion order — the ONLY place a
key is stored — beside a hash index from each key's hash to the positions
of the entries whose key hashes to it, so lookup is O(1) average time and
the key is never copied
(issues/fixed/2026-10-16-an-orderedmap-of-a-move-only-key-does-not-compile.md).
Complexity
set(new key): O(1) amortizedset(existing key): O(1) — value updated in place, order unchangedget/contains_key: O(1) averageremove: O(n) — the entries after the removed one shift down a slotswap_remove: O(1) — moves the last entry into the removed slot, so the iteration order changes (Rust'sIndexMap::swap_remove)index_of/get_index: O(1) — positional lookup, both directionsiter/keys/values: O(n), in insertion order
Example
{ OrderedMap } :: import("std/collections/ordered_map");
m := OrderedMap(String, i32).new();
m.insert(`alpha`, i32(1));
m.insert(`beta`, i32(2));
m.insert(`gamma`, i32(3));
// Iteration yields keys in insertion order.
it := m.keys();
while(true, {
match(
it.next(),
.Some(k) => println(&k),
.None => break
);
});
Stability
unstable — plans/archive/STD_API_STABILIZATION.md §4 still lists one shape open
here: remove is O(n) because it rebuilds the key-order list, and the O(1)
swap_remove that indexmap offers beside it (removing by swapping the
last key into the hole, at the cost of the order) has not been decided.
Adding it would change what remove's cost is worth accepting. Everything
else is settled — D14's pointer iter() and the IntoIterator that makes
for(map, ...) work both landed 2026-09-08.
Types
Ordered map preserving insertion order of keys.
Keys must implement Eq and Hash.
The key of each entry is stored ONCE, in _entries; _index maps the
key's HASH to the positions of the entries whose key hashes to it (two
keys can share a hash, so the value is a list of positions, each compared
by key in place). A move-only key — a Drop type, a Box, a plain type
with neither Copy nor Clone — therefore moves in with its entry and
out again, never through a copy.
Type Parameters
| Name | Type | Notes |
|---|---|---|
K | Type | comptime |
V | Type | comptime |
Trait Implementations
impl(generic(K : Type, V : Type), where(K <: (Eq(K), Hash)), OrderedMap(K, V), ...)
new : (fn() -> Self)Create an empty OrderedMap.
Returns: Self
len : (fn(self : &Self) -> usize)Number of entries.
Returns: usize
is_empty : (fn(self : &Self) -> bool)Whether the map is empty.
Returns: bool
_entries_ptr : (fn(self : &Self) -> *MapEntry(K, V))The entry buffer, for the in-place readers. Only called with a position
below len(), so the buffer exists.
Returns: *MapEntry(K, V)
_hash_key : (fn(self : &Self, key : &K) -> u64)A key's hash. The FIXED SipHash keys keep the index reproducible run to
run, as HashMap does for its bucket order.
Returns: u64
_find_pos : (fn(self : &Self, key : &K) -> Option(usize))The position of key in _entries, comparing each candidate's key in
place — a &K is all a lookup ever needs, so a move-only key is found.
Returns: Option(usize)
_index_add : (fn(self : &mut Self, h : u64, pos : usize) -> unit)Record that pos holds an entry whose key hashes to h.
The position list is written WHERE THE INDEX HOLDS IT, through the
bucket's entry pointer — a projection into the map's own storage. A
list read out with get is a copy once ArrayList is a value type,
and a push onto the copy would be lost; the same holds for
_index_drop and _index_bump.
Returns: unit
_index_drop : (fn(self : &mut Self, h : u64, pos : usize) -> unit)Forget the position pos under h (remove/swap_remove).
Returns: unit
_index_bump : (fn(self : &mut Self, h : u64, from : usize, to : usize) -> unit)Move a position record from from to to under h — the fix-up a
shift or a swap leaves behind.
Returns: unit
contains_key : (fn(self : &Self, key : &K) -> bool)Returns true if key is present.
Returns: bool
get : (fn(self : &Self, key : &K) -> Option(V))Returns the value for key, or .None.
Returns: Option(V)
try_insert : (fn(self : &mut Self, key : K, value : V) -> Result(Option(V), HashMapError))Insert or update key -> value.
- For a new key, the whole entry (key and value) moves into the list.
- For an existing key, only the value moves: it is swapped in place, bitwise, and the old one moves out. The key never moves.
Returns Ok(.Some(old_value)) if key already existed, Ok(.None) for
a new key, or .Err(_) on allocation failure.
The allocator-aware form (D9); insert is the one to reach for.
Returns: Result(Option(V), HashMapError)
insert : (fn(self : &mut Self, key : K, value : V) -> Option(V))Insert a key/value pair, returning the PREVIOUS value for that key. A new key is appended to the insertion order; an existing key keeps its position.
PANICS on allocation failure (D9). Use try_insert to handle OOM.
Returns: Option(V)
remove : (fn(self : &mut Self, key : &K) -> Option(V))Remove key, keeping the insertion order of everything else — Rust's
IndexMap::shift_remove. Returns the removed value or .None.
O(n) in the number of entries AFTER the removed one: they each shift
down a slot, and the hash index has to learn where they went. Use
swap_remove when the order does not matter.
Returns: Option(V)
swap_remove : (fn(self : &mut Self, key : &K) -> Option(V))Remove key in O(1), moving the LAST entry into its position — Rust's
IndexMap::swap_remove. Returns the removed value or .None.
This CHANGES the iteration order, which is the whole trade: remove
preserves insertion order and pays O(n) to rebuild the entry list, while
this touches two slots and is done. Reach for it when you are draining
a map, or when order stops mattering once a key is gone.
Returns: Option(V)
index_of : (fn(self : &Self, key : &K) -> Option(usize))The position of key in the iteration order, or .None if it is
absent — Rust's IndexMap::get_index_of. O(1): the hash index that
swap_remove needs already answers this.
Returns: Option(usize)
get_index : (fn(self : &Self, i : usize) -> Option(MapEntry(K, V)))clear : (fn(self : &mut Self) -> unit)Remove all entries.
Returns: unit
impl(generic(K : Type, V : Type), where(K <: (Eq(K), Hash), V <: Clone), OrderedMap(K, V), ...)
get_cloned : (fn(self : &Self, key : &K) -> Option(V))A clone of the value for key, or .None.
Returns: Option(V)
impl(generic(K : Type, V : Type), where(K <: (Eq(K), Hash, Clone), V <: Clone), OrderedMap(K, V), ...)
impl(generic(K : Type, V : Type), where(K <: (Eq(K), Hash)), OrderedMap(K, V), IntoIterator(...))
Item : MapEntry(K, V)IntoIter : OrderedMapIter(K, V)into_iter : (fn(self : Self) -> OrderedMapIter(K, V))Iterate (key, value) pairs BY VALUE in insertion order — the shape
iter() had before D14, and what for(map, ...) expands to.
Returns: OrderedMapIter(K, V)
impl(generic(K : Type, V : Type), where(K <: (Eq(K), Hash)), OrderedMap(K, V), ...)
keys : (fn(self : Self) -> OrderedMapKeys(K, V))Iterator over keys in insertion order. Consumes the map (lookahead D20).
Returns: OrderedMapKeys(K, V)
values : (fn(self : Self) -> OrderedMapValues(K, V))Iterator over values in insertion order. Consumes the map (lookahead D20).
Returns: OrderedMapValues(K, V)
iter : (fn(self : &Self) -> OrderedMapIterPtr(K, V))Iterator over (key, value) pairs in insertion order, yielding a
*(MapEntry(K, V)) into the map's own storage (D14): the
pragma(Pragma.AllowUnsafe) form, whose iterator holds the entry
buffer, not the map (B7b). Use into_iter() for the consuming by-value
form and for(&map, (k, v) => ...) to read in place.
Returns: OrderedMapIterPtr(K, V)
impl(generic(K : Type, V : Type), where(K <: (Eq(K), Hash)), OrderedMap(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), where(K <: (Eq(K), Hash)), OrderedMap(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), where(K <: (Eq(K), Hash)), OrderedMap(K, V), Default(...))
default : (fn() -> Self)The default value of the type.
Returns: Self
Iterator over the keys of an OrderedMap in insertion order.
Type Parameters
| Name | Type | Notes |
|---|---|---|
K | Type | comptime |
V | Type | comptime |
impl(generic(K : Type, V : Type), where(K <: (Eq(K), Hash)), OrderedMapKeys(K, V), ...)
next : (fn(self : &mut Self) -> Option(K))Next key in INSERTION order, or .None at the end — O(1), straight off
the entry list.
The keys are yielded by value (dup'd for a refcounted K). Inserting a
new key during the walk appends to that list and so extends the walk;
removing one shifts everything after the removed entry.
Returns: Option(K)
Iterator over the values of an OrderedMap in insertion order.
Type Parameters
| Name | Type | Notes |
|---|---|---|
K | Type | comptime |
V | Type | comptime |
impl(generic(K : Type, V : Type), where(K <: (Eq(K), Hash)), OrderedMapValues(K, V), ...)
next : (fn(self : &mut Self) -> Option(V))Next value in the KEYS' insertion order, or .None at the end — O(1),
a plain array read off the entry list.
Returns: Option(V)
Pointer iterator over an OrderedMap's (key, value) pairs, in insertion
order — what iter() returns (D14).
Each next yields a *(MapEntry(K, V)) straight into the entry list's
buffer, so entries are borrowed rather than rebuilt by value, and writing
p.*.value updates the map in place. A raw view (decision 39, B7b): it
holds the entry list'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; any
insertion that grows the buffer reallocates it, and a
remove/swap_remove shifts entries, so both invalidate or reorder
pointers already yielded.
Type Parameters
| Name | Type | Notes |
|---|---|---|
K | Type | comptime |
V | Type | comptime |