Collections
std/collections ships three generic containers:
ArrayList<T>: a growable array. Positions are dense,0tosize() - 1, so it is the right choice for an ordered sequence you read by index.HashMap<K, V>: a key-to-value table. A lookup costs one probe into a SwissTable-style open-addressing table, not a scan.HashSet<T>: a set of distinct values. Itsaddanswers “was this new?” in one probe, which makes deduplication a one-liner.
Each container is generic, but the generic is resolved at compile time. The
compiler generates one specialised body per element type you use, so an ArrayList<i32> and an ArrayList<string> never share code that has to
check types at run time.
ArrayList<i32> ──▶ body compiled for i32 slots
ArrayList<string> ─▶ body compiled for string slots (owned copies)
HashMap<string, i32> ─▶ probes by string hash, values as i32 Note The element type decides what a container can hold. Keys of a
HashMapand elements of aHashSetmust be hashable:i32,i64,string, or a class instance (hashed by identity).f64is refused for both, because NaN and float precision make equality unreliable. Collect floats in anArrayList<f64>instead.
ArrayList<T>: dynamic array
use std::collections::ArrayList;
fn main() : i32 ! IndexOutOfBoundsException {
let list : ArrayList<i32> = new ArrayList<i32>();
list.add(10);
list.add(20);
list.add(30);
if (list.size() != 3) { return 1; }
if (list.get(0) != 10) { return 2; }
if (!list.contains(20)) { return 3; }
list.set(1, 200); // bool: false, nothing written, past the end
let removed : i32 = list.removeAt(0); // returns 10; removeAt throws on a bad index
if (removed != 10) { return 4; }
if (list.size() != 2) { return 5; }
list.clear();
if (!list.isEmpty()) { return 6; }
return 0;
} Method reference
| Method | Returns | Effect |
|---|---|---|
add(v) | bool | append; always true (an append always changes the list) |
reserve(capacity) | void | grow the backing buffer to at least capacity slots |
get(i) | T \| null | indexed read; null when i is out of range; never throws |
getOrDefault(i, default) | T | indexed read; default past the end |
getUnchecked(i) | T | the same read with the bounds guard removed; the caller guarantees 0 <= i < size() |
set(i, v) | bool | indexed write; false, nothing written, when i is outside [0, size) |
setUnchecked(i, v) | void | the same write with the bounds guard removed |
replace(i, v) | T | indexed write; returns the value it displaced; throws IndexOutOfBoundsException |
removeAt(i) | T | delete at i and return the removed value; throws IndexOutOfBoundsException |
pop() | T \| null | delete and return the last element; null when empty; constant time, no allocation |
indexOf(v) | i64 | first index of v, or -1 |
contains(v) | bool | membership test |
size() | i64 | element count |
isEmpty() | bool | true when size() is 0 |
clear() | void | remove every element |
sort() | void | ascending, in place (see Sorting and searching) |
sortDescending() | void | descending, in place |
reserve(n) makes a bulk load pay one allocation instead of the doubling
sequence. Call it when you know the final size, then add n times without
a reallocation in between.
Why removeAt is not a pop
removeAt(0) on [A, B, C, D]
before: [A][B][C][D]
after: [B][C][D] every survivor shifts left: O(n)
└── copied into a fresh buffer: one malloc per call removeAt(i) is O(n) and reallocates: it copies the surviving elements
into a fresh backing buffer to keep exactly one live reference per element.
To take from the end, use pop(). It is the constant-time, allocation-free
member, the right tool when the list is a stack. Reach for removeAt only
when the position itself is what you care about.
Throwing and non-throwing access
replace and removeAt throw IndexOutOfBoundsException on a bad index. set is the non-throwing twin: past the end it answers false and writes
nothing. get never throws; it returns T | null, so it needs neither a ! clause nor a catch.
The example above lists the exception in main’s ! set, so it propagates.
To handle it at the call site, the try statement covers a call whose value
you drop:
use std::collections::ArrayList;
fn demo(list : ArrayList<i32>) : i32 {
try {
list.replace(1, 200);
} catch e : IndexOutOfBoundsException {
println("replace: index out of range");
}
let removed : i32 = list.removeAt(0) catch e {
return -1; // the catch block supplies the value on the throw path
};
return removed;
} When the call does produce the value you want, expr catch e { … } folds
the handler into the expression.
The trailing ; is required: expr catch e { … } is an expression, and the
statement still needs its terminator.
The handler must either end on a value of the guarded type or leave with return or throw. It cannot fall through, because the value it would have
produced is the one the binding reads.
Iteration
for (x of collection) walks an ArrayList, a HashSet or a HashMap (over its keys). x is each element in turn, and break, continue and return leave the loop as they do in any other:
use std::collections::ArrayList;
use std::collections::HashMap;
fn sum(list : ArrayList<i64>) : i64 {
let mut total : i64 = 0;
for (x of list) {
total = total + x;
}
return total;
}
fn describe(ages : HashMap<string, i32>, names : ArrayList<string>) : void {
for (name of names) {
println(name);
}
for (key of ages) { // a map yields its keys…
println(key);
println((ages.get(key) ?? 0).toString()); // …and `get` reads the value
}
}
fn main() : i32 {
let list : ArrayList<i64> = new ArrayList<i64>();
list.add(1);
list.add(2);
if (sum(list) != 3) { return 1; }
let ages : HashMap<string, i32> = new HashMap<string, i32>();
ages.put("alice", 30);
let names : ArrayList<string> = new ArrayList<string>();
names.add("alice");
describe(ages, names);
return 0;
} What the loop does
The loop is the while you would otherwise write over the collection’s own nextSlot / elementAt methods. Three things follow from that:
- Independent loops. The cursor lives in the loop, so two loops over the same list do not affect each other.
- Empty collections. An empty collection never runs its body.
- Order. A list is walked in its own order. A set or a map is walked in the table’s order, not in insertion order.
Adding or removing elements from inside a loop over the collection does not corrupt memory, but which elements the loop then visits is unspecified. The loop variable borrows the element: do not read it after the body removed or overwrote that element (take what you need, such as its length, first).
Iterating your own class
A class of your own is iterable the same way. Declare either pair of methods:
hasNext() : boolwithnext() : T;nextSlot(start : i64) : i64withelementAt(slot : i64) : T.
Then for (x of it) works over it, with x typed by what the second method
returns.
Listing : Iterator<T> or : Iterable<T> (from std::collections) is
optional. It only has the compiler check your methods against the contract.
Reading by position
When you need the position as well, or a different order, index with a while and get(i) ?? fallback. list.get(i) returns T | null, and ?? 0 unwraps
it.
Read as written, each access is a bounds check plus a nullable. The compiler removes both when its value-range analysis can prove the index is in range. That happens for the two shapes you actually write:
- a
i < list.size()loop guard; - an index it can bound on its own, such as
(seed % list.size()).
The read then compiles to a plain indexed load, with no branch and no tag.
When the index cannot be proven safe, the check and the ?? fallback stay
exactly as written. You never lose the safety, only the cost when the check is
provably redundant.
size() returns the exact element count as an i64. A slot nextSlot returned is read with elementAt (the loop protocol’s unguarded read); a slot
from anywhere else is read with elementAtChecked, which raises IndexOutOfBoundsException for a position the collection does not hold.
Building from a range
use std::collections::ArrayList;
fn fibs(n : i32) : ArrayList<i64> {
let out : ArrayList<i64> = new ArrayList<i64>();
let mut a : i64 = 0;
let mut b : i64 = 1;
for (i of 0..n) {
out.add(a);
let next : i64 = a + b;
a = b;
b = next;
}
return out;
} Filtering and mapping
There is no combinator API. Write the loop:
use std::collections::ArrayList;
fn evens(list : ArrayList<i32>) : ArrayList<i32> {
let out : ArrayList<i32> = new ArrayList<i32>();
let mut i : i32 = 0;
while (i < list.size()) {
let v : i32 = list.get(i) ?? 0;
if (v % 2 == 0) {
out.add(v);
}
i = i + 1;
}
return out;
}
fn squared(list : ArrayList<i32>) : ArrayList<i32> {
let out : ArrayList<i32> = new ArrayList<i32>();
let mut i : i32 = 0;
while (i < list.size()) {
let v : i32 = list.get(i) ?? 0;
out.add(v * v);
i = i + 1;
}
return out;
} Sorting and searching
ArrayList<T> sorts in place with sort() (ascending) or sortDescending().
Both order any element type the built-in compare(a, b) handles: numbers by
value, string lexicographically. You write no comparison of your own:
use std::collections::ArrayList;
fn main() : i32 {
let xs : ArrayList<i32> = new ArrayList<i32>();
xs.add(5); xs.add(1); xs.add(4); xs.add(2); xs.add(3);
xs.sort(); // [1, 2, 3, 4, 5]
println(xs.get(0) ?? -1); // 1
let names : ArrayList<string> = new ArrayList<string>();
names.add("cherry"); names.add("apple"); names.add("banana");
names.sort(); // apple, banana, cherry
println(names.get(0) ?? "?"); // apple
let desc : ArrayList<i32> = new ArrayList<i32>();
desc.add(1); desc.add(3); desc.add(2);
desc.sortDescending(); // [3, 2, 1]
println(desc.get(0) ?? -1); // 3
return 0;
} The algorithm depends on the element type:
| Element type | Algorithm | Worst case |
|---|---|---|
i8, i16, i32, i64, bool, char, f32, f64 | LSD radix sort: one counting pass per key byte that varies | linear in the key bytes |
u8, u16, u32, u64, string, and class instances | introsort: median-of-3 quicksort, heapsort past a 2 * floor(log2 n) depth budget, insertion sort on small ranges (up to 17 elements) | O(n log n) |
Neither path indexes out of range, so neither carries a ! error set.
A string sorts by its characters, never by pointer identity. A class instance
sorts by an unspecified but stable identity order, so sort by a projected key
when you need a meaningful order for objects.
Note
sort()ordersstringelements lexicographically. A bare>on two strings would compare identity, which is why the collection never uses it (see Strings and text).
Once a list is sorted, a binary search finds an element in O(log n). Halve the [lo, hi] window each step, and compute the midpoint as lo + (hi - lo) / 2 so that the sum cannot overflow an i32:
use std::collections::ArrayList;
fn binarySearch(xs : ArrayList<i32>, target : i32) : i64 {
let mut lo : i64 = 0;
let mut hi : i64 = xs.size() - 1;
while (lo <= hi) {
let mid : i64 = lo + (hi - lo) / 2;
let v : i32 = xs.get(mid) ?? 0;
if (v == target) { return mid; }
if (v < target) { lo = mid + 1; }
else { hi = mid - 1; }
}
return -1; // absent
} indexOf is the O(n) linear alternative: no sort needed, but it scans the
whole list. Sort once and binary-search when you probe the same list many
times; use indexOf for a one-off lookup.
HashMap<K, V>: key to value
use std::collections::HashMap;
fn main() : i32 {
let scores : HashMap<string, i32> = new HashMap<string, i32>();
scores.put("alice", 90);
scores.put("bob", 85);
scores.put("carol", 92);
if (scores.size() != 3) { return 1; }
if (!scores.containsKey("alice")) { return 2; }
if (scores.get("alice") != 90) { return 3; }
scores.put("alice", 95); // overwrite
if (scores.get("alice") != 95) { return 4; }
let existed : bool = scores.remove("bob");
if (!existed) { return 5; }
if (scores.containsKey("bob")) { return 6; }
return 0;
} Method reference
| Method | Returns | Effect |
|---|---|---|
put(k, v) | void | insert, or overwrite the value of an existing key |
get(k) | V \| null | lookup; null when absent; never throws |
getOrDefault(k, default) | V | lookup; default on a miss |
containsKey(k) | bool | membership test |
remove(k) | bool | delete; true if the key existed |
size() | i64 | entry count |
isEmpty() | bool | true when size() is 0 |
clear() | void | remove every entry |
remove answers whether a binding was present; it does not return the old
value. Read the value first with get if you need it.
Lookups and the missing key
get(k) returns V | null: null on a miss, never a throw. null is a
distinct type, not a falsy 0, so a stored 0 is always told apart from an
absent key. Two idioms:
use std::collections::HashMap;
fn lookup(map : HashMap<string, i32>, key : string) : i32 {
return map.get(key) ?? -1; // sentinel on miss
} use std::collections::HashMap;
fn describe(map : HashMap<string, i32>, key : string) : string {
if (map.get(key) == null) { return "absent"; }
return "present";
} A V | null compares directly against a concrete value, so the common
assertions need no ??. null != 90 is true, and an absent key never equals
the value:
use std::collections::HashMap;
fn isNinety(map : HashMap<string, i32>, key : string) : bool {
return map.get(key) == 90; // false when the key is absent
} getOrDefault(key, default) is the same single-probe miss-with-default as get(key) ?? default. Prefer it on hot paths for readability.
Counting word frequencies
use std::collections::ArrayList;
use std::collections::HashMap;
fn wordCount(words : ArrayList<string>) : HashMap<string, i32> {
let counts : HashMap<string, i32> = new HashMap<string, i32>();
let mut i : i32 = 0;
while (i < words.size()) {
let w : string = words.get(i) ?? "";
counts.put(w, counts.getOrDefault(w, 0) + 1);
i = i + 1;
}
return counts;
} Each put copies the key, so the map keeps its own string. The caller’s w stays valid for the next iteration.
Integer keys for caches
use std::collections::HashMap;
class Session {
token : string;
constructor(token : string) {
self.token = token;
}
}
fn main() : i32 {
let cache : HashMap<i64, Shared<Session>> = new HashMap<i64, Shared<Session>>();
cache.put(7, share new Session("abc"));
if (cache.containsKey(7)) { return 0; }
return 1;
} Session owns a heap string, so HashMap<i64, Session> is refused with E0604: a by-value owned element has no per-element store increment, and
the map would leak it.
Wrapping the element in Shared<U> makes the co-ownership explicit. The map
increments the count on every store, and its destructor decrements every live
slot.
HashSet<T>: unique values
use std::collections::HashSet;
fn main() : i32 {
let seen : HashSet<string> = new HashSet<string>();
let added1 : bool = seen.add("alpha"); // true: new entry
let added2 : bool = seen.add("alpha"); // false: duplicate
let added3 : bool = seen.add("beta"); // true
if (seen.size() != 2) { return 1; }
if (!seen.contains("alpha")) { return 2; }
if (seen.contains("gamma")) { return 3; }
let removed : bool = seen.remove("alpha");
if (!removed) { return 4; }
if (seen.size() != 1) { return 5; }
return 0;
} Method reference
| Method | Returns | Effect |
|---|---|---|
add(v) | bool | insert; true if the value was new |
remove(v) | bool | delete; true if the value existed |
contains(v) | bool | membership test |
size() | i64 | element count |
isEmpty() | bool | true when size() is 0 |
clear() | void | remove every element |
Deduplicating an ArrayList
use std::collections::ArrayList;
use std::collections::HashSet;
fn unique(list : ArrayList<string>) : ArrayList<string> {
let seen : HashSet<string> = new HashSet<string>();
let out : ArrayList<string> = new ArrayList<string>();
let mut i : i32 = 0;
while (i < list.size()) {
let v : string = list.get(i) ?? "";
if (seen.add(v)) { // true the first time v is seen
out.add(v); // both containers copied the string
}
i = i + 1;
}
return out;
} seen.add(v) returns true exactly when v is new. Combined with an ArrayList, it keeps first-seen order.
Strings are copied on store
A collection copies a string element on store: ArrayList.add and HashMap.put take their own copy of the payload.
The caller keeps its binding, so the same v above can go into the set and the
list on one path without any v + "". Mutating your binding afterwards does not
change what was stored.
A Shared<U> element is the exception. It is referenced, not copied, so the
container only increments its count.
Collections of user classes
A collection of a user class stores each element as a reference to the
instance. The element must be Shared<T>: a by-value owned element declares a
destructor, and a collection has no per-element store increment for it. So ArrayList<Job> is refused with E0604, and ArrayList<Shared<Job>> is what
compiles.
use std::collections::ArrayList;
class Job {
pub id : i32;
pub body : string;
constructor(id : i32, body : string) {
self.id = id;
self.body = body;
}
}
fn main() : i32 {
let jobs : ArrayList<Shared<Job>> = new ArrayList<Shared<Job>>();
jobs.add(share new Job(1, "first"));
jobs.add(share new Job(2, "second"));
let j : Shared<Job> | null = jobs.get(0);
if (j != null) { return j.id; } // narrowed to Shared<Job> here
return -1; // absent
} Lifetime: the ArrayList co-owns each element. The store increments the count,
and the list’s destructor decrements every live slot.
An entry stays alive while the list holds it. It is freed at the last release, whether that is the list or a handle you kept.
Collections of structs
A struct is not a collection element today, for one of two reasons:
| The struct | ArrayList<S> | Why |
|---|---|---|
| holds only plain data | E0761 | the collection compares its elements, and a struct has no equality |
holds an array, an object or a Shared<T> | E0604 | such a struct has one owner, and moving it asks you to write copy or own; a collection is written once for every T and cannot ask |
Two shapes work instead:
- a plain array,
Buf[]orBuf[N], which releases each element with the array (Structs:copyandown→ Arrays of structs); - a class holding the data, stored as
Shared<T>handles, as above.
Building a small index
use std::collections::HashMap;
class Index {
byId : HashMap<i64, string>,
byName : HashMap<string, i64>,
constructor() {
self.byId = new HashMap<i64, string>();
self.byName = new HashMap<string, i64>();
}
pub fn add(self, id : i64, name : string) : void {
self.byId.put(id, name); // put copies the value …
self.byName.put(name, id); // … and copies the key
}
pub fn lookupById(self, id : i64) : string | null {
return self.byId.get(id);
}
pub fn lookupByName(self, name : string) : i64 | null {
return self.byName.get(name);
}
} Keep the two maps in sync on every add. The type system cannot enforce that
invariant, so route every mutation through one helper, as add does here.
Choosing the right container
| Pattern | Container |
|---|---|
| ordered list, access by position | ArrayList<T> |
| set membership, deduplication | HashSet<T> |
| key to value lookup | HashMap<K, V> |
| ordered list and set semantics together | ArrayList<T> plus HashSet<T> side by side |
| fixed compile-time size | T[N] (built-in fixed array) |
| count occurrences | HashMap<T, i32> |
Fixed arrays: built-in, no use needed
fn main() : i32 {
let mut buf : i32[16] = i32[16](0); // 16 zeros
buf[0] = 7;
buf[15] = 42;
return buf[0] + buf[15]; // 49
} The a[i] operator does not raise a catchable exception. An out-of-bounds
index aborts the process with a message on stderr and a non-zero exit, so it
can never be listed in a ! set or caught as IndexOutOfBoundsException.
Fixed arrays live on the stack when they are small, and on the heap through
the same escape rules as classes when they are large. Use them when the size
is known at compile time. Reach for ArrayList<T> when the size grows at run
time.
Limits / Uncabled
| Feature | State | Detail or workaround |
|---|---|---|
for (entry of map) over key and value together | A map yields its keys | Read the value with map.get(key) |
list.iterator() returning an iterator object | Not provided: a collection is walked by the loop itself | for (x of list), or write your own Iterator<T> class |
Collection, List, Set, Map contracts | Declared in the stdlib, not adopted by ArrayList, HashMap or HashSet (no : Trait clause on them) | Use the concrete methods listed above |
| Map and filter combinators | Not provided | Write the loop, as in Filtering and mapping |
sort(dir : Sort) | The Sort enum (Sort::Up, Sort::Down) names the direction; no sample exercises it | Use sort() and sortDescending() |
f64 elements of a HashSet, keys of a HashMap | Refused by hash_key | Use an ArrayList<f64>, or key by a string or i64 form of the value |
getUnchecked / setUnchecked | No bounds check: the caller guarantees 0 <= i < size() | Use get and set unless the index is provably in range; the stdlib calls them inside unsafe blocks |
removeAt in a hot loop | O(n) and one allocation per call | Use pop() for stacks, or rebuild the list in one pass |
See also
std/collectionsreference- Strings and text:
StringBuilderis a related buffer type - Memory model: when collections go on shared, heap or arena storage
- Concept index: every collection type cross-linked