自
为什么谁会比std::vector
更喜欢std::deque
?
deque
中的元素在内存中是非连续的;保证vector
元素是。因此,如果您需要与需要连续数组的普通C库进行交互,或者如果您(非常)关心空间局部性,那么您可能更喜欢vector
。另外,由于还有一些额外的簿记,其他操作可能(比)同等的vector
操作昂贵。另一方面,使用很多vector
实例可能会导致不必要的堆碎片(降低对new
的调用)。
此外,正如[C0]所指出的,这里还有更多好的讨论:elsewhere on StackOverflow。
要知道区别,应该知道通常如何实现http://www.gotw.ca/gotw/054.htm。内存以大小相等的块分配,并且被链接在一起(作为数组或向量)。
因此,要找到第n个元素,请找到适当的块,然后访问其中的元素。这是恒定时间,因为它总是精确地2次查找,但仍然比向量还要多。
deque
也可以与需要连续缓冲区的API一起使用,因为它们是C API或在获取指针和长度方面更具通用性。 (因此,您可以在其下方有一个向量或一个规则数组,然后从您的内存块中调用该API)。
vector
最大的优点是:
其中的第二个鲜为人知,但是对于非常大的收藏集:
过去,当我处理大型集合并将其从连续模型转移到块模型时,在32位系统中内存不足之前,我们能够存储大约5倍的大型集合。部分原因是,在重新分配时,实际上需要在复制元素之前存储旧块和新块。
已经说了这么多,在使用“乐观”内存分配的系统上,您可能会遇到deque
的麻烦。尽管它尝试为重新分配std::deque
请求较大的缓冲区大小的尝试可能会在某个时候被vector
拒绝,但分配器的乐观性质很可能始终会允许对bad_alloc
所请求的较小缓冲区的请求deque
,这很可能导致操作系统终止试图获取某些内存的进程。它选择的任何一个都可能不太愉快。
在这种情况下,解决方法是设置系统级标志以覆盖乐观分配(并非始终可行),或者以某种方式手动管理内存,例如使用您自己的分配器检查内存使用情况或类似情况。显然不理想。 (谁可能会回答您的问题,以便选择向量...)
我已经多次实现了向量和双端队列。从实现的角度来看,双端队列要复杂得多。这种复杂性将转化为更多的代码和更复杂的代码。因此,当您在向量上选择双端队列时,通常会看到命中的代码大小。如果您的代码仅使用vector擅长的事物(即push_back),您也可能会受到较小的速度影响。
如果您需要双头队列,那么双端队列无疑是赢家。但是,如果您要在背面进行大多数插入和擦除操作,vector无疑是赢家。当您不确定时,请使用typedef声明容器(以便轻松地来回切换),然后进行测量。
std::deque
不能保证连续的内存-索引访问通常要慢一些。双端队列通常被实现为“向量列表”。
根据http://www.cplusplus.com/reference/stl/deque/,“与向量不同,双端队列不能保证其所有元素都位于连续的存储位置,因此消除了通过指针算法进行安全访问的可能性。”
双端队列比较复杂,部分原因是它们不一定具有连续的内存布局。如果需要该功能,则不应使用双端队列。
((以前,我的回答引起了标准化的不足(来自与上述相同的来源,“双端队列可能由特定的库以不同的方式实现”),但实际上几乎适用于任何标准库数据类型。)] >
双端队列是一个序列容器,它允许随机访问其元素,但不能保证具有连续存储。
我认为对每个案例进行性能测试的好主意。并根据此测试做出决定。
根据these test results (with source).,您不希望向量比双端队列更早
一方面,向量经常比双端队列快。如果您实际上并没有需要