Module

std.collections

Protocols

public protocol SeqRange

Resolves any range-like type to a half-open Range[Int64] given a collection length. Used by removeSubrange and replaceSubrange so they accept Range, ClosedRange, RangeFrom, RangeUpTo, and RangeThrough through a single generic parameter.

public protocol Slice[T]

Shared read-only protocol for contiguous collections.

Slice[T] is the contiguous-collection counterpart to Str in std.text: one kernel method (asSlice), all read-only logic in a protocol extension. Both Array[T] and ArraySlice[T] conform, so generic code constrained to S: Slice[T] accepts either without overloading.

Examples

func sum[S](s: S) -> Int64 where S: Slice[Int64] {
    var total: Int64 = 0;
    for elem in s { total = total + elem }
    total
}
sum([1, 2, 3]);              // works with Array
sum([1, 2, 3].asSlice());    // works with ArraySlice

Structs

public struct Array[T] { /* private fields */ }

A dynamic, growable, contiguous-buffer array with copy-on-write storage.

Array[T] is the standard ordered-collection type. It supports constant-time random access, amortized constant-time append, and arbitrary-position insert/remove via shifting. Storage is shared between copies until one of them mutates, at which point that copy lazily clones the buffer (see "Memory Model" below). For non-owning views over an existing buffer use ArraySlice[T]; for fixed-size or set-like collections see ArraySlice[T], Set, or Dictionary.

Examples

let evens = [2, 4, 6, 8];
var names = Array[String]();
names.append("Alice");
names.append("Bob");

let copy = names;      // O(1) — shares storage with `names`
names.append("Carol"); // O(1) clone happens here, `copy` is unchanged

for n in names.iter() { ... }
let pivot = names.partition(by: { (n) in n.count > 3 });

Indexing

The default subscript arr(i) panics on out-of-bounds. Variants exist for every common policy: arr(checked: i) returns T?, arr(unchecked: i) skips the bounds check (UB on OOB), arr(wrapped: i) wraps with modulo (and supports negative indices), and arr(clamped: i) clamps to [0, count-1]. Range arguments use the same labels — arr(0..<3), arr(checked: r), arr(unchecked: r), arr(clamped: r) — dispatched through the unified SeqIndex[T], SeqClampable[T], and SeqWrappable[T] protocols. Int64 and range types share each label; the result type varies (T? vs ArraySlice[T] for clamped:).

Capacity & Reallocation

count is the number of elements; capacity is how many can fit without reallocating. When append would exceed capacity the buffer doubles (starting from 4 if previously zero). Use reserveCapacity(minimumCapacity:) to pre-allocate, and shrinkToFit() to release excess.

Representation

Holds a single CowBox[ArrayStorage[T]] field. The storage is a (ptr, len, cap) triple over a heap-allocated buffer.

Memory Model

Reference-counted storage with copy-on-write value semantics. Copying an Array is O(1) and shares the buffer; the next mutation on a shared Array triggers makeUnique(), which deep-clones the buffer so the mutation is invisible to other copies. The user-visible behavior is indistinguishable from deep-copying on assignment.

Guarantees

Elements are stored contiguously and are accessible via asPointer() for FFI; the pointer is invalidated by any mutation that may reallocate.
count <= capacity always.
Iteration order is insertion order.
Operations marked O(1) are amortized; growth is geometric.

public struct ArrayBuilder[T] { /* private fields */ }

Write-only buffer for efficient array construction. No COW, no RcBox, no isUnique checks — every append writes directly through the pointer.

build() transfers ownership of the buffer into a new Array[T] without copying. The builder resets to empty and can be reused.

Examples

var b = ArrayBuilder[Int64](capacity: 3);
b.append(1);
b.append(2);
b.append(3);
let arr = b.build();   // [1, 2, 3], zero-copy

Representation

(ptr: Pointer[T], len: Int64, cap: Int64).

Memory Model

Owns its buffer directly — no reference counting during construction. build() donates the buffer to an Array[T] and leaves the builder empty. deinit frees the buffer if build() was never called.

public struct ArraySplitIterator[T] where T: Equatable { /* private fields */ }

public struct ArraySplitView[T] where T: Equatable { /* private fields */ }

Multi-pass lazy view over the segments produced by splitting on each occurrence of a separator value. (Named ArraySplitView to avoid collision with std.text.SplitView.)

public struct ArraySplitWhereIterator[T] { /* private fields */ }

public struct ArraySplitWhereView[T] { /* private fields */ }

Multi-pass lazy view over the segments produced by splitting on each element matching a predicate. No Equatable requirement. (Named ArraySplitWhereView to avoid collision with std.text.SplitWhereView.)

public struct ChunksIterator[T] { /* private fields */ }

public struct ChunksView[T] { /* private fields */ }

Multi-pass lazy view over non-overlapping chunkSize-sized ArraySlice[T] segments.

public struct DefaultHasher { /* private fields */ }

The standard Hasher implementation, backed by a wyhash-derived per-byte mixer.

Used by Dictionary and Set whenever the user doesn't pick a specific hasher. Each byte folds into a 64-bit running state via state = (state ^ byte) * MULT; finish() runs Murmur3's fmix64 finalizer to scramble the result so every input bit avalanches across the output.

Not adversarially safe. The mixer is unkeyed, so an attacker who can choose keys can craft collisions. For HashDoS resistance, swap in a keyed hasher (planned: SipHasher13) by spelling out Dictionary[K, V, SipHasher13] directly. For non-adversarial workloads — internal IDs, parser symbols, config values — this hasher is faster and has better distribution than FNV-1a.

Examples

var h = DefaultHasher();
"hello".hash(into: h);
let hash = h.finish();  // 64-bit hash of "hello"

// Used implicitly through the dictionary type alias:
let d: [String: Int64] = ["a": 1];   // DefaultHasher under the hood

Algorithm

Initialization seeds state with the wyhash secret 0x9e3779b97f4a7c15 (the "golden ratio" constant SplitMix64 uses). Each byte updates the state with state = (state ^ byte) * 0x100000001b3, which combines wyhash's mixing constant with FNV-1a's prime so every bit of the byte propagates across the 64-bit state. finish() runs Murmur3's fmix64 finalizer (xor-shift-multiply twice) so consecutive integer keys produce non-clustered hashes.

Representation

One UInt64 field, state, holding the running digest.

public struct Deque[T] { /* private fields */ }

A double-ended queue backed by a ring buffer with copy-on-write storage.

O(1) amortized pushBack/pushFront/popBack/popFront and O(1) random access by index. Storage is shared between copies until one mutates, at which point the COW barrier fires.

Examples

var d = Deque[Int64]();
d.pushBack(1);
d.pushFront(0);
d.pushBack(2);
d.popFront();  // .Some(0)
d.popBack();   // .Some(2)

Representation

Holds a CowBox[DequeStorage[T]]. The storage is a (ptr, len, cap, head) quad over a heap-allocated ring buffer.

Memory Model

Reference-counted storage with copy-on-write value semantics via CowBox. Copying a Deque is O(1); the first mutation on a shared copy triggers a deep clone that linearizes the ring buffer.

Guarantees

pushBack/pushFront are O(1) amortized; growth is geometric.
popBack/popFront are O(1).
Subscript access is O(1).
Iteration order is front-to-back.

public struct DequeIterator[T] { /* private fields */ }

Iterator over a Deque[T], walking the ring buffer from head through remaining elements.

Created by Deque.iter(). Yields elements front-to-back, wrapping around the ring buffer boundary transparently.

Representation

Holds a raw pointer into the deque's ring buffer, the buffer capacity, the current physical position, and a remaining-element count. Does not own the storage.

public struct Dictionary[K, V, H = DefaultHasher] where K: Hashable, H: Hasher, H: Defaultable { /* private fields */ }

An unordered hash map keyed by any K: Hashable, parameterized over the hasher type H (defaults to DefaultHasher).

Uses open addressing with linear probing and a 75% load-factor threshold for resizes; capacity always grows to the next power of two. Storage is reference-counted with copy-on-write, so copying a Dictionary is O(1) and only the next mutation pays for the deep clone. Iteration order is unspecified and may change between versions or after any mutation. For ordered alternatives consider keeping an ordered key list separately; for set-only behavior see Set.

Examples

var ages: [String: Int64] = [:];
ages("Alice") = 30;
ages("Bob")   = 25;

ages("Alice");                // Some(30)
ages("Carol", default: 0);    // 0

for (name, age) in ages.iter() { ... }
let sum = ages.values.iter().sum();

Hashing

The hash for each key is cached in its bucket so resizes don't recompute it. Replacing the hasher (H) lets you swap in SipHasher, FxHasher, etc.; the default is DefaultHasher and resolves through the [K: V] shorthand.

Capacity & Reallocation

count is live entries; capacity is total slots. The table resizes (doubling capacity, starting from 8) once count reaches 75% of capacity. Use reserveCapacity(...) to pre-grow and shrinkToFit() to release excess.

Representation

One field: an RcBox[DictionaryStorage[K, V, H]] holding (buckets, len, cap) over a heap bucket array.

Memory Model

Reference-counted storage with copy-on-write value semantics. Copying a Dictionary is O(1) and shares the bucket array; the next mutation on a shared dictionary triggers makeUnique(), which deep-clones via DictionaryStorage.clone() so the mutation is invisible to other copies.

Guarantees

Every key satisfies K: Hashable. The cached hash is computed once per insert and reused on resize.
count <= capacity * 3 / 4 after every mutation (the resize threshold).
Removing a key leaves a .Deleted tombstone; lookups still work but tombstones reduce effective capacity until the next resize.
Iteration order is not specified.

public struct DictionaryIterator[K, V] { /* private fields */ }

Single-pass forward iterator over the (key, value) entries of a Dictionary[K, V, H].

Produced by Dictionary.iter(). Walks the bucket array once, skipping .Empty and .Deleted slots, and yields each occupied entry as a tuple. Iteration order matches bucket layout, which depends on the hash and probe sequence — treat it as unspecified. For key- or value-only views see KeysIterator and ValuesIterator.

Examples

let dict = ["a": 1, "b": 2];
var it = dict.iter();
it.next();  // Some(("a", 1))   — order is unspecified
it.next();  // Some(("b", 2))
it.next();  // None

Representation

A (buckets, capacity, index) triple — pointer to the bucket array, total slots, and the current scan position.

Memory Model

Value type. The pointer aliases dictionary storage; do not retain an iterator across mutations of the source dictionary.

public struct Heap[T] where T: Comparable { /* private fields */ }

Binary min-heap backed by Array[T].

O(log n) push/pop, O(1) peek at the minimum element. Builds from an existing array in O(n) via Floyd's heapify. Iteration yields elements in storage order (NOT sorted order).

Examples

var h = Heap[Int64]();
h.push(5);
h.push(1);
h.push(3);
h.peek();   // .Some(1)
h.pop();    // .Some(1)
h.pop();    // .Some(3)

Representation

A single Array[T] field in standard binary-heap layout: the minimum lives at index 0, children of node i are at 2i + 1 and 2i + 2.

Memory Model

Delegates storage to Array[T], inheriting its COW value semantics. Copying a Heap is O(1); the first mutation on a shared copy triggers the array's copy-on-write barrier.

Guarantees

peek() always returns the minimum element.
After pop(), the next-smallest element becomes the new minimum.
Iteration order is unspecified (internal heap layout).

public struct KeysIterator[K, V] where K: Hashable { /* private fields */ }

Single-pass iterator yielding only the keys of a dictionary.

Wraps a DictionaryIterator[K, V] and discards the value half of each entry. Order matches the underlying entry iteration and is unspecified.

Examples

var it = ["a": 1, "b": 2].keys.iter();
it.next();  // Some("a")  — order unspecified
it.next();  // Some("b")
it.next();  // None

Representation

Wraps a DictionaryIterator[K, V].

Memory Model

Value type. Aliases dictionary storage; do not retain across mutations.

public struct KeysView[K, V] where K: Hashable { /* private fields */ }

Lazy Iterable view over the keys of a dictionary.

Returned by Dictionary.keys. Constructing the view is O(1) — it stores the bucket pointer and capacity. The view is invalidated by any mutation that may reallocate.

Examples

let dict = ["a": 1, "b": 2];
for k in dict.keys { print(k) }
let arr = Array(from: dict.keys);

Representation

(buckets, capacity) — a pointer into the source dictionary's bucket array plus the total slot count.

Memory Model

Value type that borrows the source dictionary's buffer.

public struct ReversedSliceIterator[T] { /* private fields */ }

public struct ReversedView[T] { /* private fields */ }

Multi-pass lazy view that iterates a contiguous collection back-to-front without allocating.

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.

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

Single-pass forward iterator over the elements of a Set[T, H].

Returned by Set.iter(). Wraps the underlying DictionaryIterator[T, Unit] and discards the (unused) value half of each entry, yielding only the key. Iteration order matches the underlying bucket layout and is unspecified.

Examples

let set: Set = [1, 2, 3];
for item in set { print(item); }

Representation

Wraps a DictionaryIterator[T, Unit].

Memory Model

Value type. Aliases the source set's bucket array; do not retain across mutations of the set.

public struct ValuesIterator[K, V] where K: Hashable { /* private fields */ }

Single-pass iterator yielding only the values of a dictionary.

Wraps a DictionaryIterator[K, V] and discards the key half of each entry. Order matches the underlying entry iteration and is unspecified.

Examples

var it = ["a": 1, "b": 2].values.iter();
it.next();  // Some(1)  — order unspecified
it.next();  // Some(2)
it.next();  // None

Representation

Wraps a DictionaryIterator[K, V].

Memory Model

Value type. Aliases dictionary storage; do not retain across mutations.

public struct ValuesView[K, V] where K: Hashable { /* private fields */ }

Lazy Iterable view over the values of a dictionary.

Returned by Dictionary.values. Constructing the view is O(1) — it stores the bucket pointer and capacity. The view is invalidated by any mutation that may reallocate.

Examples

let dict = ["a": 1, "b": 2];
for v in dict.values { print(v) }
let sum = dict.values.iter().sum();

Representation

(buckets, capacity) — a pointer into the source dictionary's bucket array plus the total slot count.

Memory Model

Value type that borrows the source dictionary's buffer.

public struct WindowsIterator[T] { /* private fields */ }

public struct WindowsView[T] { /* private fields */ }

Multi-pass lazy view over overlapping fixed-size sliding windows.

Type Aliases

public type ArrayTypeOperator[T] = Array[T]

Compiler-recognized type alias that lets [T] desugar to Array[T].

Allows annotations like let xs: [Int64] = [1, 2, 3] instead of requiring the user to spell out Array[Int64]. Not intended for direct use — the parser inserts it automatically when it sees the [T] shorthand in a type position.

Examples

let xs: [Int64] = [1, 2, 3];   // same as: Array[Int64]
func sum(of values: [Float]) -> Float { ... }

public type DictionaryTypeOperator[K, V] = Dictionary[K, V, DefaultHasher]

Compiler-recognized type alias that lets [K: V] desugar to Dictionary[K, V, DefaultHasher].

Allows annotations like let m: [String: Int64] = [:] instead of requiring the user to spell out Dictionary[String, Int64]. The hasher is fixed to DefaultHasher; for custom hashers, write the Dictionary[...] form explicitly.

Examples

let counts: [String: Int64] = [:];
func tally(of words: [String: Int64]) -> Int64 { ... }