ring buffer · 分段数组

deque 本体的两种实现模型

单调队列要求四个操作都是常数级：队尾进、队尾出、队首出，加上读队首。这正是 deque 的接口。它怎么实现，教科书通常一句「用双端队列即可」带过，但两种主流实现的代价结构差得很远，而差别恰好落在「谁在搬元素」上。

本页实现两种模型并给它们统一计数：元素级搬迁次数、指针级搬迁次数、分配与释放次数、当前容量。四个数字合起来就能说清取舍。

1 · deque 的接口契约

C++ 标准对 std::deque 的要求里有一条超出复杂度范畴：在两端插入元素，不使已有元素的引用、指针失效（迭代器会失效，引用不会）。std::vector 给不出这条保证，它扩容时把全部元素搬到新内存，旧地址全废。

这条契约是分段实现存在的唯一理由。若只看渐近复杂度，ring buffer 的四个操作都是摊还 $O(1)$ ，与分段实现打平，而且常数更小、局部性更好。选分段数组，买的是引用稳定性。

2 · ring buffer 的下标折算

一整块数组加两个整数：head 指首元素，size 是元素个数。逻辑位置 $i$ 落在物理位置 $(\text{head} + i) \bmod \text{capacity}$ 。头尾各自可以越过数组边界绕回开头，这也是它名字的来源。

装满时换一块两倍大的数组，把全部元素按逻辑顺序搬过去。搬迁总量与动态数组扩容同理：从容量 4 开始翻倍装到 1024，搬迁 $4 + 8 + \dots + 512 = 1020$ 个元素。实测 $n = 10^6$ 次尾插，元素搬迁 1048572 次，即 $1.049n$ ；分配 19 次。

3 · 分段数组的 map 与固定块

元素装在固定大小的块里，另有一张 map 数组存各块的引用。给定逻辑位置，先除以块长定位到哪一块，再取余定位到块内偏移——两次访存，但两次都不搬元素。

需要更多空间时只做两件事：新分配一个块、把它挂进 map。已有的块原地不动，块里的元素一个都不搬，所以元素级搬迁次数恒为 0。map 本身满了才重建，重建时挪的是块引用而不是元素，而 map 的长度只有元素数的 $1/B$ 。

libstdc++ 的块长口径是 512 字节：元素小于 512 字节时一块装 $512 / \text{sizeof}$ 个，否则一块装一个。它的 _M_reallocate_map 在重建 map 时把已有块引用居中放置，于是前后两端都留出空位，头尾交替插入不会反复触发重建。

图 3-1 · ring buffer 与分段数组并排执行同一条操作序列。上排是物理格子，下排是逻辑元素序列。可逐步执行任意的两端插入删除，观察两者何时搬元素、何时只挂块。

块空了要还回去。libstdc++ 在 _M_pop_front_aux 与 _M_pop_back_aux 里做这件事：一旦最后一个元素离开某个块，立刻 _M_deallocate_node。本页的模型最初漏了这一步，代价立刻在滑窗式负载上显形（见 §5）。

4 · 与链表的对照

双向链表同样能在两端做到真 $O(1)$ ，而且完全不搬元素、引用永远稳定。它输在别处。

其一是访存。链表每个节点由分配器单独给出，彼此在内存里无关，遍历时每一跳都可能是一次 cache miss；两种数组式实现里相邻元素要么完全连续、要么在同一个块内连续。其二是每元素开销：链表节点要额外存两个指针，64 位机上就是 16 字节，装一个 4 字节整数时开销是载荷的四倍。链表系列的「性能变体」一组从节点布局这一侧给出同一个结论。

真正的分工是：只在两端进出、又要顺序遍历，用数组式 deque；需要在中间任意位置 $O(1)$ 插删且手上已有该位置的引用，才轮到链表。

5 · 三种负载下的实测代价

三种负载把两个模型的差别摊开。块长取 512，ring buffer 初始容量 4。

负载	ring 元素搬迁	ring 分配	ring 容量	分段指针搬迁	分段分配 / 释放	分段容量
尾插 $10^6$ 次	1048572	19	1048576	2734	1954 / 0	1000448
两端交替插 $10^5$ 次	131068	16	131072	247	196 / 0	100352
滑窗式一进一出 $10^6$ 次	1020	9	1024	19	1954 / 1951	1536

前两行是分段实现的主场：元素一个都不搬，代价全在几千次指针挪动上。第三行反过来，这也是单调队列真实的负载形态——队列长期只装几个到几十个元素，一进一出滚一百万次。ring buffer 在这一行只分配 9 次、容量停在 1024，此后一直复用同一块内存；分段实现每 512 个元素就要新分配一个块、再释放一个块，一百万次操作下 1954 次分配与 1951 次释放。

图 5-1 · 三种负载下两个模型的四项代价。可切换负载类型、改块长与操作次数，观察块长如何在指针搬迁与分配次数之间换。

警示 · 分段实现的三处坑，都是写这一页时踩出来的。

map 必须按倍数扩张。 第一版每加一个块就重建一次 map，指针搬迁量随块数平方增长： $n = 1024$ 时 120 次、 $n = 4096$ 时 2016 次。改成「map 满了才翻倍，且把已有引用居中放」之后，同样的 $n = 1024$ 只剩 21 次， $n = 10^6$ 也只有 2734 次。

扩容会平移坐标。 pushBack 里原本先算好写入位置再判断要不要加块，而加块时若顺带重建 map，逻辑坐标会整体平移，那个先算好的位置就指向了旧坐标。表现是某个早先写入的元素被第 359 次操作的值悄悄覆盖：两个模型逐步比对元素序列的测试在那一格报出分岔，而单独看任何一个模型都自洽。

不回收空块，滑窗式负载会一直吃内存。 补上块回收之前，一进一出滚一百万次的容量涨到 1000448；补上之后停在 1536。这不是分段数组的固有缺陷，是模型漏实现了标准库本来就做的事。

6 · 参考文献

ISO/IEC 14882 · [deque.modifiers]。两端插入不使引用失效、但使迭代器失效的条款原文。
libstdc++ include/bits/stl_deque.h。_M_reallocate_map 的居中重建、_Deque_iterator 的四指针布局、_GLIBCXX_DEQUE_BUF_SIZE 的 512 字节口径。
Rust std::collections::VecDeque 文档。Rust 选了 ring buffer，文档明写扩容会移动元素，与 C++ 的取舍相反。
Knuth, D. E. (1997). The Art of Computer Programming, Vol. 1 (3rd ed., §2.2.1). Addison-Wesley. 顺序存储下 stack、queue、deque 的下标折算与溢出判定。