Skip to content

SortedMap ​

SortedMap<K, V> is an ordered key → value map backed by a balanced binary search tree. It keeps every entry sorted by key. The native handle is released automatically when the binding goes out of scope.

Construction ​

SyntaxDescription
SortedMap<K, V>()Create a new empty ordered map

K can be any integer type, any float type, boolean, or string. V can be any type.

Methods ​

MethodSignatureReturnsDescription
set(K, V) => voidvoidInsert or replace the entry for key
get(K) => V?V?Value for key, or no value when absent
has(K) => booleanbooleanWhether key is present
delete(K) => booleanbooleanRemove the entry for key; returns true when it was present
min() => K?K?Smallest key, or no value when empty
max() => K?K?Largest key, or no value when empty
len() => usizeusizeNumber of entries
isEmpty() => booleanbooleanWhether the map is empty
clear() => voidvoidRemove all entries

Complexity ​

OperationTime Complexity
setO(log n)
get / hasO(log n)
deleteO(log n)
min / maxO(log n)
len / isEmptyO(1)
clearO(n)

The tree stays balanced, so every lookup, insertion and deletion is logarithmic regardless of insertion order.

Examples ​

Complete example ​

tyrus
import { SortedMap } from "tyrus:algorithm";

const main = (): void => {
    const m = SortedMap<i32, string>();
    m.set(3, "c");
    m.set(1, "a");
    m.set(2, "b");
    m.set(2, "B");

    print(m.len());            // 3 (the entry for key 2 was replaced)
    print(m.has(2));           // true
    print(m.get(2) ?? "none"); // "B"
    print(m.min() ?? 0);       // 1
    print(m.max() ?? 0);       // 3

    m.delete(2);
    print(m.has(2));           // false
    print(m.isEmpty());        // false

    m.clear();
    print(m.isEmpty());        // true
    print(m.len());            // 0
};

String keys ​

tyrus
import { SortedMap } from "tyrus:algorithm";

const main = (): void => {
    const m = SortedMap<string, i32>();
    m.set("banana", 2);
    m.set("apple", 1);
    m.set("cherry", 3);

    print(m.min() ?? "none");      // "apple"
    print(m.max() ?? "none");      // "cherry"
    print(m.get("apple") ?? 0);    // 1
};