我一直认为在C++标准模板库（STL）中，双端队列（deque）是一个具有循环边界条件的大小可变数组（如向量），意味着有一个头指针i和一个尾指针j都指向数组的某个位置a[0..L-1]。一个push_front是i--，push_back 是j++, pop_front 是i++，并且 pop_back 是j--。当任一指针i or j达到L or -1，它重新出现在数组的另一端（0 and L-1分别）。如果数组大小耗尽（指针i==j插入新元素后），分配一个比原来大一倍的更大空间a[]数据就像向量一样被复制。还有O(1)考虑循环边界条件的时间随机访问。但有人告诉我，在 STL 双端队列中实际上有一个指针数组指向许多固定长度的数组段。它比圆形向量复杂得多。不使用简单的循环向量来实现双端队列的功能有什么好处？随机访问会变慢吗？

主要优点std::deque方法是，如果您从两端添加或删除元素，则一旦插入容器中的元素就永远不会移动。因此，在执行这些操作时，对元素的引用（和指针）不会失效（请注意，令人惊讶的是，迭代器 to deque当在末端进行插入或删除时，元素会失效）。

这虽然使实现更加复杂，但可以在不影响形式大 O 复杂性的情况下完成，并且使得std::deque一个非常有用的容器。

你可以有一个std::deque的“胖”对象，而无需使用额外的间接级别来避免移动操作并保持效率。