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

Question

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

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

(虽然 Java 的 ArrayDeque 实现了这种数据结构，但它不允许查找元素。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 prefer using vector to deque ，这与您的非常相似。