为什么 STL 双端队列不是作为循环向量实现的? [英] Why is an STL deque not implemented as just a circular vector?

问题描述

我一直认为在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 双端队列中，实际上有一个指针数组指向许多固定长度的数组段.它比圆形矢量复杂得多.不使用简单的循环向量来实现双端队列的功能有什么好处?随机访问会变慢吗?

I always thought that in C++ standard template library (STL), a double-ended queue (deque) is a size-variable array (like a vector) with circular boundary conditions, meaning there's a head pointer i and a tail pointer j both pointing to some position of an array a[0..L-1]. A push_front is i--, a push_back is j++, a pop_front is i++, and a pop_back is j--. When either pointer i or j reaches L or -1, it reappears on the other end of the array (0 and L-1 respectively). If the array size gets exhausted (pointers i==j after insering a new element), a larger space with double the original size is reallocated to a[] and data gets copied just like in a vector. There's also O(1) time random access taking into account the circular boundary condition. But someone tells me that inside an STL deque there's actually a pointer array pointing to many fixed-length array segments. It's much more complicated than a circular vector. What's the benefit of not using a simple circular vector to implement the functions of a deque? Will the random access get slower?

推荐答案

As cppreference 写

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

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 执行的.当空间用完时，只添加一个小的固定大小的数组.(当空间因为擦除而变得太大时，会发生相同但相反的情况.)

This means that the large internal reallocations std::vector occasionally does, are not performed by std::deque. When space runs out, only a small fixed-size array is added. (The same but reverse happens when space becomes too large because of erasing.)

这是一个小测试:

#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 的两倍:

On my machine, it shows deque is twice as fast as vector for this case:

$ ./a.out 
301
164

这篇关于为什么 STL 双端队列不是作为循环向量实现的?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！