std.collections

std.collections provides the owned associative containers HashMap<K, V> and Set<T>. The growable, owned, contiguous sequence is the built-in slice ^[T]; its sole literal is ^[...], while growth, editing, and duplication are methods on the slice value itself.

Contract

^[T] is a move value laid out as { ptr, length, capacity }. It owns and frees its physical buffer when one exists, dropping each initialized element when the slice is dropped. Canonical empty and zero-sized storage need no allocation. Bare [T] is a non-owning shared view and &[T] is a mutable view. Plain [...] is always a nonallocating fixed array. Build an owner with a nonempty fallible literal (try ^[1, 2, 3]), an infallible empty literal (var xs: ^[i32] = ^[];), or the growth methods below. std.slice has no arity-specific constructor helpers.

Growth and editing are move-based: each consumes the receiver and returns the updated slice, so user code threads the result back into the binding (xs = try (<-xs).push(<-v)). push, reserve, insert, and clone may allocate and report out-of-memory as AllocError, like str. clear, pop, and remove do not allocate or throw. They return a successor owner directly; pop and remove return the removed element beside it in an owning tuple.

RFC 0064 fixes these names across public target collections. A sequence uses push for one tail element and insert for one explicit position. A map uses put for one association, a set uses add for one representative, and both hash collections use merge for bulk owner transfer between the same nominal type. pop, remove, and clear retain their distinct selection/destruction meanings. There are no collection append/extend, delete, erase, take, remove_entry, map/set insert, put_all, or add_all aliases.

Quick Example

// RFC 0052 target; implementation pending.

fn main() throws(AllocError) {
	var values: ^[i32] = ^[];
	values = try (<-values).reserve(32);
	values = try (<-values).push(10);
	values = try (<-values).push(32);

	assert values.length == 2 as usize;
	assert values[0] == 10;
	assert values[1] == 32;
}

Editing

push and insert grow the slice. pop and remove return an owning tuple — the shrunk slice plus the element taken out of it — which the caller destructures before threading the successor back into the binding.

// RFC 0052 target; implementation pending.

fn main() throws(AllocError) {
	var xs: ^[i32] = ^[];
	xs = try (<-xs).push(1);
	xs = try (<-xs).push(2);
	xs = try (<-xs).push(3);

	xs = try (<-xs).insert(0, 9);
	assert xs[0] == 9;

	let (after_pop, popped) = (<-xs).pop();
	xs = <-after_pop;
	assert popped != null;
	assert popped == 3;

	let (after_remove, removed) = (<-xs).remove(0);
	xs = <-after_remove;
	assert removed == 9;

	assert xs.length == 2 as usize;
	assert xs[0] == 1;
	assert xs[1] == 2;

	xs = (<-xs).clear();
	assert xs.length == 0 as usize;
}

Cloning

The slice value is the slice — pass it directly wherever a [T] is expected. clone makes a second independent owned copy, so editing the copy leaves the source intact.

fn main() throws(AllocError) {
	let original: ^[i32] = try ^[1, 2];
	var copy = try original.clone();
	copy[0] = 9;

	assert original[0] == 1;
	assert copy[0] == 9;
	assert copy.length == 2 as usize;
}

Lookup

[T] has no built-in search method: iterate the slice (or index by position) and compare with whatever equality your element type needs. This keeps the slice from standardizing byte equality for structs with padding or custom identity rules.

fn main() {
	let values = [1, 2, 2];
	let needle = 2;

	var count: usize = 0;
	var found = false;
	for i in 0 ..< values.length {
		if values[i] == needle {
			count = count + 1;
			found = true;
		}
	}

	assert count == 2 as usize;
	assert found;
}

Sorting And Search

Sorting and binary search for [T] slices live in std.slice: one sort and one binary_search always borrow an explicit concrete (&self, T, T) -> Ordering comparator. Sort is stable, retains the exact slice owner and backing allocation, and performs no heap allocation. Search returns the first comparator-equivalent index or the lower-bound insertion point. See std.slice for the API and std.ordering for Ordering and the explicit primitive comparators.

Sets

Set<T> stores unique HashKey values. Like HashMap, growth may throw AllocError; the first insertion may also report unavailable platform entropy when creating the collection's private keyed-hash seed. The accepted target returns ownership of an equivalent incoming value instead of reducing the result to a boolean.

import std.collections.{ Set };

fn main() {
	var values = Set<i32>();
	match try values.add(10) {
		.Added => {},
		.Duplicate(value) => { assert false; },
	}

	match try values.add(10) {
		.Added => { assert false; },
		.Duplicate(value) => assert value == 10,
	}

	let needle = 10;
	assert values.length == 1 as usize;
	assert values.get(needle) != null;
}

The checked-in implementation still returns bool from add and exposes contains instead of get; the example above is the accepted migration target.

Accepted Construction And Allocation Domain

The sole empty constructors are direct type calls with no arguments:

var users = HashMap<UserId, User>();
var ids = Set<UserId>();

Both constructors are infallible. The new collection has length == 0 and capacity == 0, owns no table allocation, and has no keyed-hash seed. Empty construction performs no allocation and obtains no entropy.

reserve(total) is the sole preallocation operation. It may create or replace table storage when the requested logical total is not already guaranteed, but it never creates a seed or requests entropy. There is no capacity-taking constructor and no new, with_capacity, new_in, *_alloc, builder, or constructor alias.

Core HashMap and Set always allocate table storage through one statically known built-in process-allocation domain. An allocator is not a constructor argument, stored field, generic parameter, erased capability, borrowed capability, or ambiently selected value. The collection exposes no allocator accessor such as get_allocator, and moving or borrowing the collection never moves or borrows an allocator owner.

The first absent put or add obtains the private keyed-hash seed and commits it only with the successful insertion. Entropy, layout, or allocation failure leaves the collection's entries, seed state, allocation identity, length, and capacity unchanged. Replacement and duplicate insertion do not allocate or obtain entropy. clear retains both existing table storage and an existing seed; dropping the collection releases its table through the same statically known built-in domain.

Thread capabilities are structural and contain no hidden allocator condition: HashMap<K, V> is Send exactly when K and V are Send, and is Sync exactly when K and V are Sync. Set<T> is Send exactly when T is Send, and is Sync exactly when T is Sync.

Custom allocation is not an extension point of these core nominal types. A specialized custom-allocator collection, if one is ever accepted, must be a separate nominal type under a future RFC; no such type or name is promised.

Accepted Structural Collection Clone

HashMap and Set are never Copy. They conditionally implement the one RFC 0003 Clone contract:

fn clone(self) throws(AllocError) -> ^Self;

Each stored type is considered independently. A Copy component is duplicated with its ordinary infallible bitwise copy. A non-Copy component must implement Clone and is cloned exactly once. Therefore HashMap<K, V> supports Clone exactly when each of K and V is either Copy or, when non-Copy, supports Clone; Set<T> uses the same rule for T. A Copy component never acquires a redundant fallible clone call merely because it also has an explicit Clone implementation.

Collection clone is structural, not a rebuild from logical entries. A successful result has a distinct backing allocation whenever the source has one, while preserving the source's exact private table shape: authoritative and mirrored controls, Full positions, Deleted tombstones, growth budget, physical capacity, logical length and capacity, and seed presence and bits. It does not hash a key, call equality, obtain entropy, or create a fresh seed. Its only checked error is AllocError, from allocating the destination table or cloning a non-Copy component.

The empty states remain distinct:

• cloning a fresh unallocated, unseeded collection returns another fresh unallocated, unseeded collection without allocating;
• cloning an allocated but still unseeded collection, such as one prepared by reserve, creates a separate structurally identical allocation and remains unseeded;
• cloning a seeded collection copies the seed bits, including when clear has left a seeded empty table with retained storage.

When a source table is allocated, destination storage is prepared before any element is duplicated. Live slots are processed by increasing authoritative slot index. A map duplicates its key before its value; a set duplicates its stored value. A destination slot becomes armed as Full only after its complete element or key/value pair is initialized.

If a map key clone fails, already completed earlier entries drop in reverse construction order. If a value clone fails, the initialized current key drops first, followed by completed earlier entries in reverse order; each complete entry drops its value before its key. Set rollback drops completed earlier values in reverse order. The destination allocation is then released exactly once through the built-in process domain. No uninitialized slot is dropped, and the source table, seed, entries, allocation identity, length, and capacity remain unchanged on success or handled failure.

The copied physical positions naturally give source and result the same immediate scan sequence, but collection order remains unordered and is not a stable ordering contract. Independent later mutations may diverge. Core has no fresh-seed clone, reseed, duplicate, rebuild, or compaction variant; such an operation would have different error and ordering semantics. None of the five collection cursor types implements Clone.

Accepted Hash-Table Storage Target

The current HashMap and Set sources are transitional. Their accepted target shares one package-private RawTable<E> implementation; RawTable is storage, not another public collection type. HashMap supplies key/value entries and Set supplies values to the same table machinery, so probing, growth, removal, allocation rollback, and cleanup have one implementation and one invariant set.

The table is a flat SwissTable-style allocation:

• one SDK-internal affine RawStorage<E> allocation contains a properly aligned MaybeUninit<E> slot prefix, any required alignment padding, the authoritative control bytes, and their mirrored suffix;
• a hash is split into an H1 probe position and an H2 control-byte fingerprint;
• lookup tests one target-sized control group at a time, then runs key equality only for matching H2 candidates;
• the private group width is either 8 or 16 lanes as selected for the target; it is not source-visible, serialized, or part of the ABI;
• growth keeps at least one empty slot and uses a maximum load of 7/8;
• removal leaves a tombstone when required to preserve a probe chain; rehashing removes tombstones instead of shifting a cluster backward in place.

RawStorage<E> owns and frees the one built-in-domain allocation, but it is liveness-blind: it neither stores a second bitmap nor knows which E slots are initialized. Only the table's authoritative control byte decides that. Full means the corresponding complete E is live; Empty and Deleted mean the slot is uninitialized. The mirrored suffix accelerates probing but is never a second source of liveness truth. RawStorage has no public API, layout promise, slot tokens, grow, reserve, realloc, iterator, or checked view over the hole-bearing prefix.

For maps, E is one private complete key/value entry. An insertion constructs that entry before initializing its slot and publishes Full(H2) only after the complete entry is live. Taking an entry moves out exactly one owner before the slot is disarmed; dropping an entry disarms the control state before invoking user cleanup. Each raw-slot/control transition is a short SDK-internal trusted sequence with no checked error, callback, suspension, or other user code in between. A checked loan returned by a lookup is anchored in the whole HashMap or Set, never in RawStorage alone, so it also blocks removal, rehash, and control-byte mutation for the borrowed slot.

Insertion always completes lookup before deciding to grow. Replacing an existing map value or submitting a value already present in a set therefore does not allocate merely because the table is at its growth threshold. A rehash is transactional with respect to checked failure: sizing and allocation complete before entries are transferred, no fallible operation occurs after transfer starts, and the old allocation remains the collection's complete state if preparation fails.

Growth and rehash are RawTable operations rather than RawStorage operations. They allocate and initialize a complete empty destination before moving only the source's Full entries; they never byte-copy the entire slot capacity as initialized E. A zero-sized E still has logical slots and one cleanup obligation per Full control byte, but consumes no payload bytes and performs no element-pointer arithmetic. Control bytes and their mirror remain physical because probing still needs them.

The target deletes the current parallel full-hash and occupancy-state arrays, backward-shift deletion, and every HashBucket name-based compiler special case. Element size and alignment use ordinary instantiated generic layout; the compiler does not recognize HashMap, Set, RawTable, or a bucket spelling.

Flat storage deliberately provides no stable element address. A grow, rehash, insertion, or removal may relocate entries. There is no node mode, inline/small table mode, public RawTable, raw bucket/control-byte API, or layout escape hatch. The accepted cursor contract below preserves that encapsulation and does not expose any physical table detail.

Accepted Mutation Ownership Target

The current HashMap.put, HashMap.remove, Set.add, and Set.remove results are transitional. Their accepted target makes every displaced owner observable:

export struct HashMapItem<K, V> {
	export let key: ^K,
	export let value: ^V,
}

export enum HashMapPutResult<K, V> {
	Inserted,
	Replaced(incoming_key: ^K, old_value: ^V),
}

export enum SetAddResult<T> {
	Added,
	Duplicate(incoming_value: ^T),
}

The target mutation signatures are:

fn HashMap.put(
	&self,
	key: ^K,
	value: ^V,
) throws(AllocError | random.RandomError) -> ^HashMapPutResult<K, V>;

fn HashMap.remove(&self, key: K) -> ^HashMapItem<K, V>?;

fn Set.add(
	&self,
	value: ^T,
) throws(AllocError | random.RandomError) -> ^SetAddResult<T>;

fn Set.remove(&self, value: T) -> ^T?;

An absent put transfers both incoming owners to the map and returns Inserted. When an equivalent key is already present, the map preserves the exact stored key as its canonical representative, replaces only the value, and returns Replaced(incoming_key, old_value). Replacing the representative itself is deliberately spelled as remove followed by put; there is no second replacement operation.

An absent add transfers its incoming owner to the set and returns Added. For an equivalent stored value, the set preserves the exact stored representative and returns the incoming owner as Duplicate(incoming_value). The operation never silently drops that owner inside the collection. Discarding the owning result remains an ordinary lexical drop chosen at the call site.

Removal likewise preserves ownership information. HashMap.remove returns the exact stored key and value together as HashMapItem, while Set.remove returns the exact stored representative. A miss returns null. Neither operation allocates, obtains entropy, or throws. There are no parallel take, remove_entry, delete, or boolean-removal spellings.

put and add finish lookup before checking the growth threshold. Replacement and duplicate paths therefore allocate nothing, obtain no entropy, and are runtime-infallible even when the table is otherwise full enough to grow. On an absent insertion, seed acquisition, sizing, allocation, and any rehash preparation finish before the new entry becomes observable. A checked failure leaves the collection's entries, seed state, and capacity unchanged; the moved arguments are cleaned up exactly once by the ordinary throwing-call contract.

Accepted Owner-Preserving Merge Target

HashMap and Set each expose one bulk mutation primitive with the same signature shape:

fn HashMap.merge(
	&self,
	source: &Self,
) throws(AllocError | random.RandomError);

fn Set.merge(
	&self,
	source: &Self,
) throws(AllocError | random.RandomError);

Both the destination receiver and source are exclusively borrowed for the complete call, so they cannot alias. merge transfers every source entry whose canonical key identity is absent from the destination. A map transfers the exact stored key and value owners together; a set transfers the exact stored representative owner. The destination hashes transferred keys with its own private seed. It never adopts or copies the source seed or table allocation.

When the destination already has an equivalent key, it wins completely. For a map, its exact stored key and value remain unchanged; for a set, its exact stored representative remains unchanged. The conflicting source entry also remains unchanged in source. Consequently a successful call leaves the destination holding the logical union and leaves source holding exactly the conflicts:

try destination.merge(&source);

// destination: its original entries plus every non-conflicting source entry
// source:      every exact source entry that conflicted with destination

No key, value, or representative is cloned, reconstructed, combined, replaced, or implicitly dropped. merge returns void: it does not return an inserted count, conflict count, result collection, or cursor. The surviving source collection itself is the explicit owner of every rejected entry.

The operation has a full transactional checked-failure guarantee. Before moving any owner, it determines which source entries can transfer and prepares all required destination capacity plus, when needed, a fresh destination seed. An AllocError or random.RandomError leaves both collections' entries, representatives, table allocations, seeds, controls, tombstones, length, and capacity exactly unchanged. Once the first owner transfers, no checked edge remains.

If every source entry conflicts, or source is empty, merge is a complete no-op: it performs no allocation, requests no entropy, and changes neither collection. Otherwise an unseeded destination obtains its own lazy seed; an already-seeded destination retains its seed. On success source retains its original table allocation and seed even when every entry transferred. Its transferred slots become ordinary removed slots under the private table policy, so it may finish empty but allocated, seeded, and tombstone-bearing.

There is no from_iter, collection-producing collect, extend, insert_all, range insertion, bulk conflict callback, merge_from, append, or other bulk alias. Arbitrary iterator ingestion remains an explicit loop over put or add, where each Replaced or Duplicate owner is handled immediately. This is the exact public mutation vocabulary fixed by RFC 0064, not merely a temporary omission from the current implementation. Apart from the in-place Set.intersect operation below, set-algebra operations and views remain deferred. In particular, there is no returning intersection, union, difference, or symmetric difference. merge remains an owner transfer primitive, not a set-algebra family.

Accepted Lookup Target

The current lookup surface is transitional. The accepted target exposes the exact stored representative together with its value and uses explicit receiver access to select shared or exclusive lookup:

export struct HashMapEntry<K, V, region Source>: Copy {
	export let key: K in Source,
	export let value: V in Source,
}

export struct HashMapExclusiveEntry<K, V, region Source> {
	export let key: K in Source,
	export let value: &V in Source,
}

HashMapEntry is a small Copy pair of shared loans. HashMapExclusiveEntry is affine: its key remains a shared loan, while its value is an exclusive loan. The accepted signatures are:

fn HashMap.get<region Source, region Query>(
	self in Source,
	key: K in Query,
) -> HashMapEntry<K, V>? in Source;

fn HashMap.get<region Source, region Query>(
	&self in Source,
	key: K in Query,
) -> HashMapExclusiveEntry<K, V>? in Source;

fn Set.get<region Source, region Query>(
	self in Source,
	value: T in Query,
) -> T? in Source;

Receiver access, never downstream result use, chooses the map overload:

let found: HashMapEntry<Name, User>? in _ = users.get(query);
let editable: HashMapExclusiveEntry<Name, User>? in _ = (&users).get(query);

The explicit in _ records each local view's inferred source region. An expected result type, later field assignment, or later use cannot turn users.get into exclusive access. There is no get_mut alias.

Both map views expose the exact stored key, not the equivalent query object. If case-insensitive identity considers Name("Alice") and Name("alice") equal, looking up the latter after storing the former observes Name("Alice") in found.key. Likewise, Set.get returns a shared loan of the exact object owned by the set:

let stored: Name? in _ = names.get(query);
if stored != null {
	show(stored); // the set's representative, not query
}

Only map values may be edited in place. Given an exclusive view, editable.value.field = replacement writes through its &V loan. Its key field is shared and cannot be assigned through, so safe code cannot change key identity without remove followed by put. Set has no exclusive get because every stored value is itself a key.

Lookup hit and miss allocate nothing, obtain no entropy, report no error, and do not mutate the table. An empty collection without a seed returns null without creating one. The query is shared-borrowed only for the call; a result borrows the stored collection entry and is tied only to the collection's source region.

A live shared entry or set-value loan blocks structural mutation that could relocate or remove its referent. A live exclusive entry blocks every structural mutation and conflicting access. Once the loan ends, a grow, rehash, insertion, removal, or clear may relocate or invalidate entries; neither view promises a stable address beyond its checked region.

contains is removed from both collections: the sole presence test is get(query) != null. There is also no contains_key, find, get_key_value, at, raw/prehashed lookup, public physical-slot view, or lookup that clones or returns an owned stored value. Ownership leaves the collection only through the RFC 0028 remove operations.

Accepted Set Equality Target

Set<T> exposes one explicit extensional equality operation over its existing canonical T: HashKey identity:

fn Set.equal(self, other: Self) -> bool;

Both sets are shared for the complete call. equal first compares their exact logical length fields. Different lengths return false immediately. For equal lengths, it scans every authoritative Full slot of the left-hand set exactly once and looks up that stored value in the right-hand set. The first missing equivalent value returns false; reaching the end returns true. Lookup uses only T's canonical HashKey hash expansion and equality. It does not compare stored representatives bytewise.

The operation allocates nothing, obtains no entropy, mutates neither set, and cannot report an error. It has expected linear time and quadratic worst-case time. Its result is independent of each set's private seed, capacity, tombstones, physical slot layout, stored representative, and iteration order. The scan order remains unspecified and is not observable through a callback, because equal takes none.

This method does not introduce general collection equality. Neither Set nor HashMap supports == or !=, and neither collection implements Hashable or HashKey. There is no Eq interface. HashMap deliberately has no equal, equal_by, or value-comparison callback: map equality remains an explicit user-written shared iteration and lookup loop using the value relation required by that call. Set has no equal_by; alternate element identity requires a nominal HashKey wrapper type.

Accepted In-Place Set Intersection Target

Set<T> exposes one destructive intersection operation over its existing canonical T: HashKey identity:

fn Set.intersect(&self, other: Self);

The left-hand receiver is exclusively borrowed for the complete call; other is shared for the call and remains exactly unchanged. Ordinary borrow checking therefore rejects aliasing the same set as both operands. There is no runtime self-alias special case and no loan escapes the call.

intersect scans every authoritative Full slot of the left-hand set. It looks up each left representative in other with T's canonical HashKey hash expansion and equality. A hit preserves the exact left representative; the equivalent right representative is never cloned, moved, or substituted. For example, with a case-insensitive Name identity:

// left stores Name("Alice"); other stores equivalent Name("alice").
left.intersect(other);

let kept: Name? in _ = left.get(Name("ALICE"));
// kept is a loan of left's exact Name("Alice") representative.

A miss removes the slot and drops that exact left-owned value once. This is an intentional bulk-destruction operation, analogous to clear, rather than a displaced-owner mutation such as remove. The public drop order is unspecified: it is not insertion order, stable order, reverse order, or a promise to follow increasing physical slots, and may vary with private seed, layout, target, execution, and SDK revision.

When at least one value survives, the general removal path uses ordinary private SwissTable deletion: a removed slot becomes Deleted unless it can safely become Empty. The operation does not rehash, compact, shrink, or free storage. The left set retains its table allocation and seed; its length decreases by the number of misses. Its tombstone-aware logical capacity is recomputed from the resulting table and may change with removal history. The resulting length and capacity become observable only as the completed mutation.

The boundary states are exact:

• an empty left set is an exact representational no-op and performs no right-hand lookup; an existing allocation, seed, controls, and tombstones are all preserved;
• an empty other takes the clear path: every left value is dropped exactly once, every authoritative and mirrored control becomes Empty, old tombstones disappear, length becomes zero, allocation and seed are retained, and logical capacity may increase;
• if both inputs are nonempty but the scan retains no left value, the result is normalized to the same clear-equivalent state: every authoritative and mirrored control is Empty, including old tombstones, while allocation and seed remain retained and logical capacity is recomputed;
• if every left value is present in other, the left set is representationally unchanged: entries, representatives, controls, tombstones, allocation, seed, length, and capacity all remain exact.

intersect supports affine and non-Clone elements. It clones and moves no kept value, allocates and deallocates no storage, obtains no entropy, invokes no callback, returns no owner, count, or cursor, and cannot report an error.

Let S_left and S_other denote the private authoritative physical slot counts, and let N_left be the left logical length at entry. Expected time is O(S_left + N_left); pathological probing gives worst-case O(S_left + N_left * S_other). The S_* quantities are not public capacity. No O(length) scan promise is made, because retained reservations can leave a physically sparse table.

This adds only intersect. There is no returning intersection, union, difference, or symmetric_difference; no subset, superset, or disjoint; no callback-based retain/retain_all; no set operators; and no form_intersection or other alias. Shared predicates remain explicit iter-plus-get loops, owner-transfer union-like work remains merge, and the rest of the algebra family remains deferred.

Accepted Length, Capacity, Reserve, And Clear Target

The checked-in collection sources still expose a physical bucket count as capacity, use their transitional 3/4 load policy, and may allocate a minimum eight-bucket table for reserve(0). The accepted target replaces that behavior with the same logical contract for HashMap and Set:

@readonly export var length: usize,
@readonly export var capacity: usize,

fn reserve(&self, total: usize) throws(AllocError);
fn clear(&self);

Both fields are readable by callers but writable only by methods of their declaring collection. length is the exact number of live distinct entries. An absent put or add increments it, successful removal decrements it, and clear sets it to zero. Replacement, duplicate insertion, lookup, removal miss, and reserve do not change length.

Logical capacity

capacity is a tombstone-aware lower bound on the total live length reachable through consecutive absent insertions without allocating table storage or performing a full-table rehash. It is never below length, and capacity - length is the number of such insertions currently guaranteed. The table may sometimes accept more; reaching the reported bound does not promise that the following insertion must grow.

The field is deliberately not a physical slot count, allocator size, 7/8 load calculation, number of empty control bytes, or target-dependent group property. Those facts, along with growth factor and minimum table shape, remain private. For example, a private 128-slot table may expose a lower logical capacity after deletions have consumed part of its no-rehash growth budget.

The guarantee changes with structural history. An absent insertion consumes one unit of growth budget and normally leaves the total capacity unchanged. A removal represented by Deleted may lower capacity, because the tombstone does not restore an early-termination slot; a removal proven safe to mark Empty may preserve it. Replacement and duplicate insertion leave it unchanged. clear removes every tombstone and may therefore increase reported capacity while retaining the same allocation.

Reserving a total length

reserve(total) names a requested total live length, not an additional count. After success, capacity >= total. If total <= capacity, the operation is a no-op. reserve(0) is unconditionally a no-op, including on a fresh empty collection: it performs no allocation, rehash, seed creation, or entropy request.

When the current guarantee is too small, reserve may transactionally rebuild the same physical table to remove tombstones, or choose a larger private power-of-two table whose 7/8 limit satisfies total. It never shrinks storage. An empty unseeded collection may reserve storage but remains unseeded; reserve never obtains entropy and reports no random.RandomError. Its first successful insertion still obtains the RFC 0026 seed and may report random.RandomError.Unavailable, even though the reserved table needs no allocation.

Every checked layout calculation, allocation, and control-byte initialization finishes before an old entry moves. On AllocError, entries and exact owners, length, capacity, seed state, allocation identity, tombstones, and physical table shape remain unchanged. Once transfer begins, no checked failure edge remains. A successful reserve may relocate every entry, so its exclusive receiver is rejected while any RFC 0029 lookup view is live.

The storage guarantee applies to consecutive absent insertions after the observation or successful reservation. Later removal, clear, or another structural operation may change the reported lower bound. Replacement and duplicate paths remain allocation-free independently of capacity under RFC 0028.

Clearing while retaining resources

clear() is an explicit bulk drop. It drops every live map key/value pair or set value exactly once, sets length to zero, changes every authoritative and mirrored control byte to Empty, and removes every tombstone. It keeps the single table allocation and an existing private seed. An unseeded collection remains unseeded. The operation allocates nothing, obtains no entropy, and cannot throw. Its public drop order is unspecified and does not promise insertion, stable, reverse, or physical-slot order.

Because clear keeps storage but restores the complete empty-slot budget, its logical capacity may increase. It invalidates every view of a removed entry and therefore requires exclusive access with no live shared or exclusive entry loan. Unlike remove, clear intentionally returns no owners: its name is the caller's explicit request to destroy all entries.

There are no length()/capacity() methods or len, size, count, and is_empty aliases. There is also no reserve_additional, ensure_capacity, try_reserve, reserve_exact, shrink, shrink_to, shrink_to_fit, trim, compact, rehash, reset, purge, remove_all, clear_and_free, or clear_and_shrink. There are no public slot-count, tombstone-count, load-factor, or growth-budget getters. reserve_exact would expose private rounding, while manual compaction would expose engine policy. Releasing storage and returning to a fresh unseeded state is ordinary replacement or drop of the complete collection, not another collection method.

Ownership, Allocation, And Errors

An ^[T] owns its backing buffer and frees it (dropping each element) on drop; bare [T] and &[T] borrow storage and free nothing. clone creates independent storage. Growth through push, reserve, and insert, plus clone and owning slice literals, reports out-of-memory as AllocError, like str; clear, pop, and remove do not allocate and cannot throw. The checked consuming methods drop the taken receiver and element exactly once on failure and do not return a recovery owner.

HashMap and Set own their backing storage in the built-in process-allocation domain and accept keys implementing one canonical std.hash.HashKey identity. Their sole constructors are HashMap<K, V>() and Set<T>(); they accept no allocator, capacity, hash, equality, hasher-policy, or seed argument. Alternate identity is represented by a nominal wrapper key. Growth may throw AllocError; the first absent put or add also obtains a private seed and may report random.RandomError.Unavailable. There is no deterministic fallback. Empty construction and reserve obtain no entropy, and clear retains its allocation and an already-created seed.

Conditional collection clone uses the same built-in allocation domain. It copies the existing seed and exact table state instead of obtaining entropy or rehashing, so it reports AllocError but never random.RandomError.

Collection merge may likewise allocate in the built-in domain, and may obtain a destination seed only when at least one owner must transfer into an unseeded destination. Its complete preflight makes AllocError and random.RandomError full rollback edges for both inputs. A successful merge retains each collection's own seed and table ownership domain.

Set.intersect allocates and deallocates no storage, obtains no entropy, and cannot throw. It retains the left allocation and seed, leaves the right set unchanged, and intentionally drops only left representatives missing from the right set in unspecified order.

Successful mutation never destroys a displaced owner inside the collection. HashMap.put returns an unused equivalent incoming key and the replaced stored value, Set.add returns an unused equivalent incoming value, and removal returns the exact stored owner or owners. The checked-in boolean/partial-owner results remain transitional until this accepted API is implemented.

Explicit-comparator sorting and binary search for [T] slices live in std.slice (sort and binary_search); neither throws or allocates.

Element order for HashMap and Set is unordered, private-seed-dependent, and may differ between maps, executions, targets, and SDK revisions. Growth strategy, capacity rounding, hash-table bucket layout, and when storage is reused are also unspecified. Deterministic output explicitly collects and sorts entries; do not depend on physical iteration order.

Set.equal is the sole collection equality operation. It observes only extensional membership under the element type's canonical HashKey identity; it does not expose or compare the unspecified representation details above.

Accepted Cursor And Iteration Target

The checked-in HashMapEntryIter, HashMapKeyIter, HashMapValueIter, SetEntry, and SetEntryIter types and the entries, keys, and values methods are transitional. The accepted surface has exactly five concrete, affine, non-default, package-constructed cursor types:

export struct HashMapIter<K, V, region Source> { /* private */ }
export struct HashMapExclusiveIter<K, V, region Source> { /* private */ }
export struct HashMapOwnedIter<K, V>: iter.Iterator<HashMapItem<K, V>> {
	/* private */
}

export struct SetIter<T, region Source> { /* private */ }
export struct SetOwnedIter<T>: iter.Iterator<T> { /* private */ }

The cursors have no public fields, raw positions, control-byte access, or public constructors. Their leading ^ result role denotes ownership of the cursor value, not a heap allocation. Creating any cursor allocates nothing, obtains no entropy, and cannot throw. Every cursor is affine and none implements Copy or Clone, independently of the stored element capabilities.

Role-selected iter

Receiver access selects the only operation name, iter:

fn HashMap.iter<region Source>(self in Source)
	-> ^HashMapIter<K, V> in Source;
fn HashMap.iter<region Source>(&self in Source)
	-> ^HashMapExclusiveIter<K, V> in Source;
fn HashMap.iter(^self) -> ^HashMapOwnedIter<K, V>;

fn Set.iter<region Source>(self in Source)
	-> ^SetIter<T> in Source;
fn Set.iter(^self) -> ^SetOwnedIter<T>;

map.iter() is shared, (&map).iter() is exclusive, and (<-map).iter() consumes a named map. Expected cursor type, loop binding, and later mutation never select an overload. Borrowed cursor bindings record their inferred source region explicitly:

let read: ^HashMapIter<K, V> in _ = map.iter();
let edit: ^HashMapExclusiveIter<K, V> in _ = (&map).iter();
let take: ^HashMapOwnedIter<K, V> = (<-map).iter();

Set deliberately has no iter(&self): every stored value is a key, so an exclusive element loan could invalidate identity and placement.

Pulling entries directly

The exact next methods are:

fn HashMapIter.next<region Step>(&self in Step)
	-> HashMapEntry<K, V>? in Source;
fn HashMapExclusiveIter.next<region Step>(&self in Step)
	-> HashMapExclusiveEntry<K, V>? in Step;
fn HashMapOwnedIter.next(&self) -> ^HashMapItem<K, V>?;

fn SetIter.next<region Step>(&self in Step) -> T? in Source;
fn SetOwnedIter.next(&self) -> ^T?;

A shared result borrows the collection's Source, not the call-local Step. Several shared entry views may coexist and may outlive the cursor, but never the collection. An exclusive map result borrows in the fresh Step; it exposes the exact shared stored key plus an exclusive value loan and prevents another next until that result ends. It is an ordinary structural affine-view cursor, not a HashMap compiler special case and not an ExclusiveIterator<HashMapEntry> implementation. Returning &HashMapEntry would incorrectly make the key mutable; ExclusiveIterator<T> remains unchanged for collections whose entire T may be mutated.

Stored results spell their regions explicitly:

let read_cursor: ^HashMapIter<K, V> in _ = map.iter();
let first: HashMapEntry<K, V>? in _ = read_cursor.next();

let edit_cursor: ^HashMapExclusiveIter<K, V> in _ = (&map).iter();
let current: HashMapExclusiveEntry<K, V>? in _ = edit_cursor.next();

let owned_cursor: ^HashMapOwnedIter<K, V> = (<-map).iter();
let item: ^HashMapItem<K, V>? = owned_cursor.next();

All five next operations are infallible and allocate nothing. Exhaustion is sticky: every later next returns null.

Loop forms

The corresponding loop forms are:

for entry: HashMapEntry<K, V> in _ in map {
	inspect(entry.key, entry.value);
}

for entry: HashMapExclusiveEntry<K, V> in _ in &map {
	inspect(entry.key);
	entry.value.enabled = true;
}

for item in <-map {
	consume_key(<-item.key);
	consume_value(<-item.value);
}

for value: T in _ in set {
	inspect(value);
}

for value in <-set {
	consume(<-value);
}

The explicit &map selects only the exclusive cursor; the affine entry binding names its fresh local region with in _. The key remains shared. A named consuming source requires <-; a fresh owning temporary already has its owner role and needs no marker. None of these loops uses try because acquisition and next are infallible.

Loans, scanning, and cleanup

HashMapIter and SetIter hold one shared source loan for the cursor's whole lifetime. Structural mutation, reserve, clear, and consuming iteration are blocked, while compatible shared observations may coexist. HashMapExclusiveIter holds one exclusive map loan for its whole lifetime; the map name is unavailable, and only the current entry's value may be changed. Each exclusive Step ends before the next backedge or direct next call.

Every cursor scans authoritative control bytes, visits each Full slot exactly once, and ignores Empty, Deleted, and mirrored suffix bytes. Iteration does not rehash keys or call equality. Order is unordered and may depend on the private seed, insertion/deletion history, target group width, and previous rehashes. Mutating a value through the exclusive cursor changes no control byte, key, length, capacity, seed, or position.

Dropping or exhausting a borrowed cursor only ends its source loan; it never drops collection entries. A consuming cursor owns the table, seed, and every still-armed entry, but no allocator owner or capability. Before yielding, next disarms the selected slot. Normal exhaustion releases table storage through the statically known built-in allocation domain exactly once and leaves a permanently empty cursor.

For a loop-owned temporary created by for item in <-map or for value in <-set, break, return, or checked failure first drops the current unmoved loop item; the temporary cursor then drops all still-armed residual entries in reverse of its private scan order and releases storage once. A separately named consuming cursor is exclusively borrowed by for instead. break releases that loan and preserves its exact residual state for a later loop or direct next; its owners and storage drop only at the cursor's own owner boundary. Writing <-cursor explicitly opts back into loop-owned cleanup. None of these rules promises reverse insertion order. continue drops an unmoved current item, a moved item is not dropped twice, and the original collection remains moved. Runtime traps remain non-unwinding.

There is no entries, keys, values, iter_mut, into_iter, drain, owned_iter, cursor, begin/end, stable/reverse iterator, or raw bucket iterator. Shared map iteration already returns an entry whose fields are the only key/value projections; shared set iteration returns T directly. Receiver role is the sole semantic selector under the one name iter.

Related Modules

Use std.slice for owning-slice growth semantics and its sole explicit-comparator sort/binary_search path, std.iter for iterator interfaces and adapters, std.mem for the shared AllocError value, std.hash for hash interfaces and checksum-style hashers, and std.ordering for the Ordering enum and ready-made explicit comparators.

API Reference

Types

Type	Kind	Public fields	Methods	Description
[T], &[T], ^[T]	built-in slice roles	Views: length, ptr; owner additionally: capacity	Owner: push, reserve, clear, insert, pop, remove; shared receiver: clone; all roles: []	Shared view, mutable view, and owning slice respectively. Only the owner frees and may replace its buffer.
HashMap<K: HashKey, V>	struct	@readonly var length, @readonly var capacity	put, get, remove, merge, reserve, clear, clone, iter	Hash map with the sole empty constructor HashMap<K, V>(), built-in allocation, canonical key identity, a private lazy keyed-hash seed, conditional structural Clone, owner-preserving merge, exact live length, logical capacity, and role-selected iteration. It has no collection equality operation.
HashMapEntry<K, V, region Source>	struct: Copy	key, value	None	Accepted shared lookup view of the exact stored key and value. Both fields borrow in Source.
HashMapExclusiveEntry<K, V, region Source>	affine struct	key, value	None	Accepted exclusive lookup view: shared stored key plus exclusive stored value.
HashMapItem<K, V>	struct	key, value	None	Accepted owning result of successful HashMap.remove; both fields are the exact stored owners.
HashMapPutResult<K, V>	enum	Inserted, Replaced(incoming_key, old_value)	None	Accepted owning insertion result; replacement preserves the stored key and returns both displaced owners.
SetAddResult<T>	enum	Added, Duplicate(incoming_value)	None	Accepted owning set-insertion result; a duplicate returns the incoming owner.
HashMapIter<K, V, region Source>	affine struct	None	next	Shared map cursor yielding exact stored HashMapEntry views in Source.
HashMapExclusiveIter<K, V, region Source>	affine struct	None	next	Exclusive projection-lending map cursor yielding one HashMapExclusiveEntry per fresh Step.
HashMapOwnedIter<K, V>	affine struct: Iterator<HashMapItem<K, V>>	None	next	Consuming map cursor owning table storage and unyielded entries.
SetIter<T, region Source>	affine struct	None	next	Shared set cursor yielding the exact stored representative in Source.
SetOwnedIter<T>	affine struct: Iterator<T>	None	next	Consuming set cursor owning table storage and unyielded values.
Set<T: HashKey>	struct	@readonly var length, @readonly var capacity	add, get, remove, merge, intersect, reserve, clear, clone, equal, iter	Hash-backed set with the sole empty constructor Set<T>(), built-in allocation, canonical key identity, a private lazy keyed-hash seed, conditional structural Clone, owner-preserving merge, in-place intersect, extensional equal, exact live length, logical capacity, and shared/consuming iteration.

Collection Constructors

These are the complete accepted constructor surface for the core associative collections:

Name	Signature	Parameters	Initial state	Description
HashMap	HashMap<K, V>()	None	length == 0, capacity == 0, unallocated, unseeded	Infallibly creates an empty map in the built-in allocation domain.
Set	Set<T>()	None	length == 0, capacity == 0, unallocated, unseeded	Infallibly creates an empty set in the built-in allocation domain.

Use reserve(total) after construction when a logical total capacity guarantee is needed. It is the only preallocation spelling and remains seed-neutral.

Hash Collection Clone

clone is available only under the structural component rule above. Self remains the exact same collection instantiation:

Type	Signature	Availability	Returns	Description
HashMap<K, V>	clone(self) throws(AllocError) -> ^Self	Each of K and V is Copy, or is non-Copy and implements Clone	^HashMap<K, V> throws(AllocError)	Independent owners in a distinct exact structural table copy; preserves seed and capacity and performs no entropy, hashing, or equality.
Set<T>	clone(self) throws(AllocError) -> ^Self	T is Copy, or is non-Copy and implements Clone	^Set<T> throws(AllocError)	Independent stored owners in a distinct exact structural table copy; preserves seed and capacity and performs no entropy, hashing, or equality.

Slice Methods

Only ^[T] has growth and editing methods. They consume the receiver and return its successor, so a named take is explicit (xs = try (<-xs).push(<-value)). [T] and &[T] have no such surface. pop and remove return owning tuples and do not throw. clone instead uses a shared receiver and returns a new independent owner.

Method	Signature	Parameters	Returns	Description
push	push(^self, value: ^T) throws(AllocError) -> ^[T]	value: moved element	^[T] throws(AllocError)	Appends one element; reuses sufficient capacity and otherwise grows at most once.
reserve	reserve(^self, total: usize) throws(AllocError) -> ^[T]	total: requested total element capacity	^[T] throws(AllocError)	Returns the exact owner unchanged when already satisfied; otherwise grows at most once.
clear	clear(^self) -> ^[T]	None	^[T]	Reverse-drops all elements, sets length to zero, and retains pointer and capacity.
insert	insert(^self, index: usize, value: ^T) throws(AllocError) -> ^[T]	index: position, value: moved element	^[T] throws(AllocError)	Inserts at index <= length; reuses capacity or grows at most once. Larger indices trap.
pop	pop(^self) -> ^(^[T], ^T?)	None	^(^[T], ^T?)	Returns the successor and last element; empty input returns the exact owner and null.
remove	remove(^self, index: usize) -> ^(^[T], ^T)	index: position	^(^[T], ^T)	Removes at index, retains capacity, and traps when index >= length.
clone	clone(self) throws(AllocError) -> ^[T]	None	^[T] throws(AllocError)	Shared source; available for Copy elements or non-Copy elements implementing Clone.
[]	xs[index]	index: position	element	Reads or assigns an element. Reading a whole owning element moves it, so index a field (xs[i].field) to borrow.

Slice Fields And Literals

All slice roles expose length (initialized element count) and ptr. Only ^[T] exposes readonly logical capacity. Shared views expose *T; mutable views and owners expose *mut T. Iterate with for x in xs. ^[...] is the only dynamic owning literal: nonempty forms require try or catch for AllocError, while ^[] is infallible. Plain [...] remains an inline fixed array and never allocates.

Already-satisfied reserve(total) and growth with sufficient capacity are allocator no-ops. Capacity rounding is private, but repeated successful push is amortized constant time. clear, pop, and remove retain allocation and capacity; assignment of ^[] is the explicit release spelling. A failure of a checked consuming operation drops each owner written with <- and leaves its source moved. For zero-sized elements, length and capacity stay logical and destructors still run even though growth performs no physical allocation. There is no slice append, Taken<T>, reserve variant, capacity constructor, shrink/resize family, or unchecked-capacity method.

Set Methods

The signatures below are the accepted target. The checked-in source still exposes boolean add/remove, contains, and no stored-representative get during migration.

Method	Signature	Parameters	Returns	Description
add	add(&self, value: ^T) throws(AllocError | random.RandomError) -> ^SetAddResult<T>	value: moved value to insert	^SetAddResult<T> throws(AllocError | random.RandomError)	Returns Added after transfer; an equivalent stored representative remains unchanged and the incoming owner returns as Duplicate. Lookup precedes growth.
get	get<region Source, region Query>(self in Source, value: T in Query) -> T? in Source	value: shared query	T? in Source	Returns a shared loan of the exact stored representative, or null; presence is get(value) != null.
equal	equal(self, other: Self) -> bool	other: shared set	bool	Extensional equality under T: HashKey: compares length, then scans the left set and looks up every value in the right set. No allocation, entropy, mutation, callback, or error.
merge	merge(&self, source: &Self) throws(AllocError | random.RandomError)	source: exclusively borrowed source set	void throws(AllocError | random.RandomError)	Moves every exact non-conflicting source owner into the destination; conflicts remain in source. Full rollback on checked failure; all-conflict is allocation- and entropy-free.
intersect	intersect(&self, other: Self)	other: shared set	void	Keeps exact left representatives present in other and explicitly drops the left complement in unspecified order. Retains left allocation/seed, leaves other unchanged, and performs no allocation, deallocation, entropy request, callback, or error.
remove	remove(&self, value: T) -> ^T?	value: value to find	^T?	Removes and returns the exact stored representative, or null; does not allocate, obtain entropy, or throw.
reserve	reserve(&self, total: usize) throws(AllocError)	total: requested total live length	void throws(AllocError)	After success capacity >= total; total <= capacity, especially zero, is a no-op. May clean tombstones or grow transactionally without obtaining entropy.
clear	clear(&self)	None	void	Explicitly drops all values, clears every tombstone/control byte, and retains allocation plus any seed; does not allocate or throw.

HashMap Lookup Methods

The two get overloads are selected only by written receiver access. The checked-in source still returns value-only loans and retains contains.

Call	Signature	Returns	Description
map.get(key)	get<region Source, region Query>(self in Source, key: K in Query) -> HashMapEntry<K, V>? in Source	HashMapEntry<K, V>? in Source	Shared exact stored key/value view, or null.
(&map).get(key)	get<region Source, region Query>(&self in Source, key: K in Query) -> HashMapExclusiveEntry<K, V>? in Source	HashMapExclusiveEntry<K, V>? in Source	Affine exact stored-key/exclusive-value view, or null; never grants a mutable key loan.

HashMap Mutation Methods

These are likewise accepted target signatures; the current source still has partial-owner results.

Method	Signature	Parameters	Returns	Description
put	put(&self, key: ^K, value: ^V) throws(AllocError | random.RandomError) -> ^HashMapPutResult<K, V>	key, value: moved owners	^HashMapPutResult<K, V> throws(AllocError | random.RandomError)	Transfers both owners on insertion. Replacement keeps the stored key, installs the incoming value, and returns Replaced(incoming_key, old_value) without allocation or entropy.
merge	merge(&self, source: &Self) throws(AllocError | random.RandomError)	source: exclusively borrowed source map	void throws(AllocError | random.RandomError)	Moves every exact non-conflicting source key/value pair into the destination; destination conflicts win and remain in source. Full rollback on checked failure.
remove	remove(&self, key: K) -> ^HashMapItem<K, V>?	key: key to find	^HashMapItem<K, V>?	Removes and returns the exact stored key and value, or null; does not allocate, obtain entropy, or throw.

HashMap Capacity Methods

HashMap uses the same RFC 0030 contract as Set:

Method	Signature	Parameters	Returns	Description
reserve	reserve(&self, total: usize) throws(AllocError)	total: requested total live length	void throws(AllocError)	After success capacity >= total; zero and every already-satisfied request are no-ops. Tombstone cleanup or growth has the strong transactional guarantee.
clear	clear(&self)	None	void	Explicitly drops all entries, resets controls/tombstones, and retains allocation plus any seed; does not allocate or throw.

Cursor Methods

Cursor	next signature	Yield
HashMapIter<K, V>	next<region Step>(&self in Step) -> HashMapEntry<K, V>? in Source	Shared exact stored key/value view tied to collection Source.
HashMapExclusiveIter<K, V>	next<region Step>(&self in Step) -> HashMapExclusiveEntry<K, V>? in Step	Fresh affine shared-key/exclusive-value view; blocks the next step while present.
HashMapOwnedIter<K, V>	next(&self) -> ^HashMapItem<K, V>?	Exact stored key and value owners after disarming the slot.
SetIter<T>	next<region Step>(&self in Step) -> T? in Source	Shared exact stored representative tied to collection Source.
SetOwnedIter<T>	next(&self) -> ^T?	Exact stored owner after disarming the slot.

Status

std.collections is the current public container API for HashMap and Set; the growable owned sequence is the built-in slice ^[T], constructed with ^[...]. For the full exported surface, see Standard Library Inventory.