跳转到内容

std.multi_array_list

标准库Zig 0.17.0官方原文
源码std/multi_array_list.zig

第 1 行

std.multi_array_list.Allocator

别名

第 6 行

别名目标 std.mem.Allocator

std.multi_array_list.assert

别名

第 3 行

别名目标 std.debug.assert

std.multi_array_list.builtin

常量

第 2 行

std.multi_array_list.doTest

函数

第 1113 行

fn doTest(ally: std.mem.Allocator, count: comptime_int) !void

参数

ally: std.mem.Allocator
count: comptime_int

std.multi_array_list.lessThan

函数

第 1033 行

fn lessThan(ctx: @This(), a: usize, b: usize) bool

参数

ctx: @This()
a: usize
b: usize

std.multi_array_list.mem

别名

第 5 行

别名目标 std.mem

std.multi_array_list.meta

别名

第 4 行

别名目标 std.meta

std.multi_array_list.MultiArrayList

类型函数

第 20 行

MultiArrayList 存储结构体或带标签联合体类型的列表。 它不存储单一元素列表,而是为结构体的各字段分别存储列表,或分别存储标签列表与裸联合体列表。 若结构体或联合体存在填充,可由此节省内存;若计算只需部分字段或仅需标签,还能改善缓存利用率。 访问字段的主要接口为 slice(),它计算每个字段数组的起始指针。可在切片上调用 .items(.<field_name>),取得字段值的切片。 对于联合体,可调用 .items(.tags) 或 .items(.data)。

pub fn MultiArrayList(comptime T: type) type

参数

T: type

字段

bytes: [*]u8 = undefined

此指针始终按 sizes.big_align 边界对齐;类型中不声明该要求, 以免 MultiArrayList(T) 依赖 T 的对齐,因为这 可能导致依赖循环。参见 allocatedBytes,它通过 @alignCast 将该指针转换为 正确类型。

len: usize = 0
capacity: usize = 0

std.multi_array_list.MultiArrayList.addOne

函数

第 303 行

将列表扩展 1 个元素,返回新预留的 索引,其数据未初始化。

必要时分配更多内存。

pub fn addOne(self: *Self, gpa: Allocator) Allocator.Error!usize

参数

self: *Self
gpa: Allocator

错误

OutOfMemory

std.multi_array_list.MultiArrayList.addOneAssumeCapacity

函数

第 312 行

将列表扩展一个元素,返回新预留位置的索引,其数据未初始化。

断言容量足以容纳一个额外项目。

pub fn addOneAssumeCapacity(self: *Self) usize

参数

self: *Self

std.multi_array_list.MultiArrayList.addOneBounded

函数

第 324 行

将列表扩展 1 个元素,返回新保留的 索引,其数据未初始化。

若容量不足以容纳一个新增 条目,则返回 error.OutOfMemory。

pub fn addOneBounded(self: *Self) error{OutOfMemory}!usize

参数

self: *Self

错误

OutOfMemory

std.multi_array_list.MultiArrayList.allocatedBytes

函数

第 662 行

fn allocatedBytes(self: Self) []align(sizes.big_align.toByteUnits()) u8

参数

self: Self

std.multi_array_list.MultiArrayList.append

函数

第 276 行

将列表扩展 1 个元素。

必要时分配更多内存。

pub fn append(self: *Self, gpa: Allocator, elem: T) Allocator.Error!void

参数

self: *Self
gpa: Allocator
elem: T

错误

OutOfMemory

std.multi_array_list.MultiArrayList.appendAssumeCapacity

函数

第 284 行

将列表增加 1 个元素。

断言容量足以容纳一个额外元素。

pub fn appendAssumeCapacity(self: *Self, elem: T) void

参数

self: *Self
elem: T

std.multi_array_list.MultiArrayList.appendBounded

函数

第 294 行

将列表扩展一个元素。

若容量不足以容纳新增元素, 返回 error.OutOfMemory。

pub fn appendBounded(self: *Self, elem: T) error{OutOfMemory}!void

参数

self: *Self
elem: T

错误

OutOfMemory

std.multi_array_list.MultiArrayList.capacityInBytes

函数

第 656 行

pub fn capacityInBytes(capacity: usize) usize

参数

capacity: usize

std.multi_array_list.MultiArrayList.clearAndFree

函数

第 497 行

pub fn clearAndFree(self: *Self, gpa: Allocator) void

参数

self: *Self
gpa: Allocator

std.multi_array_list.MultiArrayList.clearRetainingCapacity

函数

第 510 行

使所有元素指针失效。

pub fn clearRetainingCapacity(self: *Self) void

参数

self: *Self

std.multi_array_list.MultiArrayList.clone

函数

第 571 行

使用指定分配器, 以新的底层存储创建此列表的副本。

pub fn clone(self: Self, gpa: Allocator) Allocator.Error!Self

参数

self: Self
gpa: Allocator

错误

OutOfMemory

std.multi_array_list.MultiArrayList.dbHelper

函数

第 686 行

lib/lldb/ 中的调试器美化格式器使用此函数获取 子字段顺序与条目类型,以支持此类型的美化调试输出。

fn dbHelper(self: *Self, child: *Elem, field: *Field, entry: *Entry) void

参数

self: *Self
child: *Elem
field: *Field
entry: *Entry

std.multi_array_list.MultiArrayList.deinit

函数

第 222 行

释放全部已分配内存。

pub fn deinit(self: *Self, gpa: Allocator) void

参数

self: *Self
gpa: Allocator

std.multi_array_list.MultiArrayList.Elem

类型

第 44 行

std.multi_array_list.MultiArrayList.Elem.Bare

类型

第 47 行

std.multi_array_list.MultiArrayList.Elem.fromT

函数

第 53 行

pub fn fromT(outer: T) @This()

参数

outer: T

std.multi_array_list.MultiArrayList.Elem.Tag

常量

第 48 行

std.multi_array_list.MultiArrayList.Elem.toT

函数

第 62 行

pub fn toT(tag: Tag, bare: Bare) T

参数

tag: Tag
bare: Bare

std.multi_array_list.MultiArrayList.empty

常量

第 30 行

Self

std.multi_array_list.MultiArrayList.ensureTotalCapacity

函数

第 517 行

修改数组,使其至少可容纳 new_capacity 个条目。 采用超线性增长,以实现均摊 O(1) 的追加操作。 如果需要额外内存,则使元素指针失效。

pub fn ensureTotalCapacity(self: *Self, gpa: Allocator, new_capacity: usize) Allocator.Error!void

参数

self: *Self
gpa: Allocator
new_capacity: usize

错误

OutOfMemory

std.multi_array_list.MultiArrayList.ensureUnusedCapacity

函数

第 536 行

调整数组,使其至少可再容纳 additional_count 个元素。 如果需要额外内存,指针将失效。

pub fn ensureUnusedCapacity(self: *Self, gpa: Allocator, additional_count: usize) Allocator.Error!void

参数

self: *Self
gpa: Allocator
additional_count: usize

错误

OutOfMemory

std.multi_array_list.MultiArrayList.Entry

常量

第 670 行

std.multi_array_list.MultiArrayList.Field

类型

第 71 行

std.multi_array_list.MultiArrayList.field_attrs

常量

第 180 行

std.multi_array_list.MultiArrayList.field_names

常量

第 178 行

std.multi_array_list.MultiArrayList.field_types

常量

第 179 行

std.multi_array_list.MultiArrayList.FieldType

类型函数

第 666 行

fn FieldType(comptime field: Field) type

参数

field: Field

std.multi_array_list.MultiArrayList.get

函数

第 265 行

获取一个数组元素的所有数据。

pub fn get(self: Self, index: usize) T

参数

self: Self
index: usize

std.multi_array_list.MultiArrayList.growCapacity

函数

第 530 行

给定所需内存容量的下限,返回按超线性 增长得到的更大值。

pub fn growCapacity(minimum: usize) usize

参数

minimum: usize

std.multi_array_list.MultiArrayList.init_capacity

常量

第 522 行

comptime_int

std.multi_array_list.MultiArrayList.initCapacity

函数

第 38 行

初始化并分配恰好可容纳 num 个元素的容量。 使用 deinit 或 toOwnedSlice 反初始化。

pub fn initCapacity(gpa: Allocator, num: usize) Allocator.Error!Self

参数

gpa: Allocator
num: usize

错误

OutOfMemory

std.multi_array_list.MultiArrayList.insert

函数

第 343 行

向列表插入一个元素。将指定索引及其后 的所有元素向后移动一位, 并将指定索引设置为所给元素。

按需分配更多内存。

pub fn insert(self: *Self, gpa: Allocator, index: usize, elem: T) !void

参数

self: *Self
gpa: Allocator
index: usize
elem: T

std.multi_array_list.MultiArrayList.insertAssumeCapacity

函数

第 353 行

向列表插入一个元素。将指定索引及其后 的所有元素向后移动一位, 并将指定索引设置为所给元素。

断言容量足以容纳一个新增元素。

pub fn insertAssumeCapacity(self: *Self, index: usize, elem: T) void

参数

self: *Self
index: usize
elem: T

std.multi_array_list.MultiArrayList.insertBounded

函数

第 379 行

向列表插入一个元素。将指定索引及其后 的所有元素向后移动一位, 并将指定索引设置为所给元素。

若容量不足以容纳一个新增元素, 返回 error.OutOfMemory。

pub fn insertBounded(self: *Self, index: usize, elem: T) error{OutOfMemory}!void

参数

self: *Self
index: usize
elem: T

错误

OutOfMemory

std.multi_array_list.MultiArrayList.items

函数

第 254 行

获取指定字段的值切片。 如果需要多个字段,考虑改为 调用 slice()。

pub fn items(self: Self, comptime field: Field) []FieldType(field)

参数

self: Self
field: Field

std.multi_array_list.MultiArrayList.orderedRemove

函数

第 399 行

从列表中移除指定项目,并移动其后的项目以保持顺序。

pub fn orderedRemove(self: *Self, index: usize) void

参数

self: *Self
index: usize

std.multi_array_list.MultiArrayList.orderedRemoveMany

函数

第 424 行

移除 sorted_indexes 索引的元素。这些待移除索引 对应删除前的数组列表。

断言:

  • 每个待移除索引都在范围内。
  • 待移除索引按升序排列。

允许 sorted_indexes 中存在重复项。

此操作的时间复杂度为 O(N)。

使首个被删除索引之后的元素指针失效。

pub fn orderedRemoveMany(self: *Self, sorted_indexes: []const usize) void

参数

self: *Self
sorted_indexes: []const usize

std.multi_array_list.MultiArrayList.pop

函数

第 331 行

从列表移除并返回最后一个元素;若列表为空则返回 null。 使指向被移除元素字段的指针失效。

pub fn pop(self: *Self) ?T

参数

self: *Self

std.multi_array_list.MultiArrayList.resize

函数

第 450 行

将列表长度调整为 new_len。 不会初始化新增项目。

pub fn resize(self: *Self, gpa: Allocator, new_len: usize) Allocator.Error!void

参数

self: *Self
gpa: Allocator
new_len: usize

错误

OutOfMemory

std.multi_array_list.MultiArrayList.Self

别名

第 176 行

别名目标 std.multi_array_list.MultiArrayList

std.multi_array_list.MultiArrayList.set

函数

第 259 行

用新数据覆盖一个数组元素。

pub fn set(self: *Self, index: usize, elem: T) void

参数

self: *Self
index: usize
elem: T

std.multi_array_list.MultiArrayList.setCapacity

函数

第 543 行

修改数组,使其恰好可容纳 new_capacity 个条目。 如果需要额外内存,则使指针失效。 new_capacity 必须大于或等于 len。

pub fn setCapacity(self: *Self, gpa: Allocator, new_capacity: usize) Allocator.Error!void

参数

self: *Self
gpa: Allocator
new_capacity: usize

错误

OutOfMemory

std.multi_array_list.MultiArrayList.shrinkAndFree

函数

第 458 行

尝试将已分配容量缩减为 new_len。 若 new_len 大于零,则可能无法缩减容量, 但数据保持完整,长度会更新为 new_len。

pub fn shrinkAndFree(self: *Self, gpa: Allocator, new_len: usize) void

参数

self: *Self
gpa: Allocator
new_len: usize

std.multi_array_list.MultiArrayList.shrinkRetainingCapacity

函数

第 505 行

将长度缩减为 new_len。 指向元素 items[new_len..] 的指针会失效。 容量保持不变。

pub fn shrinkRetainingCapacity(self: *Self, new_len: usize) void

参数

self: *Self
new_len: usize

std.multi_array_list.MultiArrayList.sizes

常量

第 184 行

sizes.bytes 是各 T 字段 @sizeOf 的数组,按对齐要求降序排列。 sizes.fields 数组将 sizes.bytes 的数组索引映射为字段索引。 sizes.big_align 为分配的整体对齐要求,等于各字段对齐要求的最大值。

std.multi_array_list.MultiArrayList.sizes.lessThan

函数

第 201 行

fn lessThan(context: void, lhs: Data, rhs: Data) bool

参数

context: void
lhs: Data
rhs: Data

std.multi_array_list.MultiArrayList.slice

函数

第 237 行

计算指向数组每个字段起始位置的指针。 若需访问多个字段,调用此函数可能比 多次调用 items() 更高效。

pub fn slice(self: Self) Slice

参数

self: Self

std.multi_array_list.MultiArrayList.Slice

容器

第 77 行

MultiArrayList.Slice 包含列表各字段起始指针的缓存。 为减小列表的内存大小,通常不存储这些指针。 若要访问多个字段,应先调用 slice() 计算指针,再从该切片取得各字段数组。

字段

ptrs: [field_names.len][*]u8

此数组以字段索引为下标; 可对 Field 枚举调用 @intFromEnum() 获取该索引。

len: usize
capacity: usize

std.multi_array_list.MultiArrayList.Slice.dbHelper

函数

第 168 行

lib/lldb/ 中的调试器美化格式器使用此函数获取 子字段顺序与条目类型,以支持此类型的美化调试输出。

fn dbHelper(self: *Slice, child: *Elem, field: *Field, entry: *Entry) void

参数

self: *Slice
child: *Elem
field: *Field
entry: *Entry

std.multi_array_list.MultiArrayList.Slice.deinit

函数

第 144 行

pub fn deinit(self: *Slice, gpa: Allocator) void

参数

self: *Slice
gpa: Allocator

std.multi_array_list.MultiArrayList.Slice.empty

常量

第 84 行

Slice

std.multi_array_list.MultiArrayList.Slice.get

函数

第 114 行

pub fn get(self: Slice, index: usize) T

参数

self: Slice
index: usize

std.multi_array_list.MultiArrayList.Slice.items

函数

第 90 行

pub fn items(self: Slice, comptime field: Field) []FieldType(field)

参数

self: Slice
field: Field

std.multi_array_list.MultiArrayList.Slice.set

函数

第 103 行

pub fn set(self: *Slice, index: usize, elem: T) void

参数

self: *Slice
index: usize
elem: T

std.multi_array_list.MultiArrayList.Slice.subslice

函数

第 153 行

返回表示 s 中一段元素范围的 Slice,类似 arr[off..len]。 对返回的 Slice 调用 deinit 或 toMultiArrayList 属于非法操作。 断言 off + len <= s.len。

pub fn subslice(s: Slice, off: usize, len: usize) Slice

参数

s: Slice
off: usize
len: usize

std.multi_array_list.MultiArrayList.Slice.swap

函数

第 126 行

pub fn swap(self: Slice, a: usize, b: usize) void

参数

self: Slice
a: usize
b: usize

std.multi_array_list.MultiArrayList.Slice.toMultiArrayList

函数

第 133 行

pub fn toMultiArrayList(self: Slice) Self

参数

self: Slice

std.multi_array_list.MultiArrayList.sort

函数

第 623 行

此函数保证稳定排序,即排序时保留相等元素的相对顺序。 稳定排序的更多说明:https://en.wikipedia.org/wiki/Sorting_algorithm#Stability 如果不需要此保证,sortUnstable 可能更快。 ctx 具有以下方法: fn lessThan(ctx: @TypeOf(ctx), a_index: usize, b_index: usize) bool

pub fn sort(self: Self, ctx: anytype) void

参数

self: Self

std.multi_array_list.MultiArrayList.sortInternal

函数

第 589 行

ctx 具有以下方法: fn lessThan(ctx: @TypeOf(ctx), a_index: usize, b_index: usize) bool

fn sortInternal(self: Self, a: usize, b: usize, ctx: anytype, comptime mode: std.sort.Mode) void

参数

self: Self
a: usize
b: usize
mode: std.sort.Mode

std.multi_array_list.MultiArrayList.sortInternal.lessThan

函数

第 604 行

pub fn lessThan(sc: @This(), a_index: usize, b_index: usize) bool

参数

sc: @This()
a_index: usize
b_index: usize

std.multi_array_list.MultiArrayList.sortInternal.swap

函数

第 594 行

pub fn swap(sc: @This(), a_index: usize, b_index: usize) void

参数

sc: @This()
a_index: usize
b_index: usize

std.multi_array_list.MultiArrayList.sortSpan

函数

第 633 行

仅对索引 a 和 b 之间、不含 b 的元素子区间排序。 保证稳定排序,即排序时保留相等元素的相对顺序。 稳定排序的更多说明:https://en.wikipedia.org/wiki/Sorting_algorithm#Stability 若不需要此保证,sortSpanUnstable 可能更快。 ctx 具有以下方法: fn lessThan(ctx: @TypeOf(ctx), a_index: usize, b_index: usize) bool

pub fn sortSpan(self: Self, a: usize, b: usize, ctx: anytype) void

参数

self: Self
a: usize
b: usize

std.multi_array_list.MultiArrayList.sortSpanUnstable

函数

第 652 行

仅排序索引 a 与 b 之间的元素子区间,不包含 b。 此函数不保证稳定排序,即相等元素的相对顺序可能在排序期间改变。 由于保证较弱,此函数可能比稳定的 sortSpan 方法更快。 稳定排序的详细说明:https://en.wikipedia.org/wiki/Sorting_algorithm#Stability ctx 具有以下方法: fn lessThan(ctx: @TypeOf(ctx), a_index: usize, b_index: usize) bool

pub fn sortSpanUnstable(self: Self, a: usize, b: usize, ctx: anytype) void

参数

self: Self
a: usize
b: usize

std.multi_array_list.MultiArrayList.sortUnstable

函数

第 642 行

此函数不保证稳定排序,即相等元素的相对顺序可能在排序期间改变。 由于保证较弱,此函数可能比稳定的 sort 方法更快。 稳定排序的详细说明:https://en.wikipedia.org/wiki/Sorting_algorithm#Stability ctx 具有以下方法: fn lessThan(ctx: @TypeOf(ctx), a_index: usize, b_index: usize) bool

pub fn sortUnstable(self: Self, ctx: anytype) void

参数

self: Self

std.multi_array_list.MultiArrayList.swap

函数

第 269 行

pub fn swap(self: Self, a: usize, b: usize) void

参数

self: Self
a: usize
b: usize

std.multi_array_list.MultiArrayList.swapRemove

函数

第 387 行

从列表中移除指定项,将列表最后一项 交换到其位置。速度快,但不 保持列表顺序。

pub fn swapRemove(self: *Self, index: usize) void

参数

self: *Self
index: usize

std.multi_array_list.MultiArrayList.toOwnedSlice

函数

第 228 行

调用方拥有返回的内存。清空此 MultiArrayList。

pub fn toOwnedSlice(self: *Self) Slice

参数

self: *Self

std.multi_array_list.std

别名

第 1 行

别名目标 std

std.multi_array_list.testing

别名

第 7 行

别名目标 std.testing

std.multi_array_list.Type

类型函数

第 1106 行

fn Type(count: comptime_int) type

参数

count: comptime_int
源码

std/multi_array_list.zig

const std = @import("std");
const builtin = @import("builtin");
const assert = std.debug.assert;
const meta = std.meta;
const mem = std.mem;
const Allocator = mem.Allocator;
const testing = std.testing;

/// MultiArrayList 存储结构体或带标签联合体类型的列表。
/// 它不存储单一元素列表,而是为结构体的各字段分别存储列表,或分别存储标签列表与裸联合体列表。
/// 若结构体或联合体存在填充,可由此节省内存;若计算只需部分字段或仅需标签,还能改善缓存利用率。
/// 访问字段的主要接口为 `slice()`,它计算每个字段数组的起始指针。可在切片上调用 `.items(.<field_name>)`,取得字段值的切片。
/// 对于联合体,可调用 `.items(.tags)` 或 `.items(.data)`。
///
///
///
///
///
///
pub fn MultiArrayList(comptime T: type) type {
    return struct {
        /// 此指针始终按 `sizes.big_align` 边界对齐;类型中不声明该要求,
        /// 以免 `MultiArrayList(T)` 依赖 `T` 的对齐,因为这
        /// 可能导致依赖循环。参见 `allocatedBytes`,它通过 `@alignCast` 将该指针转换为
        /// 正确类型。
        bytes: [*]u8 = undefined,
        len: usize = 0,
        capacity: usize = 0,

        pub const empty: Self = .{
            .bytes = undefined,
            .len = 0,
            .capacity = 0,
        };

        /// 初始化并分配恰好可容纳 `num` 个元素的容量。
        /// 使用 `deinit` 或 `toOwnedSlice` 反初始化。
        pub fn initCapacity(gpa: Allocator, num: usize) Allocator.Error!Self {
            var self: Self = .empty;
            try self.setCapacity(gpa, num);
            return self;
        }

        const Elem = switch (@typeInfo(T)) {
            .@"struct" => T,
            .@"union" => |u| struct {
                pub const Bare = std.meta.BareUnion(T);
                pub const Tag =
                    u.tag_type orelse @compileError("MultiArrayList does not support untagged unions");
                tags: Tag,
                data: Bare,

                pub fn fromT(outer: T) @This() {
                    const tag = meta.activeTag(outer);
                    return .{
                        .tags = tag,
                        .data = switch (tag) {
                            inline else => |t| @unionInit(Bare, @tagName(t), @field(outer, @tagName(t))),
                        },
                    };
                }
                pub fn toT(tag: Tag, bare: Bare) T {
                    return switch (tag) {
                        inline else => |t| @unionInit(T, @tagName(t), @field(bare, @tagName(t))),
                    };
                }
            },
            else => @compileError("MultiArrayList only supports structs and tagged unions"),
        };

        pub const Field = meta.FieldEnum(Elem);

        /// MultiArrayList.Slice 包含列表各字段起始指针的缓存。
        /// 为减小列表的内存大小,通常不存储这些指针。
        /// 若要访问多个字段,应先调用 slice() 计算指针,再从该切片取得各字段数组。
        ///
        pub const Slice = struct {
            /// 此数组以字段索引为下标;
            /// 可对 Field 枚举调用 @intFromEnum() 获取该索引。
            ptrs: [field_names.len][*]u8,
            len: usize,
            capacity: usize,

            pub const empty: Slice = .{
                .ptrs = undefined,
                .len = 0,
                .capacity = 0,
            };

            pub fn items(self: Slice, comptime field: Field) []FieldType(field) {
                const F = FieldType(field);
                if (self.capacity == 0) {
                    return &[_]F{};
                }
                const byte_ptr = self.ptrs[@backingInt(field)];
                const casted_ptr: [*]F = if (@sizeOf(F) == 0)
                    undefined
                else
                    @ptrCast(@alignCast(byte_ptr));
                return casted_ptr[0..self.len];
            }

            pub fn set(self: *Slice, index: usize, elem: T) void {
                const e = switch (@typeInfo(T)) {
                    .@"struct" => elem,
                    .@"union" => Elem.fromT(elem),
                    else => unreachable,
                };
                inline for (field_names, 0..) |field_name, i| {
                    self.items(@as(Field, @fromBackingInt(@intCast(i))))[index] = @field(e, field_name);
                }
            }

            pub fn get(self: Slice, index: usize) T {
                var result: Elem = undefined;
                inline for (field_names, 0..) |field_name, i| {
                    @field(result, field_name) = self.items(@as(Field, @fromBackingInt(@intCast(i))))[index];
                }
                return switch (@typeInfo(T)) {
                    .@"struct" => result,
                    .@"union" => Elem.toT(result.tags, result.data),
                    else => unreachable,
                };
            }

            pub fn swap(self: Slice, a: usize, b: usize) void {
                inline for (@typeInfo(Field).@"enum".field_names) |field_name| {
                    const its = self.items(@field(Field, field_name));
                    std.mem.swap(@FieldType(T, field_name), &its[a], &its[b]);
                }
            }

            pub fn toMultiArrayList(self: Slice) Self {
                if (self.ptrs.len == 0 or self.capacity == 0) {
                    return .{};
                }
                return .{
                    .bytes = self.ptrs[sizes.fields[0]],
                    .len = self.len,
                    .capacity = self.capacity,
                };
            }

            pub fn deinit(self: *Slice, gpa: Allocator) void {
                var other = self.toMultiArrayList();
                other.deinit(gpa);
                self.* = undefined;
            }

            /// 返回表示 `s` 中一段元素范围的 `Slice`,类似 `arr[off..len]`。
            /// 对返回的 `Slice` 调用 `deinit` 或 `toMultiArrayList` 属于非法操作。
            /// 断言 `off + len <= s.len`。
            pub fn subslice(s: Slice, off: usize, len: usize) Slice {
                assert(off + len <= s.len);
                var ptrs: [field_names.len][*]u8 = undefined;
                inline for (s.ptrs, &ptrs, field_types) |in, *out, field_type| {
                    out.* = in + (off * @sizeOf(field_type));
                }
                return .{
                    .ptrs = ptrs,
                    .len = len,
                    .capacity = len,
                };
            }

            /// lib/lldb/ 中的调试器美化格式器使用此函数获取
            /// 子字段顺序与条目类型,以支持此类型的美化调试输出。
            fn dbHelper(self: *Slice, child: *Elem, field: *Field, entry: *Entry) void {
                _ = self;
                _ = child;
                _ = field;
                _ = entry;
            }
        };

        const Self = @This();

        const field_names = @typeInfo(Elem).@"struct".field_names;
        const field_types = @typeInfo(Elem).@"struct".field_types;
        const field_attrs = @typeInfo(Elem).@"struct".field_attrs;
        /// `sizes.bytes` 是各 T 字段 @sizeOf 的数组,按对齐要求降序排列。
        /// `sizes.fields` 数组将 `sizes.bytes` 的数组索引映射为字段索引。
        /// `sizes.big_align` 为分配的整体对齐要求,等于各字段对齐要求的最大值。
        const sizes = blk: {
            const Data = struct {
                size: usize,
                size_index: usize,
                alignment: usize,
            };
            var data: [field_names.len]Data = undefined;
            var big_align: usize = 1;
            for (field_types, field_attrs, 0..) |f_type, f_attrs, i| {
                data[i] = .{
                    .size = @sizeOf(f_type),
                    .size_index = i,
                    .alignment = f_attrs.@"align" orelse @alignOf(f_type),
                };
                big_align = @max(big_align, data[i].alignment);
            }
            const Sort = struct {
                fn lessThan(context: void, lhs: Data, rhs: Data) bool {
                    _ = context;
                    return lhs.alignment > rhs.alignment;
                }
            };
            @setEvalBranchQuota(3 * field_names.len * std.math.log2(field_names.len));
            mem.sort(Data, &data, {}, Sort.lessThan);
            var sizes_bytes: [field_names.len]usize = undefined;
            var field_indexes: [field_names.len]usize = undefined;
            for (data, 0..) |elem, i| {
                sizes_bytes[i] = elem.size;
                field_indexes[i] = elem.size_index;
            }
            break :blk .{
                .bytes = sizes_bytes,
                .fields = field_indexes,
                .big_align = mem.Alignment.fromByteUnits(big_align),
            };
        };

        /// 释放全部已分配内存。
        pub fn deinit(self: *Self, gpa: Allocator) void {
            gpa.free(self.allocatedBytes());
            self.* = undefined;
        }

        /// 调用方拥有返回的内存。清空此 MultiArrayList。
        pub fn toOwnedSlice(self: *Self) Slice {
            const result = self.slice();
            self.* = .{};
            return result;
        }

        /// 计算指向数组每个字段起始位置的指针。
        /// 若需访问多个字段,调用此函数可能比
        /// 多次调用 `items()` 更高效。
        pub fn slice(self: Self) Slice {
            var result: Slice = .{
                .ptrs = undefined,
                .len = self.len,
                .capacity = self.capacity,
            };
            var ptr: [*]u8 = self.bytes;
            for (sizes.bytes, sizes.fields) |field_size, i| {
                result.ptrs[i] = ptr;
                ptr += field_size * self.capacity;
            }
            return result;
        }

        /// 获取指定字段的值切片。
        /// 如果需要多个字段,考虑改为
        /// 调用 slice()。
        pub fn items(self: Self, comptime field: Field) []FieldType(field) {
            return self.slice().items(field);
        }

        /// 用新数据覆盖一个数组元素。
        pub fn set(self: *Self, index: usize, elem: T) void {
            var slices = self.slice();
            slices.set(index, elem);
        }

        /// 获取一个数组元素的所有数据。
        pub fn get(self: Self, index: usize) T {
            return self.slice().get(index);
        }

        pub fn swap(self: Self, a: usize, b: usize) void {
            return self.slice().swap(a, b);
        }

        /// 将列表扩展 1 个元素。
        ///
        /// 必要时分配更多内存。
        pub fn append(self: *Self, gpa: Allocator, elem: T) Allocator.Error!void {
            try self.ensureUnusedCapacity(gpa, 1);
            self.appendAssumeCapacity(elem);
        }

        /// 将列表增加 1 个元素。
        ///
        /// 断言容量足以容纳一个额外元素。
        pub fn appendAssumeCapacity(self: *Self, elem: T) void {
            assert(self.len < self.capacity);
            self.len += 1;
            self.set(self.len - 1, elem);
        }

        /// 将列表扩展一个元素。
        ///
        /// 若容量不足以容纳新增元素,
        /// 返回 `error.OutOfMemory`。
        pub fn appendBounded(self: *Self, elem: T) error{OutOfMemory}!void {
            if (self.capacity - self.len < 1) return error.OutOfMemory;
            return appendAssumeCapacity(self, elem);
        }

        /// 将列表扩展 1 个元素,返回新预留的
        /// 索引,其数据未初始化。
        ///
        /// 必要时分配更多内存。
        pub fn addOne(self: *Self, gpa: Allocator) Allocator.Error!usize {
            try self.ensureUnusedCapacity(gpa, 1);
            return self.addOneAssumeCapacity();
        }

        /// 将列表扩展一个元素,返回新预留位置的索引,其数据未初始化。
        ///
        /// 断言容量足以容纳一个额外项目。
        ///
        pub fn addOneAssumeCapacity(self: *Self) usize {
            assert(self.len < self.capacity);
            const index = self.len;
            self.len += 1;
            return index;
        }

        /// 将列表扩展 1 个元素,返回新保留的
        /// 索引,其数据未初始化。
        ///
        /// 若容量不足以容纳一个新增
        /// 条目,则返回 `error.OutOfMemory`。
        pub fn addOneBounded(self: *Self) error{OutOfMemory}!usize {
            if (self.capacity - self.len < 1) return error.OutOfMemory;
            return addOneAssumeCapacity(self);
        }

        /// 从列表移除并返回最后一个元素;若列表为空则返回 `null`。
        /// 使指向被移除元素字段的指针失效。
        pub fn pop(self: *Self) ?T {
            if (self.len == 0) return null;
            const val = self.get(self.len - 1);
            self.len -= 1;
            return val;
        }

        /// 向列表插入一个元素。将指定索引及其后
        /// 的所有元素向后移动一位,
        /// 并将指定索引设置为所给元素。
        ///
        /// 按需分配更多内存。
        pub fn insert(self: *Self, gpa: Allocator, index: usize, elem: T) !void {
            try self.ensureUnusedCapacity(gpa, 1);
            self.insertAssumeCapacity(index, elem);
        }

        /// 向列表插入一个元素。将指定索引及其后
        /// 的所有元素向后移动一位,
        /// 并将指定索引设置为所给元素。
        ///
        /// 断言容量足以容纳一个新增元素。
        pub fn insertAssumeCapacity(self: *Self, index: usize, elem: T) void {
            assert(self.len < self.capacity);
            assert(index <= self.len);
            self.len += 1;
            const entry = switch (@typeInfo(T)) {
                .@"struct" => elem,
                .@"union" => Elem.fromT(elem),
                else => unreachable,
            };
            const slices = self.slice();
            inline for (field_names, 0..) |field_name, field_index| {
                const field_slice = slices.items(@as(Field, @fromBackingInt(@intCast(field_index))));
                var i: usize = self.len - 1;
                while (i > index) : (i -= 1) {
                    field_slice[i] = field_slice[i - 1];
                }
                field_slice[index] = @field(entry, field_name);
            }
        }

        /// 向列表插入一个元素。将指定索引及其后
        /// 的所有元素向后移动一位,
        /// 并将指定索引设置为所给元素。
        ///
        /// 若容量不足以容纳一个新增元素,
        /// 返回 `error.OutOfMemory`。
        pub fn insertBounded(self: *Self, index: usize, elem: T) error{OutOfMemory}!void {
            if (self.capacity - self.len < 1) return error.OutOfMemory;
            return insertAssumeCapacity(self, index, elem);
        }

        /// 从列表中移除指定项,将列表最后一项
        /// 交换到其位置。速度快,但不
        /// 保持列表顺序。
        pub fn swapRemove(self: *Self, index: usize) void {
            const slices = self.slice();
            inline for (field_names, 0..) |_, i| {
                const field_slice = slices.items(@as(Field, @fromBackingInt(@intCast(i))));
                field_slice[index] = field_slice[self.len - 1];
                field_slice[self.len - 1] = undefined;
            }
            self.len -= 1;
        }

        /// 从列表中移除指定项目,并移动其后的项目以保持顺序。
        ///
        pub fn orderedRemove(self: *Self, index: usize) void {
            const slices = self.slice();
            inline for (field_names, 0..) |_, field_index| {
                const field_slice = slices.items(@as(Field, @fromBackingInt(@intCast(field_index))));
                var i = index;
                while (i < self.len - 1) : (i += 1) {
                    field_slice[i] = field_slice[i + 1];
                }
                field_slice[i] = undefined;
            }
            self.len -= 1;
        }

        /// 移除 `sorted_indexes` 索引的元素。这些待移除索引
        /// 对应删除前的数组列表。
        ///
        /// 断言:
        /// * 每个待移除索引都在范围内。
        /// * 待移除索引按升序排列。
        ///
        /// 允许 `sorted_indexes` 中存在重复项。
        ///
        /// 此操作的时间复杂度为 O(N)。
        ///
        /// 使首个被删除索引之后的元素指针失效。
        pub fn orderedRemoveMany(self: *Self, sorted_indexes: []const usize) void {
            if (sorted_indexes.len == 0) return;
            const slices = self.slice();
            var shift: usize = 1;
            for (sorted_indexes[0 .. sorted_indexes.len - 1], sorted_indexes[1..]) |removed, end| {
                if (removed == end) continue; // 允许 `sorted_indexes` 中存在重复项
                const start = removed + 1;
                const len = end - start; // 安全检查:`sorted_indexes` 已排序
                inline for (field_names, 0..) |_, field_index| {
                    const field_slice = slices.items(@fromBackingInt(@intCast(field_index)));
                    @memmove(field_slice[start - shift ..][0..len], field_slice[start..][0..len]); // 安全检查:初始 `sorted_indexes` 均在范围内
                }
                shift += 1;
            }
            const start = sorted_indexes[sorted_indexes.len - 1] + 1;
            const end = self.len;
            const len = end - start; // 安全检查:最终 `sorted_indexes` 均在范围内
            inline for (field_names, 0..) |_, field_index| {
                const field_slice = slices.items(@fromBackingInt(@intCast(field_index)));
                @memmove(field_slice[start - shift ..][0..len], field_slice[start..][0..len]);
            }
            self.len = end - shift;
        }

        /// 将列表长度调整为 `new_len`。
        /// 不会初始化新增项目。
        pub fn resize(self: *Self, gpa: Allocator, new_len: usize) Allocator.Error!void {
            try self.ensureTotalCapacity(gpa, new_len);
            self.len = new_len;
        }

        /// 尝试将已分配容量缩减为 `new_len`。
        /// 若 `new_len` 大于零,则可能无法缩减容量,
        /// 但数据保持完整,长度会更新为 new_len。
        pub fn shrinkAndFree(self: *Self, gpa: Allocator, new_len: usize) void {
            if (new_len == 0) return clearAndFree(self, gpa);

            assert(new_len <= self.capacity);
            assert(new_len <= self.len);

            const other_bytes = gpa.alignedAlloc(u8, sizes.big_align, capacityInBytes(new_len)) catch {
                const self_slice = self.slice();
                inline for (field_types, 0..) |field_type, i| {
                    if (@sizeOf(field_type) != 0) {
                        const field = @as(Field, @fromBackingInt(@intCast(i)));
                        const dest_slice = self_slice.items(field)[new_len..];
                        // 此处使用 memset,以便在启用安全检查和 valgrind 的
                        // 构建中生成更高效的代码。否则,
                        // 每个元素都会重复执行 valgrind 客户端请求。
                        @memset(dest_slice, undefined);
                    }
                }
                self.len = new_len;
                return;
            };
            var other = Self{
                .bytes = other_bytes.ptr,
                .capacity = new_len,
                .len = new_len,
            };
            self.len = new_len;
            const self_slice = self.slice();
            const other_slice = other.slice();
            inline for (field_types, 0..) |field_type, i| {
                if (@sizeOf(field_type) != 0) {
                    const field = @as(Field, @fromBackingInt(@intCast(i)));
                    @memcpy(other_slice.items(field), self_slice.items(field));
                }
            }
            gpa.free(self.allocatedBytes());
            self.* = other;
        }

        pub fn clearAndFree(self: *Self, gpa: Allocator) void {
            gpa.free(self.allocatedBytes());
            self.* = .{};
        }

        /// 将长度缩减为 `new_len`。
        /// 指向元素 `items[new_len..]` 的指针会失效。
        /// 容量保持不变。
        pub fn shrinkRetainingCapacity(self: *Self, new_len: usize) void {
            self.len = new_len;
        }

        /// 使所有元素指针失效。
        pub fn clearRetainingCapacity(self: *Self) void {
            self.len = 0;
        }

        /// 修改数组,使其至少可容纳 `new_capacity` 个条目。
        /// 采用超线性增长,以实现均摊 O(1) 的追加操作。
        /// 如果需要额外内存,则使元素指针失效。
        pub fn ensureTotalCapacity(self: *Self, gpa: Allocator, new_capacity: usize) Allocator.Error!void {
            if (self.capacity >= new_capacity) return;
            return self.setCapacity(gpa, growCapacity(new_capacity));
        }

        const init_capacity: comptime_int = init: {
            var max: comptime_int = 1;
            for (field_types) |field_type| max = @max(max, @sizeOf(field_type));
            break :init @max(1, std.atomic.cache_line / max);
        };

        /// 给定所需内存容量的下限,返回按超线性
        /// 增长得到的更大值。
        pub fn growCapacity(minimum: usize) usize {
            return minimum +| (minimum / 2 + init_capacity);
        }

        /// 调整数组,使其至少可**再**容纳 `additional_count` 个元素。
        /// 如果需要额外内存,指针将失效。
        pub fn ensureUnusedCapacity(self: *Self, gpa: Allocator, additional_count: usize) Allocator.Error!void {
            return self.ensureTotalCapacity(gpa, self.len + additional_count);
        }

        /// 修改数组,使其恰好可容纳 `new_capacity` 个条目。
        /// 如果需要额外内存,则使指针失效。
        /// `new_capacity` 必须大于或等于 `len`。
        pub fn setCapacity(self: *Self, gpa: Allocator, new_capacity: usize) Allocator.Error!void {
            assert(new_capacity >= self.len);
            const new_bytes = try gpa.alignedAlloc(u8, sizes.big_align, capacityInBytes(new_capacity));
            if (self.len == 0) {
                gpa.free(self.allocatedBytes());
                self.bytes = new_bytes.ptr;
                self.capacity = new_capacity;
                return;
            }
            var other = Self{
                .bytes = new_bytes.ptr,
                .capacity = new_capacity,
                .len = self.len,
            };
            const self_slice = self.slice();
            const other_slice = other.slice();
            inline for (field_types, 0..) |field_type, i| {
                if (@sizeOf(field_type) != 0) {
                    const field = @as(Field, @fromBackingInt(@intCast(i)));
                    @memcpy(other_slice.items(field), self_slice.items(field));
                }
            }
            gpa.free(self.allocatedBytes());
            self.* = other;
        }

        /// 使用指定分配器,
        /// 以新的底层存储创建此列表的副本。
        pub fn clone(self: Self, gpa: Allocator) Allocator.Error!Self {
            var result = Self{};
            errdefer result.deinit(gpa);
            try result.ensureTotalCapacity(gpa, self.len);
            result.len = self.len;
            const self_slice = self.slice();
            const result_slice = result.slice();
            inline for (field_types, 0..) |field_type, i| {
                if (@sizeOf(field_type) != 0) {
                    const field = @as(Field, @fromBackingInt(@intCast(i)));
                    @memcpy(result_slice.items(field), self_slice.items(field));
                }
            }
            return result;
        }

        /// `ctx` 具有以下方法:
        /// `fn lessThan(ctx: @TypeOf(ctx), a_index: usize, b_index: usize) bool`
        fn sortInternal(self: Self, a: usize, b: usize, ctx: anytype, comptime mode: std.sort.Mode) void {
            const sort_context: struct {
                sub_ctx: @TypeOf(ctx),
                slice: Slice,

                pub fn swap(sc: @This(), a_index: usize, b_index: usize) void {
                    inline for (field_types, 0..) |field_type, i| {
                        if (@sizeOf(field_type) != 0) {
                            const field: Field = @fromBackingInt(@intCast(i));
                            const ptr = sc.slice.items(field);
                            mem.swap(field_type, &ptr[a_index], &ptr[b_index]);
                        }
                    }
                }

                pub fn lessThan(sc: @This(), a_index: usize, b_index: usize) bool {
                    return sc.sub_ctx.lessThan(a_index, b_index);
                }
            } = .{
                .sub_ctx = ctx,
                .slice = self.slice(),
            };

            switch (mode) {
                .stable => mem.sortContext(a, b, sort_context),
                .unstable => mem.sortUnstableContext(a, b, sort_context),
            }
        }

        /// 此函数保证稳定排序,即排序时保留相等元素的相对顺序。
        /// 稳定排序的更多说明:https://en.wikipedia.org/wiki/Sorting_algorithm#Stability
        /// 如果不需要此保证,`sortUnstable` 可能更快。
        /// `ctx` 具有以下方法:
        /// `fn lessThan(ctx: @TypeOf(ctx), a_index: usize, b_index: usize) bool`
        pub fn sort(self: Self, ctx: anytype) void {
            self.sortInternal(0, self.len, ctx, .stable);
        }

        /// 仅对索引 `a` 和 `b` 之间、不含 `b` 的元素子区间排序。
        /// 保证稳定排序,即排序时保留相等元素的相对顺序。
        /// 稳定排序的更多说明:https://en.wikipedia.org/wiki/Sorting_algorithm#Stability
        /// 若不需要此保证,`sortSpanUnstable` 可能更快。
        /// `ctx` 具有以下方法:
        /// `fn lessThan(ctx: @TypeOf(ctx), a_index: usize, b_index: usize) bool`
        pub fn sortSpan(self: Self, a: usize, b: usize, ctx: anytype) void {
            self.sortInternal(a, b, ctx, .stable);
        }

        /// 此函数不保证稳定排序,即相等元素的相对顺序可能在排序期间改变。
        /// 由于保证较弱,此函数可能比稳定的 `sort` 方法更快。
        /// 稳定排序的详细说明:https://en.wikipedia.org/wiki/Sorting_algorithm#Stability
        /// `ctx` 具有以下方法:
        /// `fn lessThan(ctx: @TypeOf(ctx), a_index: usize, b_index: usize) bool`
        pub fn sortUnstable(self: Self, ctx: anytype) void {
            self.sortInternal(0, self.len, ctx, .unstable);
        }

        /// 仅排序索引 `a` 与 `b` 之间的元素子区间,不包含 `b`。
        /// 此函数不保证稳定排序,即相等元素的相对顺序可能在排序期间改变。
        /// 由于保证较弱,此函数可能比稳定的 `sortSpan` 方法更快。
        /// 稳定排序的详细说明:https://en.wikipedia.org/wiki/Sorting_algorithm#Stability
        /// `ctx` 具有以下方法:
        /// `fn lessThan(ctx: @TypeOf(ctx), a_index: usize, b_index: usize) bool`
        pub fn sortSpanUnstable(self: Self, a: usize, b: usize, ctx: anytype) void {
            self.sortInternal(a, b, ctx, .unstable);
        }

        pub fn capacityInBytes(capacity: usize) usize {
            comptime var elem_bytes: usize = 0;
            inline for (sizes.bytes) |size| elem_bytes += size;
            return elem_bytes * capacity;
        }

        fn allocatedBytes(self: Self) []align(sizes.big_align.toByteUnits()) u8 {
            return @alignCast(self.bytes[0..capacityInBytes(self.capacity)]);
        }

        fn FieldType(comptime field: Field) type {
            return @FieldType(Elem, @tagName(field));
        }

        const Entry = entry: {
            var entry_field_names: [field_names.len][]const u8 = undefined;
            var entry_field_types: [field_names.len]type = undefined;
            var entry_field_attrs: [field_names.len]std.builtin.Type.Struct.FieldAttributes = undefined;
            for (sizes.fields, &entry_field_names, &entry_field_types, &entry_field_attrs) |i, *name, *Type, *attrs| {
                name.* = field_names[i] ++ "_ptr";
                Type.* = *field_types[i];
                attrs.* = .{
                    .@"comptime" = field_attrs[i].@"comptime",
                    .@"align" = field_attrs[i].@"align",
                };
            }
            break :entry @Struct(.@"extern", null, &entry_field_names, &entry_field_types, &entry_field_attrs);
        };
        /// lib/lldb/ 中的调试器美化格式器使用此函数获取
        /// 子字段顺序与条目类型,以支持此类型的美化调试输出。
        fn dbHelper(self: *Self, child: *Elem, field: *Field, entry: *Entry) void {
            _ = self;
            _ = child;
            _ = field;
            _ = entry;
        }

        comptime {
            if (builtin.zig_backend == .stage2_llvm and !builtin.strip_debug_info) {
                _ = &dbHelper;
                _ = &Slice.dbHelper;
            }
        }
    };
}

test "basic usage" {
    const ally = testing.allocator;

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

    var list: MultiArrayList(Foo) = .empty;
    defer list.deinit(ally);

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

    try list.ensureTotalCapacity(ally, 2);

    list.appendAssumeCapacity(.{
        .a = 1,
        .b = "foobar",
        .c = 'a',
    });

    try list.appendBounded(.{
        .a = 2,
        .b = "zigzag",
        .c = 'b',
    });

    try testing.expectEqualSlices(u32, list.items(.a), &[_]u32{ 1, 2 });
    try testing.expectEqualSlices(u8, list.items(.c), &[_]u8{ 'a', 'b' });

    try testing.expectEqual(@as(usize, 2), list.items(.b).len);
    try testing.expectEqualStrings("foobar", list.items(.b)[0]);
    try testing.expectEqualStrings("zigzag", list.items(.b)[1]);

    try list.append(ally, .{
        .a = 3,
        .b = "fizzbuzz",
        .c = 'c',
    });

    try testing.expectEqualSlices(u32, list.items(.a), &[_]u32{ 1, 2, 3 });
    try testing.expectEqualSlices(u8, list.items(.c), &[_]u8{ 'a', 'b', 'c' });

    try testing.expectEqual(@as(usize, 3), list.items(.b).len);
    try testing.expectEqualStrings("foobar", list.items(.b)[0]);
    try testing.expectEqualStrings("zigzag", list.items(.b)[1]);
    try testing.expectEqualStrings("fizzbuzz", list.items(.b)[2]);

    // 再添加 6 个项目以强制扩容。
    var i: usize = 0;
    while (i < 6) : (i += 1) {
        try list.append(ally, .{
            .a = @as(u32, @intCast(4 + i)),
            .b = "whatever",
            .c = @as(u8, @intCast('d' + i)),
        });
    }

    try testing.expectEqualSlices(
        u32,
        &[_]u32{ 1, 2, 3, 4, 5, 6, 7, 8, 9 },
        list.items(.a),
    );
    try testing.expectEqualSlices(
        u8,
        &[_]u8{ 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i' },
        list.items(.c),
    );

    list.shrinkAndFree(ally, 3);

    try testing.expectEqualSlices(u32, list.items(.a), &[_]u32{ 1, 2, 3 });
    try testing.expectEqualSlices(u8, list.items(.c), &[_]u8{ 'a', 'b', 'c' });

    list.swap(0, 2);
    try testing.expectEqualSlices(u32, list.items(.a), &[_]u32{ 3, 2, 1 });
    try testing.expectEqualSlices(u8, list.items(.c), &[_]u8{ 'c', 'b', 'a' });
    list.swap(2, 1);
    try testing.expectEqualSlices(u32, list.items(.a), &[_]u32{ 3, 1, 2 });
    try testing.expectEqualSlices(u8, list.items(.c), &[_]u8{ 'c', 'a', 'b' });
    list.swap(2, 0);
    try testing.expectEqualSlices(u32, list.items(.a), &[_]u32{ 2, 1, 3 });
    try testing.expectEqualSlices(u8, list.items(.c), &[_]u8{ 'b', 'a', 'c' });
    list.swap(0, 1);
    try testing.expectEqualSlices(u32, list.items(.a), &[_]u32{ 1, 2, 3 });
    try testing.expectEqualSlices(u8, list.items(.c), &[_]u8{ 'a', 'b', 'c' });

    try testing.expectEqual(@as(usize, 3), list.items(.b).len);
    try testing.expectEqualStrings("foobar", list.items(.b)[0]);
    try testing.expectEqualStrings("zigzag", list.items(.b)[1]);
    try testing.expectEqualStrings("fizzbuzz", list.items(.b)[2]);

    try testing.expectError(error.OutOfMemory, list.addOneBounded());

    list.set(try list.addOne(ally), .{
        .a = 4,
        .b = "xnopyt",
        .c = 'd',
    });
    try testing.expectEqualStrings("xnopyt", list.pop().?.b);
    try testing.expectEqual(@as(?u8, 'c'), if (list.pop()) |elem| elem.c else null);
    try testing.expectEqual(@as(u32, 2), list.pop().?.a);
    try testing.expectEqual(@as(u8, 'a'), list.pop().?.c);
    try testing.expectEqual(@as(?Foo, null), list.pop());

    list.clearRetainingCapacity();
    try testing.expectEqual(0, list.len);
    try testing.expect(list.capacity > 0);

    list.clearAndFree(ally);
    try testing.expectEqual(0, list.len);
    try testing.expectEqual(0, list.capacity);
}

// 已观察到 LLVM 11 在 aarch64 上,当 capacityInBytes
// 函数使用 @reduce 代码路径时,此测试失败。
test "regression test for @reduce bug" {
    const ally = testing.allocator;
    var list: MultiArrayList(struct {
        tag: std.zig.Token.Tag,
        start: u32,
    }) = .empty;
    defer list.deinit(ally);

    try list.ensureTotalCapacity(ally, 20);

    try list.append(ally, .{ .tag = .keyword_const, .start = 0 });
    try list.append(ally, .{ .tag = .identifier, .start = 6 });
    try list.append(ally, .{ .tag = .equal, .start = 10 });
    try list.append(ally, .{ .tag = .builtin, .start = 12 });
    try list.append(ally, .{ .tag = .l_paren, .start = 19 });
    try list.append(ally, .{ .tag = .string_literal, .start = 20 });
    try list.append(ally, .{ .tag = .r_paren, .start = 25 });
    try list.append(ally, .{ .tag = .semicolon, .start = 26 });
    try list.append(ally, .{ .tag = .keyword_pub, .start = 29 });
    try list.append(ally, .{ .tag = .keyword_fn, .start = 33 });
    try list.append(ally, .{ .tag = .identifier, .start = 36 });
    try list.append(ally, .{ .tag = .l_paren, .start = 40 });
    try list.append(ally, .{ .tag = .r_paren, .start = 41 });
    try list.append(ally, .{ .tag = .identifier, .start = 43 });
    try list.append(ally, .{ .tag = .bang, .start = 51 });
    try list.append(ally, .{ .tag = .identifier, .start = 52 });
    try list.append(ally, .{ .tag = .l_brace, .start = 57 });
    try list.append(ally, .{ .tag = .identifier, .start = 63 });
    try list.append(ally, .{ .tag = .period, .start = 66 });
    try list.append(ally, .{ .tag = .identifier, .start = 67 });
    try list.append(ally, .{ .tag = .period, .start = 70 });
    try list.append(ally, .{ .tag = .identifier, .start = 71 });
    try list.append(ally, .{ .tag = .l_paren, .start = 75 });
    try list.append(ally, .{ .tag = .string_literal, .start = 76 });
    try list.append(ally, .{ .tag = .comma, .start = 113 });
    try list.append(ally, .{ .tag = .period, .start = 115 });
    try list.append(ally, .{ .tag = .l_brace, .start = 116 });
    try list.append(ally, .{ .tag = .r_brace, .start = 117 });
    try list.append(ally, .{ .tag = .r_paren, .start = 118 });
    try list.append(ally, .{ .tag = .semicolon, .start = 119 });
    try list.append(ally, .{ .tag = .r_brace, .start = 121 });
    try list.append(ally, .{ .tag = .eof, .start = 123 });

    const tags = list.items(.tag);
    try testing.expectEqual(tags[1], .identifier);
    try testing.expectEqual(tags[2], .equal);
    try testing.expectEqual(tags[3], .builtin);
    try testing.expectEqual(tags[4], .l_paren);
    try testing.expectEqual(tags[5], .string_literal);
    try testing.expectEqual(tags[6], .r_paren);
    try testing.expectEqual(tags[7], .semicolon);
    try testing.expectEqual(tags[8], .keyword_pub);
    try testing.expectEqual(tags[9], .keyword_fn);
    try testing.expectEqual(tags[10], .identifier);
    try testing.expectEqual(tags[11], .l_paren);
    try testing.expectEqual(tags[12], .r_paren);
    try testing.expectEqual(tags[13], .identifier);
    try testing.expectEqual(tags[14], .bang);
    try testing.expectEqual(tags[15], .identifier);
    try testing.expectEqual(tags[16], .l_brace);
    try testing.expectEqual(tags[17], .identifier);
    try testing.expectEqual(tags[18], .period);
    try testing.expectEqual(tags[19], .identifier);
    try testing.expectEqual(tags[20], .period);
    try testing.expectEqual(tags[21], .identifier);
    try testing.expectEqual(tags[22], .l_paren);
    try testing.expectEqual(tags[23], .string_literal);
    try testing.expectEqual(tags[24], .comma);
    try testing.expectEqual(tags[25], .period);
    try testing.expectEqual(tags[26], .l_brace);
    try testing.expectEqual(tags[27], .r_brace);
    try testing.expectEqual(tags[28], .r_paren);
    try testing.expectEqual(tags[29], .semicolon);
    try testing.expectEqual(tags[30], .r_brace);
    try testing.expectEqual(tags[31], .eof);
}

test "ensure capacity on empty list" {
    const ally = testing.allocator;

    const Foo = struct {
        a: u32,
        b: u8,
    };

    var list: MultiArrayList(Foo) = .empty;
    defer list.deinit(ally);

    try list.ensureTotalCapacity(ally, 2);
    list.appendAssumeCapacity(.{ .a = 1, .b = 2 });
    list.appendAssumeCapacity(.{ .a = 3, .b = 4 });

    try testing.expectEqualSlices(u32, &[_]u32{ 1, 3 }, list.items(.a));
    try testing.expectEqualSlices(u8, &[_]u8{ 2, 4 }, list.items(.b));

    list.len = 0;
    list.appendAssumeCapacity(.{ .a = 5, .b = 6 });
    list.appendAssumeCapacity(.{ .a = 7, .b = 8 });

    try testing.expectEqualSlices(u32, &[_]u32{ 5, 7 }, list.items(.a));
    try testing.expectEqualSlices(u8, &[_]u8{ 6, 8 }, list.items(.b));

    list.len = 0;
    try list.ensureTotalCapacity(ally, 16);

    list.appendAssumeCapacity(.{ .a = 9, .b = 10 });
    list.appendAssumeCapacity(.{ .a = 11, .b = 12 });

    try testing.expectEqualSlices(u32, &[_]u32{ 9, 11 }, list.items(.a));
    try testing.expectEqualSlices(u8, &[_]u8{ 10, 12 }, list.items(.b));
}

test "insert elements" {
    const ally = testing.allocator;

    const Foo = struct {
        a: u8,
        b: u32,
    };

    var list = try MultiArrayList(Foo).initCapacity(ally, 2);
    defer list.deinit(ally);

    try list.insertBounded(0, .{ .a = 1, .b = 2 });
    list.insertAssumeCapacity(1, .{ .a = 2, .b = 3 });
    try list.insert(ally, 0, .{ .a = 3, .b = 4 });

    try testing.expectEqualSlices(u8, &[_]u8{ 3, 1, 2 }, list.items(.a));
    try testing.expectEqualSlices(u32, &[_]u32{ 4, 2, 3 }, list.items(.b));
}

test "initCapacity" {
    const gpa = testing.allocator;

    var list = try MultiArrayList(struct { a: u8, b: u32 }).initCapacity(gpa, 404);
    defer list.deinit(gpa);

    try testing.expectEqual(0, list.len);
    try testing.expectEqual(404, list.capacity);
}

test "union" {
    const ally = testing.allocator;

    const Foo = union(enum) {
        a: u32,
        b: []const u8,
    };

    var list: MultiArrayList(Foo) = .empty;
    defer list.deinit(ally);

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

    try list.ensureTotalCapacity(ally, 3);

    list.appendAssumeCapacity(.{ .a = 1 });
    list.appendAssumeCapacity(.{ .b = "zigzag" });

    try testing.expectEqualSlices(meta.Tag(Foo), list.items(.tags), &.{ .a, .b });
    try testing.expectEqual(@as(usize, 2), list.items(.tags).len);

    list.appendAssumeCapacity(.{ .b = "foobar" });
    try testing.expectEqualStrings("zigzag", list.items(.data)[1].b);
    try testing.expectEqualStrings("foobar", list.items(.data)[2].b);

    // 再添加 6 个项目以强制扩容。
    for (0..6) |i| {
        try list.append(ally, .{ .a = @as(u32, @intCast(4 + i)) });
    }

    try testing.expectEqualSlices(
        meta.Tag(Foo),
        &.{ .a, .b, .b, .a, .a, .a, .a, .a, .a },
        list.items(.tags),
    );
    try testing.expectEqual(Foo{ .a = 1 }, list.get(0));
    try testing.expectEqual(Foo{ .b = "zigzag" }, list.get(1));
    try testing.expectEqual(Foo{ .b = "foobar" }, list.get(2));
    try testing.expectEqual(Foo{ .a = 4 }, list.get(3));
    try testing.expectEqual(Foo{ .a = 5 }, list.get(4));
    try testing.expectEqual(Foo{ .a = 6 }, list.get(5));
    try testing.expectEqual(Foo{ .a = 7 }, list.get(6));
    try testing.expectEqual(Foo{ .a = 8 }, list.get(7));
    try testing.expectEqual(Foo{ .a = 9 }, list.get(8));

    list.shrinkAndFree(ally, 3);

    try testing.expectEqual(@as(usize, 3), list.items(.tags).len);
    try testing.expectEqualSlices(meta.Tag(Foo), list.items(.tags), &.{ .a, .b, .b });

    try testing.expectEqual(Foo{ .a = 1 }, list.get(0));
    try testing.expectEqual(Foo{ .b = "zigzag" }, list.get(1));
    try testing.expectEqual(Foo{ .b = "foobar" }, list.get(2));
}

test "sorting a span" {
    var list: MultiArrayList(struct { score: u32, chr: u8 }) = .empty;
    defer list.deinit(testing.allocator);

    try list.ensureTotalCapacity(testing.allocator, 42);
    for (
        // zig fmt: off
        [42]u8{ 'b', 'a', 'c', 'a', 'b', 'c', 'b', 'c', 'b', 'a', 'b', 'a', 'b', 'c', 'b', 'a', 'a', 'c', 'c', 'a', 'c', 'b', 'a', 'c', 'a', 'b', 'b', 'c', 'c', 'b', 'a', 'b', 'a', 'b', 'c', 'b', 'a', 'a', 'c', 'c', 'a', 'c' },
        [42]u32{ 1,   1,   1,   2,   2,   2,   3,   3,   4,   3,   5,   4,   6,   4,   7,   5,   6,   5,   6,   7,   7,   8,   8,   8,   9,   9,  10,   9,  10,  11,  10,  12,  11,  13,  11,  14,  12,  13,  12,  13,  14,  14 },
        // zig fmt: on
    ) |chr, score| {
        list.appendAssumeCapacity(.{ .chr = chr, .score = score });
    }

    const sliced = list.slice();
    list.sortSpan(6, 21, struct {
        chars: []const u8,

        fn lessThan(ctx: @This(), a: usize, b: usize) bool {
            return ctx.chars[a] < ctx.chars[b];
        }
    }{ .chars = sliced.items(.chr) });

    var i: u32 = undefined;
    var j: u32 = 6;
    var c: u8 = 'a';

    while (j < 21) {
        i = j;
        j += 5;
        var n: u32 = 3;
        for (sliced.items(.chr)[i..j], sliced.items(.score)[i..j]) |chr, score| {
            try testing.expectEqual(score, n);
            try testing.expectEqual(chr, c);
            n += 1;
        }
        c += 1;
    }
}

test "0 sized struct field" {
    const ally = testing.allocator;

    const Foo = struct {
        a: u0,
        b: f32,
    };

    var list: MultiArrayList(Foo) = .empty;
    defer list.deinit(ally);

    try testing.expectEqualSlices(u0, &[_]u0{}, list.items(.a));
    try testing.expectEqualSlices(f32, &[_]f32{}, list.items(.b));

    try list.append(ally, .{ .a = 0, .b = 42.0 });
    try testing.expectEqualSlices(u0, &[_]u0{0}, list.items(.a));
    try testing.expectEqualSlices(f32, &[_]f32{42.0}, list.items(.b));

    try list.insert(ally, 0, .{ .a = 0, .b = -1.0 });
    try testing.expectEqualSlices(u0, &[_]u0{ 0, 0 }, list.items(.a));
    try testing.expectEqualSlices(f32, &[_]f32{ -1.0, 42.0 }, list.items(.b));

    list.swapRemove(list.len - 1);
    try testing.expectEqualSlices(u0, &[_]u0{0}, list.items(.a));
    try testing.expectEqualSlices(f32, &[_]f32{-1.0}, list.items(.b));
}

test "0 sized struct" {
    const ally = testing.allocator;

    const Foo = struct {
        a: u0,
    };

    var list: MultiArrayList(Foo) = .empty;
    defer list.deinit(ally);

    try testing.expectEqualSlices(u0, &[_]u0{}, list.items(.a));

    try list.append(ally, .{ .a = 0 });
    try testing.expectEqualSlices(u0, &[_]u0{0}, list.items(.a));

    try list.insert(ally, 0, .{ .a = 0 });
    try testing.expectEqualSlices(u0, &[_]u0{ 0, 0 }, list.items(.a));

    list.swapRemove(list.len - 1);
    try testing.expectEqualSlices(u0, &[_]u0{0}, list.items(.a));
}

test "struct with many fields" {
    const ManyFields = struct {
        fn Type(count: comptime_int) type {
            @setEvalBranchQuota(50000);
            var field_names: [count][]const u8 = undefined;
            for (&field_names, 0..) |*n, i| n.* = std.fmt.comptimePrint("a{d}", .{i});
            return @Struct(.@"extern", null, &field_names, &@splat(u32), &@splat(.{}));
        }

        fn doTest(ally: std.mem.Allocator, count: comptime_int) !void {
            var list: MultiArrayList(Type(count)) = .empty;
            defer list.deinit(ally);

            try list.resize(ally, 1);
            list.items(.a0)[0] = 42;
        }
    };

    try ManyFields.doTest(testing.allocator, 25);
    try ManyFields.doTest(testing.allocator, 50);
    try ManyFields.doTest(testing.allocator, 100);
    try ManyFields.doTest(testing.allocator, 200);
}

test "orderedRemoveMany" {
    const gpa = testing.allocator;

    var list: MultiArrayList(struct { x: usize }) = .empty;
    defer list.deinit(gpa);

    for (0..10) |n| {
        try list.append(gpa, .{ .x = n });
    }

    list.orderedRemoveMany(&.{ 1, 5, 5, 7, 9 });
    try testing.expectEqualSlices(usize, &.{ 0, 2, 3, 4, 6, 8 }, list.items(.x));

    list.orderedRemoveMany(&.{0});
    try testing.expectEqualSlices(usize, &.{ 2, 3, 4, 6, 8 }, list.items(.x));

    list.orderedRemoveMany(&.{});
    try testing.expectEqualSlices(usize, &.{ 2, 3, 4, 6, 8 }, list.items(.x));

    list.orderedRemoveMany(&.{ 1, 2, 3, 4 });
    try testing.expectEqualSlices(usize, &.{2}, list.items(.x));

    list.orderedRemoveMany(&.{0});
    try testing.expectEqualSlices(usize, &.{}, list.items(.x));
}