Vector vs Deque插入中间

我知道deque比更有效当插入位于前端或末端时，如果我们必须执行指针运算，则向量更好。但是当我们必须在中间执行插入时使用哪一个？和为什么。？Vector vs Deque插入中间

2012-09-14 user1543957

德克可能不是更有效率，特别是如果只有少量的元素。 –

对于相对较小的廉价复制对象集合，无论操作如何，“矢量”都会击败其他容器。（对于最多12个字符的FIFO，我测量了'vector '与'deque '，尽管'deque'针对此利用率进行了优化，但我测试的机器上的“矢量”速度明显更快。） –

你可能会认为， deque会有优势，因为它将数据分解为块。但是要在不变的时间内执行operator[]，则需要所有这些块的大小相同。在中间插入或删除元素仍然需要移动一侧或另一侧的所有值，与vector相同。由于vector更简单，并且具有更好的缓存位置，因此它应该超前。

来源

2012-09-14 14:51:55

的Deque仍然会更有效率，因为它不具有一半的数组的每次插入一个元素一次移动。

当然，如果你考虑大数的元素，甚至比最好是运行一个基准，看看哪一个更符合特定情况下，这只会真正的问题。请记住，premature optimization is the root of all evil。因为它通常作为连续的数据块的连接的序列来实现，而不是在一个std::vector中使用的单块大容器

来源

2012-09-14 14:39:06 Qnan

除非你在其中一端插入，'deque'将需要移动一些元素：或者在插入之前，或者在插入之后。 –

@JamesKanze是真实的，但通常只有有限的几个人将被移动。我敢肯定它不会像矢量一样是所有元素的一半。 – Qnan

std::deque

可以更好的表现。因此，在中间插入会导致从一个地方复制到另一个地方的数据更少，并且可能会减少重新分配。

当然，无论是重要与否取决于容器的大小和复制存储元件的成本。随着C++ 11移动语义，后者的成本并不重要。但最终，唯一的方法就是用现实的应用程序进行分析。

来源

2012-09-14 14:43:08 juanchopanza

我同意，但应该指出，第1段中的连续数据块是逻辑的，而不是物理的。 OP应该更多地研究物理布局，以充分理解插入物的分支 – WhozCraig

正如Doug T.对我的回答所指出的那样，这是错误的。如果你在接近开始的位置插入，'deque'_could_只能在插入前移动元素，因此移动的时间少于'vector'。但是，我不知道是否有任何实现实际执行此操作，并且无论如何，它必须在插入的一侧（无论是在之前还是之后）移动_all_元素。 –

@JamesKanze也许我的回答差劲。我对你说的没有不同意见。我的观点是，所有要移动的元素更可能是“”deque“”的一个小于“”矢量“”的数字。 – juanchopanza

与标准库容器的选择标准时，您可以选择取决于容器：

数据类型要存储&
类型要对数据进行操作。

如果您想在中间执行大量插入操作，使用std::list会更好。

如果选择是只是之间的std::deque和std::vector再就是要考虑许多因素：

通常，存在在双端队列存取元件的情况下，一个以上的间接，因此元件访问并且deques的迭代器移动通常比较慢。
在具有用于存储块大小限制的系统中，双端队列可能包含更多的元素，因为它使用的存储器多于一个块。因此，对于deques，max_size()可能更大。
Deques不提供支持来控制容量和重新分配的时刻。在特别地，任何插入或大于在开始或结束其它元素的删除无效引用该双端队列的元素的所有指针，引用和迭代器。然而，再分配可以执行比矢量更好，因为根据他们的典型的内部结构，双端不必复制上重新分配的所有元素。内存
块时，他们不再使用可能会释放，所以双端队列的内存大小可能萎缩（这不是由标准强加的条件，但大多数实现做）

来源

2012-09-14 14:45:14

这并不像看起来那么明显。在现代架构中，'std :: list'效率非常低，一般来说，由于它的地理位置较差，并且如果内容的拷贝便宜，插入到vector的中间可能会更快，尽管拷贝。 –

此外，'deque'的内部结构要求它至少复制插入的一侧上的所有元素，如果插入不在结尾。（更一般地说，可以说'vector'需要在插入之后移动所有元素，而'deque'需要移除之前或之前的所有元素之前的所有元素。） –

Vector vs Deque插入中间

回答

相关问题