std.array_list.addOrOom
函数
整数加法,溢出时返回 error.OutOfMemory。
fn addOrOom(a: usize, b: usize) error{OutOfMemory}!usize
参数
a: usize
b: usize
错误
- OutOfMemory
std.array_list.Aligned
类型函数
内存中连续、可增长、支持任意对齐的项目列表。
封装由 T 值组成、按 alignment 字节地址
对齐的数组。若指定对齐为 null,使用 @alignOf(T)。
可能分配内存的函数接受 Allocator 参数。
直接初始化或使用 initCapacity,使用 deinit 销毁,
也可使用 toOwnedSlice。
pub fn Aligned(comptime T: type, comptime alignment: ?mem.Alignment) type
参数
字段
items: Slice列表内容。此字段旨在供 直接访问。
此 ArrayList 的各种函数会根据各自 文档所述规则,使指向此切片元素的 指针失效。 已失效的指针可能指向有效内存,也可能指向已释放内存。
capacity: usize此列表无需额外分配内存即可容纳的 T 值数量。
pointer_stability: debug.SafetyLock用于检测内存安全违规。
SelfemptySliceSentinelSliceinitCapacityinitBufferdeinitlockPointersunlockPointerstoManagedfromOwnedSlicefromOwnedSliceSentineltoOwnedSlicetoOwnedSliceSentineltoOwnedSliceAsserttoOwnedSliceSentinelAssertcloneinsertinsertAssumeCapacityinsertBoundedaddManyAtaddManyAtAssumeCapacityaddManyAtBoundedinsertSliceinsertSliceAssumeCapacityinsertSliceBoundedreplaceRangereplaceRangeAssumeCapacityreplaceRangeBoundedappendappendAssumeCapacityappendBoundedorderedRemoveorderedRemoveManyswapRemoveappendSliceappendSliceAssumeCapacityappendSliceBoundedappendUnalignedSliceappendUnalignedSliceAssumeCapacityappendUnalignedSliceBoundedprintprintAssumeCapacityprintBoundedappendNTimesappendNTimesAssumeCapacityappendNTimesBoundedresizeshrinkAndFreeshrinkAndFreePreciseshrinkToLenshrinkToLenSentinelshrinkRetainingCapacityclearRetainingCapacityclearAndFreeensureTotalCapacityensureTotalCapacityPreciseensureUnusedCapacityexpandToCapacityaddOneaddOneAssumeCapacityaddOneBoundedaddManyAsArrayaddManyAsArrayAssumeCapacityaddManyAsArrayBoundedaddManyAsSliceaddManyAsSliceAssumeCapacityaddManyAsSliceBoundedpopallocatedSliceunusedCapacitySlicegetLastgetLastOrNulllastlastPtrgrowCapacity
std.array_list.Aligned.addManyAsArray
函数
调整数组大小,新增 n 个值为 undefined 的元素。
若需额外内存,使元素指针失效。
返回指向新分配元素的数组。
返回的指针可能因后续对此列表的操作而失效。
pub fn addManyAsArray(self: *Self, gpa: Allocator, comptime n: usize) Allocator.Error!*[n]T
参数
错误
- OutOfMemory
std.array_list.Aligned.addManyAsArrayAssumeCapacity
函数
调整数组大小,新增 n 个值为 undefined 的元素。
返回指向新分配元素的数组。
绝不会使元素指针失效。
返回的指针可能因后续对此列表的操作而失效。
断言列表能够容纳新增元素。
pub fn addManyAsArrayAssumeCapacity(self: *Self, comptime n: usize) *[n]T
参数
self: *Self
n: usize
std.array_list.Aligned.addManyAsArrayBounded
函数
调整数组大小,新增 n 个值为 undefined 的元素。
返回指向新分配元素的数组。
绝不会使元素指针失效。
返回的指针可能因后续对此列表的操作而失效。
若列表未使用容量不足以容纳新增元素,返回 error.OutOfMemory。
pub fn addManyAsArrayBounded(self: *Self, comptime n: usize) error{OutOfMemory}!*[n]T
参数
self: *Self
n: usize
错误
- OutOfMemory
std.array_list.Aligned.addManyAsSlice
函数
调整数组大小,添加 n 个值为 undefined 的新元素。
返回指向新分配元素的切片。
后续对列表的操作可能使返回的指针失效。
如果 self.capacity 不够大,则调整列表大小。
pub fn addManyAsSlice(self: *Self, gpa: Allocator, n: usize) Allocator.Error![]T
参数
错误
- OutOfMemory
std.array_list.Aligned.addManyAsSliceAssumeCapacity
函数
调整数组大小,添加 n 个值为 undefined 的
新元素,并返回指向这些新分配元素的切片。
绝不使元素指针失效。
对此列表的后续操作可能使返回的指针失效。
断言列表可以容纳新增条目。
pub fn addManyAsSliceAssumeCapacity(self: *Self, n: usize) []T
参数
self: *Self
n: usize
std.array_list.Aligned.addManyAsSliceBounded
函数
调整数组大小,添加 n 个值为 undefined 的
新元素,并返回指向这些新分配元素的切片。
绝不使元素指针失效。
对此列表的后续操作可能使返回的指针失效。
如果列表没有足够的未用容量来容纳新增条目,则返回
error.OutOfMemory。
pub fn addManyAsSliceBounded(self: *Self, n: usize) error{OutOfMemory}![]T
参数
self: *Self
n: usize
错误
- OutOfMemory
std.array_list.Aligned.addManyAt
函数
添加 count 个新元素到 index 位置,
值均为 undefined。返回指向新分配
元素的切片;后续多种 ArrayList
操作会使其失效。
使已有的指向 index 及其后元素的指针失效。
若必须增加容量以容纳新元素,
则全部已有元素指针均失效。
断言索引位于有效范围内,或等于长度。
pub fn addManyAt( self: *Self, gpa: Allocator, index: usize, count: usize, ) Allocator.Error![]T
参数
错误
- OutOfMemory
std.array_list.Aligned.addManyAtAssumeCapacity
函数
在位置 index 添加 count 个新元素,其值为
undefined。返回指向新分配元素的
切片;各种 ArrayList 操作后,此切片
可能失效。
使此前指向 index 及之后元素的指针失效。
断言列表容量足以容纳新增元素。
断言索引在范围内,或等于长度。
pub fn addManyAtAssumeCapacity(self: *Self, index: usize, count: usize) []T
参数
std.array_list.Aligned.addManyAtBounded
函数
添加 count 个新元素,位置为 index,其值为 undefined,返回指向新分配元素的切片。该切片会在执行多种 ArrayList 操作后失效。
使此前指向 index 及其后元素的指针失效。
若列表未使用容量不足以容纳新增元素,返回 error.OutOfMemory。
断言索引在边界内或等于长度。
pub fn addManyAtBounded(self: *Self, index: usize, count: usize) error{OutOfMemory}![]T
参数
错误
- OutOfMemory
std.array_list.Aligned.addOne
函数
将长度增加 1,返回指向新元素的指针。 若需要额外内存,则使元素指针失效。 对此列表的后续操作可能使返回的指针失效。
pub fn addOne(self: *Self, gpa: Allocator) Allocator.Error!*T
参数
错误
- OutOfMemory
std.array_list.Aligned.addOneAssumeCapacity
函数
将长度增加 1,返回指向新元素的指针。 绝不会使元素指针失效。 对列表的后续操作可能使返回的指针失效。 断言列表可以容纳一个新增元素。
pub fn addOneAssumeCapacity(self: *Self) *T
参数
self: *Self
std.array_list.Aligned.addOneBounded
函数
将长度增加 1,并返回指向新条目的指针。
绝不使元素指针失效。
对此列表的后续操作可能使返回的指针失效。
如果列表没有足够的未用容量来容纳新增条目,则返回 error.OutOfMemory。
pub fn addOneBounded(self: *Self) error{OutOfMemory}!*T
参数
self: *Self
错误
- OutOfMemory
std.array_list.Aligned.allocatedSlice
函数
返回涵盖所有条目和额外容量的切片,额外容量的内存
内容为 undefined。
对此列表的后续操作可能使返回的指针失效。
pub fn allocatedSlice(self: Self) Slice
参数
self: Self
std.array_list.Aligned.append
函数
将列表扩展一个元素。按需分配更多内存。 若需要额外内存,则使元素指针失效。
pub fn append(self: *Self, gpa: Allocator, item: T) Allocator.Error!void
参数
错误
- OutOfMemory
std.array_list.Aligned.appendAssumeCapacity
函数
将列表扩展 1 个元素。
绝不会使元素指针失效。
断言列表还可容纳一个元素。
pub fn appendAssumeCapacity(self: *Self, item: T) void
参数
self: *Self
item: T
std.array_list.Aligned.appendBounded
函数
将列表扩展一个元素。
永远不会使元素指针失效。
若列表的未使用容量不足以容纳新增项目,则返回 error.OutOfMemory。
pub fn appendBounded(self: *Self, item: T) error{OutOfMemory}!void
参数
self: *Self
item: T
错误
- OutOfMemory
std.array_list.Aligned.appendNTimes
函数
将某个值向列表追加 n 次。
必要时分配更多内存。
若需额外内存,使元素指针失效。
此函数采用内联,使编译期已知的 value 参数若具有重复字节模式时,能够生成更优的 memset 代码。
pub inline fn appendNTimes(self: *Self, gpa: Allocator, value: T, n: usize) Allocator.Error!void
参数
错误
- OutOfMemory
std.array_list.Aligned.appendNTimesAssumeCapacity
函数
向列表追加同一个值 n 次。
绝不会使元素指针失效。
此函数内联,使得编译期已知的 value 参数
若具有重复字节模式,可生成更好的 memset 代码。
断言列表能够容纳新增元素。
pub inline fn appendNTimesAssumeCapacity(self: *Self, value: T, n: usize) void
参数
std.array_list.Aligned.appendNTimesBounded
函数
将某个值向列表追加 n 次。
绝不会使元素指针失效。
此函数采用内联,使编译期已知的 value 参数若具有重复字节模式时,能够生成更优的 memset 代码。
若列表未使用容量不足以容纳新增元素,返回 error.OutOfMemory。
pub inline fn appendNTimesBounded(self: *Self, value: T, n: usize) error{OutOfMemory}!void
参数
错误
- OutOfMemory
std.array_list.Aligned.appendSlice
函数
将元素切片追加到列表。必要时分配 更多内存。 如果需要额外内存,元素指针将失效。
pub fn appendSlice(self: *Self, gpa: Allocator, items: []const T) Allocator.Error!void
参数
错误
- OutOfMemory
std.array_list.Aligned.appendSliceAssumeCapacity
函数
将项目切片追加到列表。 永远不会使元素指针失效。 断言列表能容纳额外项目。
pub fn appendSliceAssumeCapacity(self: *Self, items: []const T) void
参数
self: *Self
items: []const T
std.array_list.Aligned.appendSliceBounded
函数
将条目切片追加到列表。
绝不使元素指针失效。
若列表的未用容量不足以容纳新增条目,则返回 error.OutOfMemory。
pub fn appendSliceBounded(self: *Self, items: []const T) error{OutOfMemory}!void
参数
self: *Self
items: []const T
错误
- OutOfMemory
std.array_list.Aligned.appendUnalignedSlice
函数
将元素切片追加到列表。必要时分配更多
内存。仅应在改用 appendSlice 会
导致编译错误时调用此函数。
如果需要额外内存,会使元素指针失效。
pub fn appendUnalignedSlice(self: *Self, gpa: Allocator, items: []align(1) const T) Allocator.Error!void
参数
错误
- OutOfMemory
std.array_list.Aligned.appendUnalignedSliceAssumeCapacity
函数
将未对齐的元素切片追加到列表。
仅应在调用 appendSliceAssumeCapacity 会
导致编译错误时使用。
绝不会使元素指针失效。
断言列表能够容纳新增元素。
pub fn appendUnalignedSliceAssumeCapacity(self: *Self, items: []align(1) const T) void
参数
self: *Self
items: []align(1) const T
std.array_list.Aligned.appendUnalignedSliceBounded
函数
向列表追加一个未对齐的元素切片。
仅在 appendSliceAssumeCapacity 会导致
编译错误时使用。
绝不会使元素指针失效。
若列表的未使用容量不足以容纳新增元素,返回
error.OutOfMemory。
pub fn appendUnalignedSliceBounded(self: *Self, items: []align(1) const T) error{OutOfMemory}!void
参数
self: *Self
items: []align(1) const T
错误
- OutOfMemory
std.array_list.Aligned.clearAndFree
函数
使所有元素指针失效。
pub fn clearAndFree(self: *Self, gpa: Allocator) void
参数
std.array_list.Aligned.clearRetainingCapacity
函数
将长度减为 0。 使所有元素指针失效。
pub fn clearRetainingCapacity(self: *Self) void
参数
self: *Self
std.array_list.Aligned.clone
函数
创建此 ArrayList 的副本。
pub fn clone(self: Self, gpa: Allocator) Allocator.Error!Self
参数
错误
- OutOfMemory
std.array_list.Aligned.deinit
函数
释放全部已分配内存。
pub fn deinit(self: *Self, gpa: Allocator) void
参数
std.array_list.Aligned.empty
常量
不含任何元素的 ArrayList。
Self
std.array_list.Aligned.ensureTotalCapacity
函数
修改数组,使其至少可容纳 new_capacity 个条目。
采用超线性增长,以实现均摊 O(1) 的追加操作。
如果需要额外内存,则使元素指针失效。
pub fn ensureTotalCapacity(self: *Self, gpa: Allocator, new_capacity: usize) Allocator.Error!void
参数
错误
- OutOfMemory
std.array_list.Aligned.ensureTotalCapacityPrecise
函数
若当前容量小于 new_capacity,此函数会
修改数组,使其恰好能容纳 new_capacity 个元素。
若需要额外内存,则使元素指针失效。
pub fn ensureTotalCapacityPrecise(self: *Self, gpa: Allocator, new_capacity: usize) Allocator.Error!void
参数
错误
- OutOfMemory
std.array_list.Aligned.ensureUnusedCapacity
函数
修改数组,使其至少还能额外容纳 additional_count 个项目。
若需要额外内存,则使元素指针失效。
pub fn ensureUnusedCapacity( self: *Self, gpa: Allocator, additional_count: usize, ) Allocator.Error!void
参数
错误
- OutOfMemory
std.array_list.Aligned.expandToCapacity
函数
将数组长度增加到已分配的完整容量。
新元素的值为 undefined。
绝不会使元素指针失效。
pub fn expandToCapacity(self: *Self) void
参数
self: *Self
std.array_list.Aligned.fromOwnedSlice
函数
ArrayList 接管传入切片的所有权。
使用 deinit 反初始化,或使用 toOwnedSlice。
pub fn fromOwnedSlice(slice: Slice) Self
参数
slice: Slice
std.array_list.Aligned.fromOwnedSliceSentinel
函数
ArrayList 接管传入切片的所有权。
使用 deinit 反初始化,或使用 toOwnedSlice。
pub fn fromOwnedSliceSentinel(comptime sentinel: T, slice: [:sentinel]T) Self
参数
sentinel: T
slice: [:sentinel]T
std.array_list.Aligned.getLast
函数
已弃用
pub fn getLast(self: Self) T
参数
self: Self
std.array_list.Aligned.getLastOrNull
别名
已弃用,请使用 last
std.array_list.Aligned.growCapacity
函数
需要增加内存时调用。返回大于 最小值且按超线性规律增长的容量。
pub fn growCapacity(minimum: usize) usize
参数
minimum: usize
std.array_list.Aligned.initBuffer
函数
使用外部管理的内存初始化。缓冲区决定 容量,长度设为零。
以这种方式初始化后,所有接受 Allocator 参数的函数都会导致非法行为。
pub fn initBuffer(buffer: Slice) Self
参数
buffer: Slice
std.array_list.Aligned.initCapacity
函数
初始化并分配恰好可容纳 num 个元素的容量。
使用 deinit 或 toOwnedSlice 反初始化。
pub fn initCapacity(gpa: Allocator, num: usize) Allocator.Error!Self
参数
gpa: Allocator
num: usize
错误
- OutOfMemory
std.array_list.Aligned.insert
函数
在索引 index 处插入 item。将 list[index .. list.len] 移向更高索引以腾出空间。
如果 index 等于列表长度,则此操作等同于追加。
此操作的时间复杂度为 O(N)。
如果需要额外内存,会使元素指针失效。
使此前指向 index 及之后元素的指针失效。
断言索引在范围内,或等于长度。
pub fn insert(self: *Self, gpa: Allocator, index: usize, item: T) Allocator.Error!void
参数
错误
- OutOfMemory
std.array_list.Aligned.insertAssumeCapacity
函数
将 item 插入索引 index,把 list[index .. list.len] 移向更大索引以腾出空间。
若 index 等于列表长度,此操作
等同于 appendAssumeCapacity。
此操作复杂度为 O(N)。
使已有的指向 index 及其后元素的指针失效。
断言列表有容纳一个额外项目的容量。
断言索引位于有效范围内,或等于长度。
pub fn insertAssumeCapacity(self: *Self, index: usize, item: T) void
参数
std.array_list.Aligned.insertBounded
函数
插入 item,位置为索引 index。将 list[index .. list.len] 向更高索引移动以腾出空间。
若 index 等于列表长度,此操作等同于 appendAssumeCapacity。
此操作为 O(N)。
使此前指向 index 及其后元素的指针失效。
断言索引在边界内或等于长度。
若列表未使用容量不足以容纳新增元素,返回 error.OutOfMemory。
pub fn insertBounded(self: *Self, i: usize, item: T) error{OutOfMemory}!void
参数
错误
- OutOfMemory
std.array_list.Aligned.insertSlice
函数
插入切片 items,位置为索引 index,通过移动 list[index .. list.len] 腾出空间。
此操作为 O(N)。
使此前指向 index 及其后元素的指针失效。
若必须增加容量才能容纳新增元素,则使此前所有元素指针失效。
断言索引在边界内或等于长度。
pub fn insertSlice( self: *Self, gpa: Allocator, index: usize, items: []const T, ) Allocator.Error!void
参数
错误
- OutOfMemory
std.array_list.Aligned.insertSliceAssumeCapacity
函数
移动 list[index .. list.len] 腾出空间,在索引 index 处插入切片 items。
此操作的时间复杂度为 O(N)。
使此前指向 index 及之后元素的指针失效。
断言列表容量足以容纳新增元素。
断言索引在范围内,或等于长度。
pub fn insertSliceAssumeCapacity( self: *Self, index: usize, items: []const T, ) void
参数
std.array_list.Aligned.insertSliceBounded
函数
插入切片 items,位置为索引 index,通过移动 list[index .. list.len] 腾出空间。
此操作为 O(N)。
使此前指向 index 及其后元素的指针失效。
若列表未使用容量不足以容纳新增元素,返回 error.OutOfMemory。
断言索引在边界内或等于长度。
pub fn insertSliceBounded( self: *Self, index: usize, items: []const T, ) error{OutOfMemory}!void
参数
错误
- OutOfMemory
std.array_list.Aligned.last
函数
返回列表最后一个元素;列表
为空则返回 null。
pub fn last(self: Self) ?T
参数
self: Self
std.array_list.Aligned.lastPtr
函数
返回指向列表最后一个元素的指针;列表为空时
返回 null。
对此列表的后续操作可能使返回的指针失效。
pub fn lastPtr(self: Self) ?*T
参数
self: Self
std.array_list.Aligned.lockPointers
函数
将非托管数组列表置于锁定状态;任何原本会 使已有值指针失效的方法调用, 都会改为触发断言。
lockPointers 可以多次调用,使列表的多个
独立使用者可以同时保持锁定。
当 unlockPointers 的调用次数与 lockPointers
相同时,列表恢复此前状态。
pub fn lockPointers(self: *Self) void
参数
self: *Self
std.array_list.Aligned.orderedRemove
函数
从列表移除索引 i 处的元素,并返回其值。
使指向最后一个元素的指针失效。
此操作为 O(N)。
断言索引未越界。
pub fn orderedRemove(self: *Self, i: usize) T
参数
self: *Self
i: usize
std.array_list.Aligned.orderedRemoveMany
函数
移除 sorted_indexes 索引的元素。这些待移除索引
对应删除前的数组列表。
断言:
- 每个待移除索引都在范围内。
- 待移除索引按升序排列。
允许 sorted_indexes 中存在重复项。
此操作的时间复杂度为 O(N)。
使首个被删除索引之后的元素指针失效。
pub fn orderedRemoveMany(self: *Self, sorted_indexes: []const usize) void
参数
self: *Self
sorted_indexes: []const usize
std.array_list.Aligned.pop
函数
移除并返回列表最后一个元素。
列表为空则返回 null。
指向最后一个元素的指针将失效。
pub fn pop(self: *Self) ?T
参数
self: *Self
std.array_list.Aligned.print
函数
将格式化字符串打印到此列表。 如果需要额外内存,则使元素指针失效。
pub fn print(self: *Self, gpa: Allocator, comptime fmt: []const u8, args: anytype) error{OutOfMemory}!void
参数
错误
- OutOfMemory
std.array_list.Aligned.printAssumeCapacity
函数
将格式化字符串写入此列表。 断言具有足够的写入容量。 绝不会使元素指针失效。
pub fn printAssumeCapacity(self: *Self, comptime fmt: []const u8, args: anytype) void
参数
self: *Self
fmt: []const u8
std.array_list.Aligned.printBounded
函数
将格式化字符串打印到此列表中。 若写入需要额外容量,返回 error.OutOfMemory。 绝不会使元素指针失效。
pub fn printBounded(self: *Self, comptime fmt: []const u8, args: anytype) error{OutOfMemory}!void
参数
self: *Self
fmt: []const u8
错误
- OutOfMemory
std.array_list.Aligned.replaceRange
函数
根据需要增大或缩小列表。
若分配了额外容量,则使元素指针失效。
若 len 与 new_items.len 不相等,则使指向索引 start + len 及其之后元素的指针失效。
断言范围未越界。
pub fn replaceRange( self: *Self, gpa: Allocator, start: usize, len: usize, new_items: []const T, ) Allocator.Error!void
参数
错误
- OutOfMemory
std.array_list.Aligned.replaceRangeAssumeCapacity
函数
按需扩大或缩小列表。
若 len 与 new_items.len 不相等,则使索引
start + len 及其后元素的指针失效。
断言容量足以容纳新增元素。
pub fn replaceRangeAssumeCapacity( self: *Self, start: usize, len: usize, new_items: []const T, ) void
参数
std.array_list.Aligned.replaceRangeBounded
函数
当 len 与 new_items.len 不相等时,使指向索引 start + len
及其之后元素的指针失效。
如果未用容量不足以容纳新增条目,
则返回 error.OutOfMemory。
pub fn replaceRangeBounded( self: *Self, start: usize, len: usize, new_items: []const T, ) error{OutOfMemory}!void
参数
错误
- OutOfMemory
std.array_list.Aligned.resize
函数
将列表长度调整为 new_len。
新增元素包含 undefined。
若需要额外内存,则使元素指针失效。
pub fn resize(self: *Self, gpa: Allocator, new_len: usize) Allocator.Error!void
参数
错误
- OutOfMemory
std.array_list.Aligned.Self
别名
std.array_list.Aligned.SentinelSlice
类型函数
pub fn SentinelSlice(comptime s: T) type
参数
s: T
std.array_list.Aligned.shrinkAndFree
函数
将已分配容量缩减为 new_len。
可能使元素指针失效。
断言新长度小于或等于原长度。
pub fn shrinkAndFree(self: *Self, gpa: Allocator, new_len: usize) void
参数
std.array_list.Aligned.shrinkAndFreePrecise
函数
将已分配容量减至 new_len。
可能使元素指针失效。
断言新长度小于或等于原长度。
成功时,保证容量等于长度。
pub fn shrinkAndFreePrecise(self: *Self, gpa: Allocator, new_len: usize) Allocator.Error!void
参数
错误
- OutOfMemory
std.array_list.Aligned.shrinkRetainingCapacity
函数
将长度缩减为 new_len。
使指向元素 items[new_len..] 的指针失效。
容量保持不变。
断言新长度小于或等于原长度。
pub fn shrinkRetainingCapacity(self: *Self, new_len: usize) void
参数
self: *Self
new_len: usize
std.array_list.Aligned.shrinkToLen
函数
缩小容量,使其与长度一致。
可能使元素指针失效。
成功后可以安全调用 toOwnedSliceAssert。
pub fn shrinkToLen(self: *Self, gpa: Allocator) Allocator.Error!void
参数
错误
- OutOfMemory
std.array_list.Aligned.shrinkToLenSentinel
函数
缩小或扩大容量,使其等于长度加 1。
可能使元素指针失效。
成功后可以安全调用 toOwnedSliceSentinelAssert。
pub fn shrinkToLenSentinel(self: *Self, gpa: Allocator) Allocator.Error!void
参数
错误
- OutOfMemory
std.array_list.Aligned.Slice
类型
std.array_list.Aligned.swapRemove
函数
移除指定索引处的元素并返回。 用列表末尾元素填充空槽位。 使指向最后一个元素的指针失效。 此操作时间复杂度为 O(1)。 断言索引未越界。
pub fn swapRemove(self: *Self, i: usize) T
参数
self: *Self
i: usize
std.array_list.Aligned.toManaged
函数
将此列表转换为对应的内存托管列表。 返回的列表拥有底层内存的所有权。
pub fn toManaged(self: *Self, gpa: Allocator) AlignedManaged(T, alignment)
参数
std.array_list.Aligned.toOwnedSlice
函数
调用者拥有返回内存的所有权。清空此 ArrayList。 容量被清零,因此可安全调用 deinit(),但没有必要。 可能使元素指针失效。
pub fn toOwnedSlice(self: *Self, gpa: Allocator) Allocator.Error!Slice
参数
错误
- OutOfMemory
std.array_list.Aligned.toOwnedSliceAssert
函数
调用者拥有返回内存的所有权。清空此 ArrayList。 容量被清零,因此可安全调用 deinit(),但没有必要。
断言容量等于长度。 绝不会使元素指针失效。
另见:
shrinkToLen
pub fn toOwnedSliceAssert(self: *Self) Slice
参数
self: *Self
std.array_list.Aligned.toOwnedSliceSentinel
函数
调用方拥有返回的内存。ArrayList 变为空。 可能使元素指针失效。
pub fn toOwnedSliceSentinel(self: *Self, gpa: Allocator, comptime sentinel: T) Allocator.Error!SentinelSlice(sentinel)
参数
错误
- OutOfMemory
std.array_list.Aligned.toOwnedSliceSentinelAssert
函数
调用方拥有返回内存的所有权。ArrayList 变为空列表。 断言容量等于长度加 1。 永远不会使元素指针失效。
pub fn toOwnedSliceSentinelAssert(self: *Self, comptime sentinel: T) SentinelSlice(sentinel)
参数
self: *Self
sentinel: T
std.array_list.Aligned.unlockPointers
函数
撤销一次 lockPointers 调用。
pub fn unlockPointers(self: *Self) void
参数
self: *Self
std.array_list.Aligned.unusedCapacitySlice
函数
返回仅涵盖现有条目之后额外容量的切片。
可用于直接写入 ArrayList。
注意,此操作之后必须直接
修改 self.items.len。
对此列表的后续操作可能使返回的指针失效。
pub fn unusedCapacitySlice(self: Self) []T
参数
self: Self
std.array_list.AlignedManaged
类型函数
已弃用。
pub fn AlignedManaged(comptime T: type, comptime alignment: ?mem.Alignment) type
参数
字段
items: Slice列表内容。此字段旨在供 直接访问。
此 ArrayList 的各种函数会根据各自 文档所述规则,使指向此切片元素的 指针失效。 已失效的指针可能指向有效内存,也可能指向已释放内存。
capacity: usize此列表无需额外分配内存即可容纳的 T 值数量。
allocator: Allocator
pointer_stability: debug.SafetyLock用于检测内存安全违规。
SelfSliceSentinelSliceinitinitCapacitydeinitlockPointersunlockPointersfromOwnedSlicefromOwnedSliceSentinelmoveToUnmanagedtoOwnedSlicetoOwnedSliceSentinelcloneinsertinsertAssumeCapacityaddManyAtaddManyAtAssumeCapacityinsertSlicereplaceRangereplaceRangeAssumeCapacityappendappendAssumeCapacityorderedRemoveswapRemoveappendSliceappendSliceAssumeCapacityappendUnalignedSliceappendUnalignedSliceAssumeCapacityprintappendNTimesappendNTimesAssumeCapacityresizeshrinkAndFreeshrinkRetainingCapacityclearRetainingCapacityclearAndFreeensureTotalCapacityensureTotalCapacityPreciseensureUnusedCapacityexpandToCapacityaddOneaddOneAssumeCapacityaddManyAsArrayaddManyAsArrayAssumeCapacityaddManyAsSliceaddManyAsSliceAssumeCapacitypopallocatedSliceunusedCapacitySlicegetLastgetLastOrNulllastlastPtr
std.array_list.AlignedManaged.addManyAsArray
函数
调整数组大小,添加 n 个值为 undefined 的新元素。
返回值是指向新分配元素的数组。
对此列表的后续操作可能使返回的指针失效。
如果 self.capacity 不足,则调整列表容量。
如果需要额外内存,则使元素指针失效。
pub fn addManyAsArray(self: *Self, comptime n: usize) Allocator.Error!*[n]T
参数
self: *Self
n: usize
错误
- OutOfMemory
std.array_list.AlignedManaged.addManyAsArrayAssumeCapacity
函数
调整数组大小,新增 n 个值为 undefined 的元素。
返回指向新分配元素的数组。
绝不会使元素指针失效。
返回的指针可能因后续对此列表的操作而失效。
断言列表能够容纳新增元素。
pub fn addManyAsArrayAssumeCapacity(self: *Self, comptime n: usize) *[n]T
参数
self: *Self
n: usize
std.array_list.AlignedManaged.addManyAsSlice
函数
调整数组大小,新增 n 个值为 undefined 的元素。
返回指向新分配元素的切片。
返回的指针可能因后续对此列表的操作而失效。
若 self.capacity 不足,则调整列表大小。
若需额外内存,使元素指针失效。
pub fn addManyAsSlice(self: *Self, n: usize) Allocator.Error![]T
参数
self: *Self
n: usize
错误
- OutOfMemory
std.array_list.AlignedManaged.addManyAsSliceAssumeCapacity
函数
调整数组大小,添加 n 个值为 undefined 的新元素。
返回值是指向新分配元素的切片。
绝不使元素指针失效。
对此列表的后续操作可能使返回的指针失效。
断言列表可以容纳新增条目。
pub fn addManyAsSliceAssumeCapacity(self: *Self, n: usize) []T
参数
self: *Self
n: usize
std.array_list.AlignedManaged.addManyAt
函数
添加 count 个新元素到 index 位置,
值均为 undefined。返回指向新分配
元素的切片;后续多种 ArrayList
操作会使其失效。
使已有的指向 index 及其后元素的指针失效。
若必须增加容量以容纳新元素,
则全部已有元素指针均失效。
断言索引位于有效范围内,或等于长度。
pub fn addManyAt(self: *Self, index: usize, count: usize) Allocator.Error![]T
参数
错误
- OutOfMemory
std.array_list.AlignedManaged.addManyAtAssumeCapacity
函数
添加 count 个新元素,位置为 index,其值为 undefined。
返回指向新分配元素的切片,该切片会在执行多种 ArrayList 操作后失效。
使此前指向 index 及其后元素的指针失效。
断言容量足以容纳新元素。
断言索引在边界内或等于长度。
pub fn addManyAtAssumeCapacity(self: *Self, index: usize, count: usize) []T
参数
std.array_list.AlignedManaged.addOne
函数
将长度增加 1,返回指向新元素的指针。 若需要额外内存,则使元素指针失效。 对此列表的后续操作可能使返回的指针失效。
pub fn addOne(self: *Self) Allocator.Error!*T
参数
self: *Self
错误
- OutOfMemory
std.array_list.AlignedManaged.addOneAssumeCapacity
函数
将长度增加 1,并返回指向新条目的指针。 对此列表的后续操作可能使返回的指针失效。 绝不使元素指针失效。 断言列表可以容纳一个新增条目。
pub fn addOneAssumeCapacity(self: *Self) *T
参数
self: *Self
std.array_list.AlignedManaged.allocatedSlice
函数
返回涵盖所有条目和额外容量的切片,额外容量的内存
内容为 undefined。
对此列表的后续操作可能使返回的指针失效。
pub fn allocatedSlice(self: Self) Slice
参数
self: Self
std.array_list.AlignedManaged.append
函数
将列表扩展 1 个元素。必要时分配更多内存。 如果需要额外内存,元素指针将失效。
pub fn append(self: *Self, item: T) Allocator.Error!void
参数
self: *Self
item: T
错误
- OutOfMemory
std.array_list.AlignedManaged.appendAssumeCapacity
函数
将列表扩展一个元素。 永远不会使元素指针失效。 断言列表能容纳一个额外项目。
pub fn appendAssumeCapacity(self: *Self, item: T) void
参数
self: *Self
item: T
std.array_list.AlignedManaged.appendNTimes
函数
将某个值向列表追加 n 次。
必要时分配更多内存。
若需额外内存,使元素指针失效。
此函数采用内联,使编译期已知的 value 参数若具有重复字节模式时,能够生成更优的 memset 代码。
pub inline fn appendNTimes(self: *Self, value: T, n: usize) Allocator.Error!void
参数
错误
- OutOfMemory
std.array_list.AlignedManaged.appendNTimesAssumeCapacity
函数
向列表追加一个值 n 次。
绝不使元素指针失效。
此函数内联,以便在编译时已知的 value 参数具有
重复字节模式时,生成更优的 memset 代码。
断言列表可以容纳新增条目。
pub inline fn appendNTimesAssumeCapacity(self: *Self, value: T, n: usize) void
参数
std.array_list.AlignedManaged.appendSlice
函数
将元素切片追加到列表。必要时分配 更多内存。 如果需要额外内存,元素指针将失效。
pub fn appendSlice(self: *Self, items: []const T) Allocator.Error!void
参数
self: *Self
items: []const T
错误
- OutOfMemory
std.array_list.AlignedManaged.appendSliceAssumeCapacity
函数
将项目切片追加到列表。 永远不会使元素指针失效。 断言列表能容纳额外项目。
pub fn appendSliceAssumeCapacity(self: *Self, items: []const T) void
参数
self: *Self
items: []const T
std.array_list.AlignedManaged.appendUnalignedSlice
函数
向列表追加未对齐的元素切片。按需分配
更多内存。仅在改用 appendSlice
会导致编译错误时调用此函数。
若需要额外内存,则会使元素指针失效。
pub fn appendUnalignedSlice(self: *Self, items: []align(1) const T) Allocator.Error!void
参数
self: *Self
items: []align(1) const T
错误
- OutOfMemory
std.array_list.AlignedManaged.appendUnalignedSliceAssumeCapacity
函数
将条目切片追加到列表。
绝不使元素指针失效。
仅当改用 appendSliceAssumeCapacity 会由于
items 参数的对齐方式
导致编译错误时,才需要此函数。
断言列表可以容纳新增条目。
pub fn appendUnalignedSliceAssumeCapacity(self: *Self, items: []align(1) const T) void
参数
self: *Self
items: []align(1) const T
std.array_list.AlignedManaged.clearAndFree
函数
使所有元素指针失效。
pub fn clearAndFree(self: *Self) void
参数
self: *Self
std.array_list.AlignedManaged.clearRetainingCapacity
函数
将长度减为 0。 使所有元素指针失效。
pub fn clearRetainingCapacity(self: *Self) void
参数
self: *Self
std.array_list.AlignedManaged.clone
函数
使用相同的分配器创建此 ArrayList 的副本。
pub fn clone(self: Self) Allocator.Error!Self
参数
self: Self
错误
- OutOfMemory
std.array_list.AlignedManaged.deinit
函数
释放全部已分配内存。
pub fn deinit(self: Self) void
参数
self: Self
std.array_list.AlignedManaged.ensureTotalCapacity
函数
如果当前容量小于 new_capacity,此函数将
修改数组,使其至少可容纳 new_capacity 个条目。
如果需要额外内存,则使元素指针失效。
pub fn ensureTotalCapacity(self: *Self, new_capacity: usize) Allocator.Error!void
参数
self: *Self
new_capacity: usize
错误
- OutOfMemory
std.array_list.AlignedManaged.ensureTotalCapacityPrecise
函数
若当前容量小于 new_capacity,此函数会
修改数组,使其恰好能容纳 new_capacity 个元素。
若需要额外内存,则使元素指针失效。
pub fn ensureTotalCapacityPrecise(self: *Self, new_capacity: usize) Allocator.Error!void
参数
self: *Self
new_capacity: usize
错误
- OutOfMemory
std.array_list.AlignedManaged.ensureUnusedCapacity
函数
修改数组,使其至少还能额外容纳 additional_count 个项目。
若需要额外内存,则使元素指针失效。
pub fn ensureUnusedCapacity(self: *Self, additional_count: usize) Allocator.Error!void
参数
self: *Self
additional_count: usize
错误
- OutOfMemory
std.array_list.AlignedManaged.expandToCapacity
函数
将数组长度增加到已分配的完整容量。
新元素的值为 undefined。
绝不会使元素指针失效。
pub fn expandToCapacity(self: *Self) void
参数
self: *Self
std.array_list.AlignedManaged.fromOwnedSlice
函数
ArrayList 取得传入切片的所有权。该切片必须由 gpa 分配。
使用 deinit 释放,或调用 toOwnedSlice。
pub fn fromOwnedSlice(gpa: Allocator, slice: Slice) Self
参数
std.array_list.AlignedManaged.fromOwnedSliceSentinel
函数
ArrayList 取得传入切片的所有权。该切片必须由 gpa 分配。
使用 deinit 释放,或调用 toOwnedSlice。
pub fn fromOwnedSliceSentinel(gpa: Allocator, comptime sentinel: T, slice: [:sentinel]T) Self
参数
std.array_list.AlignedManaged.getLast
函数
已弃用
pub fn getLast(self: Self) T
参数
self: Self
std.array_list.AlignedManaged.getLastOrNull
别名
已弃用,请使用 last
std.array_list.AlignedManaged.init
函数
使用 deinit 反初始化,或使用 toOwnedSlice。
pub fn init(gpa: Allocator) Self
参数
gpa: Allocator
std.array_list.AlignedManaged.initCapacity
函数
初始化为可容纳 num 个元素的容量。
结果容量恰好等于 num。
使用 deinit 释放,或调用 toOwnedSlice。
pub fn initCapacity(gpa: Allocator, num: usize) Allocator.Error!Self
参数
gpa: Allocator
num: usize
错误
- OutOfMemory
std.array_list.AlignedManaged.insert
函数
在索引 index 处插入 item。将 list[index .. list.len] 移向更高索引以腾出空间。
如果 index 等于列表长度,则此操作等同于追加。
此操作的时间复杂度为 O(N)。
如果需要额外内存,会使元素指针失效。
使此前指向 index 及之后元素的指针失效。
断言索引在范围内,或等于长度。
pub fn insert(self: *Self, index: usize, item: T) Allocator.Error!void
参数
错误
- OutOfMemory
std.array_list.AlignedManaged.insertAssumeCapacity
函数
将 item 插入索引 index,把 list[index .. list.len] 移向更大索引以腾出空间。
若 index 等于列表长度,此操作
等同于 appendAssumeCapacity。
此操作复杂度为 O(N)。
使已有的指向 index 及其后元素的指针失效。
断言有足够容量容纳新项目。
断言索引位于有效范围内,或等于长度。
pub fn insertAssumeCapacity(self: *Self, index: usize, item: T) void
参数
std.array_list.AlignedManaged.insertSlice
函数
插入切片 items,位置为索引 index,通过移动 list[index .. list.len] 腾出空间。
此操作为 O(N)。
使此前指向 index 及其后元素的指针失效。
若必须增加容量才能容纳新增元素,则使此前所有元素指针失效。
断言索引在边界内或等于长度。
pub fn insertSlice( self: *Self, index: usize, items: []const T, ) Allocator.Error!void
参数
错误
- OutOfMemory
std.array_list.AlignedManaged.last
函数
返回列表的最后一个元素;若列表
为空,则返回 null。
绝不会使元素指针失效。
pub fn last(self: Self) ?T
参数
self: Self
std.array_list.AlignedManaged.lastPtr
函数
返回指向列表最后一个元素的指针;列表为空时
返回 null。
对此列表的后续操作可能使返回的指针失效。
pub fn lastPtr(self: Self) ?*T
参数
self: Self
std.array_list.AlignedManaged.lockPointers
函数
将数组列表置于特殊状态:任何会使现有值指针失效的方法调用,都改为触发断言。
lockPointers 可以多次调用,使列表的多个独立使用者能同时保持其锁定。
unlockPointers 在调用次数与 lockPointers 相同时,将列表恢复为原先状态。
pub fn lockPointers(self: *Self) void
参数
self: *Self
std.array_list.AlignedManaged.moveToUnmanaged
函数
使用此 ArrayList 的 items 和 capacity 字段初始化一个 ArrayList。
清空此 ArrayList。
pub fn moveToUnmanaged(self: *Self) Aligned(T, alignment)
参数
self: *Self
std.array_list.AlignedManaged.orderedRemove
函数
移除索引 i 处的元素,将索引
i 之后的元素前移,并返回被移除的元素。
使指向列表末尾的元素指针失效。
此操作的时间复杂度为 O(N)。
保留条目顺序。如果无需保留顺序,请使用 swapRemove。
断言索引未越界。
断言列表非空。
pub fn orderedRemove(self: *Self, i: usize) T
参数
self: *Self
i: usize
std.array_list.AlignedManaged.pop
函数
移除并返回列表最后一个元素;列表为空则返回 null。
指向被移除元素的元素指针将失效。
pub fn pop(self: *Self) ?T
参数
self: *Self
std.array_list.AlignedManaged.print
函数
将格式化字符串打印到此列表。 如果需要额外内存,则使元素指针失效。
pub fn print(self: *Self, comptime fmt: []const u8, args: anytype) error{OutOfMemory}!void
参数
self: *Self
fmt: []const u8
错误
- OutOfMemory
std.array_list.AlignedManaged.replaceRange
函数
根据需要增大或缩小列表。
若分配了额外容量,则使元素指针失效。
若 len 与 new_items.len 不相等,则使指向索引 start + len 及其之后元素的指针失效。
断言范围未越界。
pub fn replaceRange(self: *Self, start: usize, len: usize, new_items: []const T) Allocator.Error!void
参数
错误
- OutOfMemory
std.array_list.AlignedManaged.replaceRangeAssumeCapacity
函数
按需扩大或缩小列表。
若 len 与 new_items.len 不相等,则使索引
start + len 及其后元素的指针失效。
断言容量足以容纳新增元素。
pub fn replaceRangeAssumeCapacity(self: *Self, start: usize, len: usize, new_items: []const T) void
参数
std.array_list.AlignedManaged.resize
函数
将列表长度调整为 new_len。
新增元素包含 undefined。
若需要额外内存,则使元素指针失效。
pub fn resize(self: *Self, new_len: usize) Allocator.Error!void
参数
self: *Self
new_len: usize
错误
- OutOfMemory
std.array_list.AlignedManaged.Self
别名
std.array_list.AlignedManaged.SentinelSlice
类型函数
pub fn SentinelSlice(comptime s: T) type
参数
s: T
std.array_list.AlignedManaged.shrinkAndFree
函数
将已分配容量缩减为 new_len。
可能使元素指针失效。
断言新长度小于或等于原长度。
pub fn shrinkAndFree(self: *Self, new_len: usize) void
参数
self: *Self
new_len: usize
std.array_list.AlignedManaged.shrinkRetainingCapacity
函数
将长度缩小为 new_len。
使指向 items[new_len..] 中元素的指针失效。
断言新长度小于或等于原长度。
pub fn shrinkRetainingCapacity(self: *Self, new_len: usize) void
参数
self: *Self
new_len: usize
std.array_list.AlignedManaged.Slice
类型
std.array_list.AlignedManaged.swapRemove
函数
移除指定索引处的元素并返回它。
使用列表末尾的元素填补空位。
使指向列表末尾的指针失效。
此操作的时间复杂度为 O(1)。
可能不保留条目顺序。如果需要保留顺序,请使用 orderedRemove。
断言索引未越界。
pub fn swapRemove(self: *Self, i: usize) T
参数
self: *Self
i: usize
std.array_list.AlignedManaged.toOwnedSlice
函数
调用方拥有返回内存的所有权。清空此 ArrayList。
容量同时清零,因此可安全调用 deinit,但没有必要。
如果无法原地重新映射内存,则可能使元素指针失效。
pub fn toOwnedSlice(self: *Self) Allocator.Error!Slice
参数
self: *Self
错误
- OutOfMemory
std.array_list.AlignedManaged.toOwnedSliceSentinel
函数
调用者拥有返回内存的所有权。清空此 ArrayList。 若无法原地重新映射内存,可能使元素指针失效。
pub fn toOwnedSliceSentinel(self: *Self, comptime sentinel: T) Allocator.Error!SentinelSlice(sentinel)
参数
self: *Self
sentinel: T
错误
- OutOfMemory
std.array_list.AlignedManaged.unlockPointers
函数
撤销一次 lockPointers 调用。
pub fn unlockPointers(self: *Self) void
参数
self: *Self
std.array_list.AlignedManaged.unusedCapacitySlice
函数
返回仅涵盖现有条目之后额外容量的切片。
可用于直接写入 ArrayList。
注意,此操作之后必须直接
修改 self.items.len。
对此列表的后续操作可能使返回的指针失效。
pub fn unusedCapacitySlice(self: Self) []T
参数
self: Self
std.array_list.Allocator
别名
别名目标 std.mem.Allocator
std.array_list.ArrayList
别名
别名目标 std.ArrayList
std.array_list.assert
别名
别名目标 std.debug.assert
std.array_list.debug
别名
别名目标 std.debug
std.array_list.Item
容器
字段
std.array_list.ItemUnmanaged
容器
字段
integer: i32
sub_items: ArrayList(ItemUnmanaged)
std.array_list.Managed
类型函数
已弃用。
pub fn Managed(comptime T: type) type
参数
T: type
字段
items: Slice列表内容。此字段旨在供 直接访问。
此 ArrayList 的各种函数会根据各自 文档所述规则,使指向此切片元素的 指针失效。 已失效的指针可能指向有效内存,也可能指向已释放内存。
capacity: usize此列表无需额外分配内存即可容纳的 T 值数量。
allocator: Allocator
pointer_stability: debug.SafetyLock用于检测内存安全违规。
SelfSliceSentinelSliceinitinitCapacitydeinitlockPointersunlockPointersfromOwnedSlicefromOwnedSliceSentinelmoveToUnmanagedtoOwnedSlicetoOwnedSliceSentinelcloneinsertinsertAssumeCapacityaddManyAtaddManyAtAssumeCapacityinsertSlicereplaceRangereplaceRangeAssumeCapacityappendappendAssumeCapacityorderedRemoveswapRemoveappendSliceappendSliceAssumeCapacityappendUnalignedSliceappendUnalignedSliceAssumeCapacityprintappendNTimesappendNTimesAssumeCapacityresizeshrinkAndFreeshrinkRetainingCapacityclearRetainingCapacityclearAndFreeensureTotalCapacityensureTotalCapacityPreciseensureUnusedCapacityexpandToCapacityaddOneaddOneAssumeCapacityaddManyAsArrayaddManyAsArrayAssumeCapacityaddManyAsSliceaddManyAsSliceAssumeCapacitypopallocatedSliceunusedCapacitySlicegetLastgetLastOrNulllastlastPtr
std.array_list.math
别名
别名目标 std.math
std.array_list.mem
别名
别名目标 std.mem
std.array_list.std
别名
别名目标 std
std.array_list.testing
别名
别名目标 std.testing
源码
std/array_list.zig
const std = @import("std.zig");
const debug = std.debug;
const assert = debug.assert;
const testing = std.testing;
const mem = std.mem;
const math = std.math;
const Allocator = mem.Allocator;
const ArrayList = std.ArrayList;
/// 已弃用。
pub fn Managed(comptime T: type) type {
return AlignedManaged(T, null);
}
/// 已弃用。
pub fn AlignedManaged(comptime T: type, comptime alignment: ?mem.Alignment) type {
if (alignment) |a| {
if (a.toByteUnits() == @alignOf(T)) {
return AlignedManaged(T, null);
}
}
return struct {
const Self = @This();
/// 列表内容。此字段旨在供
/// 直接访问。
///
/// 此 ArrayList 的各种函数会根据各自
/// 文档所述规则,使指向此切片元素的
/// 指针失效。
/// 已失效的指针可能指向有效内存,也可能指向已释放内存。
items: Slice,
/// 此列表无需额外分配内存即可容纳的 T 值数量。
///
capacity: usize,
allocator: Allocator,
/// 用于检测内存安全违规。
pointer_stability: debug.SafetyLock,
pub const Slice = if (alignment) |a| ([]align(a.toByteUnits()) T) else []T;
pub fn SentinelSlice(comptime s: T) type {
return if (alignment) |a| ([:s]align(a.toByteUnits()) T) else [:s]T;
}
/// 使用 `deinit` 反初始化,或使用 `toOwnedSlice`。
pub fn init(gpa: Allocator) Self {
return Self{
.items = &[_]T{},
.capacity = 0,
.allocator = gpa,
.pointer_stability = .{},
};
}
/// 初始化为可容纳 `num` 个元素的容量。
/// 结果容量恰好等于 `num`。
/// 使用 `deinit` 释放,或调用 `toOwnedSlice`。
pub fn initCapacity(gpa: Allocator, num: usize) Allocator.Error!Self {
var self = Self.init(gpa);
try self.ensureTotalCapacityPrecise(num);
return self;
}
/// 释放全部已分配内存。
pub fn deinit(self: Self) void {
self.pointer_stability.assertUnlocked();
if (@sizeOf(T) > 0) {
self.allocator.free(self.allocatedSlice());
}
}
/// 将数组列表置于特殊状态:任何会使现有值指针失效的方法调用,都改为触发断言。
///
/// `lockPointers` 可以多次调用,使列表的多个独立使用者能同时保持其锁定。
///
/// `unlockPointers` 在调用次数与 `lockPointers` 相同时,将列表恢复为原先状态。
///
///
///
///
pub fn lockPointers(self: *Self) void {
self.pointer_stability.lockShared();
}
/// 撤销一次 `lockPointers` 调用。
pub fn unlockPointers(self: *Self) void {
self.pointer_stability.unlockShared();
}
/// ArrayList 取得传入切片的所有权。该切片必须由 `gpa` 分配。
/// 使用 `deinit` 释放,或调用 `toOwnedSlice`。
///
pub fn fromOwnedSlice(gpa: Allocator, slice: Slice) Self {
return Self{
.items = slice,
.capacity = slice.len,
.allocator = gpa,
.pointer_stability = .{},
};
}
/// ArrayList 取得传入切片的所有权。该切片必须由 `gpa` 分配。
/// 使用 `deinit` 释放,或调用 `toOwnedSlice`。
///
pub fn fromOwnedSliceSentinel(gpa: Allocator, comptime sentinel: T, slice: [:sentinel]T) Self {
return Self{
.items = slice,
.capacity = slice.len + 1,
.allocator = gpa,
.pointer_stability = .{},
};
}
/// 使用此 ArrayList 的 `items` 和 `capacity` 字段初始化一个 ArrayList。
/// 清空此 ArrayList。
pub fn moveToUnmanaged(self: *Self) Aligned(T, alignment) {
const allocator = self.allocator;
const result: Aligned(T, alignment) = .{
.items = self.items,
.capacity = self.capacity,
.pointer_stability = self.pointer_stability,
};
self.* = init(allocator);
return result;
}
/// 调用方拥有返回内存的所有权。清空此 ArrayList。
/// 容量同时清零,因此可安全调用 `deinit`,但没有必要。
/// 如果无法原地重新映射内存,则可能使元素指针失效。
pub fn toOwnedSlice(self: *Self) Allocator.Error!Slice {
self.pointer_stability.assertUnlocked();
const allocator = self.allocator;
const old_memory = self.allocatedSlice();
if (allocator.remap(old_memory, self.items.len)) |new_items| {
self.* = init(allocator);
return new_items;
}
const new_memory = try allocator.alignedAlloc(T, alignment, self.items.len);
@memcpy(new_memory, self.items);
self.clearAndFree();
return new_memory;
}
/// 调用者拥有返回内存的所有权。清空此 ArrayList。
/// 若无法原地重新映射内存,可能使元素指针失效。
pub fn toOwnedSliceSentinel(self: *Self, comptime sentinel: T) Allocator.Error!SentinelSlice(sentinel) {
// 此加法不可能溢出,因为 `self.items` 不可能占据整个地址空间。
try self.ensureTotalCapacityPrecise(self.items.len + 1);
self.appendAssumeCapacity(sentinel);
const result = try self.toOwnedSlice();
return result[0 .. result.len - 1 :sentinel];
}
/// 使用相同的分配器创建此 ArrayList 的副本。
pub fn clone(self: Self) Allocator.Error!Self {
var cloned = try Self.initCapacity(self.allocator, self.capacity);
cloned.appendSliceAssumeCapacity(self.items);
return cloned;
}
/// 在索引 `index` 处插入 `item`。将 `list[index .. list.len]` 移向更高索引以腾出空间。
/// 如果 `index` 等于列表长度,则此操作等同于追加。
/// 此操作的时间复杂度为 O(N)。
/// 如果需要额外内存,会使元素指针失效。
/// 使此前指向 `index` 及之后元素的指针失效。
/// 断言索引在范围内,或等于长度。
pub fn insert(self: *Self, index: usize, item: T) Allocator.Error!void {
self.pointer_stability.assertUnlocked();
const dst = try self.addManyAt(index, 1);
dst[0] = item;
}
/// 将 `item` 插入索引 `index`,把 `list[index .. list.len]` 移向更大索引以腾出空间。
/// 若 `index` 等于列表长度,此操作
/// 等同于 appendAssumeCapacity。
/// 此操作复杂度为 O(N)。
/// 使已有的指向 `index` 及其后元素的指针失效。
/// 断言有足够容量容纳新项目。
/// 断言索引位于有效范围内,或等于长度。
pub fn insertAssumeCapacity(self: *Self, index: usize, item: T) void {
self.pointer_stability.assertUnlocked();
assert(self.items.len < self.capacity);
self.items.len += 1;
@memmove(self.items[index + 1 .. self.items.len], self.items[index .. self.items.len - 1]);
self.items[index] = item;
}
/// 添加 `count` 个新元素到 `index` 位置,
/// 值均为 `undefined`。返回指向新分配
/// 元素的切片;后续多种 `ArrayList`
/// 操作会使其失效。
/// 使已有的指向 `index` 及其后元素的指针失效。
/// 若必须增加容量以容纳新元素,
/// 则全部已有元素指针均失效。
/// 断言索引位于有效范围内,或等于长度。
pub fn addManyAt(self: *Self, index: usize, count: usize) Allocator.Error![]T {
const new_len = try addOrOom(self.items.len, count);
self.pointer_stability.assertUnlocked();
if (self.capacity >= new_len)
return addManyAtAssumeCapacity(self, index, count);
// 这里通过尝试原地调整大小,
// 失败时分配新缓冲区并自行复制,
// 避免复制已分配但未使用的字节。
// 如果调用 realloc(),分配器实现会无意义地复制
// 额外容量中的内容。
const new_capacity = Aligned(T, alignment).growCapacity(new_len);
const old_memory = self.allocatedSlice();
if (self.allocator.remap(old_memory, new_capacity)) |new_memory| {
self.items.ptr = new_memory.ptr;
self.capacity = new_memory.len;
return addManyAtAssumeCapacity(self, index, count);
}
// 进行新的内存分配,避开 `ensureTotalCapacity`,
// 从而避免额外的内存复制。
const new_memory = try self.allocator.alignedAlloc(T, alignment, new_capacity);
const to_move = self.items[index..];
@memcpy(new_memory[0..index], self.items[0..index]);
@memcpy(new_memory[index + count ..][0..to_move.len], to_move);
self.allocator.free(old_memory);
self.items = new_memory[0..new_len];
self.capacity = new_memory.len;
// 插入的 `new_memory[index..][0..count]` 元素已由内存分配初始化为 `undefined`。
//
return new_memory[index..][0..count];
}
/// 添加 `count` 个新元素,位置为 `index`,其值为 `undefined`。
/// 返回指向新分配元素的切片,该切片会在执行多种 `ArrayList` 操作后失效。
/// 使此前指向 `index` 及其后元素的指针失效。
/// 断言容量足以容纳新元素。
/// 断言索引在边界内或等于长度。
///
///
pub fn addManyAtAssumeCapacity(self: *Self, index: usize, count: usize) []T {
self.pointer_stability.assertUnlocked();
const new_len = self.items.len + count;
assert(self.capacity >= new_len);
const to_move = self.items[index..];
self.items.len = new_len;
@memmove(self.items[index + count ..][0..to_move.len], to_move);
const result = self.items[index..][0..count];
@memset(result, undefined);
return result;
}
/// 插入切片 `items`,位置为索引 `index`,通过移动 `list[index .. list.len]` 腾出空间。
/// 此操作为 O(N)。
/// 使此前指向 `index` 及其后元素的指针失效。
/// 若必须增加容量才能容纳新增元素,则使此前所有元素指针失效。
/// 断言索引在边界内或等于长度。
///
pub fn insertSlice(
self: *Self,
index: usize,
items: []const T,
) Allocator.Error!void {
const dst = try self.addManyAt(index, items.len);
@memcpy(dst, items);
}
/// 根据需要增大或缩小列表。
/// 若分配了额外容量,则使元素指针失效。
/// 若 `len` 与 `new_items.len` 不相等,则使指向索引 `start + len` 及其之后元素的指针失效。
/// 断言范围未越界。
///
pub fn replaceRange(self: *Self, start: usize, len: usize, new_items: []const T) Allocator.Error!void {
var unmanaged = self.moveToUnmanaged();
defer self.* = unmanaged.toManaged(self.allocator);
return unmanaged.replaceRange(self.allocator, start, len, new_items);
}
/// 按需扩大或缩小列表。
/// 若 `len` 与 `new_items.len` 不相等,则使索引
/// `start + len` 及其后元素的指针失效。
/// 断言容量足以容纳新增元素。
pub fn replaceRangeAssumeCapacity(self: *Self, start: usize, len: usize, new_items: []const T) void {
var unmanaged = self.moveToUnmanaged();
defer self.* = unmanaged.toManaged(self.allocator);
return unmanaged.replaceRangeAssumeCapacity(start, len, new_items);
}
/// 将列表扩展 1 个元素。必要时分配更多内存。
/// 如果需要额外内存,元素指针将失效。
pub fn append(self: *Self, item: T) Allocator.Error!void {
const new_item_ptr = try self.addOne();
new_item_ptr.* = item;
}
/// 将列表扩展一个元素。
/// 永远不会使元素指针失效。
/// 断言列表能容纳一个额外项目。
pub fn appendAssumeCapacity(self: *Self, item: T) void {
self.addOneAssumeCapacity().* = item;
}
/// 移除索引 `i` 处的元素,将索引
/// `i` 之后的元素前移,并返回被移除的元素。
/// 使指向列表末尾的元素指针失效。
/// 此操作的时间复杂度为 O(N)。
/// 保留条目顺序。如果无需保留顺序,请使用 `swapRemove`。
/// 断言索引未越界。
/// 断言列表非空。
pub fn orderedRemove(self: *Self, i: usize) T {
const old_item = self.items[i];
self.replaceRangeAssumeCapacity(i, 1, &.{});
return old_item;
}
/// 移除指定索引处的元素并返回它。
/// 使用列表末尾的元素填补空位。
/// 使指向列表末尾的指针失效。
/// 此操作的时间复杂度为 O(1)。
/// 可能不保留条目顺序。如果需要保留顺序,请使用 `orderedRemove`。
/// 断言索引未越界。
pub fn swapRemove(self: *Self, i: usize) T {
self.pointer_stability.assertUnlocked();
const val = self.items[i];
self.items[i] = self.items[self.items.len - 1];
self.items[self.items.len - 1] = undefined;
self.items.len -= 1;
return val;
}
/// 将元素切片追加到列表。必要时分配
/// 更多内存。
/// 如果需要额外内存,元素指针将失效。
pub fn appendSlice(self: *Self, items: []const T) Allocator.Error!void {
try self.ensureUnusedCapacity(items.len);
self.appendSliceAssumeCapacity(items);
}
/// 将项目切片追加到列表。
/// 永远不会使元素指针失效。
/// 断言列表能容纳额外项目。
pub fn appendSliceAssumeCapacity(self: *Self, items: []const T) void {
const old_len = self.items.len;
const new_len = old_len + items.len;
assert(new_len <= self.capacity);
self.items.len = new_len;
@memcpy(self.items[old_len..][0..items.len], items);
}
/// 向列表追加未对齐的元素切片。按需分配
/// 更多内存。仅在改用 `appendSlice`
/// 会导致编译错误时调用此函数。
/// 若需要额外内存,则会使元素指针失效。
pub fn appendUnalignedSlice(self: *Self, items: []align(1) const T) Allocator.Error!void {
try self.ensureUnusedCapacity(items.len);
self.appendUnalignedSliceAssumeCapacity(items);
}
/// 将条目切片追加到列表。
/// 绝不使元素指针失效。
/// 仅当改用 `appendSliceAssumeCapacity` 会由于
/// `items` 参数的对齐方式
/// 导致编译错误时,才需要此函数。
/// 断言列表可以容纳新增条目。
pub fn appendUnalignedSliceAssumeCapacity(self: *Self, items: []align(1) const T) void {
const old_len = self.items.len;
const new_len = old_len + items.len;
assert(new_len <= self.capacity);
self.items.len = new_len;
@memcpy(self.items[old_len..][0..items.len], items);
}
/// 将格式化字符串打印到此列表。
/// 如果需要额外内存,则使元素指针失效。
pub fn print(self: *Self, comptime fmt: []const u8, args: anytype) error{OutOfMemory}!void {
const gpa = self.allocator;
var unmanaged = self.moveToUnmanaged();
defer self.* = unmanaged.toManaged(gpa);
try unmanaged.print(gpa, fmt, args);
}
/// 将某个值向列表追加 `n` 次。
/// 必要时分配更多内存。
/// 若需额外内存,使元素指针失效。
/// 此函数采用内联,使编译期已知的 `value` 参数若具有重复字节模式时,能够生成更优的 memset 代码。
///
pub inline fn appendNTimes(self: *Self, value: T, n: usize) Allocator.Error!void {
const old_len = self.items.len;
try self.resize(try addOrOom(old_len, n));
@memset(self.items[old_len..self.items.len], value);
}
/// 向列表追加一个值 `n` 次。
/// 绝不使元素指针失效。
/// 此函数内联,以便在编译时已知的 `value` 参数具有
/// 重复字节模式时,生成更优的 memset 代码。
/// 断言列表可以容纳新增条目。
pub inline fn appendNTimesAssumeCapacity(self: *Self, value: T, n: usize) void {
const new_len = self.items.len + n;
assert(new_len <= self.capacity);
@memset(self.items.ptr[self.items.len..new_len], value);
self.items.len = new_len;
}
/// 将列表长度调整为 `new_len`。
/// 新增元素包含 `undefined`。
/// 若需要额外内存,则使元素指针失效。
pub fn resize(self: *Self, new_len: usize) Allocator.Error!void {
try self.ensureTotalCapacity(new_len);
self.items.len = new_len;
}
/// 将已分配容量缩减为 `new_len`。
/// 可能使元素指针失效。
/// 断言新长度小于或等于原长度。
pub fn shrinkAndFree(self: *Self, new_len: usize) void {
var unmanaged = self.moveToUnmanaged();
unmanaged.shrinkAndFree(self.allocator, new_len);
self.* = unmanaged.toManaged(self.allocator);
}
/// 将长度缩小为 `new_len`。
/// 使指向 `items[new_len..]` 中元素的指针失效。
/// 断言新长度小于或等于原长度。
pub fn shrinkRetainingCapacity(self: *Self, new_len: usize) void {
self.pointer_stability.assertUnlocked();
assert(new_len <= self.items.len);
@memset(self.items[new_len..], undefined);
self.items.len = new_len;
}
/// 将长度减为 0。
/// 使所有元素指针失效。
pub fn clearRetainingCapacity(self: *Self) void {
self.pointer_stability.assertUnlocked();
@memset(self.items, undefined);
self.items.len = 0;
}
/// 使所有元素指针失效。
pub fn clearAndFree(self: *Self) void {
self.pointer_stability.assertUnlocked();
self.allocator.free(self.allocatedSlice());
self.items.len = 0;
self.capacity = 0;
}
/// 如果当前容量小于 `new_capacity`,此函数将
/// 修改数组,使其至少可容纳 `new_capacity` 个条目。
/// 如果需要额外内存,则使元素指针失效。
pub fn ensureTotalCapacity(self: *Self, new_capacity: usize) Allocator.Error!void {
if (@sizeOf(T) == 0) {
self.capacity = math.maxInt(usize);
return;
}
// 防止无必要的增长,因为 better_capacity 会更大。
if (self.capacity >= new_capacity) return;
const better_capacity = Aligned(T, alignment).growCapacity(new_capacity);
return self.ensureTotalCapacityPrecise(better_capacity);
}
/// 若当前容量小于 `new_capacity`,此函数会
/// 修改数组,使其恰好能容纳 `new_capacity` 个元素。
/// 若需要额外内存,则使元素指针失效。
pub fn ensureTotalCapacityPrecise(self: *Self, new_capacity: usize) Allocator.Error!void {
if (@sizeOf(T) == 0) {
self.capacity = math.maxInt(usize);
return;
}
if (self.capacity >= new_capacity) return;
self.pointer_stability.assertUnlocked();
// 此处尝试重新映射,并在失败时回退到分配
// 新缓冲区并自行复制,以避免复制已分配但未使用的字节。
// 使用 realloc() 调用时,分配器实现会无谓地复制
// 额外容量。
//
const old_memory = self.allocatedSlice();
if (self.allocator.remap(old_memory, new_capacity)) |new_memory| {
self.items.ptr = new_memory.ptr;
self.capacity = new_memory.len;
} else {
const new_memory = try self.allocator.alignedAlloc(T, alignment, new_capacity);
@memcpy(new_memory[0..self.items.len], self.items);
self.allocator.free(old_memory);
self.items.ptr = new_memory.ptr;
self.capacity = new_memory.len;
}
}
/// 修改数组,使其至少还能额外容纳 `additional_count` 个项目。
/// 若需要额外内存,则使元素指针失效。
pub fn ensureUnusedCapacity(self: *Self, additional_count: usize) Allocator.Error!void {
return self.ensureTotalCapacity(try addOrOom(self.items.len, additional_count));
}
/// 将数组长度增加到已分配的完整容量。
/// 新元素的值为 `undefined`。
/// 绝不会使元素指针失效。
pub fn expandToCapacity(self: *Self) void {
self.items.len = self.capacity;
}
/// 将长度增加 1,返回指向新元素的指针。
/// 若需要额外内存,则使元素指针失效。
/// 对此列表的后续操作可能使返回的指针失效。
pub fn addOne(self: *Self) Allocator.Error!*T {
// 此处绝不会溢出,因为 `self.items` 不可能占据整个地址空间
const newlen = self.items.len + 1;
try self.ensureTotalCapacity(newlen);
return self.addOneAssumeCapacity();
}
/// 将长度增加 1,并返回指向新条目的指针。
/// 对此列表的后续操作可能使返回的指针失效。
/// 绝不使元素指针失效。
/// 断言列表可以容纳一个新增条目。
pub fn addOneAssumeCapacity(self: *Self) *T {
assert(self.items.len < self.capacity);
self.items.len += 1;
return &self.items[self.items.len - 1];
}
/// 调整数组大小,添加 `n` 个值为 `undefined` 的新元素。
/// 返回值是指向新分配元素的数组。
/// 对此列表的后续操作可能使返回的指针失效。
/// 如果 `self.capacity` 不足,则调整列表容量。
/// 如果需要额外内存,则使元素指针失效。
pub fn addManyAsArray(self: *Self, comptime n: usize) Allocator.Error!*[n]T {
const prev_len = self.items.len;
try self.resize(try addOrOom(self.items.len, n));
return self.items[prev_len..][0..n];
}
/// 调整数组大小,新增 `n` 个值为 `undefined` 的元素。
/// 返回指向新分配元素的数组。
/// 绝不会使元素指针失效。
/// 返回的指针可能因后续对此列表的操作而失效。
/// 断言列表能够容纳新增元素。
pub fn addManyAsArrayAssumeCapacity(self: *Self, comptime n: usize) *[n]T {
assert(self.items.len + n <= self.capacity);
const prev_len = self.items.len;
self.items.len += n;
return self.items[prev_len..][0..n];
}
/// 调整数组大小,新增 `n` 个值为 `undefined` 的元素。
/// 返回指向新分配元素的切片。
/// 返回的指针可能因后续对此列表的操作而失效。
/// 若 `self.capacity` 不足,则调整列表大小。
/// 若需额外内存,使元素指针失效。
pub fn addManyAsSlice(self: *Self, n: usize) Allocator.Error![]T {
const prev_len = self.items.len;
try self.resize(try addOrOom(self.items.len, n));
return self.items[prev_len..][0..n];
}
/// 调整数组大小,添加 `n` 个值为 `undefined` 的新元素。
/// 返回值是指向新分配元素的切片。
/// 绝不使元素指针失效。
/// 对此列表的后续操作可能使返回的指针失效。
/// 断言列表可以容纳新增条目。
pub fn addManyAsSliceAssumeCapacity(self: *Self, n: usize) []T {
assert(self.items.len + n <= self.capacity);
const prev_len = self.items.len;
self.items.len += n;
return self.items[prev_len..][0..n];
}
/// 移除并返回列表最后一个元素;列表为空则返回 `null`。
/// 指向被移除元素的元素指针将失效。
pub fn pop(self: *Self) ?T {
if (self.items.len == 0) return null;
self.pointer_stability.assertUnlocked();
const val = self.items[self.items.len - 1];
self.items[self.items.len - 1] = undefined;
self.items.len -= 1;
return val;
}
/// 返回涵盖所有条目和额外容量的切片,额外容量的内存
/// 内容为 `undefined`。
/// 对此列表的后续操作可能使返回的指针失效。
pub fn allocatedSlice(self: Self) Slice {
// `items.len` 是长度,不是容量。
return self.items.ptr[0..self.capacity];
}
/// 返回仅涵盖现有条目之后额外容量的切片。
/// 可用于直接写入 ArrayList。
/// 注意,此操作之后必须直接
/// 修改 `self.items.len`。
/// 对此列表的后续操作可能使返回的指针失效。
pub fn unusedCapacitySlice(self: Self) []T {
return self.allocatedSlice()[self.items.len..];
}
/// 已弃用
pub fn getLast(self: Self) T {
return self.items[self.items.len - 1];
}
/// 已弃用,请使用 `last`
pub const getLastOrNull = last;
/// 返回列表的最后一个元素;若列表
/// 为空,则返回 `null`。
/// 绝不会使元素指针失效。
pub fn last(self: Self) ?T {
if (self.items.len == 0) return null;
return self.items[self.items.len - 1];
}
/// 返回指向列表最后一个元素的指针;列表为空时
/// 返回 `null`。
/// 对此列表的后续操作可能使返回的指针失效。
pub fn lastPtr(self: Self) ?*T {
if (self.items.len == 0) return null;
return &self.items[self.items.len - 1];
}
};
}
/// 内存中连续、可增长、支持任意对齐的项目列表。
/// 封装由 T 值组成、按 `alignment` 字节地址
/// 对齐的数组。若指定对齐为 `null`,使用 `@alignOf(T)`。
///
/// 可能分配内存的函数接受 `Allocator` 参数。
/// 直接初始化或使用 `initCapacity`,使用 `deinit` 销毁,
/// 也可使用 `toOwnedSlice`。
pub fn Aligned(comptime T: type, comptime alignment: ?mem.Alignment) type {
if (alignment) |a| {
if (a.toByteUnits() == @alignOf(T)) {
return Aligned(T, null);
}
}
return struct {
const Self = @This();
/// 列表内容。此字段旨在供
/// 直接访问。
///
/// 此 ArrayList 的各种函数会根据各自
/// 文档所述规则,使指向此切片元素的
/// 指针失效。
/// 已失效的指针可能指向有效内存,也可能指向已释放内存。
items: Slice,
/// 此列表无需额外分配内存即可容纳的 T 值数量。
///
capacity: usize,
/// 用于检测内存安全违规。
pointer_stability: debug.SafetyLock,
/// 不含任何元素的 ArrayList。
pub const empty: Self = .{
.items = &.{},
.capacity = 0,
.pointer_stability = .{},
};
pub const Slice = if (alignment) |a| ([]align(a.toByteUnits()) T) else []T;
pub fn SentinelSlice(comptime s: T) type {
return if (alignment) |a| ([:s]align(a.toByteUnits()) T) else [:s]T;
}
/// 初始化并分配恰好可容纳 `num` 个元素的容量。
/// 使用 `deinit` 或 `toOwnedSlice` 反初始化。
pub fn initCapacity(gpa: Allocator, num: usize) Allocator.Error!Self {
var self: Self = .empty;
try self.ensureTotalCapacityPrecise(gpa, num);
return self;
}
/// 使用外部管理的内存初始化。缓冲区决定
/// 容量,长度设为零。
///
/// 以这种方式初始化后,所有接受 Allocator
/// 参数的函数都会导致非法行为。
pub fn initBuffer(buffer: Slice) Self {
return .{
.items = buffer[0..0],
.capacity = buffer.len,
.pointer_stability = .{},
};
}
/// 释放全部已分配内存。
pub fn deinit(self: *Self, gpa: Allocator) void {
self.pointer_stability.assertUnlocked();
gpa.free(self.allocatedSlice());
self.* = undefined;
}
/// 将非托管数组列表置于锁定状态;任何原本会
/// 使已有值指针失效的方法调用,
/// 都会改为触发断言。
///
/// `lockPointers` 可以多次调用,使列表的多个
/// 独立使用者可以同时保持锁定。
///
/// 当 `unlockPointers` 的调用次数与 `lockPointers`
/// 相同时,列表恢复此前状态。
pub fn lockPointers(self: *Self) void {
self.pointer_stability.lockShared();
}
/// 撤销一次 `lockPointers` 调用。
pub fn unlockPointers(self: *Self) void {
self.pointer_stability.unlockShared();
}
/// 将此列表转换为对应的内存托管列表。
/// 返回的列表拥有底层内存的所有权。
pub fn toManaged(self: *Self, gpa: Allocator) AlignedManaged(T, alignment) {
return .{
.items = self.items,
.capacity = self.capacity,
.allocator = gpa,
.pointer_stability = self.pointer_stability,
};
}
/// ArrayList 接管传入切片的所有权。
/// 使用 `deinit` 反初始化,或使用 `toOwnedSlice`。
pub fn fromOwnedSlice(slice: Slice) Self {
return Self{
.items = slice,
.capacity = slice.len,
.pointer_stability = .{},
};
}
/// ArrayList 接管传入切片的所有权。
/// 使用 `deinit` 反初始化,或使用 `toOwnedSlice`。
pub fn fromOwnedSliceSentinel(comptime sentinel: T, slice: [:sentinel]T) Self {
return Self{
.items = slice,
.capacity = slice.len + 1,
.pointer_stability = .{},
};
}
/// 调用者拥有返回内存的所有权。清空此 ArrayList。
/// 容量被清零,因此可安全调用 deinit(),但没有必要。
/// 可能使元素指针失效。
pub fn toOwnedSlice(self: *Self, gpa: Allocator) Allocator.Error!Slice {
const old_memory = self.allocatedSlice();
self.pointer_stability.assertUnlocked();
if (gpa.remap(old_memory, self.items.len)) |new_items| {
self.* = .empty;
return new_items;
}
const new_memory = try gpa.alignedAlloc(T, alignment, self.items.len);
@memcpy(new_memory, self.items);
self.clearAndFree(gpa);
return new_memory;
}
/// 调用方拥有返回的内存。ArrayList 变为空。
/// 可能使元素指针失效。
pub fn toOwnedSliceSentinel(self: *Self, gpa: Allocator, comptime sentinel: T) Allocator.Error!SentinelSlice(sentinel) {
self.pointer_stability.assertUnlocked();
// 此加法绝不会溢出,因为 `self.items` 不可能占满整个地址空间。
try self.ensureTotalCapacityPrecise(gpa, self.items.len + 1);
self.appendAssumeCapacity(sentinel);
errdefer self.items.len -= 1;
const result = try self.toOwnedSlice(gpa);
return result[0 .. result.len - 1 :sentinel];
}
/// 调用者拥有返回内存的所有权。清空此 ArrayList。
/// 容量被清零,因此可安全调用 deinit(),但没有必要。
///
/// 断言容量等于长度。
/// 绝不会使元素指针失效。
///
/// 另见:
/// * `shrinkToLen`
pub fn toOwnedSliceAssert(self: *Self) Slice {
assert(self.items.len == self.capacity);
const items = self.items;
self.* = .empty;
return items;
}
/// 调用方拥有返回内存的所有权。ArrayList 变为空列表。
/// 断言容量等于长度加 1。
/// 永远不会使元素指针失效。
pub fn toOwnedSliceSentinelAssert(self: *Self, comptime sentinel: T) SentinelSlice(sentinel) {
std.debug.assert(self.items.len + 1 == self.capacity);
self.appendAssumeCapacity(sentinel);
const result = self.toOwnedSliceAssert();
return result[0 .. result.len - 1 :sentinel];
}
/// 创建此 ArrayList 的副本。
pub fn clone(self: Self, gpa: Allocator) Allocator.Error!Self {
var cloned = try Self.initCapacity(gpa, self.capacity);
cloned.appendSliceAssumeCapacity(self.items);
return cloned;
}
/// 在索引 `index` 处插入 `item`。将 `list[index .. list.len]` 移向更高索引以腾出空间。
/// 如果 `index` 等于列表长度,则此操作等同于追加。
/// 此操作的时间复杂度为 O(N)。
/// 如果需要额外内存,会使元素指针失效。
/// 使此前指向 `index` 及之后元素的指针失效。
/// 断言索引在范围内,或等于长度。
pub fn insert(self: *Self, gpa: Allocator, index: usize, item: T) Allocator.Error!void {
self.pointer_stability.assertUnlocked();
const dst = try self.addManyAt(gpa, index, 1);
dst[0] = item;
}
/// 将 `item` 插入索引 `index`,把 `list[index .. list.len]` 移向更大索引以腾出空间。
/// 若 `index` 等于列表长度,此操作
/// 等同于 appendAssumeCapacity。
/// 此操作复杂度为 O(N)。
/// 使已有的指向 `index` 及其后元素的指针失效。
/// 断言列表有容纳一个额外项目的容量。
/// 断言索引位于有效范围内,或等于长度。
pub fn insertAssumeCapacity(self: *Self, index: usize, item: T) void {
self.pointer_stability.assertUnlocked();
assert(self.items.len < self.capacity);
self.items.len += 1;
@memmove(self.items[index + 1 .. self.items.len], self.items[index .. self.items.len - 1]);
self.items[index] = item;
}
/// 插入 `item`,位置为索引 `index`。将 `list[index .. list.len]` 向更高索引移动以腾出空间。
/// 若 `index` 等于列表长度,此操作等同于 appendAssumeCapacity。
/// 此操作为 O(N)。
/// 使此前指向 `index` 及其后元素的指针失效。
/// 断言索引在边界内或等于长度。
/// 若列表未使用容量不足以容纳新增元素,返回 `error.OutOfMemory`。
///
///
pub fn insertBounded(self: *Self, i: usize, item: T) error{OutOfMemory}!void {
if (self.capacity - self.items.len == 0) return error.OutOfMemory;
return insertAssumeCapacity(self, i, item);
}
/// 添加 `count` 个新元素到 `index` 位置,
/// 值均为 `undefined`。返回指向新分配
/// 元素的切片;后续多种 `ArrayList`
/// 操作会使其失效。
/// 使已有的指向 `index` 及其后元素的指针失效。
/// 若必须增加容量以容纳新元素,
/// 则全部已有元素指针均失效。
/// 断言索引位于有效范围内,或等于长度。
pub fn addManyAt(
self: *Self,
gpa: Allocator,
index: usize,
count: usize,
) Allocator.Error![]T {
const new_len = try addOrOom(self.items.len, count);
self.pointer_stability.assertUnlocked();
if (self.capacity >= new_len)
return addManyAtAssumeCapacity(self, index, count);
// 这里通过尝试原地调整大小,
// 失败时分配新缓冲区并自行复制,
// 避免复制已分配但未使用的字节。
// 如果调用 realloc(),分配器实现会无意义地复制
// 额外容量中的内容。
const new_capacity = Aligned(T, alignment).growCapacity(new_len);
const old_memory = self.allocatedSlice();
if (gpa.remap(old_memory, new_capacity)) |new_memory| {
self.items.ptr = new_memory.ptr;
self.capacity = new_memory.len;
return addManyAtAssumeCapacity(self, index, count);
}
// 进行新的内存分配,避开 `ensureTotalCapacity`,
// 从而避免额外的内存复制。
const new_memory = try gpa.alignedAlloc(T, alignment, new_capacity);
const to_move = self.items[index..];
@memcpy(new_memory[0..index], self.items[0..index]);
@memcpy(new_memory[index + count ..][0..to_move.len], to_move);
gpa.free(old_memory);
self.items = new_memory[0..new_len];
self.capacity = new_memory.len;
// 插入的 `new_memory[index..][0..count]` 元素已由内存分配初始化为 `undefined`。
//
return new_memory[index..][0..count];
}
/// 在位置 `index` 添加 `count` 个新元素,其值为
/// `undefined`。返回指向新分配元素的
/// 切片;各种 `ArrayList` 操作后,此切片
/// 可能失效。
/// 使此前指向 `index` 及之后元素的指针失效。
/// 断言列表容量足以容纳新增元素。
/// 断言索引在范围内,或等于长度。
pub fn addManyAtAssumeCapacity(self: *Self, index: usize, count: usize) []T {
self.pointer_stability.assertUnlocked();
const new_len = self.items.len + count;
assert(self.capacity >= new_len);
const to_move = self.items[index..];
self.items.len = new_len;
@memmove(self.items[index + count ..][0..to_move.len], to_move);
const result = self.items[index..][0..count];
@memset(result, undefined);
return result;
}
/// 添加 `count` 个新元素,位置为 `index`,其值为 `undefined`,返回指向新分配元素的切片。该切片会在执行多种 `ArrayList` 操作后失效。
/// 使此前指向 `index` 及其后元素的指针失效。
/// 若列表未使用容量不足以容纳新增元素,返回 `error.OutOfMemory`。
/// 断言索引在边界内或等于长度。
///
///
///
///
pub fn addManyAtBounded(self: *Self, index: usize, count: usize) error{OutOfMemory}![]T {
if (self.capacity - self.items.len < count) return error.OutOfMemory;
return addManyAtAssumeCapacity(self, index, count);
}
/// 插入切片 `items`,位置为索引 `index`,通过移动 `list[index .. list.len]` 腾出空间。
/// 此操作为 O(N)。
/// 使此前指向 `index` 及其后元素的指针失效。
/// 若必须增加容量才能容纳新增元素,则使此前所有元素指针失效。
/// 断言索引在边界内或等于长度。
///
pub fn insertSlice(
self: *Self,
gpa: Allocator,
index: usize,
items: []const T,
) Allocator.Error!void {
const dst = try self.addManyAt(
gpa,
index,
items.len,
);
@memcpy(dst, items);
}
/// 移动 `list[index .. list.len]` 腾出空间,在索引 `index` 处插入切片 `items`。
/// 此操作的时间复杂度为 O(N)。
/// 使此前指向 `index` 及之后元素的指针失效。
/// 断言列表容量足以容纳新增元素。
/// 断言索引在范围内,或等于长度。
pub fn insertSliceAssumeCapacity(
self: *Self,
index: usize,
items: []const T,
) void {
const dst = self.addManyAtAssumeCapacity(index, items.len);
@memcpy(dst, items);
}
/// 插入切片 `items`,位置为索引 `index`,通过移动 `list[index .. list.len]` 腾出空间。
/// 此操作为 O(N)。
/// 使此前指向 `index` 及其后元素的指针失效。
/// 若列表未使用容量不足以容纳新增元素,返回 `error.OutOfMemory`。
/// 断言索引在边界内或等于长度。
///
pub fn insertSliceBounded(
self: *Self,
index: usize,
items: []const T,
) error{OutOfMemory}!void {
const dst = try self.addManyAtBounded(index, items.len);
@memcpy(dst, items);
}
/// 根据需要增大或缩小列表。
/// 若分配了额外容量,则使元素指针失效。
/// 若 `len` 与 `new_items.len` 不相等,则使指向索引 `start + len` 及其之后元素的指针失效。
/// 断言范围未越界。
///
pub fn replaceRange(
self: *Self,
gpa: Allocator,
start: usize,
len: usize,
new_items: []const T,
) Allocator.Error!void {
try self.ensureTotalCapacity(gpa, try addOrOom(self.items.len - len, new_items.len));
self.replaceRangeAssumeCapacity(start, len, new_items);
}
/// 按需扩大或缩小列表。
/// 若 `len` 与 `new_items.len` 不相等,则使索引
/// `start + len` 及其后元素的指针失效。
/// 断言容量足以容纳新增元素。
pub fn replaceRangeAssumeCapacity(
self: *Self,
start: usize,
len: usize,
new_items: []const T,
) void {
std.debug.assert(self.capacity - self.items.len >= new_items.len -| len);
self.pointer_stability.assertUnlocked();
const tail = self.items[start + len ..];
const vacated = self.items[self.items.len - (len -| new_items.len) ..];
self.items.len = self.items.len - len + new_items.len;
@memmove(self.items[start + new_items.len ..], tail);
@memcpy(self.items[start..][0..new_items.len], new_items);
@memset(vacated, undefined);
}
/// 当 `len` 与 `new_items.len` 不相等时,使指向索引 `start + len`
/// 及其之后元素的指针失效。
/// 如果未用容量不足以容纳新增条目,
/// 则返回 `error.OutOfMemory`。
pub fn replaceRangeBounded(
self: *Self,
start: usize,
len: usize,
new_items: []const T,
) error{OutOfMemory}!void {
if (self.capacity - self.items.len < new_items.len -| len) return error.OutOfMemory;
return replaceRangeAssumeCapacity(self, start, len, new_items);
}
/// 将列表扩展一个元素。按需分配更多内存。
/// 若需要额外内存,则使元素指针失效。
pub fn append(self: *Self, gpa: Allocator, item: T) Allocator.Error!void {
const new_item_ptr = try self.addOne(gpa);
new_item_ptr.* = item;
}
/// 将列表扩展 1 个元素。
///
/// 绝不会使元素指针失效。
///
/// 断言列表还可容纳一个元素。
pub fn appendAssumeCapacity(self: *Self, item: T) void {
self.addOneAssumeCapacity().* = item;
}
/// 将列表扩展一个元素。
///
/// 永远不会使元素指针失效。
///
/// 若列表的未使用容量不足以容纳新增项目,则返回 `error.OutOfMemory`。
///
pub fn appendBounded(self: *Self, item: T) error{OutOfMemory}!void {
if (self.capacity - self.items.len == 0) return error.OutOfMemory;
return appendAssumeCapacity(self, item);
}
/// 从列表移除索引 `i` 处的元素,并返回其值。
/// 使指向最后一个元素的指针失效。
/// 此操作为 O(N)。
/// 断言索引未越界。
pub fn orderedRemove(self: *Self, i: usize) T {
const old_item = self.items[i];
self.replaceRangeAssumeCapacity(i, 1, &.{});
return old_item;
}
/// 移除 `sorted_indexes` 索引的元素。这些待移除索引
/// 对应删除前的数组列表。
///
/// 断言:
/// * 每个待移除索引都在范围内。
/// * 待移除索引按升序排列。
///
/// 允许 `sorted_indexes` 中存在重复项。
///
/// 此操作的时间复杂度为 O(N)。
///
/// 使首个被删除索引之后的元素指针失效。
pub fn orderedRemoveMany(self: *Self, sorted_indexes: []const usize) void {
self.pointer_stability.assertUnlocked();
if (sorted_indexes.len == 0) return;
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` 已排序
@memmove(self.items[start - shift ..][0..len], self.items[start..][0..len]); // 安全检查:初始 `sorted_indexes` 均在范围内
shift += 1;
}
const start = sorted_indexes[sorted_indexes.len - 1] + 1;
const end = self.items.len;
const len = end - start; // 安全检查:最终 `sorted_indexes` 均在范围内
@memmove(self.items[start - shift ..][0..len], self.items[start..][0..len]);
self.items.len = end - shift;
}
/// 移除指定索引处的元素并返回。
/// 用列表末尾元素填充空槽位。
/// 使指向最后一个元素的指针失效。
/// 此操作时间复杂度为 O(1)。
/// 断言索引未越界。
pub fn swapRemove(self: *Self, i: usize) T {
self.pointer_stability.assertUnlocked();
const val = self.items[i];
self.items[i] = self.items[self.items.len - 1];
self.items[self.items.len - 1] = undefined;
self.items.len -= 1;
return val;
}
/// 将元素切片追加到列表。必要时分配
/// 更多内存。
/// 如果需要额外内存,元素指针将失效。
pub fn appendSlice(self: *Self, gpa: Allocator, items: []const T) Allocator.Error!void {
try self.ensureUnusedCapacity(gpa, items.len);
self.appendSliceAssumeCapacity(items);
}
/// 将项目切片追加到列表。
/// 永远不会使元素指针失效。
/// 断言列表能容纳额外项目。
pub fn appendSliceAssumeCapacity(self: *Self, items: []const T) void {
const old_len = self.items.len;
const new_len = old_len + items.len;
assert(new_len <= self.capacity);
self.items.len = new_len;
@memcpy(self.items[old_len..][0..items.len], items);
}
/// 将条目切片追加到列表。
/// 绝不使元素指针失效。
/// 若列表的未用容量不足以容纳新增条目,则返回 `error.OutOfMemory`。
pub fn appendSliceBounded(self: *Self, items: []const T) error{OutOfMemory}!void {
if (self.capacity - self.items.len < items.len) return error.OutOfMemory;
return appendSliceAssumeCapacity(self, items);
}
/// 将元素切片追加到列表。必要时分配更多
/// 内存。仅应在改用 `appendSlice` 会
/// 导致编译错误时调用此函数。
/// 如果需要额外内存,会使元素指针失效。
pub fn appendUnalignedSlice(self: *Self, gpa: Allocator, items: []align(1) const T) Allocator.Error!void {
try self.ensureUnusedCapacity(gpa, items.len);
self.appendUnalignedSliceAssumeCapacity(items);
}
/// 将未对齐的元素切片追加到列表。
///
/// 仅应在调用 `appendSliceAssumeCapacity` 会
/// 导致编译错误时使用。
/// 绝不会使元素指针失效。
/// 断言列表能够容纳新增元素。
pub fn appendUnalignedSliceAssumeCapacity(self: *Self, items: []align(1) const T) void {
const old_len = self.items.len;
const new_len = old_len + items.len;
assert(new_len <= self.capacity);
self.items.len = new_len;
@memcpy(self.items[old_len..][0..items.len], items);
}
/// 向列表追加一个未对齐的元素切片。
///
/// 仅在 `appendSliceAssumeCapacity` 会导致
/// 编译错误时使用。
/// 绝不会使元素指针失效。
/// 若列表的未使用容量不足以容纳新增元素,返回
/// `error.OutOfMemory`。
pub fn appendUnalignedSliceBounded(self: *Self, items: []align(1) const T) error{OutOfMemory}!void {
if (self.capacity - self.items.len < items.len) return error.OutOfMemory;
return appendUnalignedSliceAssumeCapacity(self, items);
}
/// 将格式化字符串打印到此列表。
/// 如果需要额外内存,则使元素指针失效。
pub fn print(self: *Self, gpa: Allocator, comptime fmt: []const u8, args: anytype) error{OutOfMemory}!void {
comptime assert(T == u8);
try self.ensureUnusedCapacity(gpa, fmt.len);
var aw: std.Io.Writer.Allocating = .fromArrayList(gpa, self);
defer self.* = aw.toArrayList();
return aw.writer.print(fmt, args) catch |err| switch (err) {
error.WriteFailed => return error.OutOfMemory,
};
}
/// 将格式化字符串写入此列表。
/// 断言具有足够的写入容量。
/// 绝不会使元素指针失效。
pub fn printAssumeCapacity(self: *Self, comptime fmt: []const u8, args: anytype) void {
comptime assert(T == u8);
var w: std.Io.Writer = .fixed(self.unusedCapacitySlice());
w.print(fmt, args) catch unreachable;
self.items.len += w.end;
}
/// 将格式化字符串打印到此列表中。
/// 若写入需要额外容量,返回 error.OutOfMemory。
/// 绝不会使元素指针失效。
pub fn printBounded(self: *Self, comptime fmt: []const u8, args: anytype) error{OutOfMemory}!void {
comptime assert(T == u8);
var w: std.Io.Writer = .fixed(self.unusedCapacitySlice());
w.print(fmt, args) catch return error.OutOfMemory;
self.items.len += w.end;
}
/// 将某个值向列表追加 `n` 次。
/// 必要时分配更多内存。
/// 若需额外内存,使元素指针失效。
/// 此函数采用内联,使编译期已知的 `value` 参数若具有重复字节模式时,能够生成更优的 memset 代码。
///
pub inline fn appendNTimes(self: *Self, gpa: Allocator, value: T, n: usize) Allocator.Error!void {
const old_len = self.items.len;
try self.resize(gpa, try addOrOom(old_len, n));
@memset(self.items[old_len..self.items.len], value);
}
/// 向列表追加同一个值 `n` 次。
///
/// 绝不会使元素指针失效。
///
/// 此函数内联,使得编译期已知的 `value` 参数
/// 若具有重复字节模式,可生成更好的 memset 代码。
///
/// 断言列表能够容纳新增元素。
pub inline fn appendNTimesAssumeCapacity(self: *Self, value: T, n: usize) void {
const new_len = self.items.len + n;
assert(new_len <= self.capacity);
@memset(self.items.ptr[self.items.len..new_len], value);
self.items.len = new_len;
}
/// 将某个值向列表追加 `n` 次。
///
/// 绝不会使元素指针失效。
///
/// 此函数采用内联,使编译期已知的 `value` 参数若具有重复字节模式时,能够生成更优的 memset 代码。
///
/// 若列表未使用容量不足以容纳新增元素,返回 `error.OutOfMemory`。
///
///
pub inline fn appendNTimesBounded(self: *Self, value: T, n: usize) error{OutOfMemory}!void {
const new_len = self.items.len + n;
if (self.capacity < new_len) return error.OutOfMemory;
@memset(self.items.ptr[self.items.len..new_len], value);
self.items.len = new_len;
}
/// 将列表长度调整为 `new_len`。
/// 新增元素包含 `undefined`。
/// 若需要额外内存,则使元素指针失效。
pub fn resize(self: *Self, gpa: Allocator, new_len: usize) Allocator.Error!void {
try self.ensureTotalCapacity(gpa, new_len);
self.items.len = new_len;
}
/// 将已分配容量缩减为 `new_len`。
/// 可能使元素指针失效。
/// 断言新长度小于或等于原长度。
pub fn shrinkAndFree(self: *Self, gpa: Allocator, new_len: usize) void {
self.shrinkAndFreePrecise(gpa, new_len) catch |e| switch (e) {
error.OutOfMemory => {
// 没有问题,此时容量仍正确。
self.items.len = new_len;
return;
},
};
}
/// 将已分配容量减至 `new_len`。
/// 可能使元素指针失效。
/// 断言新长度小于或等于原长度。
/// 成功时,保证容量等于长度。
pub fn shrinkAndFreePrecise(self: *Self, gpa: Allocator, new_len: usize) Allocator.Error!void {
self.pointer_stability.assertUnlocked();
assert(new_len <= self.items.len);
if (@sizeOf(T) == 0) {
self.items.len = new_len;
return;
}
const old_memory = self.allocatedSlice();
if (gpa.remap(old_memory, new_len)) |new_items| {
self.capacity = new_items.len;
self.items = new_items;
return;
}
const new_memory = try gpa.alignedAlloc(T, alignment, new_len);
@memcpy(new_memory, self.items[0..new_len]);
gpa.free(old_memory);
self.items = new_memory;
self.capacity = new_memory.len;
}
/// 缩小容量,使其与长度一致。
/// 可能使元素指针失效。
/// 成功后可以安全调用 `toOwnedSliceAssert`。
pub fn shrinkToLen(self: *Self, gpa: Allocator) Allocator.Error!void {
try self.shrinkAndFreePrecise(gpa, self.items.len);
}
/// 缩小或扩大容量,使其等于长度加 1。
/// 可能使元素指针失效。
/// 成功后可以安全调用 `toOwnedSliceSentinelAssert`。
pub fn shrinkToLenSentinel(self: *Self, gpa: Allocator) Allocator.Error!void {
std.debug.assert(self.items.len <= self.capacity);
const required_len = self.items.len + 1;
switch (std.math.order(required_len, self.capacity)) {
.eq => return,
.gt => {
try self.ensureTotalCapacityPrecise(gpa, required_len);
},
.lt => {
self.items.len += 1;
defer self.items.len -= 1;
try self.shrinkToLen(gpa);
},
}
}
/// 将长度缩减为 `new_len`。
/// 使指向元素 `items[new_len..]` 的指针失效。
/// 容量保持不变。
/// 断言新长度小于或等于原长度。
pub fn shrinkRetainingCapacity(self: *Self, new_len: usize) void {
self.pointer_stability.assertUnlocked();
assert(new_len <= self.items.len);
@memset(self.items[new_len..], undefined);
self.items.len = new_len;
}
/// 将长度减为 0。
/// 使所有元素指针失效。
pub fn clearRetainingCapacity(self: *Self) void {
self.pointer_stability.assertUnlocked();
@memset(self.items, undefined);
self.items.len = 0;
}
/// 使所有元素指针失效。
pub fn clearAndFree(self: *Self, gpa: Allocator) void {
self.pointer_stability.assertUnlocked();
gpa.free(self.allocatedSlice());
self.items.len = 0;
self.capacity = 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.ensureTotalCapacityPrecise(gpa, growCapacity(new_capacity));
}
/// 若当前容量小于 `new_capacity`,此函数会
/// 修改数组,使其恰好能容纳 `new_capacity` 个元素。
/// 若需要额外内存,则使元素指针失效。
pub fn ensureTotalCapacityPrecise(self: *Self, gpa: Allocator, new_capacity: usize) Allocator.Error!void {
self.pointer_stability.assertUnlocked();
if (@sizeOf(T) == 0) {
self.capacity = math.maxInt(usize);
return;
}
if (self.capacity >= new_capacity) return;
// 这里通过尝试原地调整大小,
// 失败时分配新缓冲区并自行复制,
// 避免复制已分配但未使用的字节。
// 如果调用 realloc(),分配器实现会无意义地复制
// 额外容量中的内容。
const old_memory = self.allocatedSlice();
if (gpa.remap(old_memory, new_capacity)) |new_memory| {
self.items.ptr = new_memory.ptr;
self.capacity = new_memory.len;
} else {
const new_memory = try gpa.alignedAlloc(T, alignment, new_capacity);
@memcpy(new_memory[0..self.items.len], self.items);
gpa.free(old_memory);
self.items.ptr = new_memory.ptr;
self.capacity = new_memory.len;
}
}
/// 修改数组,使其至少还能额外容纳 `additional_count` 个项目。
/// 若需要额外内存,则使元素指针失效。
pub fn ensureUnusedCapacity(
self: *Self,
gpa: Allocator,
additional_count: usize,
) Allocator.Error!void {
return self.ensureTotalCapacity(gpa, try addOrOom(self.items.len, additional_count));
}
/// 将数组长度增加到已分配的完整容量。
/// 新元素的值为 `undefined`。
/// 绝不会使元素指针失效。
pub fn expandToCapacity(self: *Self) void {
self.items.len = self.capacity;
}
/// 将长度增加 1,返回指向新元素的指针。
/// 若需要额外内存,则使元素指针失效。
/// 对此列表的后续操作可能使返回的指针失效。
pub fn addOne(self: *Self, gpa: Allocator) Allocator.Error!*T {
// 此处绝不会溢出,因为 `self.items` 不可能占据整个地址空间
const newlen = self.items.len + 1;
try self.ensureTotalCapacity(gpa, newlen);
return self.addOneAssumeCapacity();
}
/// 将长度增加 1,返回指向新元素的指针。
/// 绝不会使元素指针失效。
/// 对列表的后续操作可能使返回的指针失效。
/// 断言列表可以容纳一个新增元素。
pub fn addOneAssumeCapacity(self: *Self) *T {
assert(self.items.len < self.capacity);
self.items.len += 1;
return &self.items[self.items.len - 1];
}
/// 将长度增加 1,并返回指向新条目的指针。
/// 绝不使元素指针失效。
/// 对此列表的后续操作可能使返回的指针失效。
/// 如果列表没有足够的未用容量来容纳新增条目,则返回 `error.OutOfMemory`。
pub fn addOneBounded(self: *Self) error{OutOfMemory}!*T {
if (self.capacity - self.items.len < 1) return error.OutOfMemory;
return addOneAssumeCapacity(self);
}
/// 调整数组大小,新增 `n` 个值为 `undefined` 的元素。
/// 若需额外内存,使元素指针失效。
/// 返回指向新分配元素的数组。
/// 返回的指针可能因后续对此列表的操作而失效。
pub fn addManyAsArray(self: *Self, gpa: Allocator, comptime n: usize) Allocator.Error!*[n]T {
const prev_len = self.items.len;
try self.resize(gpa, try addOrOom(self.items.len, n));
return self.items[prev_len..][0..n];
}
/// 调整数组大小,新增 `n` 个值为 `undefined` 的元素。
/// 返回指向新分配元素的数组。
/// 绝不会使元素指针失效。
/// 返回的指针可能因后续对此列表的操作而失效。
/// 断言列表能够容纳新增元素。
pub fn addManyAsArrayAssumeCapacity(self: *Self, comptime n: usize) *[n]T {
assert(self.items.len + n <= self.capacity);
const prev_len = self.items.len;
self.items.len += n;
return self.items[prev_len..][0..n];
}
/// 调整数组大小,新增 `n` 个值为 `undefined` 的元素。
/// 返回指向新分配元素的数组。
/// 绝不会使元素指针失效。
/// 返回的指针可能因后续对此列表的操作而失效。
/// 若列表未使用容量不足以容纳新增元素,返回 `error.OutOfMemory`。
///
pub fn addManyAsArrayBounded(self: *Self, comptime n: usize) error{OutOfMemory}!*[n]T {
if (self.capacity - self.items.len < n) return error.OutOfMemory;
return addManyAsArrayAssumeCapacity(self, n);
}
/// 调整数组大小,添加 `n` 个值为 `undefined` 的新元素。
/// 返回指向新分配元素的切片。
/// 后续对列表的操作可能使返回的指针失效。
/// 如果 `self.capacity` 不够大,则调整列表大小。
pub fn addManyAsSlice(self: *Self, gpa: Allocator, n: usize) Allocator.Error![]T {
const prev_len = self.items.len;
try self.resize(gpa, try addOrOom(self.items.len, n));
return self.items[prev_len..][0..n];
}
/// 调整数组大小,添加 `n` 个值为 `undefined` 的
/// 新元素,并返回指向这些新分配元素的切片。
/// 绝不使元素指针失效。
/// 对此列表的后续操作可能使返回的指针失效。
/// 断言列表可以容纳新增条目。
pub fn addManyAsSliceAssumeCapacity(self: *Self, n: usize) []T {
assert(self.items.len + n <= self.capacity);
const prev_len = self.items.len;
self.items.len += n;
return self.items[prev_len..][0..n];
}
/// 调整数组大小,添加 `n` 个值为 `undefined` 的
/// 新元素,并返回指向这些新分配元素的切片。
/// 绝不使元素指针失效。
/// 对此列表的后续操作可能使返回的指针失效。
/// 如果列表没有足够的未用容量来容纳新增条目,则返回
/// `error.OutOfMemory`。
pub fn addManyAsSliceBounded(self: *Self, n: usize) error{OutOfMemory}![]T {
if (self.capacity - self.items.len < n) return error.OutOfMemory;
return addManyAsSliceAssumeCapacity(self, n);
}
/// 移除并返回列表最后一个元素。
/// 列表为空则返回 `null`。
/// 指向最后一个元素的指针将失效。
pub fn pop(self: *Self) ?T {
if (self.items.len == 0) return null;
self.pointer_stability.assertUnlocked();
const val = self.items[self.items.len - 1];
self.items[self.items.len - 1] = undefined;
self.items.len -= 1;
return val;
}
/// 返回涵盖所有条目和额外容量的切片,额外容量的内存
/// 内容为 `undefined`。
/// 对此列表的后续操作可能使返回的指针失效。
pub fn allocatedSlice(self: Self) Slice {
return self.items.ptr[0..self.capacity];
}
/// 返回仅涵盖现有条目之后额外容量的切片。
/// 可用于直接写入 ArrayList。
/// 注意,此操作之后必须直接
/// 修改 `self.items.len`。
/// 对此列表的后续操作可能使返回的指针失效。
pub fn unusedCapacitySlice(self: Self) []T {
return self.allocatedSlice()[self.items.len..];
}
/// 已弃用
pub fn getLast(self: Self) T {
return self.items[self.items.len - 1];
}
/// 已弃用,请使用 `last`
pub const getLastOrNull = last;
/// 返回列表最后一个元素;列表
/// 为空则返回 `null`。
pub fn last(self: Self) ?T {
if (self.items.len == 0) return null;
return self.items[self.items.len - 1];
}
/// 返回指向列表最后一个元素的指针;列表为空时
/// 返回 `null`。
/// 对此列表的后续操作可能使返回的指针失效。
pub fn lastPtr(self: Self) ?*T {
if (self.items.len == 0) return null;
return &self.items[self.items.len - 1];
}
/// 需要增加内存时调用。返回大于
/// 最小值且按超线性规律增长的容量。
pub fn growCapacity(minimum: usize) usize {
if (@sizeOf(T) == 0) return math.maxInt(usize);
const init_capacity: comptime_int = @max(1, std.atomic.cache_line / @sizeOf(T));
return minimum +| (minimum / 2 + init_capacity);
}
};
}
/// 整数加法,溢出时返回 `error.OutOfMemory`。
fn addOrOom(a: usize, b: usize) error{OutOfMemory}!usize {
const result, const overflow = @addWithOverflow(a, b);
if (overflow != 0) return error.OutOfMemory;
return result;
}
test "init" {
{
var list = Managed(i32).init(testing.allocator);
defer list.deinit();
try testing.expect(list.items.len == 0);
try testing.expect(list.capacity == 0);
}
{
const list: ArrayList(i32) = .empty;
try testing.expect(list.items.len == 0);
try testing.expect(list.capacity == 0);
}
}
test "initCapacity" {
const a = testing.allocator;
{
var list = try Managed(i8).initCapacity(a, 200);
defer list.deinit();
try testing.expect(list.items.len == 0);
try testing.expect(list.capacity >= 200);
}
{
var list = try ArrayList(i8).initCapacity(a, 200);
defer list.deinit(a);
try testing.expect(list.items.len == 0);
try testing.expect(list.capacity >= 200);
}
}
test "clone" {
const a = testing.allocator;
{
var array = Managed(i32).init(a);
try array.append(-1);
try array.append(3);
try array.append(5);
const cloned = try array.clone();
defer cloned.deinit();
try testing.expectEqualSlices(i32, array.items, cloned.items);
try testing.expectEqual(array.allocator, cloned.allocator);
try testing.expect(cloned.capacity >= array.capacity);
array.deinit();
try testing.expectEqual(@as(i32, -1), cloned.items[0]);
try testing.expectEqual(@as(i32, 3), cloned.items[1]);
try testing.expectEqual(@as(i32, 5), cloned.items[2]);
}
{
var array: ArrayList(i32) = .empty;
try array.append(a, -1);
try array.append(a, 3);
try array.append(a, 5);
var cloned = try array.clone(a);
defer cloned.deinit(a);
try testing.expectEqualSlices(i32, array.items, cloned.items);
try testing.expect(cloned.capacity >= array.capacity);
array.deinit(a);
try testing.expectEqual(@as(i32, -1), cloned.items[0]);
try testing.expectEqual(@as(i32, 3), cloned.items[1]);
try testing.expectEqual(@as(i32, 5), cloned.items[2]);
}
}
test "basic" {
const a = testing.allocator;
{
var list = Managed(i32).init(a);
defer list.deinit();
{
var i: usize = 0;
while (i < 10) : (i += 1) {
list.append(@as(i32, @intCast(i + 1))) catch unreachable;
}
}
{
var i: usize = 0;
while (i < 10) : (i += 1) {
try testing.expect(list.items[i] == @as(i32, @intCast(i + 1)));
}
}
for (list.items, 0..) |v, i| {
try testing.expect(v == @as(i32, @intCast(i + 1)));
}
try testing.expect(list.pop() == 10);
try testing.expect(list.items.len == 9);
list.appendSlice(&[_]i32{ 1, 2, 3 }) catch unreachable;
try testing.expect(list.items.len == 12);
try testing.expect(list.pop() == 3);
try testing.expect(list.pop() == 2);
try testing.expect(list.pop() == 1);
try testing.expect(list.items.len == 9);
var unaligned: [3]i32 align(1) = [_]i32{ 4, 5, 6 };
list.appendUnalignedSlice(&unaligned) catch unreachable;
try testing.expect(list.items.len == 12);
try testing.expect(list.pop() == 6);
try testing.expect(list.pop() == 5);
try testing.expect(list.pop() == 4);
try testing.expect(list.items.len == 9);
list.appendSlice(&[_]i32{}) catch unreachable;
try testing.expect(list.items.len == 9);
// 只能设置索引小于 self.items.len 的位置
list.items[7] = 33;
list.items[8] = 42;
try testing.expect(list.pop() == 42);
try testing.expect(list.pop() == 33);
}
{
var list: ArrayList(i32) = .empty;
defer list.deinit(a);
{
var i: usize = 0;
while (i < 10) : (i += 1) {
list.append(a, @as(i32, @intCast(i + 1))) catch unreachable;
}
}
{
var i: usize = 0;
while (i < 10) : (i += 1) {
try testing.expect(list.items[i] == @as(i32, @intCast(i + 1)));
}
}
for (list.items, 0..) |v, i| {
try testing.expect(v == @as(i32, @intCast(i + 1)));
}
try testing.expect(list.pop() == 10);
try testing.expect(list.items.len == 9);
list.appendSlice(a, &[_]i32{ 1, 2, 3 }) catch unreachable;
try testing.expect(list.items.len == 12);
try testing.expect(list.pop() == 3);
try testing.expect(list.pop() == 2);
try testing.expect(list.pop() == 1);
try testing.expect(list.items.len == 9);
var unaligned: [3]i32 align(1) = [_]i32{ 4, 5, 6 };
list.appendUnalignedSlice(a, &unaligned) catch unreachable;
try testing.expect(list.items.len == 12);
try testing.expect(list.pop() == 6);
try testing.expect(list.pop() == 5);
try testing.expect(list.pop() == 4);
try testing.expect(list.items.len == 9);
list.appendSlice(a, &[_]i32{}) catch unreachable;
try testing.expect(list.items.len == 9);
// 只能设置索引小于 self.items.len 的位置
list.items[7] = 33;
list.items[8] = 42;
try testing.expect(list.pop() == 42);
try testing.expect(list.pop() == 33);
}
}
test "appendNTimes" {
const a = testing.allocator;
{
var list = Managed(i32).init(a);
defer list.deinit();
try list.appendNTimes(2, 10);
try testing.expectEqual(@as(usize, 10), list.items.len);
for (list.items) |element| {
try testing.expectEqual(@as(i32, 2), element);
}
}
{
var list: ArrayList(i32) = .empty;
defer list.deinit(a);
try list.appendNTimes(a, 2, 10);
try testing.expectEqual(@as(usize, 10), list.items.len);
for (list.items) |element| {
try testing.expectEqual(@as(i32, 2), element);
}
}
}
test "appendNTimes with failing allocator" {
const a = testing.failing_allocator;
{
var list = Managed(i32).init(a);
defer list.deinit();
try testing.expectError(error.OutOfMemory, list.appendNTimes(2, 10));
}
{
var list: ArrayList(i32) = .empty;
defer list.deinit(a);
try testing.expectError(error.OutOfMemory, list.appendNTimes(a, 2, 10));
}
}
test "orderedRemove" {
const a = testing.allocator;
{
var list = Managed(i32).init(a);
defer list.deinit();
try list.append(1);
try list.append(2);
try list.append(3);
try list.append(4);
try list.append(5);
try list.append(6);
try list.append(7);
// 从中间移除
try testing.expectEqual(@as(i32, 4), list.orderedRemove(3));
try testing.expectEqual(@as(i32, 5), list.items[3]);
try testing.expectEqual(@as(usize, 6), list.items.len);
// 从末尾移除
try testing.expectEqual(@as(i32, 7), list.orderedRemove(5));
try testing.expectEqual(@as(usize, 5), list.items.len);
// 从前端移除
try testing.expectEqual(@as(i32, 1), list.orderedRemove(0));
try testing.expectEqual(@as(i32, 2), list.items[0]);
try testing.expectEqual(@as(usize, 4), list.items.len);
}
{
var list: ArrayList(i32) = .empty;
defer list.deinit(a);
try list.append(a, 1);
try list.append(a, 2);
try list.append(a, 3);
try list.append(a, 4);
try list.append(a, 5);
try list.append(a, 6);
try list.append(a, 7);
// 从中间移除
try testing.expectEqual(@as(i32, 4), list.orderedRemove(3));
try testing.expectEqual(@as(i32, 5), list.items[3]);
try testing.expectEqual(@as(usize, 6), list.items.len);
// 从末尾移除
try testing.expectEqual(@as(i32, 7), list.orderedRemove(5));
try testing.expectEqual(@as(usize, 5), list.items.len);
// 从前端移除
try testing.expectEqual(@as(i32, 1), list.orderedRemove(0));
try testing.expectEqual(@as(i32, 2), list.items[0]);
try testing.expectEqual(@as(usize, 4), list.items.len);
}
{
// 移除末项
var list = Managed(i32).init(a);
defer list.deinit();
try list.append(1);
try testing.expectEqual(@as(i32, 1), list.orderedRemove(0));
try testing.expectEqual(@as(usize, 0), list.items.len);
}
{
// 移除末项
var list: ArrayList(i32) = .empty;
defer list.deinit(a);
try list.append(a, 1);
try testing.expectEqual(@as(i32, 1), list.orderedRemove(0));
try testing.expectEqual(@as(usize, 0), list.items.len);
}
}
test "swapRemove" {
const a = testing.allocator;
{
var list = Managed(i32).init(a);
defer list.deinit();
try list.append(1);
try list.append(2);
try list.append(3);
try list.append(4);
try list.append(5);
try list.append(6);
try list.append(7);
// 从中间移除
try testing.expect(list.swapRemove(3) == 4);
try testing.expect(list.items[3] == 7);
try testing.expect(list.items.len == 6);
// 从末尾移除
try testing.expect(list.swapRemove(5) == 6);
try testing.expect(list.items.len == 5);
// 从前端移除
try testing.expect(list.swapRemove(0) == 1);
try testing.expect(list.items[0] == 5);
try testing.expect(list.items.len == 4);
}
{
var list: ArrayList(i32) = .empty;
defer list.deinit(a);
try list.append(a, 1);
try list.append(a, 2);
try list.append(a, 3);
try list.append(a, 4);
try list.append(a, 5);
try list.append(a, 6);
try list.append(a, 7);
// 从中间移除
try testing.expect(list.swapRemove(3) == 4);
try testing.expect(list.items[3] == 7);
try testing.expect(list.items.len == 6);
// 从末尾移除
try testing.expect(list.swapRemove(5) == 6);
try testing.expect(list.items.len == 5);
// 从前端移除
try testing.expect(list.swapRemove(0) == 1);
try testing.expect(list.items[0] == 5);
try testing.expect(list.items.len == 4);
}
}
test "insert" {
const a = testing.allocator;
{
var list = Managed(i32).init(a);
defer list.deinit();
try list.insert(0, 1);
try list.append(2);
try list.insert(2, 3);
try list.insert(0, 5);
try testing.expect(list.items[0] == 5);
try testing.expect(list.items[1] == 1);
try testing.expect(list.items[2] == 2);
try testing.expect(list.items[3] == 3);
}
{
var list: ArrayList(i32) = .empty;
defer list.deinit(a);
try list.insert(a, 0, 1);
try list.append(a, 2);
try list.insert(a, 2, 3);
try list.insert(a, 0, 5);
try testing.expect(list.items[0] == 5);
try testing.expect(list.items[1] == 1);
try testing.expect(list.items[2] == 2);
try testing.expect(list.items[3] == 3);
}
{
var list: ArrayList(struct {}) = .empty;
defer list.deinit(a);
try list.insert(a, 0, .{});
try list.append(a, .{});
try testing.expect(list.items.len == 2);
}
}
test "insertSlice" {
const a = testing.allocator;
{
var list = Managed(i32).init(a);
defer list.deinit();
try list.append(1);
try list.append(2);
try list.append(3);
try list.append(4);
try list.insertSlice(1, &[_]i32{ 9, 8 });
try testing.expect(list.items[0] == 1);
try testing.expect(list.items[1] == 9);
try testing.expect(list.items[2] == 8);
try testing.expect(list.items[3] == 2);
try testing.expect(list.items[4] == 3);
try testing.expect(list.items[5] == 4);
const items = [_]i32{1};
try list.insertSlice(0, items[0..0]);
try testing.expect(list.items.len == 6);
try testing.expect(list.items[0] == 1);
}
{
var list: ArrayList(i32) = .empty;
defer list.deinit(a);
try list.append(a, 1);
try list.append(a, 2);
try list.append(a, 3);
try list.append(a, 4);
try list.insertSlice(a, 1, &[_]i32{ 9, 8 });
try testing.expect(list.items[0] == 1);
try testing.expect(list.items[1] == 9);
try testing.expect(list.items[2] == 8);
try testing.expect(list.items[3] == 2);
try testing.expect(list.items[4] == 3);
try testing.expect(list.items[5] == 4);
const items = [_]i32{1};
try list.insertSlice(a, 0, items[0..0]);
try testing.expect(list.items.len == 6);
try testing.expect(list.items[0] == 1);
}
}
test "Managed.replaceRange" {
const a = testing.allocator;
{
var list = Managed(i32).init(a);
defer list.deinit();
try list.appendSlice(&[_]i32{ 1, 2, 3, 4, 5 });
try list.replaceRange(1, 0, &[_]i32{ 0, 0, 0 });
try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0, 2, 3, 4, 5 }, list.items);
}
{
var list = Managed(i32).init(a);
defer list.deinit();
try list.appendSlice(&[_]i32{ 1, 2, 3, 4, 5 });
try list.replaceRange(1, 1, &[_]i32{ 0, 0, 0 });
try testing.expectEqualSlices(
i32,
&[_]i32{ 1, 0, 0, 0, 3, 4, 5 },
list.items,
);
}
{
var list = Managed(i32).init(a);
defer list.deinit();
try list.appendSlice(&[_]i32{ 1, 2, 3, 4, 5 });
try list.replaceRange(1, 2, &[_]i32{ 0, 0, 0 });
try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0, 4, 5 }, list.items);
}
{
var list = Managed(i32).init(a);
defer list.deinit();
try list.appendSlice(&[_]i32{ 1, 2, 3, 4, 5 });
try list.replaceRange(1, 3, &[_]i32{ 0, 0, 0 });
try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0, 5 }, list.items);
}
{
var list = Managed(i32).init(a);
defer list.deinit();
try list.appendSlice(&[_]i32{ 1, 2, 3, 4, 5 });
try list.replaceRange(1, 4, &[_]i32{ 0, 0, 0 });
try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0 }, list.items);
}
}
test "Managed.replaceRangeAssumeCapacity" {
const a = testing.allocator;
{
var list = Managed(i32).init(a);
defer list.deinit();
try list.appendSlice(&[_]i32{ 1, 2, 3, 4, 5 });
list.replaceRangeAssumeCapacity(1, 0, &[_]i32{ 0, 0, 0 });
try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0, 2, 3, 4, 5 }, list.items);
}
{
var list = Managed(i32).init(a);
defer list.deinit();
try list.appendSlice(&[_]i32{ 1, 2, 3, 4, 5 });
list.replaceRangeAssumeCapacity(1, 1, &[_]i32{ 0, 0, 0 });
try testing.expectEqualSlices(
i32,
&[_]i32{ 1, 0, 0, 0, 3, 4, 5 },
list.items,
);
}
{
var list = Managed(i32).init(a);
defer list.deinit();
try list.appendSlice(&[_]i32{ 1, 2, 3, 4, 5 });
list.replaceRangeAssumeCapacity(1, 2, &[_]i32{ 0, 0, 0 });
try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0, 4, 5 }, list.items);
}
{
var list = Managed(i32).init(a);
defer list.deinit();
try list.appendSlice(&[_]i32{ 1, 2, 3, 4, 5 });
list.replaceRangeAssumeCapacity(1, 3, &[_]i32{ 0, 0, 0 });
try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0, 5 }, list.items);
}
{
var list = Managed(i32).init(a);
defer list.deinit();
try list.appendSlice(&[_]i32{ 1, 2, 3, 4, 5 });
list.replaceRangeAssumeCapacity(1, 4, &[_]i32{ 0, 0, 0 });
try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0 }, list.items);
}
}
test "ArrayList.replaceRange" {
const a = testing.allocator;
{
var list: ArrayList(i32) = .empty;
defer list.deinit(a);
try list.appendSlice(a, &[_]i32{ 1, 2, 3, 4, 5 });
try list.replaceRange(a, 1, 0, &[_]i32{ 0, 0, 0 });
try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0, 2, 3, 4, 5 }, list.items);
}
{
var list: ArrayList(i32) = .empty;
defer list.deinit(a);
try list.appendSlice(a, &[_]i32{ 1, 2, 3, 4, 5 });
try list.replaceRange(a, 1, 1, &[_]i32{ 0, 0, 0 });
try testing.expectEqualSlices(
i32,
&[_]i32{ 1, 0, 0, 0, 3, 4, 5 },
list.items,
);
}
{
var list: ArrayList(i32) = .empty;
defer list.deinit(a);
try list.appendSlice(a, &[_]i32{ 1, 2, 3, 4, 5 });
try list.replaceRange(a, 1, 2, &[_]i32{ 0, 0, 0 });
try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0, 4, 5 }, list.items);
}
{
var list: ArrayList(i32) = .empty;
defer list.deinit(a);
try list.appendSlice(a, &[_]i32{ 1, 2, 3, 4, 5 });
try list.replaceRange(a, 1, 3, &[_]i32{ 0, 0, 0 });
try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0, 5 }, list.items);
}
{
var list: ArrayList(i32) = .empty;
defer list.deinit(a);
try list.appendSlice(a, &[_]i32{ 1, 2, 3, 4, 5 });
try list.replaceRange(a, 1, 4, &[_]i32{ 0, 0, 0 });
try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0 }, list.items);
}
}
test "ArrayList.replaceRangeAssumeCapacity" {
const a = testing.allocator;
{
var list: ArrayList(i32) = .empty;
defer list.deinit(a);
try list.appendSlice(a, &[_]i32{ 1, 2, 3, 4, 5 });
list.replaceRangeAssumeCapacity(1, 0, &[_]i32{ 0, 0, 0 });
try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0, 2, 3, 4, 5 }, list.items);
}
{
var list: ArrayList(i32) = .empty;
defer list.deinit(a);
try list.appendSlice(a, &[_]i32{ 1, 2, 3, 4, 5 });
list.replaceRangeAssumeCapacity(1, 1, &[_]i32{ 0, 0, 0 });
try testing.expectEqualSlices(
i32,
&[_]i32{ 1, 0, 0, 0, 3, 4, 5 },
list.items,
);
}
{
var list: ArrayList(i32) = .empty;
defer list.deinit(a);
try list.appendSlice(a, &[_]i32{ 1, 2, 3, 4, 5 });
list.replaceRangeAssumeCapacity(1, 2, &[_]i32{ 0, 0, 0 });
try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0, 4, 5 }, list.items);
}
{
var list: ArrayList(i32) = .empty;
defer list.deinit(a);
try list.appendSlice(a, &[_]i32{ 1, 2, 3, 4, 5 });
list.replaceRangeAssumeCapacity(1, 3, &[_]i32{ 0, 0, 0 });
try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0, 5 }, list.items);
}
{
var list: ArrayList(i32) = .empty;
defer list.deinit(a);
try list.appendSlice(a, &[_]i32{ 1, 2, 3, 4, 5 });
list.replaceRangeAssumeCapacity(1, 4, &[_]i32{ 0, 0, 0 });
try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0 }, list.items);
}
}
const Item = struct {
integer: i32,
sub_items: Managed(Item),
};
const ItemUnmanaged = struct {
integer: i32,
sub_items: ArrayList(ItemUnmanaged),
};
test "Managed(T) of struct T" {
const a = std.testing.allocator;
{
var root = Item{ .integer = 1, .sub_items = .init(a) };
defer root.sub_items.deinit();
try root.sub_items.append(Item{ .integer = 42, .sub_items = .init(a) });
try testing.expect(root.sub_items.items[0].integer == 42);
}
{
var root = ItemUnmanaged{ .integer = 1, .sub_items = .empty };
defer root.sub_items.deinit(a);
try root.sub_items.append(a, ItemUnmanaged{ .integer = 42, .sub_items = .empty });
try testing.expect(root.sub_items.items[0].integer == 42);
}
}
test "shrink still sets length when resizing is disabled" {
var failing_allocator = testing.FailingAllocator.init(testing.allocator, .{ .resize_fail_index = 0 });
const a = failing_allocator.allocator();
{
var list = Managed(i32).init(a);
defer list.deinit();
try list.append(1);
try list.append(2);
try list.append(3);
list.shrinkAndFree(1);
try testing.expect(list.items.len == 1);
}
{
var list: ArrayList(i32) = .empty;
defer list.deinit(a);
try list.append(a, 1);
try list.append(a, 2);
try list.append(a, 3);
list.shrinkAndFree(a, 1);
try testing.expect(list.items.len == 1);
}
}
test "shrinkAndFree with a copy" {
var failing_allocator = testing.FailingAllocator.init(testing.allocator, .{ .resize_fail_index = 0 });
const a = failing_allocator.allocator();
var list = Managed(i32).init(a);
defer list.deinit();
try list.appendNTimes(3, 16);
list.shrinkAndFree(4);
try testing.expect(mem.eql(i32, list.items, &.{ 3, 3, 3, 3 }));
}
test "shrinkAndFreePrecise without resize succeeds" {
var failing_allocator = testing.FailingAllocator.init(testing.allocator, .{ .resize_fail_index = 0 });
const a = failing_allocator.allocator();
var list: Aligned(i32, null) = .empty;
defer list.deinit(a);
try list.appendNTimes(a, 3, 16);
try list.shrinkAndFreePrecise(a, 4);
try testing.expectEqualSlices(i32, &.{ 3, 3, 3, 3 }, list.items);
try testing.expectEqual(list.items.len, list.capacity);
}
test "shrinkAndFreePrecise without resize and no copy failes" {
var failing_allocator = testing.FailingAllocator.init(testing.allocator, .{ .resize_fail_index = 0, .fail_index = 1 });
const a = failing_allocator.allocator();
var list: Aligned(i32, null) = .empty;
defer list.deinit(a);
try list.appendNTimes(a, 3, 16);
try std.testing.expectError(error.OutOfMemory, list.shrinkAndFreePrecise(a, 4));
}
test "addManyAsArray" {
const a = std.testing.allocator;
{
var list = Managed(u8).init(a);
defer list.deinit();
(try list.addManyAsArray(4)).* = "aoeu".*;
try list.ensureTotalCapacity(8);
list.addManyAsArrayAssumeCapacity(4).* = "asdf".*;
try testing.expectEqualSlices(u8, list.items, "aoeuasdf");
}
{
var list: ArrayList(u8) = .empty;
defer list.deinit(a);
(try list.addManyAsArray(a, 4)).* = "aoeu".*;
try list.ensureTotalCapacity(a, 8);
list.addManyAsArrayAssumeCapacity(4).* = "asdf".*;
try testing.expectEqualSlices(u8, list.items, "aoeuasdf");
}
}
test "growing memory preserves contents" {
// 每次插入后缩小列表,确保
// 下次操作触发内存增长。
const a = std.testing.allocator;
{
var list = Managed(u8).init(a);
defer list.deinit();
(try list.addManyAsArray(4)).* = "abcd".*;
list.shrinkAndFree(4);
try list.appendSlice("efgh");
try testing.expectEqualSlices(u8, list.items, "abcdefgh");
list.shrinkAndFree(8);
try list.insertSlice(4, "ijkl");
try testing.expectEqualSlices(u8, list.items, "abcdijklefgh");
}
{
var list: ArrayList(u8) = .empty;
defer list.deinit(a);
(try list.addManyAsArray(a, 4)).* = "abcd".*;
list.shrinkAndFree(a, 4);
try list.appendSlice(a, "efgh");
try testing.expectEqualSlices(u8, list.items, "abcdefgh");
list.shrinkAndFree(a, 8);
try list.insertSlice(a, 4, "ijkl");
try testing.expectEqualSlices(u8, list.items, "abcdijklefgh");
}
}
test "fromOwnedSlice" {
const a = testing.allocator;
{
var orig_list = Managed(u8).init(a);
defer orig_list.deinit();
try orig_list.appendSlice("foobar");
const slice = try orig_list.toOwnedSlice();
var list = Managed(u8).fromOwnedSlice(a, slice);
defer list.deinit();
try testing.expectEqualStrings(list.items, "foobar");
}
{
var list = Managed(u8).init(a);
defer list.deinit();
try list.appendSlice("foobar");
const slice = try list.toOwnedSlice();
var unmanaged = ArrayList(u8).fromOwnedSlice(slice);
defer unmanaged.deinit(a);
try testing.expectEqualStrings(unmanaged.items, "foobar");
}
}
test "fromOwnedSliceSentinel" {
const a = testing.allocator;
{
var orig_list = Managed(u8).init(a);
defer orig_list.deinit();
try orig_list.appendSlice("foobar");
const sentinel_slice = try orig_list.toOwnedSliceSentinel(0);
var list = Managed(u8).fromOwnedSliceSentinel(a, 0, sentinel_slice);
defer list.deinit();
try testing.expectEqualStrings(list.items, "foobar");
}
{
var list = Managed(u8).init(a);
defer list.deinit();
try list.appendSlice("foobar");
const sentinel_slice = try list.toOwnedSliceSentinel(0);
var unmanaged = ArrayList(u8).fromOwnedSliceSentinel(0, sentinel_slice);
defer unmanaged.deinit(a);
try testing.expectEqualStrings(unmanaged.items, "foobar");
}
}
test "toOwnedSliceSentinel" {
const a = testing.allocator;
{
var list = Managed(u8).init(a);
defer list.deinit();
try list.appendSlice("foobar");
const result = try list.toOwnedSliceSentinel(0);
defer a.free(result);
try testing.expectEqualStrings(result, mem.sliceTo(result.ptr, 0));
}
{
var list: ArrayList(u8) = .empty;
defer list.deinit(a);
try list.appendSlice(a, "foobar");
const result = try list.toOwnedSliceSentinel(a, 0);
defer a.free(result);
try testing.expectEqualStrings(result, mem.sliceTo(result.ptr, 0));
}
}
test "toOwnedSliceAssert" {
var failing_allocator: testing.FailingAllocator = .init(testing.allocator, .{
.fail_index = 2,
});
const a = failing_allocator.allocator();
var list: Aligned(u8, null) = try .initCapacity(a, 6); // 首次分配
list.appendSliceAssumeCapacity(&.{ 1, 2, 3 });
try list.shrinkToLen(a); // 首次调整大小
try std.testing.expectEqual(list.items.len, list.capacity);
try list.shrinkToLen(a); // 不分配也不调整大小
const slice = list.toOwnedSliceAssert();
defer a.free(slice);
try std.testing.expectEqual(Aligned(u8, null).empty, list);
try std.testing.expectEqualSlices(u8, &.{ 1, 2, 3 }, slice);
}
test "toOwnedSliceSentinelAssert" {
const a = testing.allocator;
var list: Aligned(u8, null) = try .initCapacity(a, 6);
list.appendSliceAssumeCapacity(&.{ 1, 2, 3 });
// shrinkToLenSentinel 会缩小数组
try list.shrinkToLenSentinel(a);
// shrinkToLenSentinel 扩展数组
try list.shrinkToLen(a);
try list.shrinkToLenSentinel(a);
const slice = list.toOwnedSliceSentinelAssert(10);
defer a.free(slice);
try std.testing.expectEqualSentinel(u8, 10, &.{ 1, 2, 3 }, slice);
}
test "accepts unaligned slices" {
const a = testing.allocator;
{
var list = AlignedManaged(u8, .@"8").init(a);
defer list.deinit();
try list.appendSlice(&.{ 0, 1, 2, 3 });
try list.insertSlice(2, &.{ 4, 5, 6, 7 });
try list.replaceRange(1, 3, &.{ 8, 9 });
try testing.expectEqualSlices(u8, list.items, &.{ 0, 8, 9, 6, 7, 2, 3 });
}
{
var list: Aligned(u8, .@"8") = .empty;
defer list.deinit(a);
try list.appendSlice(a, &.{ 0, 1, 2, 3 });
try list.insertSlice(a, 2, &.{ 4, 5, 6, 7 });
try list.replaceRange(a, 1, 3, &.{ 8, 9 });
try testing.expectEqualSlices(u8, list.items, &.{ 0, 8, 9, 6, 7, 2, 3 });
}
}
test "Managed(u0)" {
// 元素类型大小为零的 Managed 不应需要分配内存
const a = testing.failing_allocator;
var list = Managed(u0).init(a);
defer list.deinit();
try list.append(0);
try list.append(0);
try list.append(0);
try testing.expectEqual(list.items.len, 3);
var count: usize = 0;
for (list.items) |x| {
try testing.expectEqual(x, 0);
count += 1;
}
try testing.expectEqual(count, 3);
const ownedSlice = try list.toOwnedSlice();
defer a.free(ownedSlice);
try testing.expectEqualSlices(u0, ownedSlice, &.{ 0, 0, 0 });
}
test "Managed(?u32).pop()" {
const a = testing.allocator;
var list = Managed(?u32).init(a);
defer list.deinit();
try list.append(null);
try list.append(1);
try list.append(2);
try testing.expectEqual(list.items.len, 3);
try testing.expect(list.pop().? == @as(u32, 2));
try testing.expect(list.pop().? == @as(u32, 1));
try testing.expect(list.pop().? == null);
try testing.expect(list.pop() == null);
}
test "last" {
const a = testing.allocator;
var list: ArrayList(u32) = .empty;
defer list.deinit(a);
try testing.expectEqual(list.last(), null);
try list.append(a, 2);
try testing.expectEqual(list.last().?, 2);
}
test "return OutOfMemory when capacity would exceed maximum usize integer value" {
const a = testing.allocator;
const new_item: u32 = 42;
const items = &.{ 42, 43 };
{
var list: ArrayList(u32) = .{
.items = undefined,
.capacity = math.maxInt(usize) - 1,
.pointer_stability = .{},
};
list.items.len = math.maxInt(usize) - 1;
try testing.expectError(error.OutOfMemory, list.appendSlice(a, items));
try testing.expectError(error.OutOfMemory, list.appendNTimes(a, new_item, 2));
try testing.expectError(error.OutOfMemory, list.appendUnalignedSlice(a, &.{ new_item, new_item }));
try testing.expectError(error.OutOfMemory, list.addManyAt(a, 0, 2));
try testing.expectError(error.OutOfMemory, list.addManyAsArray(a, 2));
try testing.expectError(error.OutOfMemory, list.addManyAsSlice(a, 2));
try testing.expectError(error.OutOfMemory, list.insertSlice(a, 0, items));
try testing.expectError(error.OutOfMemory, list.ensureUnusedCapacity(a, 2));
}
{
var list: Managed(u32) = .{
.items = undefined,
.capacity = math.maxInt(usize) - 1,
.allocator = a,
.pointer_stability = .{},
};
list.items.len = math.maxInt(usize) - 1;
try testing.expectError(error.OutOfMemory, list.appendSlice(items));
try testing.expectError(error.OutOfMemory, list.appendNTimes(new_item, 2));
try testing.expectError(error.OutOfMemory, list.appendUnalignedSlice(&.{ new_item, new_item }));
try testing.expectError(error.OutOfMemory, list.addManyAt(0, 2));
try testing.expectError(error.OutOfMemory, list.addManyAsArray(2));
try testing.expectError(error.OutOfMemory, list.addManyAsSlice(2));
try testing.expectError(error.OutOfMemory, list.insertSlice(0, items));
try testing.expectError(error.OutOfMemory, list.ensureUnusedCapacity(2));
}
}
test "orderedRemoveMany" {
const gpa = testing.allocator;
var list: Aligned(usize, null) = .empty;
defer list.deinit(gpa);
for (0..10) |n| {
try list.append(gpa, n);
}
list.orderedRemoveMany(&.{ 1, 5, 5, 7, 9 });
try testing.expectEqualSlices(usize, &.{ 0, 2, 3, 4, 6, 8 }, list.items);
list.orderedRemoveMany(&.{0});
try testing.expectEqualSlices(usize, &.{ 2, 3, 4, 6, 8 }, list.items);
list.orderedRemoveMany(&.{});
try testing.expectEqualSlices(usize, &.{ 2, 3, 4, 6, 8 }, list.items);
list.orderedRemoveMany(&.{ 1, 2, 3, 4 });
try testing.expectEqualSlices(usize, &.{2}, list.items);
list.orderedRemoveMany(&.{0});
try testing.expectEqualSlices(usize, &.{}, list.items);
}
test "insertSlice*" {
var buf: [10]u8 = undefined;
var list: ArrayList(u8) = .initBuffer(&buf);
list.appendSliceAssumeCapacity("abcd");
list.insertSliceAssumeCapacity(2, "ef");
try testing.expectEqualStrings("abefcd", list.items);
try list.insertSliceBounded(4, "gh");
try testing.expectEqualStrings("abefghcd", list.items);
try testing.expectError(error.OutOfMemory, list.insertSliceBounded(6, "ijkl"));
try testing.expectEqualStrings("abefghcd", list.items); // 确保返回 error.OutOfMemory 前没有任何元素被更改
list.insertSliceAssumeCapacity(6, "ij");
try testing.expectEqualStrings("abefghijcd", list.items);
}