第11章 常用数据结构
第11章 常用数据结构
在前面的章节中，我们学习了数组（Array）和切片（Slice）。它们非常高效，但有一个共同的限制：长度固定或依赖外部内存。
在实际开发中，我们经常需要能动态增长或支持键值对映射的容器。Zig 标准库提供了两个最常用的数据结构来满足这些需求：
std.ArrayList：动态数组。std.AutoHashMap（及相关变体）：哈希表。
本章将带你熟练掌握这两种数据结构。
1. 动态数组 (ArrayList)
std.ArrayList(T) 是 Zig 中最常用的连续内存容器，类似于 C++ 的 std::vector 或 Rust 的 Vec。
核心概念：容量 vs 长度
理解动态数组，首先要区分两个概念：
- 长度 (Length)：数组中实际存储了多少个元素 (
items.len)。 - 容量 (Capacity)：底层分配的内存能容纳多少个元素 (
capacity)。
当添加元素且 len == capacity 时，ArrayList 会自动申请一块更大的内存，将旧数据复制过去，并释放旧内存。
基本用法
使用 ArrayList 的标准流程：初始化 -> 延迟释放 -> 使用。
const std = @import("std");
pub fn main() !void {
// 1. 初始化分配器
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
// 2. 创建 ArrayList
// 需要指定元素类型 (u8) 和分配器
var list = std.ArrayList(u8).init(allocator);
// 3. 确保释放内存
defer list.deinit();
// 4. 添加元素 (append)
try list.append('H');
try list.append('e');
try list.append('l');
try list.appendSlice("lo World"); // 添加切片
// 5. 访问元素
// list.items 是一个 []T 切片，可以直接访问
std.debug.print("String: {s}
", .{list.items});
std.debug.print("Length: {d}, Capacity: {d}
", .{list.items.len, list.capacity});
}常用方法
append(item)：在末尾添加一个元素。appendSlice(slice)：在末尾添加一个切片。pop()：移除并返回最后一个元素。popOrNull()：移除并返回最后一个元素，如果列表为空则返回null。orderedRemove(index)：移除指定索引的元素，并保留后续元素的顺序（较慢，O(N)）。swapRemove(index)：移除指定索引的元素，通过将最后一个元素移到该位置来填补空缺（不保留顺序，极快，O(1)）。insert(index, item)：在指定位置插入元素。
// swapRemove 示例
var list = std.ArrayList(u32).init(allocator);
try list.appendSlice(&[_]u32{1, 2, 3, 4});
// 移除索引 1 的元素 (2)
// 将最后一个元素 (4) 移到索引 1
const removed = list.swapRemove(1);
// list.items 现在是 {1, 4, 3}性能优化技巧
如果你预先知道大概需要存储多少元素，使用 initCapacity 可以避免多次内存重新分配，显著提升性能。
// 预先分配 1024 个元素的空间
var list = try std.ArrayList(u8).initCapacity(allocator, 1024);
// 接下来的 1024 次 append 都不会触发内存分配2. 哈希表 (HashMap)
哈希表用于存储键值对 (Key-Value Pairs)。Zig 提供了几种不同的 HashMap 实现，最常用的是 std.AutoHashMap。
AutoHashMap(K, V)：最通用的哈希表，自动选择哈希函数。StringHashMap(V)：专门针对字符串键 ([]const u8) 优化的哈希表。
AutoHashMap 示例
const std = @import("std");
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
const allocator = gpa.allocator();
// 创建一个 Key 为 u32, Value 为 u32 的哈希表
var map = std.AutoHashMap(u32, u32).init(allocator);
defer map.deinit();
// 插入数据 (put)
// put 会覆盖已存在的 Key
try map.put(1, 10);
try map.put(2, 20);
// 获取数据 (get)
// 返回 ?V (可选值)
if (map.get(1)) |val| {
std.debug.print("Key 1 has value: {d}
", .{val});
}
// 移除数据 (remove)
_ = map.remove(2);
}StringHashMap 示例
在处理字符串键时，务必使用 StringHashMap。普通的 AutoHashMap 可能会比较字符串的切片结构（指针+长度）而不是字符串内容本身。
pub fn main() !void {
// ... 初始化分配器 ...
// Value 类型为 u32
var scores = std.StringHashMap(u32).init(allocator);
defer scores.deinit();
try scores.put("Alice", 100);
try scores.put("Bob", 85);
std.debug.print("Alice's score: {?d}
", .{scores.get("Alice")});
}遍历哈希表
使用迭代器遍历哈希表中的所有数据。
var it = scores.iterator();
while (it.next()) |entry| {
// entry.key_ptr 是指向 Key 的指针
// entry.value_ptr 是指向 Value 的指针
std.debug.print("{s}: {d}
", .{entry.key_ptr.*, entry.value_ptr.*});
}注意：迭代器返回的是指针 (
key_ptr,value_ptr)，这允许你在遍历时直接修改 Value 的值（例如entry.value_ptr.* += 1），且避免了不必要的内存复制。
fetchPut 与 getOrPut
Zig 的 HashMap API 设计非常精妙，提供了原子操作来减少查找次数。
fetchPut(key, value)：插入数据，并返回该 Key 之前的值（如果存在）。getOrPut(key)：查找 Key，如果不存在则预留一个位置。这对于“计数器”类逻辑非常有用。
// 统计单词出现次数
var counts = std.StringHashMap(u32).init(allocator);
defer counts.deinit();
const words = [_][]const u8{"apple", "banana", "apple"};
for (words) |word| {
// 获取或创建条目
const result = try counts.getOrPut(word);
if (!result.found_existing) {
result.value_ptr.* = 0; // 如果是新创建的，初始化为 0
}
result.value_ptr.* += 1; // 计数 +1
}3. 其他数据结构
除了 ArrayList 和 HashMap，Zig 标准库还提供了其他丰富的数据结构，都在 std 命名空间下：
std.MultiArrayList：结构体数组优化 (SoA)。将结构体的字段拆分成多个独立的数组存储，对 CPU 缓存更友好，适合高性能场景。std.SinglyLinkedList/std.DoublyLinkedList：经典的链表实现。注意 Zig 的链表节点通常需要你自己分配内存。std.PriorityQueue：优先队列（堆），用于需要按优先级处理元素的场景。std.RingBuffer：环形缓冲区，适合固定大小的队列。
总结
- 动态数组：首选
ArrayList(T)。尽量使用initCapacity预分配内存。 - 哈希表：通用场景用
AutoHashMap(K, V)，字符串键用StringHashMap(V)。 - 内存管理：所有标准库数据结构都需要传入
Allocator，并且不仅要deinit容器本身，如果容器存储的是指针，可能还需要手动释放元素指向的内存。
掌握了这些工具，你就可以构建更加复杂和动态的应用程序了。