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

Question

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

什么是结构的好选择？std::list速度很慢push_back（这是我当前的解决方案，构建列表占用了我 50% 的运行时间），但std::vector似乎std::deque他们需要永远编译最终列表。

编辑：我忘了提 - 我需要对每个列表至少排序一次。不确定是否重要。

Answer 1

如果您事先知道向量的确切大小，则可以只创建一个大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提前保留至少大部分存储，然后使用迭代的智能迭代器依次对所有单个向量进行拼接。