当进行少量插入时，我应该使用哪个 stl 容器？

Question

我不知道我的确切数字，但我会尽力而为。我有一个 10000 个元素的双端队列，它在开始时就已填充。然后我扫描每个元素，并让我需要的每 20 个元素插入一个新元素。插入将发生在当前位置，并且可能向后移动一个元素。

我并不完全需要记住该位置，但我也并不完全需要随机访问。我想要快速插入。双端队列和向量在插入时是否要付出沉重的代价？我应该使用列表吗？

我的另一个选择是拥有第二个双端队列列表，当我遍历每个元素时，将其插入到另一个双端队列列表中，除非我需要执行我正在谈论的插入。这确实需要很快，因为它是一个性能密集型应用程序。但我使用了很多指针（每个元素都是一个指针），这让我很不安，但没有办法解决这个问题，所以我应该假设 L1 缓存总是会丢失？

Answer 1

在这种情况下，我将从 std::vector 开始，但是使用第二个 std::vector 进行大规模突变，适当地 Reserve()，然后 swap() 向量。

更新

它将采用以下一般形式：

std:vector<t_object*> source; // << source already holds 10000 elements

std:vector<t_object*> tmp;

// to minimize reallocations and frees to 1 and 1, if possible.
// if you do not swap or have to grow more, reserving can really work against you.
tmp.reserve(aMeaningfulReserveValue);

while (performingMassMutation) {
  // "i scan through each element and lets every 20 elements"
  for (twentyElements)
    tmp.push_back(source[readPos++]);

  // "every 20 elements i'll need to insert an new element"
  tmp.push_back(newElement);
}

// approximately 500 iterations later…

source.swap(tmp);

Borealid提出了一个很好的观点，即测量 - 执行情况根据您的标准库实现、数据大小、复制复杂性而有很大差异， 等等。

对于具有 my 配置的这种大小的集合的原始指针，上面的 vector 质量突变和 push_back 比 std 快 7 倍： :list 插入。 push_back 比 vector 的范围插入更快。

正如 Emile 在下面指出的那样，std::vector::swap() 不需要移动或重新分配元素——它只需交换内部元素（假设分配器是相同类型）。

Answer 2

首先，所有性能问题的答案都是“对其进行基准测试”。总是。现在...

如果您不关心内存开销，也不需要随机访问，但您确实关心恒定时间插入，list可能适合您。

当有足够的容量时，std::vector 将在末尾进行恒定时间插入。当超出容量时，需要线性时间复制。 deque 更好，因为它链接离散分配，避免完整复制，并让您也可以在前面进行常量时间插入。随机插入（每 20 个元素）始终是线性时间。

至于缓存局部性，向量是你能得到的最好的（连续内存），但你说你关心插入而不是查找；根据我的经验，在这种情况下，您并不关心扫描转储时缓存的温度，因此 list 的不良行为并不重要。

Answer 3

当您经常想要在集合中间插入元素或经常删除它们时，列表非常有用。然而，列表的读取速度很慢。

向量的读取速度非常快，并且当您只想在集合末尾添加或删除元素时速度非常快，但是当您在中间插入元素时它们非常慢。这是因为它必须将所需位置之后的所有元素移动一个位置，以便为新元素腾出空间。

双端队列基本上是可以用作向量的双向链表。

如果你不需要在集合中间插入元素（你不关心顺序），我建议你使用向量。如果您可以从一开始就估算出向量中将引入的元素数量，您还应该使用 std::vector::reserve 从一开始就分配必要的内存。您传递给 reserve 的值不需要精确，只需近似即可；如果它小于需要的大小，矢量将在必要时自动调整大小。

Answer 4

您可以采用两种方式：列表始终是随机位置插入的选项，但是当您单独分配每个元素时，这也会导致一些性能影响。在双端队列中就地插入的另一种选择也不好 - 因为您将为每次插入付出线性时间。也许您插入新双端队列的想法在这里是最好的 - 您付出了两倍的内存，但另一方面，您总是在第二个双端队列的末尾或之前的一个元素处进行插入 - 这一切都给出了恒定的摊销时间，并且您仍然对容器进行了良好的缓存。

Answer 5

std::vector/deque ::insert 等完成的副本数量与插入位置和容器末尾之间的元素数量成正比（需要移动到的元素数量）腾出空间）。 std::vector 最坏的情况是 O(N) - 当您在容器的前面插入时。如果您插入 M 元素，最坏的情况是 O(M*N)，这不太好。

如果超出集装箱容量，还可能涉及重新分配。您可以通过确保预先 ::reserve 保留足够的空间来防止重新分配。

您还有其他建议 - 复制到第二个 std::vector/deque 容器可能会更好，因为它始终可以组织起来以实现 O(N) 复杂性，但是以临时存放两个集装箱为代价。

使用 std::list 将允许您实现就地 O(1) 插入，但代价是额外的内存开销（存储列表指针等）和减少内存局部性（列表节点不是连续分配的）。您可以通过使用池内存分配器来改善内存局部性（Boost 池也许？）。

总的来说，您必须进行基准测试才能真正找出哪种方法是“最快”的。

希望这有帮助。

Answer 6

如果您需要在中间快速插入，但不关心随机访问，vector 和 deque 绝对不适合您：对于这些，每次插入内容时，该元素与末尾之间的所有元素都必须移动。在内置容器中，list 几乎肯定是您的最佳选择。然而，对于您的场景来说，更好的数据结构可能是 VList 因为它提供了更好的缓存局部性，但是C++ 标准库不提供该功能。维基百科页面链接到 C++ 实现，但是从界面的快速视图来看，它似乎并不完全兼容 STL；我不知道这对你来说是否是一个问题。

当然，最终确定哪个是最佳解决方案的唯一方法是衡量性能。