题解：B3656 【模板】双端队列 1

· · 题解

考虑到 std::list（及类似链表实现）的时间常数较大，std::deque 的静态空间较大，我决定自己实现一个双端队列，于是就有了这篇题解。

提交记录（卡常版，可读性可能较弱，模板见文章末尾）

实现的核心是循环队列。

循环队列用一个数组（一块连续内存）存储数据，设数组大小为 size，访问时，将下标 i 对 size 取模。不难发现，无论如何在前后增删元素，只要元素数量不超过数组大小，都不会出现任何问题（你别告诉我下标爆 int 了）。

为了减小常数，这里使用的是大小为 2^n 的循环队列，因为当 x=2^n 时， (v%x+x)%x 与 v&(x-1) 等价，而后者很明显常数更小。

但是我们不能固定循环队列的大小，大小过大会爆内存，大小过小会不够，我们可以考虑动态扩容和缩容。

具体来说，当大小不够时，新开一个两倍大小的数组，把数据复制进去，当大小过大（空间使用率不到四分之一）时，新开一个二分之一大小的数组，把数据复制进去。这样在两端插入和删除的时间复杂度是均摊 O(1) 的。

空间上，在最坏情况，数组部分的空间占用可保证不超过两倍的最大元素数量，且不超过四倍的当前元素数量。

因为内存空间是连续的，我们可以得到和 std::deque 相同的 O(1) 的似乎没什么用的随机访问。

其余操作除 clear() 是小常数 O(n) 外均为 O(1)。

性能测试结果如下：

单位均为 μs（千分之一毫秒），开启 O2 优化，随机访问部分可能受随机数生成影响较大。

队列大小 1 10 100 1000 10000 100000
队列数量 100000 10000 1000 100 10 1
插入删除 模板 25 1036 419 190 198 356
插入删除 std::deque 13079 1828 316 209 252 242
插入删除 std::list 17116 8431 10797 10085 8913 8800
迭代 模板 33 35 91 50 48 48
迭代 std::deque 87 37 45 52 41 50
迭代 std::list 55 43 139 132 220 229
随机访问 模板 1681 1778 1711 1707 1723 1724
随机访问 std::deque 1700 1792 1709 1876 1720 1706

模板及性能测试代码见剪贴板。