Set

public struct Set[T, H = DefaultHasher] where T: Hashable, H: Hasher, H: Defaultable { /* private fields */ }

An unordered hash set of unique elements, parameterized over the hasher type H (defaults to DefaultHasher).

Backed by a Dictionary[T, Unit, H] — the dictionary's keys are the set's elements, and Unit fills the value slot. Inherits O(1) average-case lookup, insertion, and removal, plus copy-on-write storage from the underlying dictionary: copying a Set is O(1), with the deep clone deferred until either side mutates. Iteration order is unspecified. For ordered or associative-style storage, see Array[T] and Dictionary[K, V].

Examples

var fruits: Set = ["apple", "banana", "cherry"];
fruits.insert("date");
fruits.contains("apple");   // true
fruits.remove("banana");

let a: Set = [1, 2, 3];
let b: Set = [3, 4, 5];
a.union(b);                  // {1, 2, 3, 4, 5}
a.intersection(b);           // {3}
a.isSubset(of: b);           // false

Set Literals

Sets share array-literal syntax — you tell the compiler which one you want via the type annotation:

let empty: Set[Int64] = [];
let numbers: Set = [1, 2, 3];
let strings: Set[String] = ["a", "b", "c"];

Hashing

Each element's hash is computed via T: Hashable and stored in the underlying dictionary's bucket. Swap the hasher type by writing Set[T, SipHasher] etc.; the default DefaultHasher is FNV-1a (see DefaultHasher for caveats around adversarial inputs).

Representation

One field, dict: Dictionary[T, Unit, H]. All set operations delegate to the dictionary.

Memory Model

Reference-counted storage with copy-on-write value semantics — inherited from the backing Dictionary. Copying a Set is O(1) and shares storage; the next mutation triggers the deep clone so the change is invisible to other copies.

Guarantees

Elements are unique by Hashable/Equatable equality.
Iteration order is not specified.
Operations marked O(1) are amortized; the underlying dictionary resizes geometrically.

Properties

public var capacity: Int64 { get }

Total bucket capacity in the backing dictionary — always >= count.

Resizes (via the dictionary's 75% load policy) trigger the next insert past the threshold. Use reserveCapacity(...) to pre-grow and shrinkToFit() to release excess.

Examples

let set = Set[String](capacity: 100);
set.capacity;  // 128

public var count: Int64 { get }

Number of unique elements; O(1).

Forwards to the backing dictionary's count.

Examples

Set([1, 2, 3]).count;   // 3
Set[Int64]().count;     // 0

var dict: Dictionary[T, Unit, H]

Backing dictionary. Keys are the set's elements; values are always Unit().

public var isEmpty: Bool { get }

true when the set has no elements; equivalent to count == 0.

Examples

Set[Int64]().isEmpty;   // true
Set([1]).isEmpty;       // false

Associated Types

type Element = T

ExpressibleByArrayLiteral element type — equals T.

Initializers

public init(arrayLiteral: LiteralSlice[T])

Creates a set from an array literal slice — emitted by the compiler when you write let s: Set = [1, 2, 3].

Pre-allocates capacity to the literal's element count (so the build avoids resizing) and inserts each element. Duplicates collapse.

Examples

// Triggered by the array-literal-with-Set-annotation syntax:
let nums: Set = [1, 2, 3];

public init()

Creates an empty set with no allocation.

The first insert allocates the smallest dictionary bucket array (currently 8 slots). For pre-sized creation, use init(capacity:).

Examples

let set = Set[String]();
set.isEmpty;   // true
set.capacity;  // 0

public init[I](from: I) where I: Iterable, I.Item == T

Creates a set by inserting every element produced by an iterable.

Duplicates collapse silently (insert returns false for the already-present case). Capacity grows geometrically as inserts arrive — for sized sources, follow up with shrinkToFit() if memory matters.

Examples

let arr = [1, 2, 2, 3, 3, 3];
let set = Set(from: arr);    // {1, 2, 3}
let r   = Set(from: 1..<4);  // {1, 2, 3}

public init(_arrayLiteralPointer: consuming lang.ptr[T], _arrayLiteralCount: consuming lang.i64)

Compiler-emitted bridge for [a, b, c] literals constructing a Set.

Forwards to init(arrayLiteral:) after wrapping the raw (ptr, count) in a LiteralSlice. Not called by user code.

Safety

The compiler guarantees _arrayLiteralPointer covers exactly _arrayLiteralCount initialized elements of T.

public init(capacity: Int64)

Creates an empty set sized to hold at least capacity elements without resizing.

The actual allocated capacity rounds up to the next power of two (minimum 8) per the underlying dictionary policy. A non-positive capacity behaves like init(). Panics on allocation failure.

Examples

var set = Set[String](capacity: 1000);
set.capacity;  // 1024
set.count;     // 0

Methods

public func all(where: (T) -> Bool) -> Bool

true when every element satisfies predicate (vacuously true for empty sets).

Short-circuits on the first failure. Dual of any { ... }.

Examples

Set([2, 4, 6]).all { (x) in x % 2 == 0 };  // true
Set([1, 2, 4]).all { (x) in x % 2 == 0 };  // false
Set[Int64]().all { (x) in false };           // true (vacuous)

public func any(where: (T) -> Bool) -> Bool

true when at least one element satisfies predicate.

Alias for contains { ... } — both names exist so predicate-style code reads naturally regardless of context. Short-circuits.

Examples

Set([1, 2, 3]).any { (x) in x > 2 };  // true
Set[Int64]().any { (x) in true };     // false (empty)

public mutating func clear()

Removes every element, leaving capacity untouched.

Forwards to the dictionary's clear(). Follow with shrinkToFit() to release the buffer.

Examples

var set: Set = [1, 2, 3];
set.clear();      // set == {}
set.capacity;     // unchanged

public func compactMap[U]((T) -> U?) -> Set[U, H] where U: Hashable

Returns a new set with each element run through transform, dropping any None results.

Useful for parse-or-skip patterns. Same uniqueness caveat as map(...) — collisions in the transformed values collapse.

Examples

let set: Set = ["1", "two", "3"];
let nums = set.compactMap { (s) in Int64.parse(s) };
// {1, 3}  — "two" failed to parse

public func contains(T) -> Bool

true if element is a member of the set; O(1) average.

Forwards to the dictionary's key lookup. For predicate-based search use contains { ... }.

Examples

let set: Set = [1, 2, 3];
set.contains(2);  // true
set.contains(5);  // false

public func contains(where: (T) -> Bool) -> Bool

true if any element satisfies predicate.

Linear scan; short-circuits on the first match. false for empty sets. The aliased shape any { ... } exists for symmetry with Array.

Examples

Set([1, 2, 3]).contains { (x) in x > 2 };  // true
Set([1, 2, 3]).contains { (x) in x > 5 };  // false

public func countItems(where: (T) -> Bool) -> Int64

Returns the number of elements for which predicate is true.

Linear scan, no short-circuit. For just a presence check use any { ... }; for a yes/no on every element, all { ... }.

Examples

Set([1, 2, 3, 4, 5]).countItems { (x) in x % 2 == 0 };  // 2
Set[Int64]().countItems { (x) in true };                // 0

public func deepClone() -> Set[T, H]

Returns a fully-detached copy of the set with no shared storage; every element is also clone()-d.

Use over clone() when you specifically want to break the lazy COW share — for example, before passing the copy to another thread or system that might race with further mutations.

Examples

let a: Set = [[1, 2], [3, 4]];  // Set of arrays
let b = a.deepClone();          // fully independent copy

public func difference(Set[T, H]) -> Set[T, H]

Returns a new set of every element in self that is not in other — the set difference, "self minus other".

Non-mutating mirror of formDifference(...). Order of arguments matters: a.difference(b) is generally not equal to b.difference(a).

Examples

let a: Set = [1, 2, 3];
let b: Set = [2, 3, 4];
a.difference(b);  // {1}
b.difference(a);  // {4}

public func filter(where: (T) -> Bool) -> Set[T, H]

Returns a new set containing only elements for which predicate is true.

Non-mutating mirror of retain { ... }. Allocates a fresh set; for in-place filtering use retain or removeAll { ... }.

Examples

let set: Set = [1, 2, 3, 4, 5];
let evens = set.filter { (x) in x % 2 == 0 };  // {2, 4}

public func first(where: (T) -> Bool) -> T?

Returns some element matching predicate, or None.

"First" is determined by iteration order, which is unspecified — treat the result as arbitrary among matching elements. Short-circuits on the first match.

Examples

let set: Set = [1, 2, 3, 4, 5];
set.first { (x) in x > 3 };   // Some(4) or Some(5)
set.first { (x) in x > 99 };  // None

public func flatMap[U]((T) -> Set[U, H]) -> Set[U, H] where U: Hashable

Returns a new set formed by unioning every set produced by transform.

Each element maps to a Set[U, H]; those sets are merged together. The result holds the unique union — duplicates across sub-sets collapse, as with all set operations.

Examples

let set: Set = [1, 2];
let expanded = set.flatMap { (x) in Set([x, x * 10]) };
// {1, 10, 2, 20}

public mutating func formDifference(Set[T, H])

In-place difference: removes every element of self that is in other.

Mutating mirror of difference(...). The result is "self minus other".

Examples

var a: Set = [1, 2, 3];
let b: Set = [2, 3, 4];
a.formDifference(b);  // a == {1}

public mutating func formIntersection(Set[T, H])

In-place intersection: removes every element of self that is not in other.

Mutating mirror of intersection(...). Iterates over self, so the cost scales with self.count, not other.count.

Examples

var a: Set = [1, 2, 3];
let b: Set = [2, 3, 4];
a.formIntersection(b);  // a == {2, 3}

public mutating func formSymmetricDifference(Set[T, H])

In-place symmetric difference: keeps elements in exactly one of self or other.

Mutating mirror of symmetricDifference(...). Two passes: removes shared elements, then inserts elements unique to other.

Examples

var a: Set = [1, 2, 3];
let b: Set = [2, 3, 4];
a.formSymmetricDifference(b);  // a == {1, 4}

public mutating func formUnion(Set[T, H])

In-place union: adds every element of other to self.

Mutating mirror of union(...). For multi-source unions, chain calls or use insert(contentsOf:) over the elements.

Examples

var a: Set = [1, 2];
let b: Set = [2, 3];
a.formUnion(b);  // a == {1, 2, 3}

func getDict() -> Dictionary[T, Unit, H]

Returns the backing Dictionary[T, Unit, H]. Internal helper for extensions that need direct dictionary access.

public mutating func insert(T) -> Bool

Inserts element, returning whether it was newly added.

Returns true if the element was added, false if it was already present (in which case the set is unchanged). May trigger a dictionary resize and COW. For bulk inserts, see insert(contentsOf:).

Examples

var set: Set = [1, 2];
set.insert(3);  // true; set == {1, 2, 3}
set.insert(2);  // false; already present

public mutating func insert[I](contentsOf: I) where I: Iterable, I.Item == T

Inserts every element produced by an iterable; duplicates collapse silently.

Sugar for "insert in a loop". For union with another Set, prefer formUnion(...) — it's the same semantically but reads more naturally.

Examples

var set: Set = [1, 2];
set.insert(contentsOf: [3, 4, 5]);  // {1, 2, 3, 4, 5}
set.insert(contentsOf: 5..<8);      // {1, 2, 3, 4, 5, 6, 7}

public func intersection(Set[T, H]) -> Set[T, H]

Returns a new set containing only elements present in both self and other.

Non-mutating mirror of formIntersection(...). For efficiency, iterates over self; pass the smaller set as the receiver if it matters.

Examples

let a: Set = [1, 2, 3];
let b: Set = [2, 3, 4];
a.intersection(b);  // {2, 3}

public func isDisjoint(with: Set[T, H]) -> Bool

true if self and other share no elements.

Iterates over the smaller set for efficiency (swaps the arguments internally if needed). Empty sets are disjoint from anything, including each other.

Examples

let a: Set = [1, 2];
let b: Set = [3, 4];
let c: Set = [2, 3];
a.isDisjoint(with: b);  // true
a.isDisjoint(with: c);  // false (share 2)

public func isStrictSubset(of: Set[T, H]) -> Bool

true if self is a subset of other and the two sets are not equal.

Strict (proper) subset — excludes the case where the sets are equal. Mirror of isStrictSuperset(of:).

Examples

let a: Set = [1, 2];
let b: Set = [1, 2, 3];
a.isStrictSubset(of: b);  // true
a.isStrictSubset(of: a);  // false (equal, not strict)

public func isStrictSuperset(of: Set[T, H]) -> Bool

true if self is a superset of other and the two sets are not equal.

Strict (proper) superset. Mirror of isStrictSubset(of:).

Examples

let a: Set = [1, 2, 3];
let b: Set = [1, 2];
a.isStrictSuperset(of: b);  // true
a.isStrictSuperset(of: a);  // false (equal, not strict)

public func isSubset(of: Set[T, H]) -> Bool

true if every element of self appears in other.

A set is always a subset of itself (reflexive). Short-circuits on the first missing element, and skips the inner scan when self.count > other.count. For "subset but not equal" use isStrictSubset(of:).

Examples

let a: Set = [1, 2];
let b: Set = [1, 2, 3];
a.isSubset(of: b);  // true
b.isSubset(of: a);  // false
a.isSubset(of: a);  // true

public func isSuperset(of: Set[T, H]) -> Bool

true if every element of other appears in self.

Reflexive (a set is its own superset). Implemented as other.isSubset(of: self) for code reuse.

Examples

let a: Set = [1, 2, 3];
let b: Set = [1, 2];
a.isSuperset(of: b);  // true
b.isSuperset(of: a);  // false

public func map[U]((T) -> U) -> Set[U, H] where U: Hashable

Returns a new set with each element run through transform.

Cardinality may shrink: if transform maps two distinct elements to the same output, the result holds only one copy (sets are unique). For an Optional-aware variant that drops None, use compactMap(...).

Examples

let set: Set = [1, 2, 3];
let doubled = set.map { (x) in x * 2 };
// {2, 4, 6}

let words: Set = ["Hello", "WORLD"];
let lower = words.map { (s) in s.lowercase() };
// {"hello", "world"} — even though both originals lowercase to distinct strings

public func max() -> T?

Returns the largest element, or None for an empty set.

Single linear pass. Mirror of min().

Examples

Set([3, 1, 4]).max();  // Some(4)
Set[Int64]().max();    // None

public func min() -> T?

Returns the smallest element, or None for an empty set.

Single linear pass; ties go to the first occurrence in iteration order (which is unspecified, so equally-minimal elements compare equal anyway).

Examples

Set([3, 1, 4]).min();  // Some(1)
Set[Int64]().min();    // None

public mutating func remove(T) -> Bool

Removes element if present; returns whether anything was removed.

Leaves a tombstone in the backing dictionary — see Dictionary.remove. Tombstones are reclaimed by the next resize. Triggers COW only when an element is actually removed.

Examples

var set: Set = [1, 2, 3];
set.remove(2);  // true; set == {1, 3}
set.remove(5);  // false; set unchanged

public mutating func removeAll(where: (T) -> Bool)

Removes every element for which predicate is true.

Inverse of retain { ... }. Same two-pass structure.

Examples

var set: Set = [1, 2, 3, 4, 5];
set.removeAll { (x) in x % 2 == 0 };  // {1, 3, 5}

public mutating func reserveCapacity(Int64)

Grows the backing dictionary so at least minimumCapacity elements fit without resizing.

No-op when current capacity already suffices. Implemented by rebuilding the underlying dictionary at the new capacity (a little heavier than Dictionary.reserveCapacity directly, since it reinserts each element). Opposite of shrinkToFit().

Examples

var set = Set[String]();
set.reserveCapacity(1000);
// No reallocations for the first ~750 inserts.

public mutating func retain(where: (T) -> Bool)

Keeps only elements for which predicate is true.

Two-pass implementation: collects elements to remove, then deletes each. Stable in iteration semantics (set is unordered anyway). Mirror is removeAll { ... }.

Examples

var set: Set = [1, 2, 3, 4, 5];
set.retain { (x) in x % 2 == 0 };  // {2, 4}

public mutating func shrinkToFit()

Reduces backing-dictionary capacity to fit the current count.

Rebuilds the dictionary at a smaller capacity, dropping any tombstones. No-op when capacity already matches. Useful after large removals.

Examples

var set = Set[String](capacity: 1000);
set.insert("a");
set.shrinkToFit();  // capacity drops toward count

public func sorted() -> Array[T]

Returns the set's elements as an ascending-sorted Array[T].

Convenience for "I want this set as an ordered list". Duplicates have already collapsed in the set, so the result has no repeats.

Examples

Set([3, 1, 4, 1, 5]).sorted();  // [1, 3, 4, 5]

public func sum() -> T

Returns the sum of every element, starting from T() (the default-constructed zero).

Empty sets return T() — 0 for Int64, "" for String, etc. Linear in count.

Examples

Set([1, 2, 3]).sum();  // 6
Set[Int64]().sum();    // 0

public func symmetricDifference(Set[T, H]) -> Set[T, H]

Returns a new set of elements in exactly one of self or other.

Non-mutating mirror of formSymmetricDifference(...). Equivalent to union(...) - intersection(...). The operation is commutative — order of arguments doesn't change the result.

Examples

let a: Set = [1, 2, 3];
let b: Set = [2, 3, 4];
a.symmetricDifference(b);  // {1, 4}

public func toArray() -> Array[T]

Returns an Array[T] with every element of the set.

Order matches iteration order (i.e. unspecified). Capacity is pre-reserved to count so the build avoids reallocations. For an ordering, follow with Array.sort() or sorted() (in the T: Comparable extension below).

Examples

let set: Set = [1, 2, 3];
let arr = set.toArray();  // [1, 2, 3] in some order

public func union(Set[T, H]) -> Set[T, H]

Returns a new set containing every element from self and other.

Non-mutating mirror of formUnion(...). Internally clones self (cheap COW) and adds other into the copy.

Examples

let a: Set = [1, 2, 3];
let b: Set = [3, 4, 5];
a.union(b);  // {1, 2, 3, 4, 5}

ImplementsIterable

Associated Types

type Item = T

Iterable element type — T.

type TargetIterator = SetIterator[T, H]

Concrete iterator type returned by iter().

Methods

public func iter() -> SetIterator[T, H]

Returns a single-pass SetIterator[T, H] over the elements.

Order is unspecified and may change between mutations. The iterator borrows the underlying buffer; do not mutate the set while iterating.

Examples

for item in set.iter() { print(item); }
let arr = Array(from: set.iter());

ImplementsCloneable

Methods

public func clone() -> Set[T, H]

Returns a Set sharing the same storage; the deep copy is deferred until either side mutates.

O(1) — bumps the backing dictionary's RcBox refcount. The first mutation on either side triggers the deep clone. For an immediate eager copy, use deepClone() (in the T: Cloneable extension below).

Examples

let a: Set = [1, 2, 3];
var b = a.clone();   // O(1), shares storage
b.insert(4);         // b deep-copies here; a is unchanged

ImplementsEquatable

Associated Types

type Output = Bool

Methods

public func equal(to: Self) -> Bool

Bridges Equal.equal(to:) to Equatable.isEqual(to:).

public func isEqual(to: Set[T, H]) -> Bool

true when self and other contain exactly the same elements.

Order-independent (sets are unordered). Implemented as "equal counts and self.isSubset(of: other)" — short-circuits at the count check.

Examples

Set([1, 2, 3]).isEqual(to: Set([3, 2, 1]));  // true
Set([1, 2]).isEqual(to: Set([1, 2, 3]));     // false

public func notEqual(to: Self) -> Bool

Default !=: delegates to == so there's a single source of truth.

ImplementsFormattable

Methods

public func format(into: mutating StringBuilder, FormatOptions)

Renders the set as "{" + elements.joined(", ") + "}", passing options to each element's format.

Examples

Set([1, 2, 3]).format();  // "{1, 2, 3}" — order unspecified
Set[Int64]().format();    // "{}"
"\{Set([1, 2, 3])}";      // "{1, 2, 3}" via interpolation

public func formatted(FormatOptions) -> String

Returns this value rendered as a String.

Convenience wrapper: creates a StringBuilder, calls format(into:), and returns the built string. Uses a distinct name to avoid overload-resolution ambiguity with format(into:).

ImplementsExpressibleByArrayLiteral

Initializers

init(arrayLiteral: LiteralSlice[Element])

Builds an instance from a literal slice of elements.

Defined in lang/std/collections/set.ks