为什么STL deque不是作为一个循环向量来实现的？
我一直认为，在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)时间随机存取。但是有人告诉我，在someone中，实际上有一个指针数组，指向许多固定长度的数组段。它比圆形矢量要复杂得多。不使用简单的圆形向量来实现deque的函数有什么好处？随机访问会变慢吗？
回答 4
Stack Overflow用户
发布于 2016-09-05 05:19:42
正如优先选择所写
与std：：向量不同，deque的元素并不是连续存储的:典型的实现使用一系列单独分配的固定大小数组。
这意味着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;
}在我的机器上，它显示deque是这种情况下向量速度的两倍：
$ ./a.out
301
164Stack Overflow用户
发布于 2016-09-05 05:35:16
std::deque方法的主要优点是，一旦插入容器中的元素，如果从两端中添加或删除元素，则永远不会移动。因此，在执行这些操作时，对元素的引用(和指针)不会失效(请注意，非常令人惊讶的是，迭代器到deque元素在执行末端插入或删除时是无效的)。
这在使实现更加复杂的同时，可以在不影响形式上的大O复杂度的情况下完成，并使std::deque成为一个非常有用的容器。
您可以拥有"fat“对象的std::deque，而不必使用额外的间接操作来避免移动操作和保持效率。
Stack Overflow用户
发布于 2016-09-05 05:37:41
23.3.8.4 [deque.modifiers] (重点是我的)
在
deque中间插入使所有迭代器和对deque元素的引用无效。deque两端的插入使deque、的所有迭代器无效，但对deque元素的引用的有效性没有影响。
这在类似于循环向量的实现中是不可能的。
https://stackoverflow.com/questions/39324192
复制相似问题
腾讯云开发者
