跳转到内容
标准库Zig 0.17.1官方原文
源码std/deque.zig

第 1 行

std.deque.addOrOom

函数

第 368 行

整数加法,溢出时返回 error.OutOfMemory。

fn addOrOom(a: usize, b: usize) error{OutOfMemory}!usize

参数

a: usize
b: usize

错误

OutOfMemory

std.deque.Allocator

别名

第 3 行

别名目标 std.mem.Allocator

std.deque.assert

别名

第 2 行

别名目标 std.debug.assert

std.deque.Deque

类型函数

第 8 行

连续、可增长的双端队列。

从队列任一端压入/弹出元素的时间复杂度均为 O(1)。

pub fn Deque(comptime T: type) type

参数

T: type

字段

buffer: []T

环形缓冲区。

head: usize

逻辑双端队列中第一项在 buffer 中的存储索引。

len: usize

逻辑双端队列中存储的元素数量。

std.deque.Deque.at

函数

第 291 行

返回双端队列中给定索引处的元素。

队列首个元素的索引为 0。

断言索引未越界。

pub fn at(deque: *const Self, index: usize) T

参数

deque: *const Self
index: usize

std.deque.Deque.atPtr

函数

第 301 行

返回指向双端队列中给定索引处元素的指针。

队列中第一个元素的索引为 0。

断言索引未越界。

pub fn atPtr(deque: *const Self, index: usize) *T

参数

deque: *const Self
index: usize

std.deque.Deque.back

函数

第 275 行

返回双端队列的最后一项;若为空,则返回 null。

pub fn back(deque: *const Self) ?T

参数

deque: *const Self

std.deque.Deque.backPtr

函数

第 281 行

返回双端队列的最后一项;若为空,则返回 null。

pub fn backPtr(deque: *const Self) ?*T

参数

deque: *const Self

std.deque.Deque.bufferIndex

函数

第 354 行

返回逻辑双端队列中给定索引处的元素 在 buffer 中的存储索引。

fn bufferIndex(deque: *const Self, index: usize) usize

参数

deque: *const Self
index: usize

std.deque.Deque.deinit

函数

第 49 行

释放全部已分配内存。

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

参数

deque: *Self
gpa: Allocator

std.deque.Deque.empty

常量

第 20 行

不包含元素的 Deque。

Self

std.deque.Deque.ensureTotalCapacity

函数

第 57 行

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

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

参数

deque: *Self
gpa: Allocator
new_capacity: usize

错误

OutOfMemory

std.deque.Deque.ensureTotalCapacityPrecise

函数

第 65 行

若当前容量小于 new_capacity,此函数会 修改双端队列,使其恰好能容纳 new_capacity 个元素。 若需要额外内存,则使元素指针失效。

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

参数

deque: *Self
gpa: Allocator
new_capacity: usize

错误

OutOfMemory

std.deque.Deque.ensureUnusedCapacity

函数

第 104 行

修改双端队列,使其至少还能容纳 additional_count 个额外元素。 若需要额外内存,则使元素指针失效。

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

参数

deque: *Self
gpa: Allocator
additional_count: usize

错误

OutOfMemory

std.deque.Deque.front

函数

第 263 行

返回双端队列第一项;为空则返回 null。

pub fn front(deque: *const Self) ?T

参数

deque: *const Self

std.deque.Deque.frontPtr

函数

第 269 行

返回指向双端队列首项的指针;若为空,则返回 null。

pub fn frontPtr(deque: *const Self) ?*T

参数

deque: *const Self

std.deque.Deque.initBuffer

函数

第 40 行

使用外部管理的内存初始化。缓冲区决定容量, 双端队列初始为空。

采用此方式初始化时,所有接受 Allocator 参数的函数 都会导致非法行为。

pub fn initBuffer(buffer: []T) Self

参数

buffer: []T

std.deque.Deque.initCapacity

函数

第 29 行

初始化并分配可容纳 capacity 个元素的容量。 最终容量恰好等于 capacity。 使用 deinit 反初始化。

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

参数

gpa: Allocator
capacity: usize

错误

OutOfMemory

std.deque.Deque.iterator

函数

第 348 行

按从前到后的顺序遍历双端队列中的所有元素。

pub fn iterator(deque: *const Self) Iterator

参数

deque: *const Self

std.deque.Deque.Iterator

容器

第 322 行

字段

deque: *const Self
index: usize

std.deque.Deque.Iterator.next

函数

第 330 行

pub fn next(it: *Iterator) ?T

参数

it: *Iterator

std.deque.Deque.Iterator.nextPtr

函数

第 340 行

pub fn nextPtr(it: *Iterator) ?*T

参数

it: *Iterator

std.deque.Deque.Iterator.peek

函数

第 326 行

pub fn peek(it: Iterator) ?T

参数

it: Iterator

std.deque.Deque.Iterator.peekPtr

函数

第 336 行

pub fn peekPtr(it: Iterator) ?*T

参数

it: Iterator

std.deque.Deque.popBack

函数

第 316 行

移除并返回双端队列最后一项;为空则返回 null。

pub fn popBack(deque: *Self) ?T

参数

deque: *Self

std.deque.Deque.popFront

函数

第 307 行

移除并返回双端队列中的第一项;若为空,则返回 null。

pub fn popFront(deque: *Self) ?T

参数

deque: *Self

std.deque.Deque.pushBack

函数

第 149 行

向双端队列尾部添加一项。

如果需要额外内存,元素指针将失效。

pub fn pushBack(deque: *Self, gpa: Allocator, item: T) error{OutOfMemory}!void

参数

deque: *Self
gpa: Allocator
item: T

错误

OutOfMemory

std.deque.Deque.pushBackAssumeCapacity

函数

第 170 行

在双端队列尾部添加一个元素。

绝不会使元素指针失效。

断言双端队列可容纳一个新增元素。

pub fn pushBackAssumeCapacity(deque: *Self, item: T) void

参数

deque: *Self
item: T

std.deque.Deque.pushBackBounded

函数

第 160 行

向双端队列后端添加一个条目。

绝不使元素指针失效。

如果双端队列的未用容量不足以容纳新增条目,则返回 error.OutOfMemory。

pub fn pushBackBounded(deque: *Self, item: T) error{OutOfMemory}!void

参数

deque: *Self
item: T

错误

OutOfMemory

std.deque.Deque.pushBackSlice

函数

第 225 行

将 items 添加到双端队列后端。 等同于顺序遍历 items,并对每个 条目调用 pushBack。

如果需要额外内存,则使元素指针失效。

pub fn pushBackSlice(deque: *Self, gpa: Allocator, items: []const T) error{OutOfMemory}!void

参数

deque: *Self
gpa: Allocator
items: []const T

错误

OutOfMemory

std.deque.Deque.pushBackSliceAssumeCapacity

函数

第 250 行

将 items 加入双端队列的后端。 等同于按顺序遍历 items,对每个 条目调用 pushBack。

绝不会使元素指针失效。

断言双端队列能够容纳新增元素。

pub fn pushBackSliceAssumeCapacity(deque: *Self, items: []const T) void

参数

deque: *Self
items: []const T

std.deque.Deque.pushBackSliceBounded

函数

第 238 行

将 items 添加到双端队列尾部。 等价于按顺序遍历 items,对每个条目 调用 pushBack。

绝不会使元素指针失效。

若双端队列的未使用容量不足以容纳新增元素,返回 error.OutOfMemory。

pub fn pushBackSliceBounded(deque: *Self, items: []const T) error{OutOfMemory}!void

参数

deque: *Self
items: []const T

错误

OutOfMemory

std.deque.Deque.pushFront

函数

第 115 行

向双端队列头部添加一个元素。

如果需要额外内存,则使元素指针失效。

pub fn pushFront(deque: *Self, gpa: Allocator, item: T) error{OutOfMemory}!void

参数

deque: *Self
gpa: Allocator
item: T

错误

OutOfMemory

std.deque.Deque.pushFrontAssumeCapacity

函数

第 136 行

在双端队列前端添加一个项目。

永远不会使元素指针失效。

断言双端队列可以容纳一个额外项目。

pub fn pushFrontAssumeCapacity(deque: *Self, item: T) void

参数

deque: *Self
item: T

std.deque.Deque.pushFrontBounded

函数

第 126 行

向双端队列头部添加一个元素。

绝不会使元素指针失效。

若双端队列的未使用容量不足以容纳新元素, 则返回 error.OutOfMemory。

pub fn pushFrontBounded(deque: *Self, item: T) error{OutOfMemory}!void

参数

deque: *Self
item: T

错误

OutOfMemory

std.deque.Deque.pushFrontSlice

函数

第 182 行

将 items 添加到双端队列前端。 等同于逆序遍历 items,并对每个 条目调用 pushFront。

如果需要额外内存,则使元素指针失效。

pub fn pushFrontSlice(deque: *Self, gpa: Allocator, items: []const T) error{OutOfMemory}!void

参数

deque: *Self
gpa: Allocator
items: []const T

错误

OutOfMemory

std.deque.Deque.pushFrontSliceAssumeCapacity

函数

第 207 行

将 items 添加到双端队列头部。 等价于逆序遍历 items,对每个条目 调用 pushFront。

绝不会使元素指针失效。

断言双端队列可以容纳新增元素。

pub fn pushFrontSliceAssumeCapacity(deque: *Self, items: []const T) void

参数

deque: *Self
items: []const T

std.deque.Deque.pushFrontSliceBounded

函数

第 195 行

将 items 加入双端队列的前端。 等同于反向迭代 items,对每个 条目调用 pushFront。

绝不会使元素指针失效。

如果双端队列的未使用容量不足以容纳新增元素,则返回 error.OutOfMemory。

pub fn pushFrontSliceBounded(deque: *Self, items: []const T) error{OutOfMemory}!void

参数

deque: *Self
items: []const T

错误

OutOfMemory

std.deque.Deque.Self

别名

第 10 行

别名目标 std.deque.Deque

std.deque.fuzzAgainstArrayList

函数

第 619 行

fn fuzzAgainstArrayList(_: void, smith: *std.testing.Smith) anyerror!void

参数

_: void
smith: *std.testing.Smith

std.deque.FuzzAllocator

容器

第 521 行

字段

smith: *std.testing.Smith
bufs: [2][256 * 4]u8 align(4)
used_bitmap: u2
used_len: [2]usize

std.deque.FuzzAllocator.alloc

函数

第 552 行

fn alloc(ctx: *anyopaque, len: usize, a: std.mem.Alignment, _: usize) ?[*]u8

参数

ctx: *anyopaque
len: usize
a: std.mem.Alignment
_: usize

std.deque.FuzzAllocator.allocator

函数

第 536 行

pub fn allocator(f: *FuzzAllocator) std.mem.Allocator

参数

std.deque.FuzzAllocator.allocCount

函数

第 548 行

pub fn allocCount(f: *FuzzAllocator) u2

参数

std.deque.FuzzAllocator.free

函数

第 612 行

fn free(ctx: *anyopaque, mem: []u8, a: std.mem.Alignment, _: usize) void

参数

ctx: *anyopaque
mem: []u8
a: std.mem.Alignment
_: usize

std.deque.FuzzAllocator.init

函数

第 527 行

pub fn init(smith: *std.testing.Smith) FuzzAllocator

参数

smith: *std.testing.Smith

std.deque.FuzzAllocator.memSlot

函数

第 565 行

fn memSlot(f: *FuzzAllocator, mem: []u8) u1

参数

f: *FuzzAllocator
mem: []u8

std.deque.FuzzAllocator.remap

函数

第 588 行

fn remap(ctx: *anyopaque, mem: []u8, a: std.mem.Alignment, new_len: usize, _: usize) ?[*]u8

参数

ctx: *anyopaque
mem: []u8
a: std.mem.Alignment
new_len: usize
_: usize

std.deque.FuzzAllocator.resize

函数

第 577 行

fn resize(ctx: *anyopaque, mem: []u8, a: std.mem.Alignment, new_len: usize, _: usize) bool

参数

ctx: *anyopaque
mem: []u8
a: std.mem.Alignment
new_len: usize
_: usize

std.deque.std

别名

第 1 行

别名目标 std

源码

std/deque.zig

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

/// 连续、可增长的双端队列。
///
/// 从队列任一端压入/弹出元素的时间复杂度均为 O(1)。
pub fn Deque(comptime T: type) type {
    return struct {
        const Self = @This();

        /// 环形缓冲区。
        buffer: []T,
        /// 逻辑双端队列中第一项在 buffer 中的存储索引。
        head: usize,
        /// 逻辑双端队列中存储的元素数量。
        len: usize,

        /// 不包含元素的 Deque。
        pub const empty: Self = .{
            .buffer = &.{},
            .head = 0,
            .len = 0,
        };

        /// 初始化并分配可容纳 `capacity` 个元素的容量。
        /// 最终容量恰好等于 `capacity`。
        /// 使用 `deinit` 反初始化。
        pub fn initCapacity(gpa: Allocator, capacity: usize) Allocator.Error!Self {
            var deque: Self = .empty;
            try deque.ensureTotalCapacityPrecise(gpa, capacity);
            return deque;
        }

        /// 使用外部管理的内存初始化。缓冲区决定容量,
        /// 双端队列初始为空。
        ///
        /// 采用此方式初始化时,所有接受 Allocator 参数的函数
        /// 都会导致非法行为。
        pub fn initBuffer(buffer: []T) Self {
            return .{
                .buffer = buffer,
                .head = 0,
                .len = 0,
            };
        }

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

        /// 修改双端队列,使其至少可容纳 `new_capacity` 个条目。
        /// 采用超线性增长,以实现均摊 O(1) 的入队和出队操作。
        /// 如果需要额外内存,则使元素指针失效。
        pub fn ensureTotalCapacity(deque: *Self, gpa: Allocator, new_capacity: usize) Allocator.Error!void {
            if (deque.buffer.len >= new_capacity) return;
            return deque.ensureTotalCapacityPrecise(gpa, std.ArrayList(T).growCapacity(new_capacity));
        }

        /// 若当前容量小于 `new_capacity`,此函数会
        /// 修改双端队列,使其恰好能容纳 `new_capacity` 个元素。
        /// 若需要额外内存,则使元素指针失效。
        pub fn ensureTotalCapacityPrecise(deque: *Self, gpa: Allocator, new_capacity: usize) Allocator.Error!void {
            if (deque.buffer.len >= new_capacity) return;
            const old_buffer = deque.buffer;
            if (gpa.remap(old_buffer, new_capacity)) |new_buffer| {
                // 如果元素绕过缓冲区末尾,则需要执行
                // memcpy,防止调整缓冲区大小后出现空隙。
                if (deque.head > old_buffer.len - deque.len) {
                    // 空隙将双端队列中的元素分为头部和尾部。
                    // 选择较短的一部分进行复制。
                    const head = new_buffer[deque.head..old_buffer.len];
                    const tail = new_buffer[0 .. deque.len - head.len];
                    if (head.len > tail.len and new_buffer.len - old_buffer.len > tail.len) {
                        @memcpy(new_buffer[old_buffer.len..][0..tail.len], tail);
                    } else {
                        // 此时可能发生重叠,例如容量增加 1
                        // 且 head.len 大于 1。
                        deque.head = new_buffer.len - head.len;
                        @memmove(new_buffer[deque.head..][0..head.len], head);
                    }
                }
                deque.buffer = new_buffer;
            } else {
                const new_buffer = try gpa.alloc(T, new_capacity);
                if (deque.head < old_buffer.len - deque.len) {
                    @memcpy(new_buffer[0..deque.len], old_buffer[deque.head..][0..deque.len]);
                } else {
                    const head = old_buffer[deque.head..];
                    const tail = old_buffer[0 .. deque.len - head.len];
                    @memcpy(new_buffer[0..head.len], head);
                    @memcpy(new_buffer[head.len..][0..tail.len], tail);
                }
                deque.head = 0;
                deque.buffer = new_buffer;
                gpa.free(old_buffer);
            }
        }

        /// 修改双端队列,使其至少还能容纳 `additional_count` 个额外元素。
        /// 若需要额外内存,则使元素指针失效。
        pub fn ensureUnusedCapacity(
            deque: *Self,
            gpa: Allocator,
            additional_count: usize,
        ) Allocator.Error!void {
            return deque.ensureTotalCapacity(gpa, try addOrOom(deque.len, additional_count));
        }

        /// 向双端队列头部添加一个元素。
        ///
        /// 如果需要额外内存,则使元素指针失效。
        pub fn pushFront(deque: *Self, gpa: Allocator, item: T) error{OutOfMemory}!void {
            try deque.ensureUnusedCapacity(gpa, 1);
            deque.pushFrontAssumeCapacity(item);
        }

        /// 向双端队列头部添加一个元素。
        ///
        /// 绝不会使元素指针失效。
        ///
        /// 若双端队列的未使用容量不足以容纳新元素,
        /// 则返回 `error.OutOfMemory`。
        pub fn pushFrontBounded(deque: *Self, item: T) error{OutOfMemory}!void {
            if (deque.buffer.len - deque.len == 0) return error.OutOfMemory;
            return deque.pushFrontAssumeCapacity(item);
        }

        /// 在双端队列前端添加一个项目。
        ///
        /// 永远不会使元素指针失效。
        ///
        /// 断言双端队列可以容纳一个额外项目。
        pub fn pushFrontAssumeCapacity(deque: *Self, item: T) void {
            assert(deque.len < deque.buffer.len);
            if (deque.head == 0) {
                deque.head = deque.buffer.len;
            }
            deque.head -= 1;
            deque.buffer[deque.head] = item;
            deque.len += 1;
        }

        /// 向双端队列尾部添加一项。
        ///
        /// 如果需要额外内存,元素指针将失效。
        pub fn pushBack(deque: *Self, gpa: Allocator, item: T) error{OutOfMemory}!void {
            try deque.ensureUnusedCapacity(gpa, 1);
            deque.pushBackAssumeCapacity(item);
        }

        /// 向双端队列后端添加一个条目。
        ///
        /// 绝不使元素指针失效。
        ///
        /// 如果双端队列的未用容量不足以容纳新增条目,则返回
        /// `error.OutOfMemory`。
        pub fn pushBackBounded(deque: *Self, item: T) error{OutOfMemory}!void {
            if (deque.buffer.len - deque.len == 0) return error.OutOfMemory;
            deque.pushBackAssumeCapacity(item);
        }

        /// 在双端队列尾部添加一个元素。
        ///
        /// 绝不会使元素指针失效。
        ///
        /// 断言双端队列可容纳一个新增元素。
        pub fn pushBackAssumeCapacity(deque: *Self, item: T) void {
            assert(deque.len < deque.buffer.len);
            const buffer_index = deque.bufferIndex(deque.len);
            deque.buffer[buffer_index] = item;
            deque.len += 1;
        }

        /// 将 `items` 添加到双端队列前端。
        /// 等同于逆序遍历 `items`,并对每个
        /// 条目调用 `pushFront`。
        ///
        /// 如果需要额外内存,则使元素指针失效。
        pub fn pushFrontSlice(deque: *Self, gpa: Allocator, items: []const T) error{OutOfMemory}!void {
            try deque.ensureUnusedCapacity(gpa, items.len);
            return deque.pushFrontSliceAssumeCapacity(items);
        }

        /// 将 `items` 加入双端队列的前端。
        /// 等同于反向迭代 `items`,对每个
        /// 条目调用 `pushFront`。
        ///
        /// 绝不会使元素指针失效。
        ///
        /// 如果双端队列的未使用容量不足以容纳新增元素,则返回
        /// `error.OutOfMemory`。
        pub fn pushFrontSliceBounded(deque: *Self, items: []const T) error{OutOfMemory}!void {
            if (deque.buffer.len - deque.len < items.len) return error.OutOfMemory;
            return deque.pushFrontSliceAssumeCapacity(items);
        }

        /// 将 `items` 添加到双端队列头部。
        /// 等价于逆序遍历 `items`,对每个条目
        /// 调用 `pushFront`。
        ///
        /// 绝不会使元素指针失效。
        ///
        /// 断言双端队列可以容纳新增元素。
        pub fn pushFrontSliceAssumeCapacity(deque: *Self, items: []const T) void {
            assert(deque.buffer.len - deque.len >= items.len);
            if (deque.head < items.len) {
                @memcpy(deque.buffer[0..deque.head], items[items.len - deque.head ..]);
                deque.head = deque.buffer.len - items.len + deque.head;
                @memcpy(deque.buffer[deque.head..], items.ptr);
            } else {
                deque.head -= items.len;
                @memcpy(deque.buffer[deque.head..][0..items.len], items);
            }
            deque.len += items.len;
        }

        /// 将 `items` 添加到双端队列后端。
        /// 等同于顺序遍历 `items`,并对每个
        /// 条目调用 `pushBack`。
        ///
        /// 如果需要额外内存,则使元素指针失效。
        pub fn pushBackSlice(deque: *Self, gpa: Allocator, items: []const T) error{OutOfMemory}!void {
            try deque.ensureUnusedCapacity(gpa, items.len);
            return deque.pushBackSliceAssumeCapacity(items);
        }

        /// 将 `items` 添加到双端队列尾部。
        /// 等价于按顺序遍历 `items`,对每个条目
        /// 调用 `pushBack`。
        ///
        /// 绝不会使元素指针失效。
        ///
        /// 若双端队列的未使用容量不足以容纳新增元素,返回
        /// `error.OutOfMemory`。
        pub fn pushBackSliceBounded(deque: *Self, items: []const T) error{OutOfMemory}!void {
            if (deque.buffer.len - deque.len < items.len) return error.OutOfMemory;
            return deque.pushBackSliceAssumeCapacity(items);
        }

        /// 将 `items` 加入双端队列的后端。
        /// 等同于按顺序遍历 `items`,对每个
        /// 条目调用 `pushBack`。
        ///
        /// 绝不会使元素指针失效。
        ///
        /// 断言双端队列能够容纳新增元素。
        pub fn pushBackSliceAssumeCapacity(deque: *Self, items: []const T) void {
            assert(deque.buffer.len - deque.len >= items.len);
            const trailing_buffer = deque.buffer[deque.bufferIndex(deque.len)..];
            if (trailing_buffer.len < items.len) {
                @memcpy(trailing_buffer, items[0..trailing_buffer.len]);
                @memcpy(deque.buffer.ptr, items[trailing_buffer.len..]);
            } else {
                @memcpy(trailing_buffer[0..items.len], items);
            }
            deque.len += items.len;
        }

        /// 返回双端队列第一项;为空则返回 null。
        pub fn front(deque: *const Self) ?T {
            if (deque.len == 0) return null;
            return deque.buffer[deque.head];
        }

        /// 返回指向双端队列首项的指针;若为空,则返回 null。
        pub fn frontPtr(deque: *const Self) ?*T {
            if (deque.len == 0) return null;
            return &deque.buffer[deque.head];
        }

        /// 返回双端队列的最后一项;若为空,则返回 null。
        pub fn back(deque: *const Self) ?T {
            if (deque.len == 0) return null;
            return deque.buffer[deque.bufferIndex(deque.len - 1)];
        }

        /// 返回双端队列的最后一项;若为空,则返回 null。
        pub fn backPtr(deque: *const Self) ?*T {
            if (deque.len == 0) return null;
            return &deque.buffer[deque.bufferIndex(deque.len - 1)];
        }

        /// 返回双端队列中给定索引处的元素。
        ///
        /// 队列首个元素的索引为 0。
        ///
        /// 断言索引未越界。
        pub fn at(deque: *const Self, index: usize) T {
            assert(index < deque.len);
            return deque.buffer[deque.bufferIndex(index)];
        }

        /// 返回指向双端队列中给定索引处元素的指针。
        ///
        /// 队列中第一个元素的索引为 0。
        ///
        /// 断言索引未越界。
        pub fn atPtr(deque: *const Self, index: usize) *T {
            assert(index < deque.len);
            return &deque.buffer[deque.bufferIndex(index)];
        }

        /// 移除并返回双端队列中的第一项;若为空,则返回 null。
        pub fn popFront(deque: *Self) ?T {
            if (deque.len == 0) return null;
            const pop_index = deque.head;
            deque.head = deque.bufferIndex(1);
            deque.len -= 1;
            return deque.buffer[pop_index];
        }

        /// 移除并返回双端队列最后一项;为空则返回 null。
        pub fn popBack(deque: *Self) ?T {
            if (deque.len == 0) return null;
            deque.len -= 1;
            return deque.buffer[deque.bufferIndex(deque.len)];
        }

        pub const Iterator = struct {
            deque: *const Self,
            index: usize,

            pub fn peek(it: Iterator) ?T {
                if (it.index >= it.deque.len) return null;
                return it.deque.at(it.index);
            }
            pub fn next(it: *Iterator) ?T {
                const item = it.peek() orelse return null;
                it.index += 1;
                return item;
            }

            pub fn peekPtr(it: Iterator) ?*T {
                if (it.index >= it.deque.len) return null;
                return it.deque.atPtr(it.index);
            }
            pub fn nextPtr(it: *Iterator) ?*T {
                const item_ptr = it.peekPtr() orelse return null;
                it.index += 1;
                return item_ptr;
            }
        };

        /// 按从前到后的顺序遍历双端队列中的所有元素。
        pub fn iterator(deque: *const Self) Iterator {
            return .{ .deque = deque, .index = 0 };
        }

        /// 返回逻辑双端队列中给定索引处的元素
        /// 在 `buffer` 中的存储索引。
        fn bufferIndex(deque: *const Self, index: usize) usize {
            // 此函数采用这种写法,
            // 以避免溢出及开销较大的除法。
            const head_len = deque.buffer.len - deque.head;
            if (index < head_len) {
                return deque.head + index;
            } else {
                return index - head_len;
            }
        }
    };
}

/// 整数加法,溢出时返回 `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 "basic" {
    const testing = std.testing;
    const gpa = testing.allocator;

    var q: Deque(u32) = .empty;
    defer q.deinit(gpa);

    try testing.expectEqual(null, q.popFront());
    try testing.expectEqual(null, q.popBack());

    try q.pushBack(gpa, 1);
    try q.pushBack(gpa, 2);
    try q.pushBack(gpa, 3);
    try q.pushFront(gpa, 0);

    try testing.expectEqual(0, q.popFront());
    try testing.expectEqual(1, q.popFront());
    try testing.expectEqual(3, q.popBack());
    try testing.expectEqual(2, q.popFront());
    try testing.expectEqual(null, q.popFront());
    try testing.expectEqual(null, q.popBack());
}

test "buffer" {
    const testing = std.testing;

    var buffer: [4]u32 = undefined;
    var q: Deque(u32) = .initBuffer(&buffer);

    try testing.expectEqual(null, q.popFront());
    try testing.expectEqual(null, q.popBack());

    try q.pushBackBounded(1);
    try q.pushBackBounded(2);
    try q.pushBackBounded(3);
    try q.pushFrontBounded(0);
    try testing.expectError(error.OutOfMemory, q.pushBackBounded(4));

    try testing.expectEqual(0, q.popFront());
    try testing.expectEqual(1, q.popFront());
    try testing.expectEqual(3, q.popBack());
    try testing.expectEqual(2, q.popFront());
    try testing.expectEqual(null, q.popFront());
    try testing.expectEqual(null, q.popBack());
}

test "slow growth" {
    const testing = std.testing;
    const gpa = testing.allocator;

    var q: Deque(i32) = .empty;
    defer q.deinit(gpa);

    try q.ensureTotalCapacityPrecise(gpa, 1);
    q.pushBackAssumeCapacity(1);
    try q.ensureTotalCapacityPrecise(gpa, 2);
    q.pushFrontAssumeCapacity(0);
    try q.ensureTotalCapacityPrecise(gpa, 3);
    q.pushBackAssumeCapacity(2);
    try q.ensureTotalCapacityPrecise(gpa, 5);
    q.pushBackAssumeCapacity(3);
    q.pushFrontAssumeCapacity(-1);
    try q.ensureTotalCapacityPrecise(gpa, 6);
    q.pushFrontAssumeCapacity(-2);

    try testing.expectEqual(-2, q.popFront());
    try testing.expectEqual(-1, q.popFront());
    try testing.expectEqual(3, q.popBack());
    try testing.expectEqual(0, q.popFront());
    try testing.expectEqual(2, q.popBack());
    try testing.expectEqual(1, q.popBack());
    try testing.expectEqual(null, q.popFront());
    try testing.expectEqual(null, q.popBack());
}

test "slice" {
    const testing = std.testing;
    const gpa = testing.allocator;

    var q: Deque(i32) = .empty;
    defer q.deinit(gpa);

    try q.pushBackSlice(gpa, &.{ 3, 4, 5 });
    try q.pushBackSlice(gpa, &.{ 6, 7 });
    try q.pushFrontSlice(gpa, &.{2});
    try q.pushBackSlice(gpa, &.{});
    try q.pushFrontSlice(gpa, &.{ 0, 1 });
    try q.pushFrontSlice(gpa, &.{});

    try testing.expectEqual(0, q.popFront());
    try testing.expectEqual(1, q.popFront());
    try testing.expectEqual(7, q.popBack());
    try testing.expectEqual(6, q.popBack());

    try q.pushFrontSlice(gpa, &.{ 0, 1 });
    try q.pushBackSlice(gpa, &.{ 6, 7 });

    try testing.expectEqual(0, q.popFront());
    try testing.expectEqual(1, q.popFront());
    try testing.expectEqual(2, q.popFront());
    try testing.expectEqual(7, q.popBack());
    try testing.expectEqual(6, q.popBack());
    try testing.expectEqual(3, q.popFront());
    try testing.expectEqual(4, q.popFront());
    try testing.expectEqual(5, q.popBack());
    try testing.expectEqual(null, q.popFront());
    try testing.expectEqual(null, q.popBack());
}

test "iterator" {
    const testing = std.testing;
    const gpa = testing.allocator;

    var q: Deque(i32) = .empty;
    defer q.deinit(gpa);

    const items: []const i32 = &.{ 0, 1, 2, 3, 4, 5 };
    try q.pushFrontSlice(gpa, items);

    {
        var it = q.iterator();
        for (items) |item| {
            try testing.expectEqual(item, it.peek());
            try testing.expectEqual(item, it.next());
        }
        try testing.expectEqual(null, it.peek());
        try testing.expectEqual(null, it.next());
    }
    {
        var it = q.iterator();
        for (items) |item| {
            if (it.peekPtr()) |ptr| {
                try testing.expectEqual(item, ptr.*);
            } else return error.TestExpectedNonNull;
            if (it.nextPtr()) |ptr| {
                try testing.expectEqual(item, ptr.*);
            } else return error.TestExpectedNonNull;
        }
        try testing.expectEqual(null, it.peekPtr());
        try testing.expectEqual(null, it.nextPtr());
    }
}

test "fuzz against ArrayList oracle" {
    try std.testing.fuzz({}, fuzzAgainstArrayList, .{});
}

const FuzzAllocator = struct {
    smith: *std.testing.Smith,
    bufs: [2][256 * 4]u8 align(4),
    used_bitmap: u2,
    used_len: [2]usize,

    pub fn init(smith: *std.testing.Smith) FuzzAllocator {
        return .{
            .smith = smith,
            .bufs = undefined,
            .used_len = undefined,
            .used_bitmap = 0,
        };
    }

    pub fn allocator(f: *FuzzAllocator) std.mem.Allocator {
        return .{
            .ptr = f,
            .vtable = &.{
                .alloc = alloc,
                .resize = resize,
                .remap = remap,
                .free = free,
            },
        };
    }

    pub fn allocCount(f: *FuzzAllocator) u2 {
        return @popCount(f.used_bitmap);
    }

    fn alloc(ctx: *anyopaque, len: usize, a: std.mem.Alignment, _: usize) ?[*]u8 {
        const f: *FuzzAllocator = @ptrCast(@alignCast(ctx));
        assert(a == .@"4");
        assert(len % 4 == 0);

        const slot: u1 = @intCast(@ctz(~f.used_bitmap));
        const buf: []u8 = &f.bufs[slot];
        if (len > buf.len) return null;
        f.used_bitmap |= @as(u2, 1) << slot;
        f.used_len[slot] = len;
        return buf.ptr;
    }

    fn memSlot(f: *FuzzAllocator, mem: []u8) u1 {
        const slot: u1 = if (&mem[0] == &f.bufs[0][0])
            0
        else if (&mem[0] == &f.bufs[1][0])
            1
        else
            unreachable;
        assert((f.used_bitmap >> slot) & 1 == 1);
        assert(mem.len == f.used_len[slot]);
        return slot;
    }

    fn resize(ctx: *anyopaque, mem: []u8, a: std.mem.Alignment, new_len: usize, _: usize) bool {
        const f: *FuzzAllocator = @ptrCast(@alignCast(ctx));
        assert(a == .@"4");
        assert(f.allocCount() == 1);

        const slot = f.memSlot(mem);
        if (new_len > f.bufs[slot].len or f.smith.value(bool)) return false;
        f.used_len[slot] = new_len;
        return true;
    }

    fn remap(ctx: *anyopaque, mem: []u8, a: std.mem.Alignment, new_len: usize, _: usize) ?[*]u8 {
        const f: *FuzzAllocator = @ptrCast(@alignCast(ctx));
        assert(a == .@"4");
        assert(f.allocCount() == 1);

        const slot = f.memSlot(mem);
        if (new_len > f.bufs[slot].len or f.smith.value(bool)) return null;

        if (f.smith.value(bool)) {
            f.used_len[slot] = new_len;
            // 原地重新映射
            return mem.ptr;
        } else {
            // 移动式重新映射
            const new_slot = ~slot;
            f.used_bitmap = ~f.used_bitmap;
            f.used_len[new_slot] = new_len;

            const new_buf = &f.bufs[new_slot];
            @memcpy(new_buf[0..mem.len], mem);
            return new_buf.ptr;
        }
    }

    fn free(ctx: *anyopaque, mem: []u8, a: std.mem.Alignment, _: usize) void {
        const f: *FuzzAllocator = @ptrCast(@alignCast(ctx));
        assert(a == .@"4");
        f.used_bitmap ^= @as(u2, 1) << f.memSlot(mem);
    }
};

fn fuzzAgainstArrayList(_: void, smith: *std.testing.Smith) anyerror!void {
    const testing = std.testing;

    var q_gpa_inst: FuzzAllocator = .init(smith);
    var l_gpa_buf: [q_gpa_inst.bufs[0].len]u8 align(4) = undefined;
    var l_gpa_inst: std.heap.FixedBufferAllocator = .init(&l_gpa_buf);
    const q_gpa = q_gpa_inst.allocator();
    const l_gpa = l_gpa_inst.allocator();

    var q: Deque(u32) = .empty;
    var l: std.ArrayList(u32) = .empty;

    const Action = enum(u8) {
        grow,
        push_back,
        push_front,
        push_back_slice,
        push_front_slice,
        pop_back,
        pop_front,
    };

    while (!smith.eosWeightedSimple(15, 1)) {
        const baseline = testing.Smith.baselineWeights(Action);
        const grow_weight: testing.Smith.Weight = .value(Action, .grow, 3);
        switch (smith.valueWeighted(Action, baseline ++ .{grow_weight})) {
            .push_back => {
                const item = smith.value(u32);
                try testing.expectEqual(
                    l.appendBounded(item),
                    q.pushBackBounded(item),
                );
            },
            .push_front => {
                const item = smith.value(u32);
                try testing.expectEqual(
                    l.insertBounded(0, item),
                    q.pushFrontBounded(item),
                );
            },
            .push_back_slice => {
                var buffer: [std.math.maxInt(u3)]u32 = undefined;
                const items = buffer[0..smith.value(u3)];
                for (items) |*item| {
                    item.* = smith.value(u32);
                }
                try testing.expectEqual(
                    l.appendSliceBounded(items),
                    q.pushBackSliceBounded(items),
                );
            },
            .push_front_slice => {
                var buffer: [std.math.maxInt(u3)]u32 = undefined;
                const items = buffer[0..smith.value(u3)];
                for (items) |*item| {
                    item.* = smith.value(u32);
                }
                try testing.expectEqual(
                    l.insertSliceBounded(0, items),
                    q.pushFrontSliceBounded(items),
                );
            },
            .pop_back => {
                try testing.expectEqual(l.pop(), q.popBack());
            },
            .pop_front => {
                try testing.expectEqual(
                    if (l.items.len > 0) l.orderedRemove(0) else null,
                    q.popFront(),
                );
            },
            // 以小幅、随机、线性的增量扩容,似乎能更有效地测试 ensureTotalCapacityPrecise(),它是 Deque 实现中最复杂的部分。
            //
            //
            .grow => {
                const growth = smith.value(u3);
                try l.ensureTotalCapacityPrecise(l_gpa, l.items.len + growth);
                try q.ensureTotalCapacityPrecise(q_gpa, q.len + growth);
            },
        }
        try testing.expectEqual(l.last(), q.back());
        try testing.expectEqual(
            if (l.items.len > 0) l.items[0] else null,
            q.front(),
        );
        try testing.expectEqual(l.items.len, q.len);
        try testing.expectEqual(l.capacity, q.buffer.len);
        {
            var it = q.iterator();
            for (l.items) |item| {
                try testing.expectEqual(item, it.next());
            }
            try testing.expectEqual(null, it.next());
        }
        try testing.expectEqual(@intFromBool(q.buffer.len != 0), q_gpa_inst.allocCount());
    }
    q.deinit(q_gpa);
    try testing.expectEqual(0, q_gpa_inst.allocCount());
}