Zig标准库：最全数据结构深度解析（1）

最近新闻看到17岁中专女生拿下阿里全球数学竞赛第12名。咱们学习标准库中的数据结构是和学习数学是一脉相承的，结构体很多，也非常枯燥，但是不能全面解读过一遍，你很难写出合理的代码。所以，这一章节我们开始深度解析Zig中的数据结构，大家坐稳，让我们一起小跑前进。

1.1 ArrayList

Zig中广泛使用了std.ArrayList，它充当了一个可以动态改变大小的缓冲区。std.ArrayList(T)类似于C++中的std::vector和Rust中的Vec。deinit()方法会释放ArrayList的所有内存。我们可以通过其切片字段（.items）来读取和写入其中的数据。

接下来，我们将讲解测试分配器（std.testing.allocator）的使用方式。这是一种特殊的分配器，仅在测试环境中生效，并具备检测内存泄漏的功能。在实际编码过程中，请根据具体需求选择合适的分配器。

const std = @import("std");
const expect = std.testing.expect;

const eql = std.mem.eql;
const ArrayList = std.ArrayList;
const test_allocator = std.testing.allocator;

test "arraylist" {
    var list = ArrayList(u8).init(test_allocator);
    defer list.deinit();
    try list.append('H');
    try list.append('e');
    try list.append('l');
    try list.append('l');
    try list.append('o');
    try list.appendSlice(" World!");

    try expect(eql(u8, list.items, "Hello World!"));
}

1.2 `BoundedArray`

BoundedArray是一种结构，它包含一个固定大小的数组以及当前正在使用的长度。

它可以被用作一个变长数组，可以自由地调整大小至支持数组的最大尺寸。

如果你正在寻找Zig语言中类似于Rust超级实用的ArrayVec的等价物，这就是你想要的。

当需要传递那些确切大小仅在运行时才知悉，但最大尺寸在编译时已知的小型数组，并且无需分配器（Allocator）的情况下，使用有界数组是非常有用的。

相比于分别维护缓冲区和活动长度，或者涉及到包含指针的结构，有界数组使用起来更简便也更安全。

var actual_size = 32;
var a = try BoundedArray(u8, 64).init(actual_size);
var slice = a.slice(); // a slice of the 64-byte array
var a_clone = a; // creates a copy - the structure doesn't use any internal pointers

1.3 MultiArrayList

一个多维动态数组（MultiArrayList）存储一个结构体或带标签的联合体类型的列表。它不像普通的列表那样只存储单一的项目列表，而是为结构体的每个字段或联合体的标签和裸数据分别存储独立的列表。这种方式在结构体或联合体有填充（padding）的情况下可以节省内存，并且如果计算只需要某些字段或仅仅需要标签时，能够改善缓存的使用效率。访问字段的主要API是slice()函数，该函数计算出每个字段数组的起始指针。从slice结果中，你可以通过调用.items(.)来获取字段值的切片。对于联合体，你可以调用.items(.tags)或.items(.data)。

multi_array_list.zig代码解读https://ratfactor.com/zig/stdlib-browseable2/multi_array_list.zig.html

1.4 ArrayHashMap

一个具有默认哈希和等值函数的ArrayHashMap。有关哈希和等值实现的描述，请参阅AutoContext。

array_hash_map.zig - Zig standard libraryhttps://ratfactor.com/zig/stdlib-browseable2/array_hash_map.zig.html

1.5 BufMap

BufMap在键值对进入映射之前会复制它们，并在键值对被移除时释放它们。

buf_map.zig - Zig standard libraryhttps://ratfactor.com/zig/stdlib-browseable2/buf_map.zig.html

	
test "BufMap" {
    const allocator = std.testing.allocator;
    var bufmap = BufMap.init(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());

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

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

    try bufmap.putMove(try allocator.dupe(u8, "k"), try allocator.dupe(u8, "v1"));
    try bufmap.putMove(try allocator.dupe(u8, "k"), try allocator.dupe(u8, "v2"));
}

1.6 BufSet

BufSet是一个字符串集合。在内部，BufSet会复制字符串，且永远不会接管传递给它的字符串的所有权。

https://ratfactor.com/zig/stdlib-browseable2/buf_set.zig.htmlhttps://ratfactor.com/zig/stdlib-browseable2/buf_set.zig.html

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

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

    try bufset.insert("x");
    try bufset.insert("y");
    try bufset.insert("z");
}

1.7 ComptimeStringMap

编译时优化的字符串映射，针对少量差异较大的字符串键集进行了优化。它的工作原理是在编译时按长度对键进行分类，而在运行时仅检查相同长度的字符串。

kvs_list期望一个由struct { []const u8, V }（键值对）元组组成的列表。如果你的V类型是void，那么你可以传递struct { []const u8 }（仅包含键）的元组。

test "ComptimeStringMap list literal of list literals" {
    const map = ComptimeStringMap(TestEnum, .{
        .{ "these", .D },
        .{ "have", .A },
        .{ "nothing", .B },
        .{ "incommon", .C },
        .{ "samelen", .E },
    });

    try testMap(map);
}

comptime_string_map.zig - Zig standard libraryhttps://ratfactor.com/zig/stdlib-browseable2/comptime_string_map.zig.html