c++ - 中间插入向量与双端队列

Question

我知道当插入位于前端或末尾时，双端队列比向量更有效，如果我们必须进行指针运算，向量会更好。但是当我们必须在中间执行插入时使用哪一个。？为什么。？

Answer 1

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

Answer 2

标准库容器的选择标准是，您选择容器取决于：

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

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

如果仅在 astd::deque和a 之间进行选择，std::vector则需要考虑许多因素：

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

Answer 3

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

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

Answer 4

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

当然，这只有在您考虑大量元素时才真正重要，甚至建议运行基准测试并查看哪个在您的特定情况下效果更好。请记住，过早的优化是万恶之源。