向量与中间的Deque插入

Question

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

Answer 1

您可能会认为deque具有优势，因为它将数据存储成块。但是，要在恒定时间内实现operator[]，所有这些块都必须大小相同。插入或删除中间的元素仍然需要将所有的值移到一边或另一边，与vector相同。由于vector更简单，缓存的局部性更好，所以它应该领先。

Answer 2

使用标准库容器的选择条件是，您根据以下情况选择一个容器：

1. 要存储的数据类型&
2. 要对数据执行的操作类型。

如果要在中间执行大量插入操作，最好使用std::list。

如果选择只是在std::deque和std::vector之间，那么需要考虑以下几个因素：

• 通常，在deque访问元素的情况下，还有一个间接的方向，因此元素访问和deques的迭代器移动通常要慢一些。
• 在对内存块有大小限制的系统中，deque可能包含更多的元素，因为它使用了多个内存块。因此，对于deques来说，max_size()可能更大。
• Deques不提供任何支持来控制容量和重新分配的时刻。特别是，任何插入或删除除开头或结尾以外的元素都会使引用deque元素的所有指针、引用和迭代器无效。然而，重新分配可能比向量更好，因为根据其典型的内部结构，deques不必在重新分配时复制所有元素。
• 内存块在不再使用时可能会被释放，因此deque的内存大小可能会缩小(这不是标准强加的条件，但大多数实现都是这样)。

Answer 3

对于大型容器，std::deque的性能可能更好，因为它通常是作为连续数据块的链接序列实现的，而不是std::vector中使用的单个块。因此，在中间插入将减少从一个地方复制到另一个地方的数据，并可能导致更少的重新分配。

当然，这是否重要取决于容器的大小和复制存储元素的成本。有了C++11移动语义，后者的成本就不那么重要了。但是最终，唯一知道的方法是使用一个实际的应用程序进行分析。