因为
containers;
为什么会有人喜欢std::vector
而不是std::deque
发布于 2011-03-18 05:03:29
deque
中的元素在内存中不是连续的;vector
元素在内存中是连续的。因此,如果您需要与需要连续数组的普通C库交互,或者如果您(非常)关心空间局部性,那么您可能更喜欢vector
。此外,由于有一些额外的记账,其他操作可能(稍微)比同等的vector
操作更昂贵。另一方面,使用许多/大型vector
实例可能会导致不必要的堆碎片(减慢对new
的调用)。
此外,正如elsewhere on StackOverflow所指出的,这里有更好的讨论:http://www.gotw.ca/gotw/054.htm。
发布于 2013-01-15 18:30:14
要了解其中的区别,应该知道deque
通常是如何实现的。内存以相等大小的块进行分配,并将它们链接在一起(作为一个数组,或者可能是一个向量)。
因此,要找到第n个元素,您需要找到适当的块,然后访问其中的元素。这是恒定的时间,因为它总是恰好是2次查找,但这仍然比向量多。
vector
还可以很好地与需要连续缓冲区的API配合使用,因为它们要么是APIs,要么在能够接受指针和长度方面更加通用。(因此,您可以在下面使用一个向量或一个常规数组,并从内存块中调用API )。
deque
最大的优势是:
第二个是鲜为人知的,但对于非常大的集合大小:
当我过去处理大型集合时,从连续模型转移到块模型时,在32位系统中内存耗尽之前,我们能够存储大约5倍大的集合。这在一定程度上是因为,当重新分配时,它实际上需要在复制元素之前存储旧块和新块。
话虽如此,在使用“乐观”内存分配的系统上使用std::deque
可能会遇到麻烦。尽管分配器尝试为重新分配vector
而请求较大的缓冲区大小时,可能会在使用bad_alloc
时被拒绝,但分配器的乐观性质很可能始终允许deque
请求较小缓冲区的请求,这可能会导致操作系统终止进程以尝试获取一些内存。无论它选择哪一个,都可能不太令人愉快。
这种情况下的变通方法是设置系统级标志以覆盖乐观分配(并不总是可行的),或者更多地手动管理内存,例如使用您自己的分配器检查内存使用情况或类似情况。显然不是很理想。(这可能会回答您关于首选向量的问题...)
发布于 2011-03-18 06:06:10
我已经多次实现了vector和deque。从实现的角度来看,deque要复杂得多。这种复杂性转化为更多的代码和更复杂的代码。因此,当您选择deque而不是vector时,通常会看到代码大小命中。如果你的代码只使用向量擅长的东西(即push_back),你也可能会遇到一些小的速度问题。
如果你需要一个双端队列,那么deque是最好的选择。但是如果你在后面做大部分的插入和擦除操作,向量显然会是赢家。当你不确定的时候,声明你的容器有一个类型定义(这样就很容易来回切换),并测量。
https://stackoverflow.com/questions/5345152
复制相似问题