c++ - 向量与集合效率

Question

我正在处理一个大型数据集。在将元素一个接一个地插入到集合或向量中时，我遇到了以下困惑（在 C++ 中）：

• 是不是应该在插入前给向量预留足够的空间，然后再一个一个地添加到向量中？
• 或者，我应该将元素一个接一个地插入到一个集合中（因为插入到一个集合中比插入一个向量快），然后立即将该集合插入到一个向量中？

哪一个会更省时？

标签： c++vectortimeset

Answer 1

是不是应该在插入前给向量预留足够的空间，然后再一个一个地添加到向量中？

是的。通过为所有需要的元素分配空间，vector您将避免额外的内存分配和内存复制。vector仅当您不需要任何特定顺序的元素并且仅将元素添加到vector. 在中间某处插入元素效率非常低，因为vector将所有元素存储在连续内存中，因此需要在插入新元素之前将插入点之后的所有元素移开。

或者，我应该将元素一个接一个地插入到一个集合中（因为插入到一个集合中比插入一个向量快），然后立即将该集合插入到一个向量中？

如果您需要元素按特定顺序排列，那么您应该使用set. 该集合将有效地将元素放置到“正确”的位置，假设您的元素是可以set理解的类型（例如，数字类型或string），否则您可能需要编写自己的比较函数。或者，如果您有更复杂的数据但可以识别可排序的键值，那么您可能需要查看map而不是set. - 之后，您不能vector从set“一次”初始化 a；您需要遍历set并附加到vector.

哪一个会更省时？

考虑到您有大量数据作为输入并假设数据是随机顺序的：

如果您不关心元素的顺序，那么调用push_back向量很可能会更快。

如果您打算在中间的某处插入元素，那么set很可能会更快，即使您需要vector在第二步中将数据传输到 a 也是如此。

所有这些都取决于数据的类型、您可能想要执行的潜在比较、标准库和编译器的实现。

既然您知道预期的结果，我建议您两者都尝试。测试和测量！