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). Backed by a
HashMap for O(1) average-time lookup and an ArrayList of keys for
deterministic iteration order.
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 keys after the removed one shift down a slotswap_remove: O(1) — moves the last key 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/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.
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
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 : Self, key : K, value : V) -> Result(Option(V), HashMapError))Insert or update key -> value.
- For a new key, appends
keyto the insertion order. - For an existing key, only updates the value; order is preserved.
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 : 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 : 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 keys AFTER the removed one: they each shift down a
slot, and the position index has to learn where they went. Use
swap_remove when the order does not matter.
Returns: Option(V)
swap_remove : (fn(self : Self, key : K) -> Option(V))Remove key in O(1), moving the LAST key 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 key list, while
this touches three 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 position 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 : Self) -> unit)Remove all entries.
Returns: unit
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.
Returns: OrderedMapKeys(K, V)
values : (fn(self : Self) -> OrderedMapValues(K, V))Iterator over values in insertion order.
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). Use into_iter()
for the by-value form.
Returns: OrderedMapIterPtr(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
A single key/value entry in a map.
Type Parameters
| Name | Type | Notes |
|---|---|---|
K | Type | comptime |
V | Type | comptime |
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(inout(self) : Self) -> Option(K))Next value in the KEYS' insertion order, or .None at the end.
Costs a hash lookup per step — it reads the key off the order list and
then asks the backing map for its value — where keys() is a plain
array read. iter() yields entry pointers and pays the lookup once per
entry too, but hands back the key alongside the value.
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(inout(self) : Self) -> Option(V))Next value in the KEYS' insertion order, or .None at the end.
Costs a hash lookup per step — it reads the key off the order list and
then asks the backing map for its value — where keys() is a plain
array read. iter() yields entry pointers and pays the lookup once per
entry too, but hands back the key alongside the value.
Returns: Option(V)
Iterator over (key, value) pairs of an OrderedMap in insertion order.
Type Parameters
| Name | Type | Notes |
|---|---|---|
K | Type | comptime |
V | Type | comptime |
Trait Implementations
Pointer iterator over an OrderedMap's (key, value) pairs, in insertion
order — what iter() returns (D14).
Each next yields a *(MapEntry(K, V)) INTO the backing HashMap's
bucket array (the same storage HashMap.iter() hands out), so entries are
borrowed rather than rebuilt by value, and writing p.*.value updates the
map in place. Any mutation that rehashes the map (insert that grows it,
remove, clear) invalidates pointers already yielded.
Type Parameters
| Name | Type | Notes |
|---|---|---|
K | Type | comptime |
V | Type | comptime |