pho*_*oji 105
a deque中的元素在记忆中不连续; vector保证元素.因此,如果您需要与需要连续数组的普通C库进行交互,或者如果您(很多)关心空间局部性,那么您可能更喜欢vector.此外,由于有一些额外的簿记,其他操作可能(略微)比其等效vector操作更昂贵.另一方面,使用许多/大型实例vector可能会导致不必要的堆碎片(减慢调用new).
另外,正如StackOverflow上的其他地方所指出的,这里有更好的讨论:http://www.gotw.ca/gotw/054.htm.
Cas*_*Cow 32
要知道差异,应该知道如何deque实施.内存以相同大小的块分配,并且它们被链接在一起(作为数组或可能是向量).
因此,要找到第n个元素,您会找到适当的块然后访问其中的元素.这是恒定时间,因为它总是正好2次查找,但仍然比矢量更多.
vector也适用于需要连续缓冲区的API,因为它们是C API或者能够获取指针和长度更通用.(因此,您可以在下面使用向量或常规数组,并从内存块中调用API).
deque它最大的优势在哪里:
其中第二个鲜为人知,但对于非常大的收藏尺寸:
当我在过去处理大型集合并从连续模型转移到块模型时,我们能够在32位系统中耗尽内存之前存储大约5倍的集合.这部分是因为,在重新分配时,它实际上需要在复制元素之前存储旧块以及新块.
说完这一切之后,你可能会std::deque在使用"乐观"内存分配的系统上遇到麻烦.虽然它尝试请求大缓冲区大小以重新分配a vector可能会在某些时候被a拒绝bad_alloc,但分配器的乐观性质可能总是授予对a请求的较小缓冲区的请求deque,这可能会导致操作系统杀死进程以尝试获取一些内存.无论选择哪一个都可能不太令人愉快.
在这种情况下的解决方法是设置系统级标志以覆盖乐观分配(并非总是可行)或稍微更手动地管理内存,例如使用您自己的分配器来检查内存使用情况或类似情况.显然不理想.(这可能会回答你的问题,因为喜欢矢量......)
How*_*ant 27
我已经多次实现了vector和deque.从实现的角度来看,deque非常复杂.这种复杂性转化为更多代码和更复杂的代码.因此,当您选择deque over vector时,通常会看到代码大小.如果您的代码仅使用向量优于的东西(即push_back),您也可能会遇到小的速度.
如果你需要一个双端队列,deque是明显的赢家.但是如果你在后面进行大部分插入和擦除,矢量将成为明显的赢家.如果您不确定,请使用typedef声明容器(因此可以轻松地来回切换)并进行测量.
std::deque没有保证连续的内存 - 而索引访问通常会慢一些.deque通常被实现为"向量列表".