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

Question

我正在检查 this发布，它指出双端队列在顶部和底部提供了有效的插入。但是这post这里指出除背面之外的双端队列的时间复杂度为 O(n)。我认为如果双端队列具有有效的顶部和底部插入，它将具有 O(1)，而 vector 仅在底部插入时具有 O(1) .如果有人能澄清这一点，我将不胜感激

Answer 1

C++98，第 23.2.1 节(模板类双端队列)

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

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