Day 52: std.array_list模块：动态数组实现

1. 引言：`std.mem.ArrayList`的扩展

在Zig中，虽然切片（slice）提供了对连续内存的强大、灵活的视图，但它们本身是固定大小的。当需要一个可以动态增长的数组时，std.ArrayList 就派上了用场。它是对 std.mem.Allocator 的一个封装，提供了一个易于使用的、类似于C++ std::vector 或Rust Vec<T> 的动态数组。本节将深入探讨其实现与使用。

2. 定义：`ArrayList(T)`

ArrayList 是一个泛型结构体，通过 std.ArrayList(T) 的形式进行实例化，其中 T 是你想存储在列表中的元素类型。

它的基本结构包含三个主要部分：

items: 一个指向堆上分配内存的 []T 切片。
capacity: 当前已分配内存能够容纳的元素数量。
len: 当前列表中实际存储的元素数量。

创建一个ArrayList 需要一个分配器（Allocator）实例：

const std = @import("std");

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

    var list = std.ArrayList(u8).init(allocator);
    defer list.deinit(); // 释放所有内存

    // ... 使用list
}

3. 操作：`append`, `insert`, `pop`

ArrayList 提供了一套丰富的API来管理其内容。

append(item: T) !void: 在列表末尾添加一个元素。如果当前容量不足，它会自动进行扩容。
insert(index: usize, item: T) !void: 在指定索引处插入一个元素，其后的元素会向后移动。
pop() T: 移除并返回列表的最后一个元素。
orderedRemove(index: usize) T: 移除指定索引的元素，并保持剩余元素的顺序。
swapRemove(index: usize) T: 移除指定索引的元素，用最后一个元素替换它。这比orderedRemove更快，但不保持顺序。

try list.append('a');
try list.append('b');
try list.append('d');

try list.insert(2, 'c'); // list.items现在是 "abcd"

const last = list.pop(); // last = 'd'
std.debug.print("Popped: {c}
", .{last});

const removed = list.orderedRemove(0); // removed = 'a', list.items现在是 "bc"
std.debug.print("Removed: {c}
", .{removed});

4. 扩容：`ensureTotalCapacity`

当你append一个元素而len == capacity时，ArrayList会自动为你处理内存的重新分配和旧数据的复制。这个过程通常遵循一个增长因子策略（例如，容量翻倍），以摊销分配成本。

你也可以手动管理容量：

ensureTotalCapacity(new_capacity: usize) !void: 确保列表至少有new_capacity的容量。
resize(new_len: usize) !void: 调整列表的长度。如果new_len大于当前长度，新元素是未定义的。

// 预分配100个元素的空间，避免多次重新分配
try list.ensureTotalCapacity(100);

5. 示例：动态列表

下面是一个完整的例子，展示了如何创建、填充和迭代一个ArrayList。

const std = @import("std");

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

    var numbers = std.ArrayList(i32).init(allocator);
    defer numbers.deinit();

    // 添加元素
    for (0..10) |i| {
        try numbers.append(@intCast(i));
    }

    // 迭代和打印
    for (numbers.items) |num, i| {
        std.debug.print("Index {d}: {d}\n", .{i, num});
    }

    std.debug.print("Final length: {d}\n", .{numbers.len});
}

6. 实践练习：用`ArrayList`实现一个队列

使用std.ArrayList来实现一个简单的FIFO（先进先出）队列。你需要实现以下功能：

enqueue(item: T): 将元素添加到队列尾部。
dequeue() ?T: 从队列头部移除并返回一个元素，如果队列为空则返回null。

点击查看参考实现

const std = @import("std");

fn Queue(comptime T: type) type {
    return struct {
        list: std.ArrayList(T),

        pub fn init(allocator: std.mem.Allocator) Self {
            return .{ .list = std.ArrayList(T).init(allocator) };
        }

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

        pub fn enqueue(self: *Self, item: T) !void {
            try self.list.append(item);
        }

        pub fn dequeue(self: *Self) ?T {
            if (self.list.len == 0) {
                return null;
            }
            return self.list.orderedRemove(0);
        }
    };
}

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

    var q = Queue(i32).init(allocator);
    defer q.deinit();

    try q.enqueue(10);
    try q.enqueue(20);

    std.debug.print("Dequeued: {any}\n", .{q.dequeue()}); // 10
    std.debug.print("Dequeued: {any}\n", .{q.dequeue()}); // 20
    std.debug.print("Dequeued: {any}\n", .{q.dequeue()}); // null
}

7. 常见问题

容量增长策略是怎样的？ 默认情况下，当需要扩容时，ArrayList会尝试将容量加倍。这是一种常见的摊销策略，可以在大多数情况下提供良好的性能。

迭代器失效 任何可能导致重新分配的操作（如append、insert）都会使之前获取的items切片失效。在修改列表后，应重新从.items获取最新的切片。

var list = std.ArrayList(u8).init(allocator);
defer list.deinit();
try list.append('a');
const items1 = list.items;
try list.append('b'); // 可能导致重新分配
// items1现在可能是一个悬垂指针！
const items2 = list.items; // 总是使用最新的切片
std.debug.print("Items: {s}\n", .{items2});

8. 总结

std.ArrayList是Zig标准库中不可或缺的数据结构，它通过封装内存分配器，提供了一个健壮且高效的动态数组。它完美地体现了Zig的哲学：在提供高级抽象的同时，仍然保持对底层内存的明确控制（通过分配器）。掌握ArrayList是进行任何涉及动态数据集合的Zig编程的关键一步。

Day 52: std.array_list模块：动态数组实现

1. 引言：std.mem.ArrayList的扩展

2. 定义：ArrayList(T)

3. 操作：append, insert, pop

4. 扩容：ensureTotalCapacity