Start with the Rule

Building Your Own Collections

A collection is a type that stores many values.

You have already seen several examples:

std.ArrayList(T)
std.AutoHashMap(K, V)
std.StringHashMap(V)

These are general-purpose collections. They are useful because they solve common problems.

But sometimes you need a collection with rules that are specific to your program.

Examples:

a stack that never grows past 64 items
a queue that overwrites old values
a list that stores only unique IDs
a pool that reuses deleted objects
a table optimized for small strings

In Zig, building your own collection is normal. You do not need classes or inheritance. You define a struct, choose its fields, and write functions that operate on it.

Start with the Rule

Before writing code, decide what the collection promises.

For example, a stack promises:

push adds to the top
pop removes from the top
peek reads the top without removing it

A unique list promises:

each value appears at most once

A fixed buffer promises:

capacity never changes
no heap allocation happens

A good collection has a small, clear rule.

A Fixed Stack

Here is a stack with fixed capacity.

It stores at most 8 integers.

const std = @import("std");

const FixedStack = struct {
    items: [8]i32,
    len: usize,

    pub fn init() FixedStack {
        return FixedStack{
            .items = undefined,
            .len = 0,
        };
    }

    pub fn push(self: *FixedStack, value: i32) !void {
        if (self.len == self.items.len) return error.Full;

        self.items[self.len] = value;
        self.len += 1;
    }

    pub fn pop(self: *FixedStack) ?i32 {
        if (self.len == 0) return null;

        self.len -= 1;
        return self.items[self.len];
    }

    pub fn peek(self: *const FixedStack) ?i32 {
        if (self.len == 0) return null;

        return self.items[self.len - 1];
    }
};

Using it:

pub fn main() !void {
    var stack = FixedStack.init();

    try stack.push(10);
    try stack.push(20);
    try stack.push(30);

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

Output:

30
20
10

This stack does not allocate. Its storage is inside the struct.

The Fields Are the Design

Look at the fields:

items: [8]i32,
len: usize,

The array stores the values.

The length tells us how many slots are currently used.

The valid items are:

items[0..len]

The unused part of the array does not matter.

items:
[10][20][30][?][?][?][?][?]
             ^
             len = 3

The values after len are not part of the stack.

Why `items` Is Undefined

The stack starts with:

.items = undefined

This is safe because no value is read until it has been written.

At the beginning:

len = 0

So the stack contains no valid items.

When we push:

self.items[self.len] = value;
self.len += 1;

we write the slot before it becomes part of the valid range.

Make Invalid States Impossible

A collection should protect its own rules.

For this stack, callers should not modify len directly.

This is why collection fields are often kept as implementation details. Zig does not have private fields in the same way some languages do, but you can still design the public API carefully.

The user of the type should call:

try stack.push(10);
_ = stack.pop();

They should not manually write:

stack.len = 999;

The convention is: treat fields as internal unless the type clearly exposes them.

A Generic Fixed Stack

The previous stack works only for i32.

We can make it generic.

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

        items: [capacity]T,
        len: usize,

        pub fn init() Self {
            return Self{
                .items = undefined,
                .len = 0,
            };
        }

        pub fn push(self: *Self, value: T) !void {
            if (self.len == self.items.len) return error.Full;

            self.items[self.len] = value;
            self.len += 1;
        }

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

            self.len -= 1;
            return self.items[self.len];
        }

        pub fn peek(self: *const Self) ?T {
            if (self.len == 0) return null;

            return self.items[self.len - 1];
        }

        pub fn slice(self: *const Self) []const T {
            return self.items[0..self.len];
        }
    };
}

Now you can create different stack types:

const IntStack = FixedStack(i32, 8);
const ByteStack = FixedStack(u8, 256);

Example:

pub fn main() !void {
    var stack = FixedStack([]const u8, 4).init();

    try stack.push("alpha");
    try stack.push("beta");

    while (stack.pop()) |value| {
        std.debug.print("{s}\n", .{value});
    }
}

Output:

beta
alpha

This is a common Zig pattern.

A function returns a type.

The type is specialized at compile time.

Methods Are Just Functions

This method:

pub fn push(self: *Self, value: T) !void {
    if (self.len == self.items.len) return error.Full;

    self.items[self.len] = value;
    self.len += 1;
}

takes:

self: *Self

because it modifies the stack.

This method:

pub fn peek(self: *const Self) ?T {
    if (self.len == 0) return null;

    return self.items[self.len - 1];
}

takes:

self: *const Self

because it only reads the stack.

Use *Self when the method mutates the collection.

Use *const Self when the method only reads.

Returning Optionals

pop can fail in a normal way.

The stack might be empty.

So it returns:

?T

That means:

maybe a T, maybe null

This is better than crashing on empty input.

if (stack.pop()) |value| {
    std.debug.print("{}\n", .{value});
} else {
    std.debug.print("empty\n", .{});
}

Use optionals for expected absence.

Use errors for operations that can fail for operational reasons, such as allocation, full capacity, or invalid input.

Returning Errors

push can fail because the stack has fixed capacity.

So it returns:

!void

This means:

success, or an error

The error is explicit:

if (self.len == self.items.len) return error.Full;

Then callers must handle it:

try stack.push(10);

This makes the collection’s limits visible.

A Unique List

Now let’s build a small collection with a different rule.

It stores each integer at most once.

const UniqueList = struct {
    items: std.ArrayList(i32),

    pub fn init(allocator: std.mem.Allocator) UniqueList {
        return UniqueList{
            .items = std.ArrayList(i32).init(allocator),
        };
    }

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

    pub fn contains(self: *const UniqueList, value: i32) bool {
        for (self.items.items) |item| {
            if (item == value) return true;
        }

        return false;
    }

    pub fn append(self: *UniqueList, value: i32) !void {
        if (self.contains(value)) return;

        try self.items.append(value);
    }

    pub fn slice(self: *const UniqueList) []const i32 {
        return self.items.items;
    }
};

Using it:

pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();

    var list = UniqueList.init(gpa.allocator());
    defer list.deinit();

    try list.append(10);
    try list.append(20);
    try list.append(10);

    std.debug.print("{any}\n", .{list.slice()});
}

Output:

{ 10, 20 }

The second 10 is ignored.

The rule lives inside the collection.

Callers do not need to remember to check for duplicates themselves.

Wrapping Standard Collections

UniqueList wraps std.ArrayList.

This is a good technique.

You can use the standard library for storage and still enforce your own API.

Examples:

Stack over ArrayList
Queue over ArrayList
UniqueList over ArrayList
NameTable over StringHashMap
ObjectPool over ArrayList

The wrapper hides operations that would break your rule.

For example, UniqueList should not expose direct mutable access to its inner ArrayList, because a caller could insert duplicates.

Ownership Rules

Every collection should make ownership clear.

Ask these questions:

Does the collection allocate memory?
Does it own the memory?
Who calls deinit?
Does it store borrowed slices?
Does it copy inserted data?
Does removal free anything?

A fixed stack owns its storage directly:

items: [capacity]T

No allocator, no deinit.

An ArrayList wrapper owns heap memory:

items: std.ArrayList(T)

It needs deinit.

A string map may store borrowed keys:

try map.put("name", value);

or owned keys:

const copy = try allocator.dupe(u8, name);
try map.put(copy, value);

The cleanup rules are different.

Borrowed vs Owned Data

Suppose a collection stores strings.

Borrowed version:

const NameList = struct {
    items: std.ArrayList([]const u8),
};

This stores slices. It does not copy the bytes.

The caller must ensure those bytes remain valid.

Owned version:

const OwnedNameList = struct {
    allocator: std.mem.Allocator,
    items: std.ArrayList([]u8),
};

This collection copies each string into heap memory and frees it later.

That design needs more code, but ownership is safer.

An Owned String List

const OwnedStringList = struct {
    allocator: std.mem.Allocator,
    items: std.ArrayList([]u8),

    pub fn init(allocator: std.mem.Allocator) OwnedStringList {
        return OwnedStringList{
            .allocator = allocator,
            .items = std.ArrayList([]u8).init(allocator),
        };
    }

    pub fn deinit(self: *OwnedStringList) void {
        for (self.items.items) |item| {
            self.allocator.free(item);
        }

        self.items.deinit();
    }

    pub fn append(self: *OwnedStringList, value: []const u8) !void {
        const copy = try self.allocator.dupe(u8, value);
        errdefer self.allocator.free(copy);

        try self.items.append(copy);
    }

    pub fn slice(self: *const OwnedStringList) []const []u8 {
        return self.items.items;
    }
};

Important line:

errdefer self.allocator.free(copy);

If append fails after copying the string, errdefer frees the copy.

Without this, allocation failure inside items.append could leak memory.

This is why collection code must be careful.

Designing Cleanup

If a collection allocates, give it a deinit.

pub fn deinit(self: *Self) void {
    // free owned resources
}

Callers should use:

defer collection.deinit();

If a collection does not allocate, it usually does not need deinit.

For example, this fixed stack owns only inline storage:

items: [capacity]T

No heap memory exists.

Exposing Slices

Many collections expose their contents as a slice:

pub fn slice(self: *const Self) []const T {
    return self.items[0..self.len];
}

A read-only slice is safer:

[]const T

It lets callers read items without changing the collection.

A mutable slice:

[]T

is more dangerous because callers can modify elements directly.

Sometimes that is fine. Sometimes it breaks your collection’s rule.

For UniqueList, a mutable slice could let the caller create duplicates by assigning values.

So prefer []const T unless mutation is part of the design.

Keep the API Small

A collection should expose only the operations it wants to support.

For a stack:

push
pop
peek
len
isEmpty

For a queue:

enqueue
dequeue
peek
len
isEmpty

For a map:

put
get
remove
contains
iterator

Do not expose everything by default.

A smaller API is easier to maintain and harder to misuse.

Test the Invariants

An invariant is a rule that must always remain true.

For FixedStack:

len <= capacity
items[0..len] are valid
items[len..capacity] are ignored

For a ring buffer:

head < capacity
len <= capacity
logical index maps through modulo

For a unique list:

no duplicate values

Write tests for these rules.

test "fixed stack pops in reverse order" {
    var stack = FixedStack(i32, 4).init();

    try stack.push(10);
    try stack.push(20);

    try std.testing.expectEqual(@as(?i32, 20), stack.pop());
    try std.testing.expectEqual(@as(?i32, 10), stack.pop());
    try std.testing.expectEqual(@as(?i32, null), stack.pop());
}

Tests are especially useful for collections because small mistakes can corrupt state.

Common Beginner Mistakes

The first mistake is exposing internal fields too freely. If callers can change len, they can break the collection.

The second mistake is forgetting cleanup for owned memory.

The third mistake is returning mutable access when read-only access would be enough.

The fourth mistake is not handling allocation failure after partially changing state.

The fifth mistake is making the collection too general too early.

Start with the rule your program needs. Generalize later.

A Useful Mental Model

A collection is a small machine.

It has state:

fields

It has operations:

functions

It has rules:

invariants

Good collection code keeps those three things aligned.

The fields should support the rules.

The functions should protect the rules.

The caller should not need to remember hidden rules.

Summary

To build your own collection in Zig, define a struct, choose the state, and write methods that protect the collection’s rules.

Use fixed arrays when capacity is known.

Use ArrayList when the collection grows.

Use allocators when the collection owns heap memory.

Use deinit when cleanup is needed.

Expose slices carefully.

Keep the API small.

Most importantly, decide ownership and invariants before you write too much code.

Start with the Rule

Building Your Own Collections

Start with the Rule

A Fixed Stack

The Fields Are the Design

Why items Is Undefined

Make Invalid States Impossible

A Generic Fixed Stack

Methods Are Just Functions

Returning Optionals

Returning Errors

A Unique List

Wrapping Standard Collections

Ownership Rules

Borrowed vs Owned Data

An Owned String List

Designing Cleanup

Exposing Slices

Keep the API Small

Test the Invariants

Common Beginner Mistakes

A Useful Mental Model

Summary

Why `items` Is Undefined