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

Question

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

3

我不知道确切的数字，但我会尽力而为。我有一个在一开始就被填充了10,000个元素的双向队列(deque)。然后我扫描每个元素，并且每20个元素就需要插入一个新的元素。这个插入将发生在当前位置和可能一个元素之前。

我确实不需要记住位置，但我也不需要随机访问。我希望插入速度快。在插入方面，deque和vector是否需要付出很高的代价？我应该使用链表(list)吗？

我的另一个选择是拥有第二个双向队列列表，在遍历每个元素时将其插入到另一个双向队列列表中，除非我需要进行上述插入操作。由于这是一个性能密集型应用程序，因此这需要很快速。但是我正在使用大量指针（每个元素都是指针），这使我感到不安，但没有其他办法，所以我应该假设L1缓存总是会错过吗？

- user34537

6个回答

3

首先，回答所有关于性能的问题的答案都是“进行基准测试”。始终如此。现在...

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

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

至于缓存局部性，vector是您可以得到的最好的（连续的内存），但是您说您关心的是插入而不是查找；在我的经验中，当情况如此时，您不关心扫描到转储时缓存变得多热，因此list的差劲行为并不太重要。

- Borealid

1

我不同意你的观点。如果我们谈论在随机位置插入，向量始终是线性的。只有当你在容器末尾进行插入时，向量才始终以摊销速度保持恒定。在这种情况下，向量的性能将非常出色。 - Boris Strandjev

@BorisStrandjev 我明确限定了我的陈述 - 当您调用reserve以大于向量大小的容量时，下一个插入到末尾将是常数时间。这是C++标准的一部分。而“平摊常数”并不意味着特定的插入是常数时间 - 这就是我所说的。 - Borealid

你认为使用列表比起在遍历过程中构建第二个容器（可能是向量）更好吗？ - user34537

@Borealid - 确实，我错过了“在结尾处”的短语。也许因为它是粗体？然而，在这种情况下，我认为我们更担心一系列操作的摊销速度，而不是单个操作。此外，我不明白为什么有人会在这种情况下调用reserve，因为容器的默认行为已经使我们达到了相同的时间复杂度，而且没有人必须考虑首先要保留多少元素（更不用说当保留用完时还要保留多少元素）。 - Boris Strandjev

1

关于deque的评论是错误的。当容量已满时，只需分配另一个“页面”，不需要复制先前的元素。 deque 基本上是指向包含固定数量元素的页面的指针数组。 - Xeo

@Xeo 你说得对，我忘记了 deque 不会将所有元素放在一起。已更正。 - Borealid

2

列表在需要经常在集合中间插入元素或频繁删除元素时很有用，但是读取速度较慢。

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

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

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

- Paul Manta

2

您可以选择两种方法：列表始终是在随机位置插入时的选项，但是由于您必须单独分配每个元素，这也会导致某些性能问题。另一种在deque中就地插入的选项也不好-因为您将为每个插入付出线性时间。也许您在新deque中插入的想法在这里是最好的-您支付了两倍的内存，但是另一方面，您总是在第二个deque的末尾或前一个元素处进行插入-这都可提供常数平均时间，并且仍然具有良好的容器缓存。

- Boris Strandjev

2

std::vector/deque::insert等函数所做的复制次数与插入位置后面的元素数量成比例（需要移动的元素数量）。对于std::vector，最坏情况是在容器前面插入，时间复杂度为O(N)。如果要插入M个元素，则最坏情况的时间复杂度为O(M*N)，不是很好。

如果超出了容器的容量，就可能涉及到重新分配内存。你可以通过确保预先使用::reserve来避免重新分配。

另一个建议是将数据复制到第二个std::vector/deque容器中，这样始终可以组织以实现O(N)的复杂度，但代价是暂时存储两个容器。

使用std::list可以实现原地O(1)插入，但代价是额外的内存开销（存储链表指针等）和降低的内存局部性（列表节点不是连续分配的）。您可以通过使用池化内存分配器（例如 Boost pools）来提高内存局部性。

总的来说，您需要进行基准测试以确定哪种方法是“最快”的。

希望这能帮到您。

- Darren Engwirda

有趣的是，人们说我会支付两个容器的成本，但我不知道一个 list<void*> 是否和 2 个 vector<void*> 一样大。 - user34537

2

@acidzombie24：我预计大多数列表实现每个节点都包含两个指针+实际数据，所以内存使用的粗略估计将是：2个向量=2 * N * sizeof(data_type)。1个列表将是：N * sizeof(data_type) + 2 * N * sizeof(void *)。如果你的data_type大小很小（我认为你说它只是一个指针），那么列表可能会使用更多内存... - Darren Engwirda

1

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

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

- celtschk

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- justin · Accepted Answer

在这种情况下，我会建议使用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提出了一个很好的观点，即测量 - 执行方式取决于您的std库实现、数据大小、复制的复杂度等因素，因此会有显著差异。

对于这种规模的集合的原始指针和我的配置，上面的vector大规模突变和push_back比std::list插入快7倍。push_back比vector的范围插入更快。

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