c++ - 进行少量插入时应该使用哪个 STL 容器？

Question

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

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

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

Answer 1

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

更新

它将采用以下一般形式:

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 提出了一个很好的观点，即衡量——执行会根据您的 std 库实现、数据大小、复制的复杂性等而有很大差异。

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

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