c++ - 大型、偶尔拼接列表的数据结构选择

Question

我的情况如下。我有几个(5-15)相当长(〜500,000)的两个 float 的点列表。我需要能够快速构建它们，迭代它们(进行计算并在此过程中修改或重建它们)，然后在最后将它们拼接在一起以获得包含所有点的单一结构，然后我将不得不这样做遍历。

什么是好的结构选择？ std::list 有一个非常慢的 push_back(这是我目前的解决方案，构建列表占用了我 50% 的运行时间)，但是 std::vector 和 std::deque 似乎要花很长时间才能编译出最终列表。

编辑:我忘了提及 - 我将需要至少对每个列表进行一次排序。不确定这是否重要。

Answer 1

如果您事先知道 vector 的确切大小，则可以只创建一个大的 vector ，然后遍历该大 vector 的不同部分，例如:

std::vector<Point> data;
data.resize(totalSize); // totalSize is the sum of the sizes of the individual vectors
generatePart1(data.begin(), data.begin() + sizeOfPart1);
generatePart2(data.begin() + sizeOfPart1, data.begin() + sizeOfPart1 + sizeOfPart2);
// ...
iteratePart1(data.begin(), data.begin() + sizeOfPart1);
//...
//You don't need to splice the vectors now anymore, it's one big vector already.

如果您无法提前知道确切的尺寸，或者不喜欢这种方法，您仍然可以使用 std::vector::reserve至少提前保留大部分存储空间，然后使用智能迭代器按顺序迭代所有单个 vector 以进行拼接。