c++ - unordered_set 范围插入 VS 迭代器

Question

我试图理解为什么下面的范围插入比使用迭代器更快。

vector<string> &paths // 3 milion strings

方法一:范围插入

unordered_set<string> mySet;
mySet.insert(paths.begin(), paths.end());

方法二:迭代器

vector<string>::iterator row;
for (row = paths.begin(); row != paths.end(); row++)
{
  mySet.insert(row[0]);
}

结果:

方法 1:753 毫秒

方法 2:1221 毫秒

==============================

操作系统:Windows 10

IDE: Visual Studio Code

编译器:gcc 版本 8.1.0

标志:-O3

Answer 1

直觉上，范围插入过程应该更快。例如，假设您想插入一百万个元素。如果做范围插入，集合可以

1. 计算总共要插入多少个元素，看看需要多少空间；
2. 分配一个足够大的桶数组，以将负载因子保持在适当的范围内，可能会将所有旧元素移动到新表上；然后
3. 插入所有元素。

还有一些可能的优化可以在这里完成(使用池分配器进行批量分配，执行多线程插入过程等)，但我不确定这些是否真的完成了。

另一方面，如果一次插入一个东西，则每个步骤都需要执行一百万次。这意味着分配中间桶数组会浪费时间和空间，这些桶最终不会被使用，但实现无法告诉它们不会被使用，因为实现必须在每一步都保持良好状态。

对于 unordered_set，这些优化只是对每次插入的预期 O(1) 成本的改进。在其他一些容器中，例如 vector 或 deque，批量插入比重复的单个插入快得渐进，因为容器可以在批量插入期间移动其他元素一次，而不是做很多反复轮类。

希望这对您有所帮助!