为什么 STL 双端队列不作为循环向量实现？

Question

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

Answer 1

std::deque（双端队列）是一个索引序列容器，允许在其开始和结束时进行快速插入和删除。此外，双端队列两端的插入和删除永远不会使指向其余元素的指针或引用无效。

与std::vector相反，双端队列的元素不是连续存储的：典型的实现使用一系列单独分配的固定大小数组。

双端队列的存储会根据需要自动扩展和收缩。双端队列的扩展比 std::vector 的扩展便宜，因为它不涉及将现有元素复制到新的内存位置。

双端队列常用操作的复杂度（效率）如下：

随机访问 - 常数 O(1)
在结尾或开头插入或删除元素 - 常量 O(1)
插入或删除元素 - 线性 O(n)

来源：std::deque

Answer 2

如cppreference 所写

As opposed to std::vector, the elements of a deque are not stored contiguously: typical implementations use a sequence of individually allocated fixed-size arrays.

这意味着大型内部重新分配 std::vector 偶尔会执行，而不是由 std::deque 执行。当 space 用完时，只添加一个固定大小的小数组。（当 space 由于擦除而变得太大时，会发生相同但相反的情况。）

这里有一个小测试：

#include <vector>
#include <deque>
#include <string>
#include <iostream>
#include <chrono>


using namespace std;


int main()
{
    {
        const auto start = chrono::high_resolution_clock::now();

        vector<string> v;
        for(size_t i = 0; i < 9999999; ++i)
            v.push_back(string("hello"));

        cout << chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - start).count() << endl;
    }

    {
        const auto start = chrono::high_resolution_clock::now();

        deque<string> v;
        for(size_t i = 0; i < 9999999; ++i)
            v.push_back(string("hello"));

        cout << chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - start).count() << endl;
    }

    return 0;
}

在我的机器上，在这种情况下，它显示 deque 的速度是 vector 的两倍：

$ ./a.out 
301
164

Answer 3

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

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

您可以拥有 std::deque 个 "fat" 个对象，而无需使用额外的间接级别来避免移动操作并保持效率。

Answer 4

23.3.8.4 [deque.modifiers]（重点是我的）

An insertion in the middle of the deque invalidates all the iterators and references to elements of the deque. An insertion at either end of the deque invalidates all the iterators to the deque, but has no effect on the validity of references to elements of the deque.

这对于类似循环向量的实现是不可能的。

为什么 STL 双端队列不作为循环向量实现？

Why is an STL deque not implemented as just a circular vector?

c++

stl

deque