Skip to content
Tutorials Center
My learning

Topics

Lesson 27 of 37 ยท Comptime and Generics

Generic Data Structures

Build generic containers in Zig by returning a struct type from a function: a stack, a linked list and a queue, with allocators, deinit, iterators and a Go generics stand-in.

In Generic functions with comptime you saw that a function can return a type. That is the whole trick behind Zig's generic containers: std.ArrayList(T), std.AutoHashMap(K, V) and std.ArrayHashMap are all ordinary functions that take types and return a struct type. In this lesson you build three of your own.

The pattern

ZIG
fn Stack(comptime T: type) type {
    return struct {
        const Self = @This();

        items: std.ArrayList(T) = .empty,

        pub fn deinit(self: *Self, gpa: std.mem.Allocator) void {
            self.items.deinit(gpa);
        }

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

        pub fn pop(self: *Self) ?T {
            return self.items.pop();
        }

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

Three things to notice:

  1. The function returns an anonymous struct type that can use T inside any field or method.
  2. @This() gives the type being defined, conventionally named Self. An anonymous struct has no name, so @This() is how it refers to itself.
  3. The struct's methods follow the usual Zig conventions: an init/deinit pair, the allocator passed to anything that may allocate, and ?T for "nothing here".

Use it like any type:

ZIG
var stack: Stack(i32) = .{};
defer stack.deinit(gpa);

try stack.push(gpa, 10);
try stack.push(gpa, 20);
std.debug.print("{?d}\n", .{stack.peek()}); // 20
while (stack.pop()) |v| std.debug.print("{d}\n", .{v});

Stack(i32) and Stack(u8) are two distinct types. Calling Stack(i32) twice yields the same type, because comptime function calls with equal arguments are memoized.

A singly linked list

Linked lists need nodes with stable addresses, which is a good use of create and destroy:

ZIG
fn LinkedList(comptime T: type) type {
    return struct {
        const Self = @This();
        const Node = struct {
            value: T,
            next: ?*Node = null,
        };

        head: ?*Node = null,
        len: usize = 0,

        pub fn prepend(self: *Self, gpa: std.mem.Allocator, value: T) !void {
            const node = try gpa.create(Node);
            node.* = .{ .value = value, .next = self.head };
            self.head = node;
            self.len += 1;
        }

        pub fn popFront(self: *Self, gpa: std.mem.Allocator) ?T {
            const node = self.head orelse return null;
            defer gpa.destroy(node);
            self.head = node.next;
            self.len -= 1;
            return node.value;
        }

        pub fn deinit(self: *Self, gpa: std.mem.Allocator) void {
            while (self.popFront(gpa)) |_| {}
        }
    };
}

Pay attention to the order in popFront: we read node.next and node.value while the node is still alive, and the defer destroys it after the return value has been computed. The nested Node type may refer to itself (?*Node), which is how recursive types are written.

Zig's standard library also ships intrusive list types (std.SinglyLinkedList, std.DoublyLinkedList) where the link lives inside your own struct, so you do not need to allocate nodes separately. Study them once you are comfortable with @fieldParentPtr.

An iterator

Zig has no iterator interface. The convention is a struct with a next method returning an optional, which works directly with while (it.next()) |x|:

ZIG
pub const Iterator = struct {
    current: ?*Node,

    pub fn next(self: *Iterator) ?T {
        const node = self.current orelse return null;
        self.current = node.next;
        return node.value;
    }
};

pub fn iterator(self: *const Self) Iterator {
    return .{ .current = self.head };
}

Put this inside the struct returned by LinkedList(T), so it can see T and Node.

A ring-buffer queue without allocation

Generic containers do not have to allocate. A fixed-capacity queue takes its size as a comptime parameter and keeps everything inside the struct:

ZIG
fn RingQueue(comptime T: type, comptime capacity: usize) type {
    return struct {
        const Self = @This();

        buf: [capacity]T = undefined,
        head: usize = 0,
        len: usize = 0,

        pub fn push(self: *Self, value: T) error{Full}!void {
            if (self.len == capacity) return error.Full;
            self.buf[(self.head + self.len) % capacity] = value;
            self.len += 1;
        }

        pub fn pop(self: *Self) ?T {
            if (self.len == 0) return null;
            const value = self.buf[self.head];
            self.head = (self.head + 1) % capacity;
            self.len -= 1;
            return value;
        }
    };
}

RingQueue(u8, 64) is a type whose size is known at compile time, so it can live on the stack or in a global with no allocator at all. This is the style embedded Zig programs use.

flowchart LR
  F["Stack(T)<br/>function"] -->|"T = i32"| A["type Stack(i32)"]
  F -->|"T = []const u8"| B["type Stack([]const u8)"]
  A --> X["values, methods, size"]
  B --> Y["values, methods, size"]

Caption: one type-returning function creates a separate, fully typed container per argument.

Design tips

  • Provide init or default field values and a deinit. Callers rely on the pair.
  • Take the allocator per call (as 0.15's ArrayList does) or store it once in the struct; either is fine, but be consistent.
  • Return ?T for empty-container operations and an explicit error set (error{Full}) for capacity problems.
  • Mark query methods with self: *const Self so they work on constant containers.
  • Test with std.testing.allocator so leaks fail the test (see Testing in Zig).

A runnable stand-in

Go generics let you write the same containers with type parameters. The linked list below mirrors the Zig version: nodes, a head pointer, prepend, popFront and an iterator-style method.

Go Stand-in: generic stack and linked list (Go generics)

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 const Self = @This(); and then being unable to name the struct inside its own methods.
  • Destroying a node before reading its next field.
  • Returning a pointer to an element of a growable container and then growing it.
  • Making every container allocate when a fixed comptime capacity would do.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How does a generic container like Stack(T) work in Zig?

    Types are comptime values, so a function can build and return a new struct type for each T.
  2. 2. What does const Self = @This(); give you?

    An anonymous struct has no name, so @This() is how its methods refer to its own type.
  3. 3. What is Zig's iterator convention?

    There is no iterator interface; an optional-returning next method works naturally with while capture loops.
  4. 4. Why can RingQueue(u8, 64) avoid an allocator?

    With the capacity known at compile time the array is part of the type's size, so it can sit on the stack or in a global.

Summary

  • A generic container is a function that takes comptime types and returns a struct type.
  • Use @This() for the self type, follow init/deinit, take allocators explicitly.
  • Nodes that must not move are allocated with create/destroy; fixed-capacity queues need no allocator.
  • Iterators are structs with next() ?T.

Next: Type reflection and comptime tricks