std.set

std.set is Set<T>, an unordered set generic over its element type, added in 1.8.1 and built over std.map. The source is lib/std/set.dusk in the repository, and like the map it wraps, it is written in Dusk itself with no new compiler surface behind it.

@import std.set

A set holds each of its elements at most once and answers one question well: is this element a member. It carries no values and keeps no user-visible order beyond the order you inserted in, so reach for it when what you need is presence rather than a mapping.

The set as a map

A Set<T> is a thin wrap over a Map<T, bool> keyed by the element, with a bool value that is always true.

export struct Set<T> {
    m: *Map<T, bool>,
}

The map maps each present element to true, and that value is a placeholder that carries no information: presence is the whole of membership, so the bool never needs to be read. The set owns the map allocation, and set_free releases it.

Two things follow from the wrap being a real type rather than an alias for the map. First, a *Set<string> parameter cannot take a *Map<string, bool> by mistake, because the two are distinct types even though one is built from the other. Second, the wrap seals the value channel: there is no function that puts a value other than true, so membership is exactly key presence and there is no way to hold an element that is present but false. Add an element and it is a member; remove it and it is not.

Functions

Function	Description
`set_new<T>() -> Set<T>`	A new empty set.
`set_add<T>(s: *Set<T>, x: T) -> bool`	Add an element; `true` when it was newly added.
`set_has<T>(s: *Set<T>, x: T) -> bool`	True when the element is present.
`set_remove<T>(s: *Set<T>, x: T) -> bool`	Remove an element; `true` when it was there.
`set_len<T>(s: *Set<T>) -> int64`	The member count.
`set_items<T>(s: Set<T>) -> Vector<T>`	The members in first-insertion order, as a fresh vector you own.
`set_free<T>(s: *Set<T>) -> void`	Free the backing map.

Build a set on the heap with alloc(set_new()) and pass it by pointer so inserts persist across calls, the same shape std.map uses.

set_add and set_remove both report whether the call changed the set. set_add probes membership first and returns true only when x was not already there, so a repeat of an existing element neither grows the set nor disturbs its first-insertion order; a repeat returns false and leaves everything as it was. set_remove returns true when x was a member before the call and false when it was not there to begin with. That return is how you tell an add or a remove that did work from one that was already a no-op, without a second set_has to check.

set_items hands back the members in the order they were first inserted, copied into a fresh Vector<T> that you own and free with vec_free plus free. The vector is independent of the set: it is copied out of the backing map’s own order record, so freeing it never touches the set and set_free never touches it. For a string element the copy is the same borrowed string the set holds, so freeing the returned vector releases its own backing buffer only and never the element strings.

What an element may be

The element contract is the map key contract verbatim. T must be hashable, which is the set the hash builtin accepts: an integer of any width, a char, a rune, or a string. An element hashes through hash and compares with ==, so a string element hashes and compares by its content, byte for byte, and a scalar element by its value.

The set stores its elements by value. A string element is still the caller’s own pointer and must outlive the set, exactly the contract the map carries for a string key, while a scalar element carries no lifetime at all. set_free never frees the elements, only the backing map.

A pointer element is refused. A Set<*Json>, for one, is rejected once the type is ground, through the backing map’s hash and == restriction rather than anything the set adds, so the diagnostic locates inside map.dusk: cannot hash a managed pointer; a map key is an integer, char, rune, or string. If you need a set of things behind pointers, key it on a scalar or string derived from each one instead, and keep the pointers elsewhere.

Example

This builds a *Set<string>, adds a few names with one duplicate that reports false, tests membership, removes one, and walks the members in first-insertion order before releasing everything.

@paradigm procedural

@import std.set
@import std.vector

func main() -> int32 {
    s: *Set<string> = alloc(set_new())
    println(set_add(s, "ada"))       // true, newly added
    println(set_add(s, "bo"))        // true
    println(set_add(s, "cy"))        // true
    println(set_add(s, "bo"))        // false, "bo" is already present
    println(set_len(s))              // 3, the repeat neither grew it nor moved "bo"

    if set_has(s, "ada") {
        println("ada is a member")   // ada is a member
    }

    println(set_remove(s, "bo"))     // true, "bo" was a member
    println(set_remove(s, "bo"))     // false, it is gone now
    println(set_len(s))              // 2

    items: *Vector<string> = set_items(s)
    mut i: int64 = 0
    while i < vec_len(items) {
        println(vec_get(items, i))   // ada then cy, first-insertion order
        i = i + 1
    }
    vec_free(items)
    free(items)

    set_free(s)
    free(s)
    return 0
}

The two-step alloc then set_free plus free is the same allocation shape the vector and map use: set_free releases the backing map, and free releases the Set struct itself. The while loop and mut require the procedural paradigm; see /reference/paradigm-system/. The walk prints ada then cy, because the members come back in the order they were first inserted and bo, which was removed, no longer appears.

Ownership summary

The set owns its backing map. set_free releases that map and nothing else: the elements are borrowed, so none is freed here.
A set built on the heap with alloc(set_new()) needs a second free for the Set struct itself, after set_free, as in the example above.
The set does not copy or free a string element; the caller keeps ownership of it, and it must outlive the set. A scalar element, an integer or a char or a rune, is stored by value and carries no lifetime.
A vector handed back by set_items is yours: free it with vec_free plus free, independently of the set.

For the map this is built on, see std.map. For the rest of the standard library, see /stdlib/overview/.