Zenn
🗂

Zig 標準ライブラリで用意されているコレクション型をざっくり押さえる

2022/08/12に公開
Zig
tech

Zig の標準ライブラリではコレクション型が提供されていますが、ドキュメント整備が途上ということもあり、どのようなコレクションが提供されているのかを把握するのが難しいと感じています。

提供されているコレクションを簡単にまとめ、適切な場面で適切なコレクション型を利用することができるようになることを狙いとした記事です。

なお、対象のZigバージョンは 0.10.0-dev.3513+e218b7ea0 です。
また、掲載しているサンプルコードは以下のgistにまとめてあります。
https://gist.github.com/magurotuna/90335c8df3df00392d966156a371f4fa

ArrayList

全要素がメモリ上で連続した領域に配置され、実行時に動的に長さを変えることができるコレクションです。
C++のstd::vector, Rustのstd::vec::Vec に相当します。
添字によるランダムアクセス、末尾への要素追加、順方向・逆方向のイテレーションをしたいユースケースで役立ちます。

サンプルコード
test "ArrayList" {
    var list = ArrayList(usize).init(testing.allocator);
    defer list.deinit();

    {
        var i: usize = 0;
        while (i < 10) : (i += 1) {
            try list.append(i);
        }
    }

    for (list.items) |v, i| {
        try testing.expectEqual(v, i);
    }

    try testing.expectEqual(@as(usize, 9), list.popOrNull().?);
    try testing.expectEqual(@as(usize, 9), list.items.len);
    try testing.expectEqual(@as(usize, 4), list.items[4]);
}

MultiArrayList

構造体を要素とする ArrayList を作りたいときは MultiArrayList の利用を検討してみてください。以下のような構造体 S があったときに

const S = struct {
    a: u32,
    b: []const u8,
};

以下のように S をまとめて ArrayList に格納するというやり方があります。

S をまるごとメモリの連続領域に格納
+-----------------------
| S_1 | S_2 | S_3 | ...
+-----------------------

これは ArrayList(S) に相当します。
一方、以下のように、S の各フィールドを別々のリストで管理するやり方があります。こちらが MultiArrayList(S) に相当します。

フィールド a をメモリの連続領域に格納
+-----------------------
| a_1 | a_2 | a_3 | ...
+-----------------------

フィールド b をメモリの別の連続領域に格納
+-----------------------
| b_1 | b_2 | b_3 | ...
+-----------------------

このようにフィールドごとに別々のリストを使って値を管理することで、メモリの節約[1]やキャッシュ利用の効率化[2]を図るのが MultiArrayList です。

サンプルコード
test "MultiArrayList" {
    const allocator = testing.allocator;

    const Foo = struct {
        field_one: u32,
        field_two: []const u8,
    };

    var list = MultiArrayList(Foo){};
    defer list.deinit(allocator);

    try testing.expectEqual(@as(usize, 0), list.items(.field_one).len);

    try list.append(allocator, .{
        .field_one = 1,
        .field_two = "foo",
    });
    try list.append(allocator, .{
        .field_one = 2,
        .field_two = "bar",
    });

    try testing.expectEqualSlices(u32, list.items(.field_one), &[_]u32{ 1, 2 });

    try testing.expectEqual(@as(usize, 2), list.items(.field_two).len);
    try testing.expectEqualStrings("foo", list.items(.field_two)[0]);
    try testing.expectEqualStrings("bar", list.items(.field_two)[1]);
}

SegmentedList

ArrayList と同様に、高速なランダムアクセスと末尾への追加・削除を行うことができるデータ構造です。
違いは、ArrayList は確保したメモリ領域が足りなくなった場合は、別の大きな領域を確保して、すべての要素をそこにコピーするのに対して、SegmentedList では、追加領域を確保したあとも、それまで格納されていたデータは元の位置に残るというところにあります。
つまり、ArrayList はすべての要素が順番にメモリ上に並んでいるのが保証されていますが、SegmentedList ではある程度の大きさの要素の「固まり」ごとに、別のメモリ領域に配置されることになります。
SegmentedList のメリットは、要素を指すポインタが生存する期間が、SegmentedList 自体のライフタイムと一致することです。さきほど書いたように、ArrayList では、確保したメモリ領域が足りなくなったときに他の領域へのコピーが行われるため、元の領域を指すポインタはこの時点で不正となります。一方、SegmentedList では、メモリ領域が足りなくなった場合にも元の要素のコピーは行われないので、ポインタが不正になることはありません。

サンプルコード
test "SegmentedList" {
    const L = SegmentedList(u32, 2);
    var list = L{};
    defer list.deinit(testing.allocator);

    try list.append(testing.allocator, 1);
    try list.append(testing.allocator, 2);
    try list.append(testing.allocator, 3);
    try testing.expectEqual(@as(usize, 3), list.count());

    {
        var it = list.iterator(0);
        var s: u32 = 0;
        while (it.next()) |item| {
            s += item.*;
        }
        try testing.expectEqual(@as(u32, 6), s);
    }

    {
        var it = list.constIterator(0);
        var s: u32 = 0;
        while (it.next()) |item| {
            s += item.*;
        }
        try testing.expectEqual(@as(u32, 6), s);
    }
}

SinglyLinkedList

片方向連結リストです。C++の std::forward_list に相当します。
要素のメモリ、ライフタイムの管理は呼び出し側の責任です。

サンプルコード
test "SinglyLinkedList" {
    const L = SinglyLinkedList(u32);
    var list = L{};

    try testing.expectEqual(@as(usize, 0), list.len());

    var one = L.Node{ .data = 1 };
    var two = L.Node{ .data = 2 };

    list.prepend(&two);
    list.prepend(&one);

    {
        var it = list.first;
        var val: u32 = 1;
        while (it) |node| : (it = node.next) {
            try testing.expectEqual(val, node.data);
            val += 1;
        }
    }

    try testing.expectEqual(@as(usize, 2), list.len());
    try testing.expectEqual(@as(u32, 1), list.first.?.data);
    try testing.expectEqual(@as(u32, 1), list.popFirst().?.data);
}

TailQueue

双方向連結リストです。C++の std::list、Rust の std::collections::LinkedList に相当します。
要素のメモリ、ライフタイムの管理は呼び出し側の責任です。

サンプルコード
test "TailQueue" {
    const L = TailQueue(u32);
    var list = L{};

    try testing.expectEqual(@as(usize, 0), list.len);

    var one = L.Node{ .data = 1 };
    var two = L.Node{ .data = 2 };
    var three = L.Node{ .data = 3 };

    list.append(&two);
    list.append(&three);
    list.prepend(&one);
    try testing.expectEqual(@as(usize, 3), list.len);

    // 順方向イテレート
    {
        var it = list.first;
        var val: u32 = 1;
        while (it) |node| : (it = node.next) {
            try testing.expectEqual(val, node.data);
            val += 1;
        }
    }

    // 逆方向イテレート
    {
        var it = list.last;
        var val: u32 = 3;
        while (it) |node| : (it = node.prev) {
            try testing.expectEqual(val, node.data);
            val -= 1;
        }
    }
}

HashMap

いわゆる連想配列です。C++のstd::unordered_map、 Rust のstd::collections::HashMap に相当します。
基本的には AutoHashMap という Auto という prefix がついたものを使うことになると思います。こちらはハッシュ関数やキーの同値判定を行う関数をよしなに生成してくれます。
逆に、ハッシュ関数やキーの同値判定をカスタマイズしたい場合は、HashMap を使います。

サンプルコード
test "AutoHashMap" {
    var map = AutoHashMap(u32, u8).init(testing.allocator);
    defer map.deinit();

    try map.put(0, 'a');
    try map.put(1, 'b');

    try testing.expectEqual(@as(u8, 'a'), map.get(0).?);
    try testing.expectEqual(@as(u8, 'b'), map.get(1).?);
    try testing.expect(map.get(2) == null);

    const prev = try map.fetchPut(0, 'x');
    try testing.expectEqual(@as(u32, 0), prev.?.key);
    try testing.expectEqual(@as(u8, 'a'), prev.?.value);
}

ArrayHashMap

挿入順が保持される HashMap です。挿入順を保持したままイテレーションしたい場合や、イテレーション時のパフォーマンスを重視する場合は HashMap よりも ArrayHashMap を利用するのが良いようです。
HashMap と同様に、AutoArrayHashMap も用意されていて、基本的なユースケースではこちらで事足りるかと思います。

サンプルコード
test "AutoArrayHashMap" {
    var map = AutoArrayHashMap(u32, u8).init(testing.allocator);
    defer map.deinit();

    try map.put(0, 'a');
    try map.put(1, 'b');

    var it = map.iterator();
    try testing.expectEqual(@as(u8, 'a'), it.next().?.value_ptr.*);
    try testing.expectEqual(@as(u8, 'b'), it.next().?.value_ptr.*);
    try testing.expect(it.next() == null);
}

StringHashMap, StringArrayHashMap

キーが文字列 ([]const u8) の場合はこれらを利用します。なお、キーとなる文字列のメモリを管理するのは呼び出し側の責任です。管理するデータのライフタイムをデータ構造と同一にしたい場合は、次に紹介する BufMap の利用を検討してください。
使い方は HashMap, ArrayHashMap と同じなので割愛します。

BufMap, BufSet

BufMap は、キー、バリューがともに []const u8 であるような HashMap です。
ただし、キー・バリューを追加するときに、文字列をコピーしてそのライフタイムを BufMap 内で管理するようにする、という違いがあります[3]。
例えば、BufMap を使っている場合、値の上書きが発生する際、上書きされる側のメモリ領域を自動で適切に解放してくれます。また、deinit() メソッドによって、格納されているすべてのキー、バリューのメモリ領域が解放されます。

BufSet はキーが []const u8、バリューが void であるような HashMap で、文字列の集合を表現したいときに利用できます。
メモリ管理については BufMap と同様です。

サンプルコード
test "BufMap" {
    var bufmap = BufMap.init(testing.allocator);
    defer bufmap.deinit();

    try bufmap.put("x", "1");
    try testing.expect(mem.eql(u8, bufmap.get("x").?, "1"));
    try testing.expect(1 == bufmap.count());

    try bufmap.put("x", "2");
    try testing.expect(mem.eql(u8, bufmap.get("x").?, "2"));
    try testing.expect(1 == bufmap.count());

    bufmap.remove("x");
    try testing.expect(0 == bufmap.count());
}

test "BufSet" {
    var bufset = BufSet.init(testing.allocator);
    defer bufset.deinit();

    try bufset.insert("x");
    try testing.expect(bufset.count() == 1);
    try testing.expect(bufset.contains("x"));
    bufset.remove("x");
    try testing.expect(bufset.count() == 0);
}

ComptimeStringMap

キーが []const u8 で、コンパイル時にすべての要素が確定するような Map が欲しい場合、ComptimeStringMap の出番です。
コンパイル時に前計算を行うことで、実行時のlookup処理の最適化を行います。具体的には、lookup時に、キーとなる文字列の長さが一致する部分のみを探索するようになります。例えば、map.get("foo") というようにしたら、キーの長さが3のもののみを探索します。

サンプルコード
test "ComptimeStringMap" {
    const KV = struct {
        @"0": []const u8,
        @"1": u32,
    };
    const map = ComptimeStringMap(u32, [_]KV{
        .{ .@"0" = "foo", .@"1" = 42 },
        .{ .@"0" = "barbaz", .@"1" = 99 },
    });

    try testing.expectEqual(@as(u32, 42), map.get("foo").?);
    try testing.expectEqual(@as(u32, 99), map.get("barbaz").?);
    try testing.expect(!map.has("hello"));
    try testing.expect(map.get("hello") == null);
}

BoundedArray

正確なサイズは実行時になるまで不明だが、最大サイズはコンパイル時に分かっている、というような配列が欲しいときに便利なデータ構造です。
コンパイル時に最大サイズ分のメモリ領域を確保するため、アロケータが不要です。

アイデアとしてはRust の smallvec に近いです。ただし smallvec は、事前に確保した配列サイズを超えるとヒープ領域に移動してくれますが、BoundedArray は、指定した最大サイズを超える要素数を指定すると、Overflow エラーになります。

サンプルコード
test "BoundedArray" {
    const BoundedArrayMax4 = BoundedArray(u8, 4);

    try testing.expectError(error.Overflow, BoundedArrayMax4.init(8));

    var a = try BoundedArrayMax4.init(2);

    try testing.expectEqual(a.capacity(), 4);
    try testing.expectEqual(a.len, 2);
    try testing.expectEqual(a.slice().len, 2);
    try testing.expectEqual(a.constSlice().len, 2);

    try a.resize(4);
    try testing.expectEqual(a.len, 4);

    a.set(0, 42);
    try testing.expectEqual(a.get(0), 42);
}

StaticBitSet, DynamicBitSet

ビット集合を表すデータ構造です。C++の std::bitset に相当します。
コンパイル時にビットサイズが決定する場合は StaticBitSet を、実行時に決定する場合は DynamicBitSet を利用します。
ビットサイズによって最適なデータ構造が選択されます。ビットサイズが小さい場合は整数を利用し、大きい場合は配列が使われます。

サンプルコード
test "StaticBitSet" {
    var bitset = StaticBitSet(4).initEmpty();

    try testing.expectEqual(@as(usize, 0), bitset.count());

    bitset.setValue(1, true);
    try testing.expectEqual(@as(usize, 1), bitset.count());
    try testing.expect(!bitset.isSet(0));
    try testing.expect(bitset.isSet(1));

    bitset.setRangeValue(.{ .start = 2, .end = 4 }, true);
    try testing.expectEqual(@as(usize, 3), bitset.count());
}

test "DynamicBitSet" {
    const size = @intCast(usize, time.timestamp()) % 60;

    var bitset = try DynamicBitSet.initEmpty(std.testing.allocator, size);
    defer bitset.deinit();

    try testing.expectEqual(@as(usize, 0), bitset.count());

    bitset.toggleAll();
    try testing.expectEqual(size, bitset.count());
}

EnumArray, EnumMap, EnumSet

Enum をキー（インデックス）とする Array, Map, Set が欲しい場合に便利なデータ構造です。

サンプルコード
test "EnumArray" {
    const A = EnumArray(enum {
        foo,
        bar,
    }, u32);
    try testing.expectEqual(@as(usize, 2), A.len);

    var a = A.initFill(42);
    try testing.expectEqual(@as(u32, 42), a.get(.foo));
    try testing.expectEqual(@as(u32, 42), a.get(.bar));
}

test "EnumMap" {
    const A = EnumMap(enum {
        foo,
        bar,
    }, u32);

    try testing.expectEqual(@as(usize, 2), A.len);

    var a = A{};
    try testing.expectEqual(@as(usize, 0), a.count());
    a.put(.foo, 42);
    try testing.expectEqual(@as(usize, 1), a.count());
    try testing.expect(a.contains(.foo));
    try testing.expect(!a.contains(.bar));
}

test "EnumSet" {
    const A = EnumSet(enum {
        foo,
        bar,
    });

    try testing.expectEqual(@as(usize, 2), A.len);

    var a = A{};
    try testing.expectEqual(@as(usize, 0), a.count());
    a.insert(.foo);
    try testing.expectEqual(@as(usize, 1), a.count());
    try testing.expect(a.contains(.foo));
    try testing.expect(!a.contains(.bar));

    a.remove(.foo);
    try testing.expectEqual(@as(usize, 0), a.count());
}

PriorityQueue, PriorityDequeue

優先度付きキューです。C++のstd::priority_queue や Rust の std::collections::BinaryHeap に相当します。

最大値、もしくは最小値のみを高速に取り出したい場合は PriorityQueue を使い、最大値と最小値の両方を高速に取り出したい場合は PriorityDequeue を利用します。

サンプルコード
test "PriorityQueue" {
    {
        const MinHeap = PriorityQueue(u32, void, struct {
            fn lessThan(context: void, a: u32, b: u32) math.Order {
                _ = context;
                return math.order(a, b);
            }
        }.lessThan);
        var queue = MinHeap.init(testing.allocator, {});
        defer queue.deinit();

        try queue.add(12);
        try queue.add(7);
        try queue.add(23);
        try testing.expectEqual(@as(usize, 3), queue.len);
        try testing.expectEqual(@as(u32, 7), queue.remove());
        try testing.expectEqual(@as(u32, 12), queue.remove());
        try testing.expectEqual(@as(u32, 23), queue.remove());
    }

    {
        const MaxHeap = PriorityQueue(u32, void, struct {
            fn greaterThan(context: void, a: u32, b: u32) math.Order {
                _ = context;
                return math.order(a, b).invert();
            }
        }.greaterThan);
        var queue = MaxHeap.init(testing.allocator, {});
        defer queue.deinit();

        try queue.add(12);
        try queue.add(7);
        try queue.add(23);
        try testing.expectEqual(@as(usize, 3), queue.len);
        try testing.expectEqual(@as(u32, 23), queue.remove());
        try testing.expectEqual(@as(u32, 12), queue.remove());
        try testing.expectEqual(@as(u32, 7), queue.remove());
    }
}

test "PriorityDequeue" {
    const PQ = PriorityDequeue(u32, void, struct {
        fn lessThan(context: void, a: u32, b: u32) math.Order {
            _ = context;
            return math.order(a, b);
        }
    }.lessThan);
    var queue = PQ.init(testing.allocator, {});
    defer queue.deinit();

    try queue.add(12);
    try queue.add(7);
    try queue.add(23);
    try testing.expectEqual(@as(usize, 3), queue.len);
    try testing.expectEqual(@as(u32, 7), queue.removeMin());
    try testing.expectEqual(@as(u32, 23), queue.removeMax());
    try testing.expectEqual(@as(u32, 12), queue.removeMin());
}

Treap

平衡二分探索木です。Treap - Wikipedia
赤黒木などの他の平衡二分探索木ではなく Treap が採用されているのは、実装のシンプルさというのが最大の理由とのことです。
https://github.com/ziglang/zig/pull/11444

サンプルコード
test "Treap" {
    const MyTreap = Treap(u32, math.order);
    const Node = MyTreap.Node;
    var treap = MyTreap{};
    var nodes: [10]Node = undefined;

    var i: u32 = 0;
    while (i < 10) : (i += 1) {
        var entry = treap.getEntryFor(i);
        try testing.expectEqual(i, entry.key);
        try testing.expect(entry.node == null);

        entry.set(&nodes[i]);
    }

    try testing.expectEqual(@as(u32, 9), treap.getMax().?.key);
    try testing.expectEqual(@as(u32, 0), treap.getMin().?.key);
}

おまけ

C++ の std::deque、Rustの std::collections::VecDeque に相当するデータ構造は提供されていないということに気づき、ざっくりと自作してみました。
ArrayList と同じくランダムアクセスと末尾への追加・削除が高速に行えるのに加えて、先頭への追加・削除も効率的に行うことができるデータ構造です。

https://github.com/magurotuna/zig-deque

脚注

  1. 構造体をメモリに配置する際にパディングが必要な場合 ↩︎

  2. ある計算を行う際に、構造体の一部のフィールドのみが必要になる場合 ↩︎

  3. key, value の所有権を奪う putMove というメソッドもあります。 ↩︎

Discussion