为什么不总是使用循环数组双端队列而不是数组列表？

Question

几乎所有的编程语言都有一些使用动态数组的列表的实现，当它达到一定容量时会自动扩展。例如，Java 有ArrayList，C++ 有std::vector。

最近我了解了循环数组双端队列，它也是使用动态数组实现的。它们跟踪列表的起始索引，并使用模运算来访问元素。与数组列表一样，它们允许 O(1) 查找和 O(1) 在末尾插入，并且空间与 O(N) 成正比。但是，它们也允许在开头插入 O(1)。

（虽然 JavaArrayDeque实现了这种数据结构，但它不允许查找元素。C++std::deque似乎使用了不同的实现。）

如果这些数组双端队列具有与数组列表相同或更好的性能特征，那么为什么不总是将它们用作列表的默认实现呢？

Answer 1

如果不需要在列表头部插入，那么循环双端队列会带来不必要的开销，例如对于索引方法。在循环双端队列中，访问索引 i 需要将 i 添加到头元素的索引并在访问底层数组之前循环（例如使用模或位运算符），而对于普通向量，在访问之前不需要对 i 进行任何操作底层数组。

为了演示这种开销，典型的双端队列实现可能如下所示：

template <typename T>
class Deque {
  private:
    T* array; // The underlying array, holding elements of the deque.
    int size; // The number of elements held by the deque.
    int capacity; // The size of array ** must be a power of two **.
    int head; // The index of the head element within array.

  public:
    T& operator[](int index) {
        // Notice the calculation required before accessing array.
        return array[(head + index) & (capacity - 1)]
    }
};

此外，如果您需要访问底层数组，其中元素从索引 0 开始是连续的，则双端队列将无法提供。

请参阅问题Why would I like using vector to deque，这与您的非常相似。