Introduce Array List in Zig

What is Array List?#

在高级语言中，数组通常是动态的。它们可以轻松根据需要增长大小，而你无需担心这一点。相比之下，低层次语言中的数组默认通常是静态的。这是C、C++、Rust以及Zig的现实情况。

动态数组简单来说就是在程序运行时可以增长大小的数组。大多数低层次语言在其标准库中都有动态数组的某种实现。C++有std::vector，Rust有Vec，而Zig有std.ArrayList。

std.ArrayList结构体为您提供了一个连续且可增长的数组。它的工作方式与其他动态数组类似：它会分配一块连续的内存空间，当这块空间耗尽时，ArrayList会分配另一块更大且连续的内存空间，将元素复制到这个新位置，并释放之前的内存块。

Capacity vs Length#

这里直接截个网图：

简单来说，Capacity是ArrayList当前可以容纳的最大元素数量，而Length是ArrayList当前实际包含的元素数量。

当长度和容量相等时，意味着数组已经没有剩余空间了。我们已经达到了容量的上限，因此，如果我们想在这个数组中存储更多的值，就需要扩展它。我们需要获得一个更大的空间，能够容纳比当前更多的值。

动态数组的工作原理是，每当长度等于数组容量时，就会扩展底层数组。它基本上是分配一个比之前更大的连续内存块，然后将当前存储的所有值复制到这个新位置（即这个新的内存块），接着释放之前的内存块。在这个过程的最后，新的底层数组拥有了更大的容量，因此，长度再次小于数组的容量。

这是动态数组的一个循环。请注意，在整个循环过程中，数组的容量始终等于或大于其长度。如果你有一个 ArrayList 对象（假设你将其命名为 buffer），可以通过访问 ArrayList 对象的 capacity 属性来检查数组的当前容量，而当前长度可以通过 items.len 属性获取。

// Check capacity
buffer.capacity;
// Check length
buffer.items.len;

Basic Operations#

Create An Array List#

可以使用std.ArrayList.initCapacity函数创建一个Array List实例。该函数需要两个参数：一个分配器和初始容量。

    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    const allocator = gpa.allocator();

    var buf = try std.ArrayList(u8).initCapacity(allocator, 100);
    defer buf.deinit(allocator);

std.ArrayList后面跟上数组具体的类型。在上面的例子中，我们创建了一个可以存储u8类型元素的Array List。初始容量设置为100，这意味着该Array List在创建时可以容纳最多100个u8元素而无需扩展。

Adding Elements#

使用append方法可以向Array List添加单个元素，使用appendSlice方法可以添加一个切片。

    try buf.append(allocator, 'H');
    try buf.append(allocator, 'e');
    try buf.append(allocator, 'l');
    try buf.append(allocator, 'l');
    try buf.append(allocator, 'o');
    try buf.appendSlice(allocator, " World!");

当你需要在数组中间插入值，而不仅仅是追加到数组末尾时，你需要使用insert和insertSlice方法，而不是append和appendSlice方法。

var gpa = std.heap.GeneralPurposeAllocator(.{}){};
const allocator = gpa.allocator();
var buffer = try std.ArrayList(u8)
    .initCapacity(allocator, 10);
defer buffer.deinit(allocator);

try buffer.appendSlice(allocator, "My Pedro");
try buffer.insert(allocator, 4, '3');
try buffer.insertSlice(allocator, 2, " name");
for (buffer.items) |char| {
    try stdout.print("{c}", .{char});
}

try stdout.flush();

Removing Elements#

使用pop方法可以从Array List中移除并返回最后一个元素。

    const last_element = try buf.pop();

现在，如果你想从数组的特定位置移除特定元素，可以使用ArrayList对象中的orderedRemove方法。该方法允许你传入一个索引作为参数，随后它会删除数组中该索引对应的值。每次执行orderedRemove操作时，数组的长度实际上都会减少。

下面的示例中，我们首先创建一个ArrayList对象，并向其中填充数字。接着，我们连续两次使用orderedRemove()方法移除索引为3的值。

另外，注意到我们将orderedRemove的返回结果赋值给了下划线字符。这意味着我们丢弃了该方法的返回值。orderedRemove方法会返回被删除的值，这一点与pop方法类似。

var gpa = std.heap.GeneralPurposeAllocator(.{}){};
const allocator = gpa.allocator();
var buffer = try std.ArrayList(u8)
    .initCapacity(allocator, 100);
defer buffer.deinit(allocator);

for (0..10) |i| {
    const index: u8 = @intCast(i);
    try buffer.append(allocator, index);
}

std.debug.print(
    "{any}\n", .{buffer.items}
);
_ = buffer.orderedRemove(3);
_ = buffer.orderedRemove(3);

std.debug.print("{any}\n", .{buffer.items});
std.debug.print("{any}\n", .{buffer.items.len});

References#

有关Array List的更多信息，请参阅Zig标准库文档中的ArrayList部分。