SortedMap

1 min read

Import: import system.collections;

Read the usage guide for examples and common tasks. This reference lists the public declarations for this part of the library. See Reading API signatures for parameter and result notation.

SortedMap

An ordered map backed by parallel sorted arrays (binary search + shift on insert/remove). O(log n) lookup, O(n) insert/remove, ascending-key iteration. Prefer Map<K, V> when key order doesn't matter — it has O(1) average insert/lookup.

public class SortedMap<K: Comparable<K>, V>

constructor

Allocates an empty sorted map with an initial capacity (defaults to 8).

public constructor(capacity: int = 8)

length

Number of key/value pairs currently stored.

public get length(): int

is_empty

True when the map is empty.

public fun is_empty(): bool

clear

Removes every entry, keeping capacity. Live slots are overwritten with a zero value so reference keys/values release immediately.

public fun clear(): void

this

Inserts or updates the value for a key. O(log n) to locate, O(n) worst case to shift.

public fun this[key: K] = value: V

get

Value for key, or None when the key is absent.

public fun get(borrow key: K): Option<V>

this

Value for key. Panics when the key is absent — this is what sm[k] compiles to; use get(k) for absence-tolerant reads.

public fun this[borrow key: K]: V

contains

True if the map contains the key.

public fun contains(borrow key: K): bool

remove

Removes a key and returns true if it was present.

public fun remove(borrow key: K): bool

first_key

The smallest key, or None when empty.

public fun first_key(): Option<K>

last_key

The largest key, or None when empty.

public fun last_key(): Option<K>

ceiling_key

The smallest key >= key, or None if every key is smaller.

public fun ceiling_key(borrow key: K): Option<K>

floor_key

The largest key <= key, or None if every key is larger.

public fun floor_key(borrow key: K): Option<K>

keys

Returns a new list of the keys in ascending order.

public fun keys(): List<K>

values

Returns a new list of the values, ordered by ascending key.

public fun values(): List<V>

iterator

Gets an iterator over entries in ascending key order.

public fun iterator(): SortedMapIterator<K, V>