unordered_set 范围插入 VS 迭代器

unordered_set range insertion VS iterator

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

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 毫秒

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

OS: Windows 10

IDE: visual studio 代码

编译器：gcc 版本 8.1.0

标志：-O3

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

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

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

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

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

希望对您有所帮助！