std.map

open-addressed maps/sets and SortedMap, all in an Arena; no per-entry frees

ByteKey

pub ByteKey :: constraint($K)

keys whose bytes are their value: no floats, slices, unions or padding

AutoHashMap

pub AutoHashMap :: struct($K: ByteKey, $V: type) {
    region: *Arena,
    states: []u8,
    keys: []K,
    vals: []V,
    count: usize,
    tombs: usize,
}

keys hashed and compared by their raw bytes

• count: live entries
• tombs: tombstone slots (count toward the load factor)

AutoHashMap.len

pub len :: fn(self: *Self) -> usize

AutoHashMap.cap

pub cap :: fn(self: *Self) -> usize

AutoHashMap.is_empty

pub is_empty :: fn(self: *Self) -> bool

AutoHashMap.put

pub put :: fn(self: *Self, k: K, v: V)

overwrites; grows past 0.75 load (live + tombstones)

AutoHashMap.get

pub get :: fn(self: *Self, k: K) -> ?V

AutoHashMap.contains

pub contains :: fn(self: *Self, k: K) -> bool

AutoHashMap.remove

pub remove :: fn(self: *Self, k: K) -> bool

false if absent; leaves a tombstone

AutoHashMap.clear

pub clear :: fn(self: *Self)

keeps the tables for reuse

AutoHashMap.entries

pub entries :: fn(self: *Self) -> AutoEntries(K, V)

no particular order; put/remove while iterating may skip or repeat

Entry

pub Entry :: struct($K: type, $V: type) {
    key: K,
    value: V,
}

AutoEntries

pub AutoEntries :: struct($K: ByteKey, $V: type) {
    m: *AutoHashMap(K, V),
    i: usize,
}

AutoHashMap.entries iterator

• i: the next slot to look at

AutoEntries.next

pub next :: fn(self: *Self) -> ?Entry(K, V)

auto

pub auto :: fn($K: ByteKey, $V: type, a: *Arena) -> AutoHashMap(K, V)

empty map in a

StrMap

pub StrMap :: struct($V: type) {
    region: *Arena,
    states: []u8,
    keys: [][]const u8,
    vals: []V,
    count: usize,
    tombs: usize,
}

string keys by content; keys are copied into the arena

StrMap.len

pub len :: fn(self: *Self) -> usize

StrMap.cap

pub cap :: fn(self: *Self) -> usize

StrMap.is_empty

pub is_empty :: fn(self: *Self) -> bool

StrMap.put

pub put :: fn(self: *Self, k: []const u8, v: V)

StrMap.get

pub get :: fn(self: *Self, k: []const u8) -> ?V

StrMap.contains

pub contains :: fn(self: *Self, k: []const u8) -> bool

StrMap.remove

pub remove :: fn(self: *Self, k: []const u8) -> bool

StrMap.clear

pub clear :: fn(self: *Self)

StrMap.entries

pub entries :: fn(self: *Self) -> StrEntries(V)

no particular order; put/remove while iterating may skip or repeat

StrEntries

pub StrEntries :: struct($V: type) {
    m: *StrMap(V),
    i: usize,
}

StrMap.entries iterator; keys are the map’s own copies

StrEntries.next

pub next :: fn(self: *Self) -> ?Entry([]const u8, V)

strmap

pub strmap :: fn($V: type, a: *Arena) -> StrMap(V)

empty map in a

AutoSet

pub AutoSet :: struct($K: ByteKey) {
    m: AutoHashMap(K, u8),
}

AutoHashMap(K, u8) with nothing stored

AutoSet.len

pub len :: fn(self: *Self) -> usize

AutoSet.is_empty

pub is_empty :: fn(self: *Self) -> bool

AutoSet.contains

pub contains :: fn(self: *Self, k: K) -> bool

AutoSet.add

pub add :: fn(self: *Self, k: K) -> bool

true if newly added

AutoSet.remove

pub remove :: fn(self: *Self, k: K) -> bool

true if it was there

AutoSet.clear

pub clear :: fn(self: *Self)

AutoSet.each

pub each :: fn(self: *Self) -> AutoSetKeys(K)

no particular order

AutoSetKeys

pub AutoSetKeys :: struct($K: ByteKey) {
    it: AutoEntries(K, u8),
}

AutoSet.each iterator

AutoSetKeys.next

pub next :: fn(self: *Self) -> ?K

StrSet

pub StrSet :: struct {
    m: StrMap(u8),
}

strings by content; keeps its own copies

StrSet.len

pub len :: fn(self: *Self) -> usize

StrSet.is_empty

pub is_empty :: fn(self: *Self) -> bool

StrSet.contains

pub contains :: fn(self: *Self, k: []const u8) -> bool

StrSet.add

pub add :: fn(self: *Self, k: []const u8) -> bool

true if newly added

StrSet.remove

pub remove :: fn(self: *Self, k: []const u8) -> bool

true if it was there

StrSet.clear

pub clear :: fn(self: *Self)

StrSet.each

pub each :: fn(self: *Self) -> StrSetKeys

no particular order

StrSetKeys

pub StrSetKeys :: struct {
    it: StrEntries(u8),
}

StrSet.each iterator

StrSetKeys.next

pub next :: fn(self: *Self) -> ?[]const u8

autoset

pub autoset :: fn($K: ByteKey, a: *Arena) -> AutoSet(K)

empty set in a

strset

pub strset :: fn(a: *Arena) -> StrSet

empty set in a

SortedMap

pub SortedMap :: struct($K: type, $V: type, $C: type) {
    region: *Arena,
    keys: []K,
    vals: []V,
    count: usize,
    order: C,
}

sorted arrays in the arena; binary-search get, put/remove shift (fine to ~10k entries) C has less(self, a, b), like sort::Asc(K) or sort::By(K)

• keys: first count in use

SortedMap.len

pub len :: fn(self: *Self) -> usize

SortedMap.is_empty

pub is_empty :: fn(self: *Self) -> bool

SortedMap.put

pub put :: fn(self: *Self, k: K, v: V)

replaces an existing value

SortedMap.get

pub get :: fn(self: *Self, k: K) -> ?V

SortedMap.contains

pub contains :: fn(self: *Self, k: K) -> bool

SortedMap.remove

pub remove :: fn(self: *Self, k: K) -> bool

true if it was there

SortedMap.first

pub first :: fn(self: *Self) -> ?Entry(K, V)

smallest key; null if empty

SortedMap.last

pub last :: fn(self: *Self) -> ?Entry(K, V)

largest key; null if empty

SortedMap.entries

pub entries :: fn(self: *Self) -> SortedEntries(K, V, C)

smallest first; put/remove while iterating may skip or repeat

SortedMap.from

pub from :: fn(self: *Self, k: K) -> SortedEntries(K, V, C)

from the first key not before k

SortedMap.clear

pub clear :: fn(self: *Self)

SortedEntries

pub SortedEntries :: struct($K: type, $V: type, $C: type) {
    m: *SortedMap(K, V, C),
    i: usize,
}

SortedMap.entries/from iterator, key order

SortedEntries.next

pub next :: fn(self: *Self) -> ?Entry(K, V)

sorted_with

pub sorted_with :: fn($K: type, $V: type, $C: type, a: *Arena, order: C) -> SortedMap(K, V, C)

map in a ordered by order

sorted

pub sorted :: fn($K: type, $V: type, a: *Arena) -> SortedMap(K, V, sort::Asc(K))

keys ordered by <

sorted_by

pub sorted_by :: fn($K: type, $V: type, a: *Arena, less: fn(K, K) -> bool) -> SortedMap(K, V, sort::By(K))

keys ordered by less (mem::less_bytes for text)