collections

Six containers, all built on alloc and all generic over the allocator with a GlobalAlloc default. Each owns heap storage and exposes drop(mut &this); the compiler synthesises the call at scope exit.

Type	Import	Shape
Array<T, A>	(prelude)	Growable contiguous sequence
Str	import std::collections::str;	Borrowed UTF-8 view
String<A>	import std::collections::string;	Owned growable UTF-8
HashMap<K, V, A>	import std::collections::hashmap;	Separate-chaining hash table
HashSet<T, A>	import std::collections::hashset;	Unique values, over HashMap<T, ()>
Pair<A, B>	import std::collections::pair;	Owned two-element tuple

A note on Copy-gated methods#

Several methods across these containers carry a where T: Copy bound — get, iter, append, resize. The reason is the same every time: they hand back an independent bitwise duplicate while the container still owns the stored element. That is only sound when T has no drop obligation; otherwise both copies would own the same heap buffer and both would free it.

For an owning element type, reach for the borrowing counterpart instead: get_ref rather than get, iter_ref rather than iter, entries / keys_ref / values_ref on a map. Those hand out pointers, never copies, and are sound for every T.

Array<T, A>#

A growable, heap-backed, contiguous sequence. T[] desugars to Array<T>, which is why it is in the prelude. Push and pop at the end are amortized O(1); indexed access is O(1). Growth doubles capacity, starting at 4.

Algorithms that do not need ownership should take a Slice<T> — call as_slice() at the boundary and write the algorithm once.

mut names: Array<String> = Array<String>::new();
names.push(String::from("ada"));
names.push(String::from("grace"));

for (n in names.iter_ref()) {
    printf("%s\n", n.as_cstr());
}

Constructing#

Constructor	Notes
static new()	Empty, backed by GlobalAlloc.
static new_in(alloc: A)	Empty, with your allocator.
static with_capacity(capacity: u64)	Preallocates. Panics on allocation failure.
static with_capacity_in(capacity: u64, alloc: A)
static try_with_capacity_in(capacity: u64, alloc: A)	Result<Array<T, A>, AllocError>

The free function from_iter<I, T>(it: I) -> Array<T> collects an iterator into a fresh array:

mut squares: Array<i32> = from_iter((0..10).map(square));

It is a free function rather than an Iterator::collect default for a specific reason: a non-self-returning trait default gets cloned into every Iterator impl, including the by-reference cursor over Array<T> — whose clone would instantiate Array<T>, then Array<T*>, then Array<T**>, diverging until it ran out of memory. As a free function only concrete call sites instantiate it.

Reading#

Method	Returns	Notes
length() / capacity() / is_empty()	u64 / u64 / boolean
get(index: u64) (where T: Copy)	Option<T>	Bounds-checked read by value.
get_ref(index: u64)	Option<T*>	Bounds-checked borrow; sound for every T.
first() / last()	Option<T*>	Borrowed; None when empty.
as_ptr() / as_slice()	T* / Slice<T>
index_of(value: &T) (where T: Eq)	Option<u64>	Linear scan.
contains(value: &T) (where T: Eq)	boolean

Every pointer, slice, and iterator handed out here is invalidated by any method that may reallocate — push, insert, reserve, shrink_to_fit.

Iterating#

• iter() (where T: Copy) yields each element by value.
• iter_ref() yields T* and is sound for every T. This is how you walk an Array<String> or Array<Box<...>> without cloning.
• iter_ref().copied() (where T: Copy) and iter_ref().cloned() (where T: Clone) turn the borrowing cursor back into a by-value one.

Modifying#

Method	Notes
push(value: T) / try_push(value: T)	Append. try_push returns Result<(), AllocError>.
pop()	Option<T> from the end.
insert(index: u64, value: T)	Shifts later elements right. index == length appends; panics beyond that.
remove(index: u64)	T, shifting later elements left — O(n), order preserved.
swap_remove(index: u64)	T in O(1) by swapping in the last element. Does not preserve order.
reverse()	In place. Sound for owning T.
append(source: Slice<T>) (where T: Copy)	Bulk memcpy. try_append reserves up front, so a partial copy is impossible.
resize(new_length: u64, value: T) (where T: Copy + Drop)	Sets the length exactly, filling new slots with value.
reserve(additional: u64) / reserve_exact	Result<(), AllocError>
shrink_to_fit()	Return unused capacity.

resize is how you build a fixed-size read buffer. An array only exposes [0, length), so with_capacity alone leaves nothing to read into.

Sorting#

sort() (where T: Ord) sorts ascending in place using a hybrid in-place quicksort: median-of-three pivot above a cutoff of 16 elements, insertion sort below it. O(n log n) average, no allocation. Two caveats: it is not stable, and the worst case is O(n²) — v1.0 has no introsort fallback. Owning elements are moved with mem::swap, so the drop obligation stays intact.

sort_by(less: (&T, &T) -> boolean) takes your own strict-weak-ordering predicate. It must be a function pointer; non-capturing lambdas convert implicitly, and a capturing closure in method position is rejected (E0458) in v1.0. Capture by indirection, or pull the sort into a free function.

Trait impls#

Clone (deep copy, requires T: Clone), Default (a fresh empty array, allocating nothing), Eq (equal length, equal elements in order), and Hash (folds the length first, so [1, 2] and [1, 2, 0] differ).

Str#

A borrowed UTF-8 slice: (bytes, length) over memory the caller guarantees outlives the view. There is no NUL terminator — the length is authoritative.

Constructor	Notes
static new(text: string)	From a NUL-terminated C string literal. The NUL is not part of the view. This is the implicit string to Str conversion.
static from_raw(bytes: u8*, length: u64)	Raw pointer plus length.
static from<T>(src: T)	Compile-time dispatch over string (length via strlen) and Slice<u8> (borrowed verbatim).

Method	Returns
length() / is_empty()	u64 — bytes, not scalars — / boolean
as_bytes() / as_ptr()	Slice<u8> / u8*
byte_at(index: u64)	Option<u8>
sub_bytes(start: u64, end: u64)	Str
equals(other: &Str)	boolean
starts_with / ends_with(&Str)	boolean
find(needle: &Str)	Option<u64>
contains(needle: &Str)	boolean
trim() / trim_start() / trim_end()	Str
to_ascii_lowercase() / to_ascii_uppercase()	String — these allocate
split(sep: &Str)	implement Iterator<Str>
chars()	implement Iterator<u32> — decoded scalars
char_indices()	implement Iterator<Pair<u64, u32>> — byte offset and scalar
try_to_hex()	Result<u64, ConversionError>

Str implements Eq, Ord (lexicographic), and Hash, so it works as a HashMap key.

Parsing numbers#

TryFrom<Str> is implemented for every integer width, which is how you parse text:

import std::collections::str;
import std::core::convert;

match (u32::try_from(arg)) {
    Result::Ok(n)  => { /* parsed */ }
    Result::Err(e) => { printf("not a number: %s\n", e.describe().as_ptr()); }
}

String<A>#

The owned, growable companion to Str: a heap byte buffer plus a length. No NUL terminator, no encoding assumptions beyond "the bytes are valid UTF-8".

Constructor	Notes
static new() / new_in(alloc: A)	Empty.
static with_capacity(capacity: u64)	Preallocated. try_with_capacity_in is the fallible form.
static from_str(source: Str)	Copy a borrowed view into owned storage.
static from_string(text: string)	Copy a C string.
static from<T>(item: T)	The general constructor — same dispatch as push.
static with_null(source: Str)	Owned copy that keeps a trailing NUL for the FFI boundary.

Appending#

push<T> appends item as its text representation, dispatched at compile time through static match (T) — no runtime cost and no trait bound, because the available arms are the accepted types:

• Str, String, and string — the UTF-8 bytes verbatim (a string's terminating NUL is not copied).
• Every primitive integer — its decimal text. s.push(65 as u8) appends "65".
• f32 and f64 — their Display text.
• boolean — "true" or "false".

Anything else is a compile error; the static match has no _ arm.

mut s: String = String::new();
s.push("count: ");
s.push(42);            // "count: 42"
s.push_byte(0x0A);     // a raw newline byte

push_byte appends a single raw byte rather than its decimal text — for NUL terminators, control characters, and binary buffers. Keeping the result valid UTF-8 is your responsibility. Both have try_ forms returning Result<(), AllocError> instead of panicking.

Reading and borrowing#

length(), capacity(), is_empty(), as_str() -> Str, as_bytes() -> Slice<u8>, as_ptr() -> u8*, plus clear(), truncate(new_length), reserve, reserve_exact, and shrink_to_fit.

The Str conveniences are forwarded so you don't write s.as_str().starts_with(...) everywhere: starts_with, ends_with, find, contains, trim, trim_start, trim_end, to_ascii_uppercase, to_ascii_lowercase, split, chars, and char_indices. Everything they return borrows this string's buffer and is valid only while it lives unmutated.

Crossing into C#

A String built by push carries no trailing NUL, so as_ptr() alone is not a valid C string. Two methods bridge the gap:

• as_cstr(mut &this) -> u8* borrows the buffer as a NUL-terminated C string. It writes the terminator at index length — reserving one spare byte if the buffer is full — without changing the logical length. Idempotent and zero-allocation once the spare byte exists. The pointer is valid until the next mutating call and must not be freed by the caller.
• into_raw(mut this) -> string consumes the string, appends a terminator, and hands back the raw buffer, leaking the allocation so the caller owns the bytes outright.

As in C, an interior NUL ends the string early; the bytes are not otherwise validated.

String implements Eq, Ord, Hash, Clone, Default, and Display.

HashMap<K, V, A>#

Separate chaining over a bucket array: each bucket holds a linked list of entries. Keys must implement Hash + Eq.

import std::collections::hashmap;

mut counts: HashMap<Str, u64> = HashMap<Str, u64>::new();
mut slot: u64* = counts.get_or_insert(word, 0);
*slot = *slot + 1;

Method	Returns	Notes
insert(key: K, value: V)	Option<V> — the replaced value	try_insert is the fallible form.
get(key: &K) (where V: Copy)	Option<V>
get_ref(key: &K)	Option<V*>	Sound for owning values.
get_or_insert(key: K, default: V)	V*	try_get_or_insert is the fallible form.
remove(key: &K)	Option<V>
contains_key(key: &K)	boolean
length() / is_empty() / clear()
bucket_count()	u64	Buckets allocated, not capacity — chaining means a bucket holds many entries.
get_bucket(index: u64)	Entry<K, V>*	Head of a chain, for manual traversal. Null when empty or out of range.

Iterating#

iter(), keys(), and values() yield by value and carry Copy bounds. entries(), keys_ref(), and values_ref() yield Pair<K*, V*>, K*, and V* respectively, and are sound for any key and value type — so they are what you want for a HashMap<String, Foo>. Order is bucket-major and unstable across resizes; every borrow is invalidated by any insert, remove, or resize.

Hash seeding#

The hasher is FNV-1a, seeded per map from a per-process random value drawn from the kernel CSPRNG. Bucket placement therefore varies between runs, so adversarial keys cannot be precomputed to flood a single bucket. FNV-1a is not collision-resistant, so treat this as hardening rather than a cryptographic guarantee — supply a custom hasher where it matters.

with_seed(seed) and with_seed_in(seed, alloc) fix the seed for tests that need reproducible layout or iteration order. Production code should use new.

Chaining was chosen over open addressing because it sidesteps storing uninitialized key/value slots. The cost is one heap allocation per entry.

Clone requires K: Hash + Eq + Clone and V: Clone. Default is a fresh empty map that allocates no buckets until the first insert.

HashSet<T, A>#

A thin wrapper over HashMap<T, ()> with the same storage, hasher, and growth behaviour, plus friendlier names. T must implement Hash + Eq.

new, new_in, with_capacity, with_seed, length, is_empty, clear, contains(value: &T) -> boolean, insert(value: T) -> boolean (true when the value was newly added), try_insert, remove(value: &T) -> boolean, iter() (where T: Copy), and iter_ref() -> implement Iterator<T*> for owning element types.

Pair<A, B>#

An owned two-element tuple — first: A, second: B. It owns both members and drops them in declaration order. The fields are public; there are no getters.

Use it wherever you would otherwise reach for two parallel arrays or a single-purpose struct:

• Key-value entries. Pair<Str, Config>[] is a small associative list, cheaper than a HashMap when the count is in the low tens and the keys need no Hash impl.
• Multi-return without naming a type. function divmod(...) -> Pair<i64, i64>.
• Zipping. Pair is the element type of Iterator::zip and Iterator::enumerate, because Cryo has no heterogeneous tuple literal.

Drop, Eq, and Clone are parametric: a Pair has each when both members do.