# Building Generic Data Structures

### Building Generic Data Structures

A generic data structure is a data structure that works with more than one element type.

For example, an array list of `u8` stores bytes.

An array list of `i32` stores signed integers.

An array list of `User` stores `User` values.

The behavior is mostly the same, but the element type changes.

Zig does not use classes, inheritance, or a separate template language for this. Zig usually builds generic data structures with functions that return types.

#### A Simple Generic Box

Start with the smallest useful example.

```zig
fn Box(comptime T: type) type {
    return struct {
        value: T,
    };
}
```

This function receives a type named `T`.

Then it returns a new struct type whose field uses `T`.

Use it like this:

```zig
const IntBox = Box(i32);
const BoolBox = Box(bool);

const a = IntBox{ .value = 123 };
const b = BoolBox{ .value = true };
```

`IntBox` and `BoolBox` are different types.

`IntBox` has this shape:

```zig
struct {
    value: i32,
}
```

`BoolBox` has this shape:

```zig
struct {
    value: bool,
}
```

The source code is shared, but the generated types are specific.

#### Generic Types Are Compile-Time Functions

This line is the key:

```zig
fn Box(comptime T: type) type
```

It means:

Take a type at compile time.

Return a type.

That is how generic data structures usually work in Zig.

A generic type is often written as a function whose name starts with a capital letter:

```zig
fn Stack(comptime T: type) type {
    return struct {
        // fields and methods
    };
}
```

Then you create a concrete type by calling it:

```zig
const IntStack = Stack(i32);
const UserStack = Stack(User);
```

This is different from many languages.

In Zig, `Stack(i32)` does not create a value. It creates a type.

#### Using `@This()` Inside a Generic Struct

Inside the returned struct, you often need to refer to the struct itself.

Use `@This()`.

```zig
fn Pair(comptime T: type) type {
    return struct {
        first: T,
        second: T,

        pub fn swap(self: *@This()) void {
            const temp = self.first;
            self.first = self.second;
            self.second = temp;
        }
    };
}
```

For `Pair(i32)`, `@This()` means the concrete `Pair(i32)` type.

For `Pair(bool)`, `@This()` means the concrete `Pair(bool)` type.

Usage:

```zig
pub fn main() void {
    var pair = Pair(i32){
        .first = 10,
        .second = 20,
    };

    pair.swap();
}
```

After `swap`, `first` is `20` and `second` is `10`.

#### A Fixed-Size Generic Stack

Now let us build a small stack.

A stack has two basic operations:

`push` adds an item.

`pop` removes the most recent item.

This version has a fixed capacity known at compile time.

```zig
fn Stack(comptime T: type, comptime capacity: usize) type {
    return struct {
        items: [capacity]T = undefined,
        len: usize = 0,

        pub fn push(self: *@This(), value: T) !void {
            if (self.len >= capacity) {
                return error.StackFull;
            }

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

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

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

This function takes two compile-time arguments:

```zig
comptime T: type
comptime capacity: usize
```

So the element type and the stack capacity are both part of the generated type.

Use it like this:

```zig
const std = @import("std");

pub fn main() !void {
    var stack = Stack(i32, 4){};

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

    const value = stack.pop();

    std.debug.print("{?}\n", .{value});
}
```

The type of `stack` is a concrete stack of `i32` with capacity `4`.

The compiler knows the array type:

```zig
[4]i32
```

No heap allocation is needed.

#### Why Capacity Is Compile-Time Here

The stack stores its items in a fixed array:

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

In Zig, array lengths are part of the type. The compiler must know the length before runtime.

That is why `capacity` must be a compile-time value.

This works:

```zig
var stack = Stack(u8, 16){};
```

This does not work if `n` comes from user input:

```zig
const n = readNumberFromUser();
var stack = Stack(u8, n){};
```

User input is runtime data. It arrives after the program starts.

A fixed array needs a compile-time length.

#### Returning Errors from Generic Methods

The `push` method can fail when the stack is full.

```zig
pub fn push(self: *@This(), value: T) !void
```

The return type `!void` means:

Either the function succeeds and returns nothing.

Or it returns an error.

Inside the method:

```zig
if (self.len >= capacity) {
    return error.StackFull;
}
```

Zig infers an error set that includes `StackFull`.

The caller must handle the error:

```zig
try stack.push(10);
```

Generic data structures should still use normal Zig error handling. There is no special exception system.

#### Optionals for Missing Values

The `pop` method returns an optional:

```zig
pub fn pop(self: *@This()) ?T
```

The return type `?T` means:

Either the function returns a `T`.

Or it returns `null`.

If the stack is empty, there is no value to remove:

```zig
if (self.len == 0) {
    return null;
}
```

This is a good use of optionals. An empty stack is not necessarily an error. It may be a normal state.

#### Adding a `peek` Method

A stack often has a `peek` method.

`peek` returns the top item without removing it.

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

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

Now the full stack becomes:

```zig
fn Stack(comptime T: type, comptime capacity: usize) type {
    return struct {
        items: [capacity]T = undefined,
        len: usize = 0,

        pub fn push(self: *@This(), value: T) !void {
            if (self.len >= capacity) {
                return error.StackFull;
            }

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

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

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

        pub fn peek(self: *@This()) ?T {
            if (self.len == 0) {
                return null;
            }

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

This is now a small reusable generic data structure.

#### Generic Methods Still Type-Check Normally

If you create a stack of `i32`, you can only push `i32` values:

```zig
var stack = Stack(i32, 4){};

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

This is valid.

But this is not:

```zig
try stack.push(true);
```

The compiler rejects it because `true` is a `bool`, not an `i32`.

Generic code does not mean weakly typed code. Zig specializes the code and checks the concrete types.

#### A Generic Dynamic Array

The fixed stack above uses no allocator.

Many real data structures need heap memory. For that, the data structure should accept an allocator.

Here is a small generic dynamic array:

```zig
const std = @import("std");

fn Vec(comptime T: type) type {
    return struct {
        allocator: std.mem.Allocator,
        items: []T,
        len: usize,

        pub fn init(allocator: std.mem.Allocator) @This() {
            return .{
                .allocator = allocator,
                .items = &.{},
                .len = 0,
            };
        }

        pub fn deinit(self: *@This()) void {
            self.allocator.free(self.items);
            self.* = undefined;
        }

        pub fn append(self: *@This(), value: T) !void {
            if (self.len == self.items.len) {
                const new_capacity = if (self.items.len == 0)
                    4
                else
                    self.items.len * 2;

                const new_items = try self.allocator.alloc(T, new_capacity);

                @memcpy(new_items[0..self.len], self.items[0..self.len]);

                self.allocator.free(self.items);
                self.items = new_items;
            }

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

        pub fn slice(self: @This()) []T {
            return self.items[0..self.len];
        }
    };
}
```

This is simplified, but it shows the core shape.

Use it like this:

```zig
const std = @import("std");

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

    var numbers = Vec(i32).init(gpa.allocator());
    defer numbers.deinit();

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

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

Here, `Vec(i32)` creates a dynamic array type for `i32`.

#### Why the Allocator Is Stored

The dynamic array needs to allocate and free memory.

So it stores:

```zig
allocator: std.mem.Allocator
```

The caller decides which allocator to use.

This is normal Zig design. The data structure does not hide memory allocation. The allocator is visible in the API.

#### Generic Data Structures Can Use Existing `std`

In real code, you usually do not need to build every data structure yourself.

Zig’s standard library already provides many useful generic containers, such as array lists and hash maps.

For example:

```zig
const std = @import("std");

pub fn main() !void {
    var list = std.ArrayList(i32).init(std.heap.page_allocator);
    defer list.deinit();

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

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

`std.ArrayList(i32)` follows the same idea.

It is a function-like generic type. You pass the element type, and it gives you a concrete array list type.

#### Compile-Time Parameters Should Be Structural

A good compile-time parameter is part of the data structure’s shape.

Good examples:

```zig
comptime T: type
comptime capacity: usize
comptime alignment: u29
```

These affect layout, field types, or generated code.

Poor examples:

```zig
comptime username: []const u8
comptime current_time: u64
```

Those usually belong to runtime, not type structure.

Use `comptime` when the value defines what the type is.

Use runtime fields when the value defines what a value contains.

#### Mental Model

A generic data structure in Zig is usually a function that returns a type.

```zig
fn Name(comptime T: type) type {
    return struct {
        // fields using T
        // methods using T
    };
}
```

Calling that function with a type creates a concrete type:

```zig
const A = Name(u8);
const B = Name(i32);
```

Then you create values of that concrete type:

```zig
var value = A{};
```

This is the pattern behind many Zig containers.

Generic code in Zig is explicit, compile-time, and strongly typed.