Standard Library Data Structures

19.1 ArrayList (Dynamic Array)

// 0.15: std.ArrayList is "unmanaged": pass the allocator to each mutating call
var list: std.ArrayList(i32) = .empty;
defer list.deinit(allocator);
try list.append(allocator, 1);
try list.appendSlice(allocator, &.{ 2, 3, 4 });
try list.insert(allocator, 0, 0);
_ = list.orderedRemove(1);                  // keep order (O(n))
_ = list.swapRemove(0);                     // O(1)
const last = list.pop();                    // ?i32
try list.ensureTotalCapacity(allocator, 100);
list.appendAssumeCapacity(5);
for (list.items) |x| std.debug.print("{d} ", .{x});   // .items is the slice
list.clearRetainingCapacity();
_ = last;

var fixed = try std.ArrayList(u8).initCapacity(allocator, 64);
defer fixed.deinit(allocator);
// The managed variant (stores its allocator) still exists: std.array_list.Managed(T)

19.2 Hash Maps

Map keys aren't copied. For string keys, ensure the key memory outlives the map (or dupe keys and free them on deinit).

Custom hashing: std.HashMap(K, V, Context, max_load) with a hash and eql context.

std.BufSet, std.BufMap own their string keys.

var ages = std.StringHashMap(u32).init(allocator);        // managed: stores the allocator
defer ages.deinit();
try ages.put("Ana", 30);
try ages.put("Bo", 25);
if (ages.get("Ana")) |age| std.debug.print("{d}\n", .{age});
_ = ages.contains("Bo");
_ = ages.remove("Bo");
const gop = try ages.getOrPut("Cy");                       // insert-or-get in one lookup
if (!gop.found_existing) gop.value_ptr.* = 0;
gop.value_ptr.* += 1;
var it = ages.iterator();
while (it.next()) |entry| std.debug.print("{s}={d}\n", .{ entry.key_ptr.*, entry.value_ptr.* });

var by_id = std.AutoHashMap(u64, User).init(allocator);    // auto-hashed keys
defer by_id.deinit();

var unmanaged: std.AutoHashMapUnmanaged(u32, u32) = .empty;   // pass the allocator per call
defer unmanaged.deinit(allocator);
try unmanaged.put(allocator, 1, 2);

var ordered = std.StringArrayHashMap(i32).init(allocator);    // insertion-ordered, iterable as arrays
defer ordered.deinit();

19.3 Other Containers

Struct-of-arrays layout (data-oriented, cache-friendly) Stable pointers on growth std.PriorityQueue(T, Ctx, cmp)

std.DoublyLinkedList / std.SinglyLinkedList Intrusive linked lists (0.15: embed a Node in your struct and use @fieldParentPtr)

std.EnumArray, std.EnumMap, std.EnumSet std.StaticBitSet, std.DynamicBitSet, std.bit_set

std.fifo / std.Deque (version-dependent) Compile-time perfect string map (keywords)

Removed/deprecated in 0.15: use an array + len or ArrayList.initBuffer

const keywords = std.StaticStringMap(Token).initComptime(.{
    .{ "fn", .kw_fn },
    .{ "const", .kw_const },
});
const tok = keywords.get("fn");     // ?Token, perfect hashing at comptime
_ = tok;

var pq = std.PriorityQueue(u32, void, struct {
    fn cmp(_: void, a: u32, b: u32) std.math.Order { return std.math.order(a, b); }
}.cmp).init(allocator, {});
defer pq.deinit();
try pq.add(5);
try pq.add(1);
_ = pq.remove();   // 1

19.4 Sorting and Searching

var nums = [_]i32{ 5, 2, 9, 1 };
std.mem.sort(i32, &nums, {}, std.sort.asc(i32));
std.mem.sort(Person, people, {}, struct {
    fn lessThan(_: void, a: Person, b: Person) bool { return a.age < b.age; }
}.lessThan);
const idx = std.sort.binarySearch(i32, &nums, @as(i32, 5), struct {
    fn cmp(key: i32, item: i32) std.math.Order { return std.math.order(key, item); }
}.cmp);
_ = idx;
// std.sort.pdq, std.sort.heap, std.sort.insertion, std.sort.block (stable)

19.5 Math, Random and Time

const math = std.math;
_ = math.sqrt(2.0);
_ = math.pow(f64, 2, 10);
_ = math.clamp(15, 0, 10);
_ = math.pi;
_ = math.log2_int(u32, 1024);
_ = math.isPowerOfTwo(64);
_ = math.divCeil(u32, 7, 2) catch 0;
_ = @abs(@as(i32, -5));
_ = @min(1, 2);
_ = @max(1, 2);

var prng = std.Random.DefaultPrng.init(42);
const rand = prng.random();
_ = rand.intRangeAtMost(u8, 1, 6);
_ = rand.float(f64);
rand.shuffle(i32, &nums);
var seed: u64 = undefined;
std.crypto.random.bytes(std.mem.asBytes(&seed));   // cryptographically secure

const start = std.time.milliTimestamp();
std.Thread.sleep(10 * std.time.ns_per_ms);
var timer = try std.time.Timer.start();
const elapsed_ns = timer.read();
_ = .{ start, elapsed_ns };