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

Question

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

最近学习了循环数组deques，也是使用动态数组实现的。它们跟踪列表的起始索引，并使用模块化算法访问元素。与数组列表一样，它们允许 O(1) 查找和 O(1) 最后插入，并且 space 与 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，与您的非常相似。

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

Why not always use circular array deques instead of array lists?

arrays

data-structures

computer-science

deque