无序集范围插入与迭代器

Question

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

vector<string> &paths // 3 milion strings

方法1：范围插入

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

方法2：迭代器

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

结果：

方法1：753毫秒

方法2：1221毫秒

==============================>

操作系统：Windows 10

IDE：视觉工作室代码

编译器：gcc版本8.1.0

标志：-O3

我试图理解为什么下面的范围插入比使用迭代器更快。 vector ＆paths // 3百万个字符串方法1：范围插入unordered_set mySet; ...

Answer 1

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

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

[还有一些其他可能的优化可以在这里完成（使用池分配器进行批量分配，执行多线程插入过程等，尽管我不确定这些是否确实完成。

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

对于unordered_set，这些优化只是对每次插入的预期O（1）成本的改进。在某些其他容器中，例如vector或deque，批量插入可以比重复的单个插入渐近地渐近，因为容器可以在批量插入期间一次移动其他元素，而不是进行大量的重复移位。

希望这会有所帮助！