Module collections/ordered_map

collections/ordered_map
Stability: unstable — may still change; see below.

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) amortized
  • set (existing key): O(1) — value updated in place, order unchanged
  • get / contains_key: O(1) average
  • remove: O(n) — the entries after the removed one shift down a slot
  • swap_remove: O(1) — moves the last entry into the removed slot, so the iteration order changes (Rust's IndexMap::swap_remove)
  • index_of / get_index: O(1) — positional lookup, both directions
  • iter / 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

OrderedMap type-function
fn(K : Type, V : Type) -> Type

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

NameTypeNotes
KTypecomptime
VTypecomptime

Trait Implementations

impl(generic(T : Type), where(T <: Clone), T : (Clone))
impl(generic(T : Type), where(T <: Clone), T : (Clone), CloneInto)
clone_into : fn(self : &Self, dst : *(Self)) -> unit

Write a clone of self into the uninitialized slot dst, which has room for size_of_val(self) bytes at align_of_val(self).

Parameters

NameTypeNotes
selfSelf
dst*(Self)

Returns: unit

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)

_find_among : (fn(self : &Self, positions : &ArrayList(usize), key : &K) -> Option(usize))

The entry among positions whose key is key, compared in place.

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)))

The (key, value) pair at position i in the iteration order, or .None when i is out of range — Rust's IndexMap::get_index.

Returns: 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), ...)
get_index_cloned : (fn(self : &Self, i : usize) -> Option(MapEntry(K, V)))

A clone of the (key, value) pair at position i in the iteration order, or .None when i is out of range — get_index for a key or value that is not copied implicitly.

Returns: Option(MapEntry(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), Default(...))
default : (fn() -> Self)

The default value of the type.

Returns: Self

impl(generic(K : Type, V : Type, p : Origin), where(K <: (Eq(K), Hash)), &(OrderedMap(K, V), p), IntoIterator(...))
Item : Tuple(&(K, p), &(V, p))
IntoIter : OrderedMapCursor(K, V, p)
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, p : Origin), where(K <: (Eq(K), Hash)), &mut(OrderedMap(K, V), p), IntoIterator(...))
Item : Tuple(&(K, p), &mut(V, p))
IntoIter : OrderedMapCursorMut(K, V, p)
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)

MapEntry type-function
fn(K : Type, V : Type) -> Type

A single key/value entry in a map.

Type Parameters

NameTypeNotes
KTypecomptime
VTypecomptime

Trait Implementations

impl(generic(T : Type), where(T <: Clone), T : (Clone))
impl(generic(T : Type), where(T <: Clone), T : (Clone), CloneInto)
clone_into : fn(self : &Self, dst : *(Self)) -> unit

Write a clone of self into the uninitialized slot dst, which has room for size_of_val(self) bytes at align_of_val(self).

Parameters

NameTypeNotes
selfSelf
dst*(Self)

Returns: unit

OrderedMapKeys type-function
fn(K : Type, V : Type) -> Type

Iterator over the keys of an OrderedMap in insertion order.

Type Parameters

NameTypeNotes
KTypecomptime
VTypecomptime

Trait Implementations

impl(generic(T : Type), where(T <: Clone), T : (Clone))
impl(generic(T : Type), where(T <: Clone), T : (Clone), CloneInto)
clone_into : fn(self : &Self, dst : *(Self)) -> unit

Write a clone of self into the uninitialized slot dst, which has room for size_of_val(self) bytes at align_of_val(self).

Parameters

NameTypeNotes
selfSelf
dst*(Self)

Returns: unit

impl(generic(K : Type, V : Type), where(K <: (Eq(K), Hash, Clone)), 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.

Each key is yielded as a clone (K <: Clone), as HashMapKeys does: the entry list keeps its own (B8). 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)

OrderedMapValues type-function
fn(K : Type, V : Type) -> Type

Iterator over the values of an OrderedMap in insertion order.

Type Parameters

NameTypeNotes
KTypecomptime
VTypecomptime

Trait Implementations

impl(generic(T : Type), where(T <: Clone), T : (Clone))
impl(generic(T : Type), where(T <: Clone), T : (Clone), CloneInto)
clone_into : fn(self : &Self, dst : *(Self)) -> unit

Write a clone of self into the uninitialized slot dst, which has room for size_of_val(self) bytes at align_of_val(self).

Parameters

NameTypeNotes
selfSelf
dst*(Self)

Returns: unit

impl(generic(K : Type, V : Type), where(K <: (Eq(K), Hash), V <: Clone), 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 clone (V <: Clone) read off the entry list.

Returns: Option(V)

OrderedMapIter type-function
fn(K : Type, V : Type) -> Type

Iterator over (key, value) pairs of an OrderedMap in insertion order.

Type Parameters

NameTypeNotes
KTypecomptime
VTypecomptime

Trait Implementations

impl(generic(T : Type), where(T <: Clone), T : (Clone))
impl(generic(T : Type), where(T <: Clone), T : (Clone), CloneInto)
clone_into : fn(self : &Self, dst : *(Self)) -> unit

Write a clone of self into the uninitialized slot dst, which has room for size_of_val(self) bytes at align_of_val(self).

Parameters

NameTypeNotes
selfSelf
dst*(Self)

Returns: unit

impl(generic(K : Type, V : Type), where(K <: (Eq(K), Hash, Clone), V <: Clone), OrderedMapIter(K, V), Iterator(...))
Item : MapEntry(K, V)
next : (fn(self : &mut Self) -> Option(MapEntry(K, V)))

Advance the iterator and return the next value, or None when exhausted.

Returns: Option(MapEntry(K, V))

OrderedMapIterPtr type-function
fn(K : Type, V : Type) -> Type

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

NameTypeNotes
KTypecomptime
VTypecomptime

Trait Implementations

impl(generic(T : Type), where(T <: Clone), T : (Clone))
impl(generic(T : Type), where(T <: Clone), T : (Clone), CloneInto)
clone_into : fn(self : &Self, dst : *(Self)) -> unit

Write a clone of self into the uninitialized slot dst, which has room for size_of_val(self) bytes at align_of_val(self).

Parameters

NameTypeNotes
selfSelf
dst*(Self)

Returns: unit

impl(generic(K : Type, V : Type), where(K <: (Eq(K), Hash)), OrderedMapIterPtr(K, V), Iterator(...))
Item : *MapEntry(K, V)
next : (fn(self : &mut Self) -> Option(*MapEntry(K, V)))

Advance the iterator and return the next value, or None when exhausted.

Returns: Option(*MapEntry(K, V))

OrderedMapCursor type-function
fn(K : Type, V : Type, p : Origin) -> Type

The shared walk over a OrderedMap (Rust's indexmap::Iter<'a, K, V>): a &(OrderedMap(K, V), p) lend and a position, yielding each entry as (&(K, p), &(V, p)). Binding the cursor freezes the map for its life (E0911 on a write), which is what makes the borrowed for(&map, (k, v) => body) lower to the value form over (&map).into_iter().

Type Parameters

NameTypeNotes
KTypecomptime
VTypecomptime
pOrigincomptime

Trait Implementations

impl(generic(T : Type), where(T <: Clone), T : (Clone))
impl(generic(T : Type), where(T <: Clone), T : (Clone), CloneInto)
clone_into : fn(self : &Self, dst : *(Self)) -> unit

Write a clone of self into the uninitialized slot dst, which has room for size_of_val(self) bytes at align_of_val(self).

Parameters

NameTypeNotes
selfSelf
dst*(Self)

Returns: unit

impl(generic(K : Type, V : Type, p : Origin), where(K <: (Eq(K), Hash)), OrderedMapCursor(K, V, p), Iterator(...))
Item : Tuple(&(K, p), &(V, p))
next : (fn(self : &mut Self) -> Option(Tuple(&(K, p), &(V, p))))

Advance the iterator and return the next value, or None when exhausted.

Returns: Option(Tuple(&(K, p), &(V, p)))

OrderedMapCursorMut type-function
fn(K : Type, V : Type, p : Origin) -> Type

The write walk over a OrderedMap (Rust's indexmap::IterMut<'a, K, V>): a &mut(OrderedMap(K, V), p) lend and a position, yielding each entry as (&(K, p), &mut(V, p)): the key is read-only (a written key would break the map's order), the value is writable. The map is frozen exclusively while the cursor lives.

Type Parameters

NameTypeNotes
KTypecomptime
VTypecomptime
pOrigincomptime

Trait Implementations

impl(generic(T : Type), where(T <: Clone), T : (Clone))
impl(generic(T : Type), where(T <: Clone), T : (Clone), CloneInto)
clone_into : fn(self : &Self, dst : *(Self)) -> unit

Write a clone of self into the uninitialized slot dst, which has room for size_of_val(self) bytes at align_of_val(self).

Parameters

NameTypeNotes
selfSelf
dst*(Self)

Returns: unit

impl(generic(K : Type, V : Type, p : Origin), where(K <: (Eq(K), Hash)), OrderedMapCursorMut(K, V, p), Iterator(...))
Item : Tuple(&(K, p), &mut(V, p))
next : (fn(self : &mut Self) -> Option(Tuple(&(K, p), &mut(V, p))))

Advance the iterator and return the next value, or None when exhausted.

Returns: Option(Tuple(&(K, p), &mut(V, p)))