c ++容器在向末尾添加元素时非常有效

Question

我一直是运行一个用于科学目的的 c++ 程序，现在我正在考虑优化它。

瓶颈似乎是我需要堆叠整数对的函数。他们的数量从一开始就不可能知道，我一直在使用一个包含两个 ints 的自定义结构的 std::vector。是否有更高效的数据容器用于在末尾重复添加元素？我应该将它与两个 ints 一起使用，而不是一对或自定义结构吗？

编辑：在对我的程序进行计时和分析后，我可以说，就我的使用而言，vector 比 deque 稍快（仅快 3%）。我的外行结论是 CPU 很好地利用了数据的连续性。优化对我来说比以往任何时候都更像魔法！对于那些可能有帮助的人：我实际上通过从 STL C++ 11 随机数生成器切换到 BOOST 生成器显着改善了我的运行时间。

Answer 1

您必须执行的重新分配的对数成本可以说是无关紧要的。但是，您可以考虑使用 std::deque 来保证在前端和末尾插入 O(1)。您会失去连续性，但一些缓存友好性得以保留。 deque 通常是一个不错的权衡，尤其是当你需要从前面弹出时。

同时考虑估计向量将存储的元素数量，并使用 reserve。但是要注意不要浪费太多内存，否则会适得其反。

Answer 2

正如gd1已经提到的，std::deque（双端队列）允许在两端进行快速插入和删除。此外，双端队列两端的插入和删除永远不会使指针或引用无效。

在您的情况下，您可以使用 std::deque 和 std::pair（在 <utility> 中定义）以满足您的需要：

// Small example:
deque<pair<int, int>> deq;
deq.push_back({1234, 4321});
cout << deq.at(0).first << " " << deq.at(0).second;

// using 'at' above, should normally be inside a try block as it may throw 
// out_of_range exception

c ++容器在向末尾添加元素时非常有效

c++ container very efficient at adding elements to the end

c++

containers

vector