为什么STL双端队列没有实现为圆形向量？

Question

我一直认为在C++标准模板库(STL)中,双端队列(deque)是一个带有圆形边界条件的大小可变数组(如矢量),这意味着有一个头指针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插入新元素后的指针),则会将原始大小加倍的较大空间重新分配给a[]数据,并将数据复制到向量中.O(1)考虑到圆形边界条件,还有随机访问的时间.但有人告诉我,在STL双端队列中,实际上有一个指针阵列指向许多固定长度的数组段.它比圆形矢量复杂得多.不使用简单的圆形向量来实现双端队列的功能有什么好处？随机访问会变慢吗？

Answer 1

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

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

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

Answer 2

正如cppreference所写

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

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

这是一个小测试：

#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;
}

在我的机器上，它显示在这种情况下双端队列的速度是矢量的两倍：

$ ./a.out 
301
164