Collections

std/collections ships three generic containers — ArrayList<T>, HashMap<K, V>, HashSet<T>. ArrayList is a dynamic array, HashSet a hash-backed set, and HashMap an open-addressing hash table tuned for fast lookups. ArrayList is specialised over four element representations — i32 / i64 / f64 / string — while HashSet elements and HashMap keys exclude f64 (NaN and float-equality footguns), covering i32 / i64 / string ; values of a user class type all share the i32 representation, so they reuse the same compiled container methods while the compiler keeps their source-level types distinct.

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);                           // set / removeAt throw on a bad index
    let removed : i32 = list.removeAt(0);       // returns 10
    if (removed != 10)          { return 4; }
    if (list.size() != 2)       { return 5; }

    list.clear();
    if (!list.isEmpty())        { return 6; }
    return 0;
}

API surface:

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.

removeAt(i) is O(n) and reallocates: it copies the surviving elements into a fresh backing buffer (one malloc per call) to keep exactly one live reference per element. It is not a stack pop, so avoid it in a hot loop; to drain a list, iterate by descending index rather than repeatedly removing at 0.

set and removeAt are the two throwing members — a bad index is an IndexOutOfBoundsException, not a silent no-op. The example above lists it in main’s ! set so the throw propagates. To handle it right at the call, the try statement covers a call whose value you drop:

use std::collections::ArrayList;

fn demo(list : ArrayList<i32>) : i32 {
    try {
        list.set(1, 200);
    } catch e : IndexOutOfBoundsException {
        println("set: 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 instead. Note the trailing ; — expr catch e { … } is an expression, and the statement still needs its terminator. Its handler must either end on a value of the guarded type or leave with return / throw; it cannot simply fall through, because the value it would have produced is the one the binding reads.

get(i) never throws — it returns T | null and yields null past the end — so it needs neither a ! clause nor a catch.

Iteration

use std::collections::ArrayList;

fn sum(list : ArrayList<i64>) : i64 {
    let total : i64 = 0;
    let i : i32 = 0;
    while (i < list.size()) {
        total = total + (list.get(i) ?? 0);
        i = i + 1;
    }
    return total;
}

for (x of list) { … } syntax does not work over user collection types — explicit index loops are the idiom.

list.get(i) returns T | null and ?? 0 unwraps it, so read as written each access is a bounds check plus a nullable. You rarely pay for either: when the compiler’s value-range analysis can prove the index is in range, it drops the bounds check and the whole T | null, so list.get(i) ?? 0 compiles to a plain indexed load — no branch, no tag. It fires for the two shapes you actually write: an i < list.size() loop guard (as above), and an index it can bound on its own, like a scattered (seed % list.size()). On a read-heavy benchmark that elision brought Axle level with — and slightly ahead of — the same program in C++ and Rust. When the index can’t be proven safe, the check and the ?? fallback stay exactly as written: you never lose the safety, only the cost when it’s provably redundant.

Building from a range

use std::collections::ArrayList;

fn fibs(n : i32) : ArrayList<i64> {
    let out : ArrayList<i64> = new ArrayList<i64>();
    let a : i64 = 0;
    let b : i64 = 1;
    for (i of 0..n) {
        out.add(a);
        let next : i64 = a + b;
        a = b;
        b = next;
    }
    return out;
}

Filtering / mapping

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 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 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 natural order) or sortDescending(). Both order any element type the built-in compare(a, b) handles — numbers by value, string lexicographically — so 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;
}

sort() is in-place, and the algorithm depends on the element type. For every integer width (i8–i64), bool, char and both floats it runs an LSD radix sort — a linear-time pass over the key bytes. For string and class elements it falls back to an introsort: a median-of-3 quicksort that falls back to heapsort past a 2*floor(log2 n) recursion-depth budget (so the worst case stays O(n log n)), with an insertion-sort base case under 16 elements. Either way it never indexes out of range, so it carries no ! error set.

Ordering, not equality. sort() orders string elements lexicographically, never by the pointer identity a bare > would use (see Strings and text). A class element with no natural order sorts by an unspecified but stable identity order — sort by a projected key when you need a meaningful one.

Once a list is sorted, a binary search finds an element in O(log n). Halve the [lo, hi] window each step; the midpoint is computed as lo + (hi - lo) / 2 to avoid an i32 overflow on large indices:

use std::collections::ArrayList;

fn binarySearch(xs : ArrayList<i32>, target : i32) : i32 {
    let lo : i32 = 0;
    let hi : i32 = xs.size() - 1;
    while (lo <= hi) {
        let mid : i32 = 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 required, but it scans the whole list. Sort once and binary-search when you probe the same list many times; reach for indexOf for a one-off lookup.

HashMap<K, V> — key → 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;
}

API surface:

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, kept for symmetry with other languages.

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 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;
}

HashMap<i64, T> — 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, new shared 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 on every store and the map’s 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;
}

API surface:

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 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 being inserted for the first time — combine with an ArrayList to keep insertion order.

A collection copies a string element on store: ArrayList.add clones the payload and HashMap.put copies both key and value, so the caller keeps its own binding. That is why the same v above can go to the set and the list on one path without a v + ""; the container’s copy is independent of yours, and 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 merely increments its count.

Collections of user classes

A collection of a user class type stores each element as a reference to the instance. The element must be Shared<T> : a by-value owned element declares a destructor, which a carried-body collection has no per-element store increment for, 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(new shared Job(1, "first"));
    jobs.add(new shared 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 — so an entry stays alive while the list holds it and is freed at the last release, whether that is the list or a handle you kept.

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 can’t enforce the invariant, so wrap mutation in a single helper.

Choosing the right container

Fixed arrays — built-in, no use needed

fn main() : i32 {
    let 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 (stderr message + non-zero exit), it is never an IndexOutOfBoundsException you can list in a ! set or catch. Fixed arrays live on the stack when small, otherwise on the heap via the same escape rules as classes. Use them when the size is known at compile time ; reach for ArrayList<T> when the size grows dynamically.

See also

• std/collections reference
• Strings and text — StringBuilder is a related buffer type
• Memory model — when collections go on shared / heap / arena
• Concept index — every collection type cross-linked