Zig Iterators

Iterators. When to use one and why? Before we get into taht let’s talk about what an iterator is and how to write one for your collection. In the example below we’re creating a generic Slice with very basic features. For this post, simpler is best.

const std = @import("std");

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

        allocator: std.mem.Allocator,
        buffer: []T,
        len: usize,

        pub fn init(allocator: std.mem.Allocator) Self {}

        pub fn deinit(self: *Self) void {}

        fn resize(self: *Self, new_capacity: usize) !void {}

        pub fn append(self: *Self, item: T) !void {}

        pub fn iterator(self: *Self) SliceIterator {
            return SliceIterator{ .slice = self, .index = 0 };
        }

        pub const SliceIterator = struct {
            slice: *Self,
            index: usize,

            pub fn next(self: *SliceIterator) ?T {
                if (self.index >= self.slice.len) {
                    return null;
                }

                const item = self.slice.buffer[self.index];
                self.index += 1;
                return item;
            }
        };
    };
}

Here we have a Slice object. It’s created with a generic function that takes in a type and has a few useful methods to do some basic slice stuff. We’re going to focus on the iterating part of this the nested SliceIterator struct and the iterator() method.

An iterator is nothing more than a struct that holds our Slice and an index. It has a next() method that will return the item in the buffer at the index, and if that index is out-of-bounds it returns null, which means we’ve reached the end.

The iterator() method returns a new SliceIterator setting the index to 0. This is what the user will call to start iterating a slice. Let’s visualize this.

Slice                                          SliceIterator
   ┌──────────────────────────────┐               ┌──────────────────┐
   │ buffer: ┌─────┬─────┬─────┐  │  ◄─────────── │ .slice = &slice  │
   │         │ 'a' │ 'b' │ 'c' │  │               │ .index = 0       │
   │         └─────┴─────┴─────┘  │               └──────────────────┘
   │ len: 3                       │
   └──────────────────────────────┘


   ════════════════════════════════ it.next() calls ════════════════════════════════


   Call 1                         Call 2                         Call 3                         Call 4
   ┌─────┬─────┬─────┐           ┌─────┬─────┬─────┐           ┌─────┬─────┬─────┐           ┌─────┬─────┬─────┐
   │ 'a' │ 'b' │ 'c' │           │ 'a' │ 'b' │ 'c' │           │ 'a' │ 'b' │ 'c' │           │ 'a' │ 'b' │ 'c' │
   └─────┴─────┴─────┘           └─────┴─────┴─────┘           └─────┴─────┴─────┘           └─────┴─────┴─────┘
     ▲                                    ▲                                    ▲
     │                                    │                                    │
   index=0                             index=1                             index=2                index=3
                                                                                                    │
   index < len? YES                index < len? YES                index < len? YES                index < len? NO
     │                                    │                                    │                    │
     ▼                                    ▼                                    ▼                    ▼
   return 'a'                      return 'b'                      return 'c'                  return null
   index becomes 1                 index becomes 2                 index becomes 3              loop ends

When you call the iterator method you get a SliceIterator which itself holds a pointer back to the slice and a cursor index. Each time you call next two things happen.

1. There’s a boundary check to know where we are in the slice and whether we’ve reached the end yet.
2. Read the current index and increment the index by one then return the item.

Let’s write a quick test to see that in action.

test "slice iterator" {
    const allocator = std.heap.page_allocator;

    var slice = Slice(u32).init(allocator);
    try slice.append(10);
    try slice.append(20);
    try slice.append(30);
    try slice.append(40);
    try slice.append(50);

    assert(slice.len == 5);

    var it = slice.iterator();
    while (it.next()) |item| {
        assert(item > 0);
    }
}

That’s it. Hopefully this helps demystify iterators.