HashSet

Module std.collections

import std.collections;

Public declaration contracts and authored examples. A page can document several related symbols. Implementation bodies are excluded.

pub final class HashSet<K, P = HashPolicy<K>, A = DefaultAllocator>
    where K: Movable where P: HashKeyPolicy<K>, Movable
    where A: Allocator, Defaultable, Movable

Owns an allocator-aware set with immutable stored-key observations.

Exact probing, tombstone and allocation rollback semantics come from HashMap. Keys are never yielded writable; remove/reinsert to change a stored key. Structural mutation, move/destruction invalidate borrowed references/cursors. External synchronization and stable hash/equality results are required. K: Movable owned key type. P: Movable safe HashKeyPolicy, defaulting to stored safe functions. A: Movable Defaultable allocator owner.

Example

module example.hash_set;
from std.collections import HashPolicy, HashSet;
fn Hash(Key: readonly u64&) -> u64 { return Key; }
fn Equals(Left: readonly u64&, Right: readonly u64&) -> bool { return Left == Right; }
fn Main() -> i32 {
    var Values = HashSet<u64>(HashPolicy<u64>(Hash, Equals));
    if Values.TryReserve(4) is .Err { Error = _ } { return 1; }
    if Values.TryInsert(20) is .Err { Error = _ } { return 2; }
    if Values.TryInsert(22) is .Err { Error = _ } { return 3; }
    switch Values.TryInsert(20) {
        case .Ok { Value = Previous } => {
            if Previous is .None || Previous.Unwrap() != 20 { return 4; }
        }
        case .Err { Error = _ } => return 5;
    }
    if Values.Length != 2 || !Values.Contains(22) || Values.Find(20).Unwrap() != 20 { return 6; }
    {
        var Cursor = Values.CreateIterator();
        var Total: u64 = 0;
        while Cursor.Next() is .Some { Value = Key } { Total += Key; }
        if Total != 42 { return 7; }
    }
    if Values.Remove(20).Unwrap() != 20 || Values.Contains(20) { return 8; }
    if Values.TryCompact() is .Err { Error = _ } { return 9; }
    if Values.TryShrinkToFit() is .Err { Error = _ } { return 10; }
    var Moved = move(Values);
    if !Values.IsEmpty || Moved.Length != 1 { return 11; }
    Values = move(Moved);
    Values.Clear();
    return 0;
}

HashSet.init

pub init(mut Policy: P)

Creates an allocation-free set with a transferred key policy. Policy: Concrete safe key policy, transferred into the owner.

HashSet.init

pub init(mut Policy: P, mut AllocatorValue: A)

Creates an empty set with transferred policy and allocator owners. Policy: Concrete safe key policy. AllocatorValue: Allocator moved into exact map storage ownership.

HashSet.init

pub init(Source: readonly Self&) = delete;

Rejects copying set ownership. Source: Noncopy owner.

HashSet.init

pub init(Source: mut Self&&)

Transfers table/policy/allocator ownership, leaving the source empty. Source: Writable owner left destructible.

HashSet.operator

pub fn operator =(Source: readonly Self&) -> void = delete;

Rejects copying live ownership. Source: Noncopy owner. Return: No value; deleted.

HashSet.operator

pub fn operator =(Source: mut Self&&) -> void

Releases previous ownership and transfers another set. Source: Writable owner left empty; exact self-assignment is unchanged. Return: No value; map ownership preserves its self-assignment guard.

HashSet.Length

pub Length: usize;

Observes stored key count in O(1).

HashSet.Capacity

pub Capacity: usize;

Observes allocated bucket count in O(1).

HashSet.IsEmpty

pub IsEmpty: bool;

Observes logical emptiness in O(1).

HashSet.TryInsert

pub fn TryInsert(mut Key: K) -> Result<K?, HashSetInsertionError<K>>

Adopts a new key or replaces an equivalent stored key. Key: Owned input, adopted on success or retained by the failure. Return: Ok(none) for insertion, Ok(Some(old key)) for replacement, or failure owning Key. Warning: May allocate/rehash; structural mutation invalidates views.

HashSet.Contains

pub readonly fn Contains(Key: readonly K&) -> bool

Searches for key membership without allocating. Key: Readonly lookup input, not retained. Return: Whether an equivalent key is present; expected O(1), worst O(capacity).

HashSet.Find

pub readonly fn Find(Key: readonly K&) -> K&?

Borrows the stored equivalent key readonly. Key: Readonly lookup input, not retained. Return: Optional readonly stored-key reference, invalidated by structural mutation.

HashSet.Remove

pub fn Remove(Key: readonly K&) -> K?

Transfers and removes one stored key without allocating. Key: Readonly lookup input, not retained. Return: Owned removed key, or none if no equivalent key exists. Warning: Structural mutation invalidates references/cursors.

HashSet.CreateIterator

pub readonly fn CreateIterator() -> HashSetIterator<K>

Borrows readonly keys in unspecified bucket order. Return: Allocation-free cursor; complete traversal costs O(capacity). Warning: Structural mutation/move/destruction invalidates cursor and references.

HashSet.TryReserve

pub fn TryReserve(MinimumKeys: usize) -> Result<void, AllocationError>

Reserves bucket capacity for a total key count. MinimumKeys: Desired total live key capacity. Return: Ok or AllocationError; failure preserves keys. Warning: May allocate/rehash and invalidate views on success.

HashSet.TryCompact

pub fn TryCompact() -> Result<void, AllocationError>

Rebuilds current capacity to remove tombstones. Return: Ok or AllocationError; failure preserves keys. Warning: May allocate/rehash and invalidate views on success.

HashSet.TryShrinkToFit

pub fn TryShrinkToFit() -> Result<void, AllocationError>

Releases excess capacity without changing key membership. Return: Ok or AllocationError; failure preserves keys. Warning: May allocate/rehash and invalidate views on success.

HashSet.Clear

pub fn Clear() -> void

Destroys all stored keys while retaining capacity/policy. Return: No value; O(capacity) cleanup; invalidates all views.