Data Structures

Zig's standard library provides efficient, allocator-aware data structures that compose cleanly with the rest of the language. Unlike languages that hide allocation behind garbage collection or smart pointers, Zig makes every allocation explicit — you pass an allocator in, you call deinit when you are done. There are no hidden costs and no surprises at runtime. The two structures you will reach for most often are ArrayList for ordered collections that grow dynamically and HashMap for key-value lookups. Beyond the standard library, Zig's comptime system makes it straightforward to write your own generic data structures that work safely across any type.

What You'll Learn

By the end of this lesson you will write a function that takes a slice of parsed records, groups them by category into a hash map, and hands the finished map back to its caller without leaking a single allocation on either the success path or the failure path. Choosing the structure is half the job; releasing it correctly is the other half, and the two decisions are made in the same breath.

This is the milestone the capstone's Aggregation Engine stands on — the Record Analyzer holds every accepted record in an ArrayList and every per-category summary in a StringHashMap, so the report it prints is only as trustworthy as the grouping underneath it. You arrive here able to read a file into caller-owned memory and walk it line by line (File I/O); what is new is that the lines now have to be kept somewhere that grows. Everything below is pinned to Zig 0.16.0, the version the Run button uses — worth knowing here in particular, because std.ArrayList stopped storing its own allocator in 0.16 and most ArrayList code you find online predates that change.

ArrayList: Dynamic Collections

std.ArrayList(T) is Zig's dynamic array. It owns a heap-allocated slice that grows automatically as you append elements. You start it empty with .empty and pass an allocator to each operation that may allocate — append, deinit, and so on — so the list itself stores no allocator and every allocation stays explicit at the call site. The underlying elements are always accessible through the .items field, which is a plain slice you can iterate, index, or pass to any function that accepts a slice.

zig

const std = @import("std");

pub fn main() !void {
    var gpa: std.heap.DebugAllocator(.{}) = .init;
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    var scores: std.ArrayList(i32) = .empty;
    defer scores.deinit(allocator);

    try scores.append(allocator, 88);
    try scores.append(allocator, 95);
    try scores.append(allocator, 72);
    try scores.append(allocator, 91);

    std.debug.print("Scores ({} total):\n", .{scores.items.len});
    for (scores.items, 0..) |score, i| {
        std.debug.print("  [{}] {}\n", .{ i, score });
    }

    // orderedRemove preserves order at O(n) cost
    _ = scores.orderedRemove(1);

    std.debug.print("After removing index 1:\n", .{});
    for (scores.items) |score| {
        std.debug.print("  {}\n", .{score});
    }
}

append may trigger a reallocation, so it takes the allocator, returns an error union, and requires try. The defer scores.deinit(allocator) pattern ensures the heap memory is released even if a later operation fails. When order does not matter, swapRemove replaces the target element with the last one and removes the tail in O(1) — use it instead of orderedRemove for large lists where preserving insertion order is not important.

Those two removal methods differ in more than cost. Predict the output before running it.

Predict

The same four-element list is built twice. One copy drops index 1 with orderedRemove, the other with swapRemove. Predict both printed lists.

zig

const std = @import("std");

fn build(allocator: std.mem.Allocator) !std.ArrayList(u8) {
  var l: std.ArrayList(u8) = .empty;
  try l.append(allocator, 10);
  try l.append(allocator, 20);
  try l.append(allocator, 30);
  try l.append(allocator, 40);
  return l;
}

pub fn main() !void {
  var gpa: std.heap.DebugAllocator(.{}) = .init;
  defer _ = gpa.deinit();
  const allocator = gpa.allocator();

  var a = try build(allocator);
  defer a.deinit(allocator);
  var b = try build(allocator);
  defer b.deinit(allocator);

  _ = a.orderedRemove(1);
  _ = b.swapRemove(1);

  std.debug.print("ordered: {any}\n", .{a.items});
  std.debug.print("swap:    {any}\n", .{b.items});
}

ordered: { 10, 30, 40 } and swap: { 10, 40, 30 } — swapRemove moves the last element into the hole instead of shifting
Both print { 10, 30, 40 } — the two methods differ only in speed, not in the resulting order
ordered: { 10, 30, 40 } and swap: { 10, 30 } — swapRemove discards both the target and the last element

orderedRemove prints { 10, 30, 40 } and swapRemove prints { 10, 40, 30 }. Both removed exactly one element; the difference is the mechanism. orderedRemove shifts every later element down a slot, which is what makes it O(n) and what preserves order. swapRemove copies the last element over the hole and shrinks the length — one move, O(1), order sacrificed. The cost and the ordering are the same fact seen twice.

HashMap: Key-Value Lookups

std.StringHashMap(V) maps string keys to values of type V. For integer or struct keys, std.AutoHashMap(K, V) selects an appropriate hash function automatically based on the key type. Both follow the same allocator-in, deinit-to-free pattern.

zig

const std = @import("std");

pub fn main() !void {
    var gpa: std.heap.DebugAllocator(.{}) = .init;
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    var inventory = std.StringHashMap(u32).init(allocator);
    defer inventory.deinit();

    try inventory.put("sword", 3);
    try inventory.put("shield", 1);
    try inventory.put("potion", 10);

    // get returns ?V — null if the key is absent
    if (inventory.get("potion")) |count| {
        std.debug.print("Potions in stock: {}\n", .{count});
    }

    // getOrPut inserts a default and avoids a second lookup
    const result = try inventory.getOrPut("arrow");
    if (!result.found_existing) {
        result.value_ptr.* = 0;
    }
    result.value_ptr.* += 24;

    std.debug.print("Arrows: {}\n", .{inventory.get("arrow").?});

    // Iterate over all entries
    std.debug.print("Full inventory:\n", .{});
    var it = inventory.iterator();
    while (it.next()) |entry| {
        std.debug.print("  {s}: {}\n", .{ entry.key_ptr.*, entry.value_ptr.* });
    }
}

get returns an optional — null when the key is absent, otherwise the value. getOrPut is the idiomatic way to insert a default or update an existing entry without two separate map lookups. It returns a struct with found_existing and a writable value_ptr.

That leaves one question the API does not answer for you: what a StringHashMap does with the key strings you hand it. The program below is what happens when you guess wrong. It compiles, every try succeeds, and it crashes. Work out why before you change anything.

Debug

Every key here is built with allocPrint and inserted successfully, yet the program crashes on the first lookup. Diagnose what the map is holding by the time main reads it, then fix it so the three entries survive and print.

zig

const std = @import("std");

fn addRecord(map: *std.StringHashMap(u32), allocator: std.mem.Allocator, name: []const u8, n: u32) !void {
  // Build the key from a temporary buffer, then hand it to the map.
  const key = try std.fmt.allocPrint(allocator, "{s}", .{name});
  defer allocator.free(key);
  try map.put(key, n);
}

pub fn main() !void {
  var gpa: std.heap.DebugAllocator(.{}) = .init;
  defer _ = gpa.deinit();
  const allocator = gpa.allocator();

  var totals = std.StringHashMap(u32).init(allocator);
  defer totals.deinit();

  try addRecord(&totals, allocator, "apples", 3);
  try addRecord(&totals, allocator, "bananas", 5);
  try addRecord(&totals, allocator, "cherries", 12);

  if (totals.get("apples")) |v| {
      if (v != 3) {
          std.debug.print("CHECK FAILED: apples is {d}, expected 3\n", .{v});
          return error.CheckFailed;
      }
  } else {
      std.debug.print("CHECK FAILED: 'apples' is missing from the map\n", .{});
      return error.CheckFailed;
  }

  std.debug.print("map holds {d} entries\n", .{totals.count()});
  // Looked up by name rather than iterated: a hash map's iteration order is
  // unspecified, so only explicit lookups give a stable printout.
  std.debug.print("  apples = {d}\n", .{totals.get("apples").?});
  std.debug.print("  bananas = {d}\n", .{totals.get("bananas").?});
  std.debug.print("  cherries = {d}\n", .{totals.get("cherries").?});
}

Expected output:

map holds 3 entries
  apples = 3
  bananas = 5
  cherries = 12

Before you change anything — why do you think this fails?

The map stored three pointers into freed memory. put keeps the slice you hand it — a pointer and a length — not a copy of the characters, so addRecord's defer allocator.free(key) released the bytes the map was still pointing at. Insertion looked perfect; the crash came on the first lookup, when the map dereferenced a dangling key to compare it. StringHashMap does not copy or own the key strings it stores, so the key's memory must outlive the entry: either pass a slice that already outlives the map, or accept ownership — errdefer instead of defer, and free every key via map.keyIterator() before deinit.

Cleanup order is the part that bites, so assemble one yourself. Assume a helper is already written for you with this signature:

zig

// Returns a new list holding just the positive values. The list is the caller's;
// tally registers an errdefer internally, so a failure part-way through cleans up,
// but a successful return hands you a collection you are responsible for.
fn tally(allocator: std.mem.Allocator, values: []const i32) !std.ArrayList(i32)

The lines below are the caller's half — the code that sets up an allocator, calls tally, and prints what came back.

Arrange the code

A debug allocator is already set up above these lines as var debug_allocator: std.heap.DebugAllocator(.{}) = .init. The seven lines below take an allocator from it, call tally to build a list of the positive values, read one element, report what came back, and then release both resources in turn — the releases written out explicitly rather than deferred, so their positions are part of the puzzle. Reorder them so the program prints the list length, the first element, and a clean leak check. Then answer what the order is really testing: two of the adjacent swaps still compile, and neither reports an error at the line that caused it. Which two, and what does each actually do to the program?

std.debug.print("leak check: {t}\n", .{leaked});
const leaked = debug_allocator.deinit();
std.debug.print("kept {d}, first {d}\n", .{ kept.items.len, first });
const allocator = debug_allocator.allocator();
var kept = try tally(allocator, &[_]i32{ 3, -1, 7, 0, 12 });
const first = kept.items[0];
kept.deinit(allocator);

The first four positions are pinned by the compiler; the last three are not, and both wrong arrangements fail silently. Reading the list after kept.deinit prints a garbage length with a clean leak check, and releasing the backing allocator before the list hangs the program outright. Written with defer instead — defer kept.deinit(allocator) registered after defer _ = debug_allocator.deinit() — the reverse-order firing produces the correct sequence automatically, which is why the deferred form is the one to reach for.

Building Generic Data Structures

Zig does not have a generics keyword. Instead, you write a function that accepts a type at compile time and returns a new struct type built around it. This pattern gives you full generic behavior through ordinary comptime evaluation.

zig

const std = @import("std");

fn Stack(comptime T: type) type {
    return struct {
        const Self = @This();
        items: std.ArrayList(T),
        allocator: std.mem.Allocator,

        pub fn init(allocator: std.mem.Allocator) Self {
            return .{ .items = .empty, .allocator = allocator };
        }

        pub fn deinit(self: *Self) void {
            self.items.deinit(self.allocator);
        }

        pub fn push(self: *Self, value: T) !void {
            try self.items.append(self.allocator, value);
        }

        pub fn pop(self: *Self) ?T {
            if (self.items.items.len == 0) return null;
            return self.items.pop();
        }

        pub fn peek(self: *const Self) ?T {
            const len = self.items.items.len;
            if (len == 0) return null;
            return self.items.items[len - 1];
        }

        pub fn isEmpty(self: *const Self) bool {
            return self.items.items.len == 0;
        }
    };
}

pub fn main() !void {
    var gpa: std.heap.DebugAllocator(.{}) = .init;
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    var stack = Stack([]const u8).init(allocator);
    defer stack.deinit();

    try stack.push("first");
    try stack.push("second");
    try stack.push("third");

    std.debug.print("Top: {?s}\n", .{stack.peek()});

    while (!stack.isEmpty()) {
        const val = stack.pop().?;
        std.debug.print("Popped: {s}\n", .{val});
    }
}

@This() inside the returned struct refers to the struct type itself, enabling self-referential method definitions. The same Stack function works equally for i32, f64, or any struct type without changes to the implementation — the compiler generates a separate concrete type for each instantiation.

That fn(comptime T: type) type shape is not new machinery, and neither is the allocator threading. Check that the earlier lessons connect.

Recall

Without scrolling up: Stack above is a function taking a comptime type parameter and returning a struct, and every method that can allocate takes an allocator. Comptime introduced compile-time evaluation and Memory and Allocators introduced explicit allocation. Which row correctly names what each contributes, and what it costs at runtime?

The comptime type parameter costs nothing at runtime — the compiler generates one concrete Stack type per T, so there is no boxing and no dispatch. The allocator parameter is a genuine runtime value that must be passed in and matched by a deinit, because Zig will not allocate behind your back.
Both are runtime costs: the type parameter is checked when the program runs, and the allocator is looked up from a global default when omitted.
Both are compile-time costs: the compiler specialises the type AND resolves the allocation, so no deinit is needed for a generic collection.

So the two halves of Stack live on opposite sides of the compile/run line. The comptime T: type parameter is resolved by the compiler, which emits a fully specialised type per instantiation — that is Comptime's zero-cost generics, with no boxing and no dispatch. The allocator is a genuine runtime value threaded in by hand, with a matching deinit, because Memory and Allocators established that Zig never allocates behind your back.

Zig's collections are not the only ones that make ownership explicit. Check that you can tell which part of the idea carries across.

Transfer

Every collection in this lesson takes the allocator as an argument on each call that might allocate: kept.append(allocator, v), kept.deinit(allocator). Rust's Vec and HashMap never take one — you write v.push(x) and the value is dropped for you at the end of its scope. Both languages are nonetheless doing the same accounting. Which statement names what actually transfers between them, rather than a surface resemblance?

Both languages track, at run time, how many references point at the buffer, and release it when the count reaches zero.
Both give the buffer exactly one owner whose scope decides when it is released; the difference is only whether the compiler writes that release for you or you write it yourself.
Both store a handle to the allocator inside the collection, so the collection always frees with the same allocator it allocated from.

Try It Yourself

Reading about collections is not the same as choosing between them. This is a build task: a small program that reports its own pass/fail. It aggregates a list of sensor readings three different ways — a growable list, a keyed tally, and a fixed-capacity generic type you write yourself. Three functions are stubbed out. Run it as-is and it fails immediately, naming the first stub that is still empty. Implement each until it prints All checks passed.

The three stubs use exactly what this lesson taught: an unmanaged ArrayList with .empty and append(allocator, x), StringHashMap with getOrPut for insert-or-update, and fn(comptime T: type) type with @This() for a generic type of your own. The starter has the data, the stubs and the checks; you write only the bodies. Nothing above spells out all three answers, so you will have to assemble them.

Build

Finish the build. Three collection helpers are stubbed out and the checks below them fail until each behaves. Run it as-is to see which check fails first, decide what that stub is missing, then implement all three until it prints 'All checks passed.' The checks run top to bottom, so the first failure you see is TODO 1 — implement it first, then work down.

zig

const std = @import("std");

fn expect(ok: bool, comptime msg: []const u8) !void {
  if (!ok) {
      std.debug.print("CHECK FAILED: {s}\n", .{msg});
      return error.CheckFailed;
  }
}

const Reading = struct { sensor: []const u8, value: i32 };

const data = [_]Reading{
  .{ .sensor = "north", .value = 12 },
  .{ .sensor = "south", .value = 40 },
  .{ .sensor = "north", .value = 55 },
  .{ .sensor = "east", .value = 7 },
  .{ .sensor = "north", .value = 31 },
};

// TODO 1: return an ArrayList of every reading value strictly above `threshold`,
//   in the order they appear. The CALLER deinits the returned list, so use
//   errdefer (not defer) for the failure path.
//   collectAbove(alloc, &data, 30) -> { 40, 55, 31 }
fn collectAbove(allocator: std.mem.Allocator, readings: []const Reading, threshold: i32) !std.ArrayList(i32) {
  var out: std.ArrayList(i32) = .empty;
  // your code here
  _ = allocator;
  _ = readings;
  _ = threshold;
  _ = &out; // keeps out a var until your loop mutates it
  return out;
}

// TODO 2: return a StringHashMap counting how many readings each sensor has.
//   Use getOrPut so you touch the map once per reading, not twice.
//   The sensor names are string literals, so nothing needs freeing.
//   countBySensor(alloc, &data) -> { north: 3, south: 1, east: 1 }
fn countBySensor(allocator: std.mem.Allocator, readings: []const Reading) !std.StringHashMap(u32) {
  var map = std.StringHashMap(u32).init(allocator);
  // your code here
  _ = readings;
  _ = &map; // keeps map a var until your loop mutates it
  return map;
}

// TODO 3: a fixed-capacity ring buffer. push appends; once full it overwrites
//   the OLDEST value. at(i) is 0-based from oldest to newest, null if out of range.
//   Ring(i32, 3): push 1,2,3,4 -> at(0)=2, at(1)=3, at(2)=4, at(3)=null
//   No allocator: the storage is an inline [cap]T array.
fn Ring(comptime T: type, comptime cap: usize) type {
  return struct {
      buf: [cap]T = undefined,
      len: usize = 0,
      head: usize = 0,
      const Self = @This();

      fn push(self: *Self, v: T) void {
          // your code here
          _ = self;
          _ = v;
      }

      fn at(self: *const Self, i: usize) ?T {
          // your code here
          _ = self;
          _ = i;
          return null;
      }
  };
}

// --- Build checks: Do not edit below this line. ---
pub fn main() !void {
  var gpa: std.heap.DebugAllocator(.{}) = .init;
  defer _ = gpa.deinit();
  const allocator = gpa.allocator();

  var above = try collectAbove(allocator, &data, 30);
  defer above.deinit(allocator);
  try expect(above.items.len == 3, "three readings are above 30");
  try expect(above.items[0] == 40, "the first reading above 30 is 40");
  try expect(above.items[2] == 31, "order must be preserved, so the last is 31");

  var none = try collectAbove(allocator, &data, 1000);
  defer none.deinit(allocator);
  try expect(none.items.len == 0, "no reading is above 1000");

  var counts = try countBySensor(allocator, &data);
  defer counts.deinit();
  try expect(counts.count() == 3, "three distinct sensors appear");
  try expect(counts.get("north").? == 3, "north has 3 readings");
  try expect(counts.get("east").? == 1, "east has 1 reading");
  try expect(counts.get("west") == null, "get of an absent key is null, not zero");

  var ring = Ring(i32, 3){};
  ring.push(1);
  ring.push(2);
  ring.push(3);
  try expect(ring.at(0).? == 1, "before wrapping, the oldest is 1");
  ring.push(4);
  try expect(ring.at(0).? == 2, "after wrapping, 1 is gone and the oldest is 2");
  try expect(ring.at(2).? == 4, "the newest is 4");
  try expect(ring.at(3) == null, "index 3 is out of range in a 3-slot ring");

  std.debug.print("All checks passed.\n", .{});
  std.debug.print("above 30: {d} readings, first {d}\n", .{ above.items.len, above.items[0] });
  std.debug.print("north count: {d}\n", .{counts.get("north").?});
  std.debug.print("ring oldest: {d}\n", .{ring.at(0).?});
}

Expected output:

All checks passed.
above 30: 3 readings, first 40
north count: 3
ring oldest: 2

Before you run — what's your plan for the first TODO?

Once it passes, try two variations and predict each before running:

Swap errdefer for defer in collectAbove. Predict what the first check sees. The list is freed the instant the function returns, so above.items.len reads through freed memory — expect either a wrong length or a crash, and the defer above.deinit(allocator) in main then double-frees. This is the practical reason a function returning a collection must use errdefer: the success path is the caller's to clean up.
Ask the tally about a sensor that is not there. Change the counts.get("west") check to try expect(counts.get("west").? == 0, "west should be 0"); and predict the outcome. It panics on the .? unwrap of a null optional, because an absent key gives null, not zero — an instructive crash showing that a hash map distinguishes "no entry" from "an entry holding 0", and that orelse 0 is how you collapse the two when you want to.

Capstone milestone

Milestone — the aggregation engine. The capstone's Record Analyzer groups parsed records by a key, tallies them, and keeps a growable list of the ones that matter. The build task above is that engine in miniature. Confirm you can pick the right collection and manage its memory.

Hint: You don't need the full analyzer yet — this confirms the collection fluency the aggregation engine is built on. There, the same ArrayList-plus-HashMap pair holds the filtered records and the per-key totals.

Built an unmanaged ArrayList with .empty and appended through append(allocator, x)
Paired every collection with a deinit — defer when you own it, errdefer when the caller will
Used getOrPut to insert-or-update a StringHashMap entry in a single lookup
Handled an absent key as null rather than assuming zero
Wrote a generic type with fn(comptime T: type) type and @This()

Key Takeaways

std.ArrayList(T) is Zig's dynamic array — start it with .empty, pass the allocator to append and deinit, access elements through .items, and always pair creation with defer deinit(allocator)
orderedRemove preserves element order at O(n) cost; swapRemove is O(1) when order does not matter
std.StringHashMap(V) and std.AutoHashMap(K, V) provide O(1) average lookups; get returns an optional, getOrPut avoids double lookups on insert-or-update patterns
HashMap does not own string keys — free any dynamically allocated keys yourself before or after removing entries
Generic data structures use fn(comptime T: type) type with @This() for self-referential method types — no separate generics syntax required
Use std.StringHashMap(void) as a set type when you only need membership testing, not stored values

Pro Tip: When you need ordered key-value iteration — something HashMap does not guarantee — reach for the array-backed hash maps: std.StringArrayHashMapUnmanaged(V) for string keys, std.AutoArrayHashMapUnmanaged(K, V) for everything else. They maintain insertion order, support O(1) appends and lookups, and let you index entries by position through .keys() and .values(), making them ideal for configuration tables, ordered caches, or any structure where you care about both fast lookup and deterministic traversal order.

Next Steps

You've built data structures that store and retrieve data. But a pile of source files is not yet a project. Next, you'll learn how Zig's build system ties everything together -- compiling, linking, running tests, and cross-compiling, all from a single build.zig file.