Skip to content
Tutorials Center
My learning

Topics

Lesson 22 of 37 ยท Allocators and Error Handling

ArrayList and Hash Maps

Use std.ArrayList and the hash map family in Zig: append, pop, insert, getOrPut, iterate, string keys and ownership rules, with examples and a runnable Go stand-in.

Arrays in Zig have a fixed length known at compile time, and slices are views over memory somebody else owns. To grow a list while a program runs you need a container that owns its memory: std.ArrayList(T). For lookups by key you use the hash map family. Both take an allocator, so the rules from Allocating and freeing memory apply: whoever creates the container must deinit it.

Since Zig 0.15 std.ArrayList is the "unmanaged" form: the list does not store its allocator, and you pass the allocator to every method that may grow it. The older allocator-storing version lives on as std.array_list.Managed. Hash maps still offer both styles (AutoHashMap stores the allocator, AutoHashMapUnmanaged does not).

ArrayList basics

ZIG
const std = @import("std");

pub fn main() !void {
    const gpa = std.heap.page_allocator;

    var list: std.ArrayList(i32) = .empty;
    defer list.deinit(gpa);

    try list.append(gpa, 10);
    try list.append(gpa, 20);
    try list.appendSlice(gpa, &.{ 30, 40, 50 });

    std.debug.print("len = {d}\n", .{list.items.len}); // 5
    for (list.items) |n| std.debug.print("{d} ", .{n});
    std.debug.print("\n", .{});
}

A list has two interesting fields: items (a slice of the used part) and capacity. Appending when items.len == capacity reallocates to a bigger buffer, so any pointer or slice you took into items before an append may dangle afterward. Take indexes, not pointers, if the list keeps growing.

Common methods:

Method What it does
append(gpa, x) add to the end (may allocate)
appendSlice(gpa, xs) add many
pop() remove and return the last item as an optional
orderedRemove(i) remove at i, shifting the rest (O(n))
swapRemove(i) remove at i by moving the last item in (O(1), order lost)
insert(gpa, i, x) insert at i
clearRetainingCapacity() set length to 0, keep the buffer
toOwnedSlice(gpa) give up the buffer as an exactly sized slice
ensureTotalCapacity(gpa, n) pre-allocate so later appends cannot fail

appendAssumeCapacity skips the error: it is valid only after you reserved room, and it is the fast path in tight loops.

Building strings

A std.ArrayList(u8) is the usual string builder:

ZIG
var text: std.ArrayList(u8) = .empty;
defer text.deinit(gpa);
try text.appendSlice(gpa, "Zig ");
try text.print(gpa, "has {d} allocators", .{6});
// text.items is "Zig has 6 allocators"

If you want the string to outlive the list, call const s = try text.toOwnedSlice(gpa); and free s yourself later.

Stack and queue use

append and pop make a stack. pop returns ?T, so you handle the empty case:

ZIG
while (stack.pop()) |top| {
    std.debug.print("{d}\n", .{top});
}

Hash maps

The two everyday maps:

  • std.AutoHashMap(K, V) hashes any key type that has a sensible default hash (integers, enums, structs of those). Not for slices.
  • std.StringHashMap(V) uses []const u8 keys and hashes their contents.
ZIG
var counts = std.StringHashMap(u32).init(gpa);
defer counts.deinit();

try counts.put("apple", 3);
try counts.put("pear", 1);

if (counts.get("apple")) |n| {
    std.debug.print("apple = {d}\n", .{n});
}
std.debug.print("has fig? {}\n", .{counts.contains("fig")}); // false

get returns an optional value copy, getPtr returns an optional pointer so you can modify in place, remove returns whether a key was present, and count() gives the size.

getOrPut: the counting idiom

Counting things needs "insert if missing, otherwise update". getOrPut does both with one lookup:

ZIG
const gop = try counts.getOrPut("kiwi");
if (!gop.found_existing) gop.value_ptr.* = 0;
gop.value_ptr.* += 1;

Iterating

ZIG
var it = counts.iterator();
while (it.next()) |entry| {
    std.debug.print("{s} -> {d}\n", .{ entry.key_ptr.*, entry.value_ptr.* });
}

Iteration order is not specified. If you need a sorted report, copy the keys to an ArrayList and sort it with std.mem.sort. If you need insertion order, use std.StringArrayHashMap, which keeps entries in a dense array.

Who owns the keys?

StringHashMap stores the slice, not a copy of the characters. If the key points into a buffer you later free or overwrite, the map is corrupted. Two safe approaches:

  1. Keys are string literals or live as long as the map (an input buffer you keep alive).
  2. dupe each new key into an arena that lives as long as the map.
ZIG
var arena: std.heap.ArenaAllocator = .init(gpa);
defer arena.deinit();
// ...
const key = try arena.allocator().dupe(u8, word_from_temporary_buffer);
try counts.put(key, 1);

Mind that put on an existing key keeps the old key, so with getOrPut only duplicate when !gop.found_existing.

A runnable stand-in

Go has slices that grow and maps built in, so this stand-in shows the same word-count idiom as getOrPut, plus the "sort the keys for a stable report" step Zig requires because map order is unspecified.

Go Stand-in: count words and report in sorted order (Go)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with bufio.Scanner or fmt.Scan), it gets the next line from this box.

Common mistakes

  • Forgetting to pass the allocator to append or deinit in 0.15 code (the compiler tells you).
  • Holding list.items[i] as a pointer across an append.
  • Calling deinit on a map whose keys you duplicated: the map frees its own table, not your key strings.
  • Expecting StringHashMap iteration to be sorted.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why can a pointer into list.items become invalid after append?

    When capacity is exceeded the list moves to a bigger buffer, so old pointers and slices dangle.
  2. 2. What does StringHashMap store for a key?

    It keeps the slice, so the bytes must stay alive and unchanged while the key is in the map.
  3. 3. Which method does 'insert if missing, otherwise update' with one lookup?

    getOrPut returns pointers plus found_existing, so you can initialize new entries and update old ones.
  4. 4. How do you get a sorted report of a hash map?

    Hash map order is unspecified, so gather the keys and sort them yourself.

Summary

  • std.ArrayList(T) owns a growable buffer; pass the allocator to growing methods and call deinit(gpa).
  • Do not keep pointers into items across appends.
  • AutoHashMap and StringHashMap give put, get, getPtr, getOrPut, remove and iterator.
  • String keys are borrowed: keep them alive or duplicate them into an arena.

Next: Error unions and try