# Start with the Rule

### Building Your Own Collections

A collection is a type that stores many values.

You have already seen several examples:

```zig
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:

```text
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:

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

A unique list promises:

```text
each value appears at most once
```

A fixed buffer promises:

```text
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.

```zig
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:

```zig
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:

```text
30
20
10
```

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

## The Fields Are the Design

Look at the fields:

```zig
items: [8]i32,
len: usize,
```

The array stores the values.

The length tells us how many slots are currently used.

The valid items are:

```zig
items[0..len]
```

The unused part of the array does not matter.

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

The values after `len` are not part of the stack.

## Why `items` Is Undefined

The stack starts with:

```zig
.items = undefined
```

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

At the beginning:

```text
len = 0
```

So the stack contains no valid items.

When we push:

```zig
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:

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

They should not manually write:

```zig
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.

```zig
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:

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

Example:

```zig
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:

```text
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:

```zig
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:

```zig
self: *Self
```

because it modifies the stack.

This method:

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

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

takes:

```zig
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:

```zig
?T
```

That means:

```text
maybe a T, maybe null
```

This is better than crashing on empty input.

```zig
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:

```zig
!void
```

This means:

```text
success, or an error
```

The error is explicit:

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

Then callers must handle it:

```zig
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.

```zig
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:

```zig
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:

```text
{ 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:

```text
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:

```text
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:

```zig
items: [capacity]T
```

No allocator, no `deinit`.

An `ArrayList` wrapper owns heap memory:

```zig
items: std.ArrayList(T)
```

It needs `deinit`.

A string map may store borrowed keys:

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

or owned keys:

```zig
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:

```zig
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:

```zig
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

```zig
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:

```zig
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`.

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

Callers should use:

```zig
defer collection.deinit();
```

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

For example, this fixed stack owns only inline storage:

```zig
items: [capacity]T
```

No heap memory exists.

## Exposing Slices

Many collections expose their contents as a slice:

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

A read-only slice is safer:

```zig
[]const T
```

It lets callers read items without changing the collection.

A mutable slice:

```zig
[]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:

```text
push
pop
peek
len
isEmpty
```

For a queue:

```text
enqueue
dequeue
peek
len
isEmpty
```

For a map:

```text
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`:

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

For a ring buffer:

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

For a unique list:

```text
no duplicate values
```

Write tests for these rules.

```zig
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:

```text
fields
```

It has operations:

```text
functions
```

It has rules:

```text
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.