std.vector and the generic std.map

The standard library ships two generic collections: std.vector, a growable array, and std.map, a hash map generic over both its key type and its value type. Both are written in Dusk itself; the sources are lib/std/vector.dusk and lib/std/map.dusk in the repository.

Both collections follow the same shape: the struct holds heap buffers that double when they fill, so you pass the collection by pointer so growth persists across calls. The usual pattern is to build one on the heap with alloc(...) and release it in two steps: the module’s *_free function frees the backing buffers, then free releases the struct itself. See /stdlib/memory/ for the allocation builtins these sit on.

std.vector

@import std.vector

A growable array, generic over its element type T. The buffer lives on the heap and doubles when it fills, so appends are amortized constant time. Element access is bounds checked, and the raw buffer never escapes the module.

export struct Vector<T> {
    data: *raw T,
    len: int64,
    cap: int64,
}

Functions

Function	Description
vec_new<T>() -> Vector<T>	A new empty vector.
vec_push<T>(v: *Vector<T>, x: T) -> void	Append one element, growing if needed.
vec_pop<T>(v: *Vector<T>) -> void	Drop the last element; a no-op when empty.
vec_get<T>(v: *Vector<T>, i: int64) -> T	The element at index i, bounds checked.
vec_set<T>(v: *Vector<T>, i: int64, x: T) -> void	Overwrite the element at index i, bounds checked.
vec_len<T>(v: *Vector<T>) -> int64	The element count.
vec_sort<T>(v: *Vector<T>, cmp: (T, T) -> int32) -> void	Sort in place behind a comparator.
vec_contains<T>(v: *Vector<T>, x: T) -> bool	True when x appears anywhere in the vector.
vec_index_of<T>(v: *Vector<T>, x: T) -> int64	The index of the first element equal to x, or -1.
vec_take<T>(v: *Vector<T>, i: int64) -> T	Remove the element at i, shift the rest down, and return it as an owned value.
vec_map<T, U>(v: *Vector<T>, f: (T) -> U) -> *Vector<U>	A fresh vector of f applied to each element in order.
vec_filter<T>(v: *Vector<T>, p: (T) -> bool) -> *Vector<T>	A fresh vector of the elements p keeps.
vec_fold<T, U>(v: *Vector<T>, init: U, f: (U, T) -> U) -> U	Reduce to a single value, folding f left to right from init.
vec_free<T>(v: *Vector<T>) -> void	Free the backing buffer.

Capacity starts at 4 on the first push and doubles from there. vec_get and vec_set both check that i is in 0..len; an out-of-range index prints fatal: vector index out of bounds and aborts the program.

vec_set, added in 0.7.0, writes x into the slot at i, overwriting whatever was there and leaving the length and the capacity where they are. The bound it checks is the length, not the capacity, so it only ever overwrites a slot a push already filled. Setting at len aborts even when the buffer still has room to spare, because growing the vector is vec_push’s job and vec_set never does it on your behalf; a negative index aborts the same way. It went in for the compiler’s own AST arenas, which append a node and then patch its slot once the rest of the parse resolves.

vec_pop, added in 1.2.0, drops the last element by decrementing the length. It never touches the backing buffer, so the popped slot is simply forgotten and the capacity stays put. On an empty vector it does nothing: the length is already zero, so there is no underflow.

Example

vector_basics.dusk

@paradigm procedural

@import std.vector

func main() -> int32 {
    v: *Vector<int64> = alloc(vec_new())
    mut i: int64 = 0
    while i < 5 {
        vec_push(v, i * 10)
        i = i + 1
    }
    println(vec_len(v))      // 5
    println(vec_get(v, 2))   // 20
    vec_set(v, 2, 99)
    println(vec_get(v, 2))   // 99
    println(vec_len(v))      // 5, a set never grows the vector
    vec_free(v)
    free(v)
    return 0
}

The while loop and mut require the procedural paradigm. See /reference/paradigm-system/.

Iterating with for

Since 1.11.0 a for loop iterates a vector directly, for x in v binding each element in index order, so the index-and-vec_get loop above has a shorter spelling:

vector_for.dusk

@paradigm procedural

@import std.vector

func main() -> int32 {
    v: *Vector<int64> = alloc(vec_new())
    mut i: int64 = 0
    while i < 5 {
        vec_push(v, i * 10)
        i = i + 1
    }
    mut sum: int64 = 0
    for x in v {                 // x is each element, 0, 10, 20, 30, 40
        sum = sum + x
    }
    println(sum)                 // 100
    vec_free(v)
    free(v)
    return 0
}

The iterand must be a pointer, so a plain for x in v needs v: *Vector<T>; iterating a container by value is rejected, iterate the container through a pointer, as in v: *Vector<T>. The loop is not a builtin, and code generation never learns the vector’s layout: a pass before monomorphization rewrites for x in v into the exact vec_len and vec_get index loop you would write by hand, re-reading the length every iteration. That re-read makes it safer than a snapshot, since a vector freed inside the body faults at the next iteration’s generation check rather than reading a stale pointer. The binder x is a borrow the vector still owns, exactly like a vec_get read: mutating through a managed element is fine, but freeing or moving x is rejected, cannot free a borrowed pointer; only its owner frees it. The binder is typed from the element, so a narrowing bind like y: int32 = x over an int64 element is a check error rather than a silent truncation. To drain and free, take with vec_take instead (see below). for, break, and continue require the procedural paradigm.

vec_pop shortens the vector from the back, and popping past empty is safe:

vector_pop.dusk

@paradigm procedural

@import std.vector

func main() -> int32 {
    v: *Vector<int64> = alloc(vec_new())
    vec_push(v, 10)
    vec_push(v, 20)
    vec_push(v, 30)
    vec_pop(v)
    println(vec_len(v))      // 2
    println(vec_get(v, 1))   // 20
    vec_pop(v)
    vec_pop(v)
    vec_pop(v)               // no-op on empty, no underflow
    println(vec_len(v))      // 0
    vec_free(v)
    free(v)
    return 0
}

Sorting

vec_sort, added in 1.4.2, sorts the vector in place behind cmp, an ordering closure that returns a negative int32 when its first argument sorts before its second, zero when the two compare equal, and a positive value when the first sorts after. Underneath it is a bottom up merge sort: passes double a run width from 1 up past the length, merging adjacent runs through a scratch buffer sized to the vector.

Two properties are worth relying on. The sort is stable, so a tie always favors the earlier run and equal elements come out in the order they went in, which lets you sort by one key and then sort again by another without the second pass scrambling the first. It is also deterministic, so two calls over the same data and the same cmp always produce the same order. A vector of fewer than two elements returns immediately with cmp never called.

vector_sort.dusk

@paradigm procedural

@import std.vector

struct Score {
    name: string,
    points: int32,
}

func by_points(a: Score, b: Score) -> int32 {
    return a.points - b.points
}

func main() -> int32 {
    v: *Vector<Score> = alloc(vec_new())
    vec_push(v, Score { name: "ada", points: 2 })
    vec_push(v, Score { name: "bo", points: 1 })
    vec_push(v, Score { name: "cy", points: 2 })
    vec_push(v, Score { name: "di", points: 1 })
    vec_sort(v, by_points)
    mut i: int64 = 0
    while i < vec_len(v) {
        s: Score = vec_get(v, i)
        print(s.points)
        print(" ")
        println(s.name)
        i = i + 1
    }
    vec_free(v)
    free(v)
    return 0
}

Stability is what makes that output predictable. bo and di both score 1, and bo stays ahead of di because it was pushed first. The comparator here is a named top level function, but a capture free lambda literal works in the same position.

Searching

vec_contains and vec_index_of, also added in 1.4.2, are a linear scan comparing each element to x with ==. vec_index_of hands back the index of the first match, or -1 when nothing matches.

Because they compare with ==, they are legal only for a T that == itself accepts, which means a scalar or a string. Dusk does not compare pointers, so a Vector<T> of a pointer typed T rejects both functions once the type is ground, the same way any other illegal == is rejected; compare the values behind the pointers instead. A string element compares by content, so a match does not depend on two equal strings sharing an address.

vector_search.dusk

@paradigm procedural

@import std.vector

func main() -> int32 {
    v: *Vector<string> = alloc(vec_new())
    vec_push(v, "ada")
    vec_push(v, "bo")
    vec_push(v, "cy")
    if vec_contains(v, "bo") {
        println("bo is in there")
    }
    println(vec_index_of(v, "cy"))    // 2
    println(vec_index_of(v, "zed"))   // -1
    vec_free(v)
    free(v)
    return 0
}

Taking an element out

vec_take, added in 1.8.0, removes the element at index i, shifts every survivor after it down one slot so the order is preserved, shortens the vector, and hands you the removed element as an owned value. That last word is the point. Where vec_get reads an element as a borrow, vec_take transfers it, so a taken managed pointer is yours to free, and the vector no longer holds a copy the free would collide with. It bounds checks exactly as vec_get: a negative index or one at or past the length aborts with fatal: vector index out of bounds.

Taking the last index shifts nothing, so draining from the back is constant time per step:

while vec_len(v) > 0 {
    x := vec_take(v, vec_len(v) - 1)
    free(x)                             // x is yours; the vector let it go
}

That is the idiom to reach for, and it is safer than it looks. A forward walk over a vector you are taking from skips the successor that shifts into each vacated slot, so take from the back, where nothing shifts, or index with the shift in mind. See owning removal from a container for why a plain free(vec_get(v, 0)) is rejected and vec_take is the sanctioned path.

Mapping and filtering

vec_map and vec_filter, added in 1.8.1, each build a fresh vector and leave the source untouched, calling the closure exactly once per element in index order. vec_map applies f to every element and infers the result vector’s type from what f returns, so a Vector<int64> mapped through a (int64) -> string comes back a Vector<string>. vec_filter copies through the elements its predicate keeps and drops the rest. Both take a capturing lambda or a named top level function, the same two shapes vec_sort accepts, and neither is paradigm gated. There is no separate vec_sort_by, since vec_sort already takes its comparator as a closure.

vector_map_filter.dusk

@paradigm procedural
@paradigm functional

@import std.vector

func main() -> int32 {
    v: *Vector<int64> = alloc(vec_new())
    mut i: int64 = 1
    while i <= 6 {
        vec_push(v, i)
        i = i + 1
    }
    evens: *Vector<int64> = vec_filter(v, lambda (x: int64) -> bool { return x % 2 == 0 })
    doubled: *Vector<int64> = vec_map(evens, lambda (x: int64) -> int64 { return x * 2 })
    mut j: int64 = 0
    while j < vec_len(doubled) {
        println(vec_get(doubled, j))    // 4, then 8, then 12
        j = j + 1
    }
    vec_free(doubled)
    free(doubled)
    vec_free(evens)
    free(evens)
    vec_free(v)
    free(v)
    return 0
}

Both results are fresh vectors you own and free with vec_free plus free, independently of the source. One sharp edge rides on vec_filter when the elements are managed pointers: the kept elements are copied, so the same pointer now sits in both vectors, and freeing it through one leaves the other holding a stale copy. The checker does not catch that aliasing across the call, so the generational check faults at the second free rather than at compile time. Filter a vector of pointers only when you will free through exactly one of the two vectors, or store indices rather than the pointers themselves. The lambda literals above need the functional paradigm; a named comparator or mapper does not.

Folding

vec_fold, added in 1.9.1, reduces a vector to a single value. It folds f left to right over the elements from init, passing the running accumulator as f’s first argument and the current element as its second, and each call’s result becomes the next accumulator. The final accumulator is returned, an empty vector returns init with f never called, and the source is neither mutated nor freed. The accumulator type is independent of the element type, so a Vector<int64> folds into an int64 sum, a string, or a structure you build up.

vector_fold.dusk

@paradigm procedural
@paradigm functional

@import std.vector

func main() -> int32 {
    v: *Vector<int64> = alloc(vec_new())
    mut i: int64 = 1
    while i <= 5 {
        vec_push(v, i)
        i = i + 1
    }
    sum := vec_fold(v, 0, lambda (acc: int64, x: int64) -> int64 { return acc + x })
    println(sum)      // 15
    vec_free(v)
    free(v)
    return 0
}

It closes the fold slot beside vec_map and vec_filter, so the three higher order helpers now cover map, filter, and reduce over a vector.

std.map

@import std.map

A hash map generic over both its key type K and its value type V. It uses open addressing with linear probing over heap buffers that double and rehash once the table is half full, which keeps an empty slot reachable so a probe always terminates.

Through 1.5.1 the map was Map<V>, keyed by strings alone. Since 1.5.2 it is Map<K, V>, and every old Map<V> spelling is now written Map<string, V>. No call site changed in the migration: map_new() and every accessor infer K and V from the annotated binding or from the map argument, so only your type annotations need the second parameter.

export struct Map<K, V> {
    used: *raw bool,
    keys: *raw K,
    vals: *raw V,
    len: int64,
    cap: int64,
    order: *Vector<K>,
}

What a key may be

K must be hashable, which is the set the hash builtin accepts: an integer of any width, a char, a rune, or a string. A key hashes through hash and compares with ==, so a string key hashes and compares by its content, byte for byte, exactly as it did before the map went generic, and a scalar key by its value.

Anything else is refused by name once the key type is ground, cannot hash 'Point'; a map key is an integer, char, rune, or string. A struct and a pointer are out, and so is a float: a NaN is never equal to itself, which would break the coherence between the hash and the equality the map compares keys by, so a float cannot be a key at all.

The map stores keys by value. A string key is still the caller’s own pointer and must outlive the map, exactly the contract the map carried back when strings were the only key it took, while a scalar key carries no lifetime at all.

Functions

Function	Description
map_new<K, V>() -> Map<K, V>	A new empty map.
map_put<K, V>(m: *Map<K, V>, k: K, v: V) -> void	Insert the value, or overwrite the key.
map_get<K, V>(m: *Map<K, V>, k: K) -> Maybe<V>	The value for a key, or None when absent.
map_has<K, V>(m: *Map<K, V>, k: K) -> bool	True when the key is present.
map_remove<K, V>(m: *Map<K, V>, k: K) -> bool	Delete the key, true when one was there.
map_take<K, V>(m: *Map<K, V>, k: K) -> V	Remove the key and hand back its value as an owned value; aborts on a missing key.
map_keys<K, V>(m: *Map<K, V>) -> *Vector<K>	The keys in insertion order, as a fresh vector you own.
map_key_at<K, V>(m: *Map<K, V>, i: int64) -> K	The key at insertion-order position i, allocation free.
map_val_at<K, V>(m: *Map<K, V>, i: int64) -> V	The value at insertion-order position i, allocation free.
map_len<K, V>(m: *Map<K, V>) -> int64	The entry count.
map_free<K, V>(m: *Map<K, V>) -> void	Free the backing buffers.
map_hash(s: string) -> int64	The old string hash, a thin wrapper over hash.

Capacity starts at 8 and doubles each time the map fills to half. map_put on an existing key overwrites the value and does not change map_len. map_free releases the map’s buffers but not the key strings, which the caller still owns.

map_hash now just calls hash on the string you give it and returns the result, kept exported under its old name for one release so an outside caller keeps working. Reach for hash directly in new code. The result may be negative, since the hash overflows and wraps; the map folds a negative index back into range internally.

map_keys returns the keys in the order they were first inserted, copied into a fresh vector that you own and free with vec_free plus free. The map keeps its own order record, so freeing the returned vector never touches the map. A key is recorded once, at its first insertion, so an overwrite does not move it and a grow rehashes the table without disturbing the order.

map_key_at and map_val_at, added in 1.11.0, read the i-th key and value in that same insertion order straight from the map’s own record, allocation free, where map_keys copies the whole key set into a vector. They are what the for k, v in m loop below lowers onto, and they are handy on their own for a positional walk that wants a single entry without building the key vector.

Iterating a map with for

Since 1.11.0 a for loop iterates a map directly, in the map’s documented insertion order. for k in m binds each key, and for k, v in m binds each key with its value:

map_for.dusk

@paradigm procedural

@import std.map

func main() -> int32 {
    m: *Map<string, int64> = alloc(map_new())
    map_put(m, "one", 1)
    map_put(m, "two", 2)
    map_put(m, "three", 3)
    for k, v in m {              // insertion order: one 1, two 2, three 3
        print(k)
        print(" ")
        println(v)
    }
    map_free(m)
    free(m)
    return 0
}

As with the vector, the iterand must be a *Map<K, V> pointer, and the loop lowers before monomorphization into a map_len count with map_key_at and map_val_at reads, so map layout stays in the library. The pair form is map only: two binders over any other iterand is rejected, two loop names bind a map's key and value; this iterand has only elements. Both k and v are borrows the map still owns, so freeing or moving a bound key or value is rejected; drain with map_take when you mean to reclaim. The order is stable across overwrites, removes, and the rehash a grow performs, exactly the contract map_keys documents.

Taking a value out

map_take, added in 1.8.0, is map_remove’s owning twin. It probes for the key, removes its entry with the same slot clear, cluster repair, and insertion-order forget that map_remove performs, and returns the stored value as an owned value rather than a borrow, so a taken managed pointer is yours to free. A missing key is a misuse, not a Maybe: map_take aborts with fatal: map_take of a missing key, so guard it with map_has first.

It frees nothing, ever. Not the value’s block, which it just handed you, and not the key’s heap bytes, which belong to whoever else holds that string. Removal and reclamation stay separate acts: map_take performs the removal and returns the owner, and you decide when the value dies. See owning removal from a container for the model these two takes settle.

Example

map_get returns a Maybe<V> from /stdlib/functional/, so import std.functional.maybe to work with the result.

map_basics.dusk

@paradigm procedural

@import std.map
@import std.functional.maybe

func main() -> int32 {
    m: *Map<string, int64> = alloc(map_new())
    map_put(m, "one", 1)
    map_put(m, "two", 2)
    map_put(m, "two", 22)                     // overwrites, len stays 2
    println(map_len(m))                       // 2
    println(unwrap_or(map_get(m, "two"), 0))  // 22
    println(unwrap_or(map_get(m, "ten"), 0))  // 0
    if map_has(m, "one") {
        println("one is present")
    }
    map_free(m)
    free(m)
    return 0
}

The annotation on m is what pins K and V; map_new() takes no arguments to infer them from. Every call below it reads both parameters off the map you hand it.

Instead of unwrap_or, you can match on the result directly.

map_match.dusk

@paradigm procedural

@import std.map
@import std.functional.maybe

func main() -> int32 {
    m: *Map<string, string> = alloc(map_new())
    map_put(m, "lang", "dusk")
    match map_get(m, "lang") {
        Some(v) => println(v),
        None => println("missing"),
    }
    map_free(m)
    free(m)
    return 0
}

Keys that are not strings

An integer key is the headline of 1.5.2. Nothing about the calls changes; the key type moves into the annotation and the rest follows. This one also removes a key and walks what is left in insertion order.

map_int_keys.dusk

@paradigm procedural

@import std.map
@import std.vector
@import std.functional.maybe

func main() -> int32 {
    m: *Map<int64, string> = alloc(map_new())
    map_put(m, 0, "zero")
    map_put(m, 8, "eight")
    map_put(m, 16, "sixteen")                  // 0, 8, and 16 all probe to slot 0
    println(unwrap_or(map_get(m, 8), "?"))     // eight
    println(unwrap_or(map_get(m, 16), "?"))    // sixteen
    map_remove(m, 8)
    println(unwrap_or(map_get(m, 16), "?"))    // sixteen, the probe chain still holds
    println(map_len(m))                        // 2
    ks: *Vector<int64> = map_keys(m)
    mut i: int64 = 0
    while i < vec_len(ks) {
        println(vec_get(ks, i))                // 0 then 16, insertion order
        i = i + 1
    }
    vec_free(ks)
    free(ks)
    map_free(m)
    free(m)
    return 0
}

0, 8, and 16 all hash to slot 0 in a table of capacity 8, so they collide and the probe walks past each other. Removing 8 from the middle of that chain still leaves 16 findable, because map_remove backshifts the rest of the chain rather than leaving a hole in it.

A char and a rune key work the same way, hashing by value:

map_char_keys.dusk

@paradigm procedural

@import std.map
@import std.functional.maybe

func main() -> int32 {
    mc: *Map<char, int64> = alloc(map_new())
    a: char = 65
    map_put(mc, a, 1)
    println(unwrap_or(map_get(mc, a), 0))         // 1
    mr: *Map<rune, string> = alloc(map_new())
    snow: rune = 9731
    map_put(mr, snow, "snowman")
    println(unwrap_or(map_get(mr, snow), "?"))    // snowman
    map_free(mc)
    free(mc)
    map_free(mr)
    free(mr)
    return 0
}

A map in a struct field, and the rebind it needs

There is one rough edge worth knowing before you hit it. The mono pass resolves a field’s type only for a generic struct, and K no longer appears in map_get’s return type for an expected type to pin it from. So a map held in a field of a plain struct does not always pin K, and you get cannot infer the type parameter 'K' on a call that looks like it has everything it needs.

The fix is one local rebind that hands the inference a binding with the full type spelled on it. The compiler’s own codegen needed exactly this at six call sites, each written slocals: *Map<string, LocalVal> = (*s).locals. A general fix is an inference improvement deferred to a later release.

map_in_struct.dusk

@paradigm procedural

@import std.map
@import std.functional.maybe

struct Scope {
    locals: *Map<string, int64>,
}

func lookup(s: *Scope, name: string) -> int64 {
    // The rebind pins K for the read below. Without it, map_get nested
    // directly inside unwrap_or has nothing to infer K from.
    slocals: *Map<string, int64> = (*s).locals
    return unwrap_or(map_get(slocals, name), -1)
}

func main() -> int32 {
    // Same story on the way in: Scope is a plain struct, so its field does
    // not pin map_new. Build the map on its own annotated binding first,
    // rather than inline as Scope { locals: alloc(map_new()) }.
    locals: *Map<string, int64> = alloc(map_new())
    s: *Scope = alloc(Scope { locals: locals })
    map_put(locals, "x", 7)
    println(lookup(s, "x"))       // 7
    println(lookup(s, "nope"))    // -1
    map_free(locals)
    free(locals)
    free(s)
    return 0
}

A generic struct does not need the rebind, since the mono pass resolves its fields; a plain struct like Scope above is the case that does.

Ownership summary

• Both collections own their heap buffers. vec_free and map_free release the buffers only. map_free also releases the map’s internal insertion order record, which you never touch directly.
• A collection built on the heap with alloc(...) needs a second free for the struct itself, as in the examples above.
• The map does not copy or free a string key; the caller keeps ownership of it, and it must outlive the map. A scalar key, an integer or a char or a rune, is stored by value and carries no lifetime.
• A vector handed back by map_keys, vec_map, or vec_filter is yours: free it with vec_free plus free, independently of the source. vec_fold returns a plain value, not a container.
• A for binder over a container is a borrow the container still owns, the same as a vec_get, map_key_at, or map_val_at read: mutate through it, but do not free or move it. To reclaim, drain with vec_take or map_take.
• vec_take and map_take transfer ownership of the element they remove, so a taken managed pointer is yours to free; the container no longer holds it. map_take never frees the key’s bytes, which the caller still owns. A vec_filter over managed pointer elements aliases them into both vectors, so free through only one.

For the rest of the standard library, see /stdlib/overview/.