双端队列循环数组和列表实现的区别

Difference between deque circular array and list implementation

根据我所做的研究,双端队列似乎是作为链表或循环数组实现的。两者在性能方面有何不同?为什么要选择一种实现而不是另一种实现?

std::deque 既不能实现为简单数组,也不能实现为链表。它被实现为指向固定大小数组的指针向量。

一般来说,双端队列 - 如果没有 std::deque 的要求 - 确实可以使用数组或链表来实现。

What is the difference in terms of performance between the two

数组具有更好的缓存局部性。列表具有更好的插入最坏情况复杂性。

why would one choose one implementation over the other?

根据用例,一个可能比另一个更快。在大多数情况下,数组更快。

元素引用的失效也存在差异。与所有基于节点的数据结构一样,对链表元素的引用在元素被删除之前仍然有效。除非特定条件适用,否则对所有数组元素的引用通常可能在插入或删除中无效。