在顶部插入时，双端队列是否提供 O(1) 复杂度

Question

我正在阅读这篇文章，它指出双端队列在顶部和底部提供有效的插入。然而，这篇文章在这里指出除后面之外的双端队列的时间复杂度是 O(n)。我认为如果双端队列具有有效的顶部和底部插入它将具有 O(1)，而向量仅在底部插入时应具有 O(1)。如果有人能澄清这一点，我将不胜感激

Answer 1

C++98，第 23.2.1 节（模板类双端队列）

“双端队列...支持在开头或结尾处进行恒定时间的插入和擦除操作；在中间插入和擦除需要线性时间。也就是说，双端队列特别针对在开头和结尾处推入和弹出元素进行了优化.与向量一样，存储管理是自动处理的。”

所以是的：O(1) 在两端插入。

Answer 2

std::deque的 cppreference 条目具有以下复杂性：

双端队列常见操作的复杂度（效率）如下：

• 随机访问 - 常数 O(1)
• 在末尾或开头插入或删除元素 - 摊余常量 O(1)
• 插入或删除元素 - 线性 O(n)

这与C++ 标准草案“23.3.3.1 类模板双端队列概述”一致，其中指出（重点是我的）：

双端队列是一个序列容器，与向量 (23.3.6) 一样，支持随机访问迭代器。另外，支持开头或结尾的恒定时间插入和擦除操作；中间的插入和擦除需要线性时间。也就是说，双端队列特别针对在开头和结尾推入和弹出元素进行了优化。与向量一样，存储管理是自动处理的。

对于std::vector cppreference 说：

向量上常见操作的复杂度（效率）如下：

• 随机访问 - 常数 O(1)
• 在末尾插入或删除元素 - 摊余常数 O(1)
• 插入或删除元素 - 与到向量末尾的距离呈线性 O(n)

这与标准草案部分23.3.6.1 类模板向量概述一致：

向量是支持随机访问迭代器的序列容器。此外，它还支持末尾（摊销）恒定时间插入和擦除操作；中间的插入和擦除需要线性时间。存储管理是自动处理的，但可以给出提示以提高效率。[...]