3

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

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

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

4

6 回答 6

4

我会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 提出了一个很好的观点，那就是度量——执行会因您的标准库实现、数据大小、复制的复杂性等而发生巨大变化。

对于使用我的配置的这种大小的集合的原始指针，vector质量突变及push_back以上是std::list插入速度的 7 倍。push_back比vector' 范围插入快。

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

于 2012-02-12T08:09:15.943 回答
3

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

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

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

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

于 2012-02-12T08:03:47.947 回答
2

当您经常想在集合中间插入元素或经常删除它们时，列表很有用。然而，列表读起来很慢。

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

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

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

于 2012-02-12T08:08:02.123 回答
2

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

于 2012-02-12T08:10:19.097 回答
2

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

如果超过容器容量，也可能涉及重新分配。您可以通过确保预先::reserve设置足够的空间来防止重新分配。

您是另一个建议 - 复制到第二个std::vector/deque容器可能会更好，因为它总是可以组织以实现O(N)复杂性，但代价是临时存储两个容器。

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

总体而言，您必须进行基准测试才能真正找出“最快”的方法。

希望这可以帮助。

于 2012-02-12T08:13:20.250 回答
1

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

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

于 2012-02-12T08:11:59.823 回答