C++ 标准 (N4901) 参考 deque push_front 函数进行了这样的说明：
\n\n\n实现应为 \xe2\x80\x9ccontainer\xe2\x80\x9d 列中显示的所有容器类型提供这些操作，并应实现它们以便采用摊余常数时间。
\n
如果我没有记错的话，这意味着符合标准的实现应该提供一个需要摊销 O(1) 时间的双端队列 push_front 函数。
\n然而，在查看了源代码并在 gdb 下运行了一些测试程序之后，我开始相信 deque push_front 函数的 libc++ 实现实际上具有 O(log n) 摊销时间。
\n对于上下文：STL 双端队列是使用两级数组在 libc++ 中实现的，它map是一个动态数组，其中包含指向名为 的固定大小数组的指针blocks。只有一个map，其大小不受限制，并且有无数个blocks，其大小是固定的。
这是一个准确的可视化（为了证明，见下文），显示了map每个新的外观block（blocks按分配顺序命名，因此 b01 是第一个block分配的，b02 是第二个block分配的，依此类推）是map通过调用添加到push_front. 线性时间操作，例如map通过复制或移动整个数组memmove标记为：
[]\n[b01]\n[b02, b01] copied\n[b03, b02, b01, ___] copied\n[b04, b03, b02, b01] …