使用开始时可用的所有数据构建大型（ish）无序集

Question

我有一种情况需要优化无序集的创建。预期的元素数量约为 5-25M。我的第一个想法是我应该事先准备好所有数据并做一些类似的事情

unordered_set s(data); 

代替

for (auto& elem : data)
    s.insert(elem); 

STL 无序集能否使用批量加载方法并加快其创建速度？如果我在构建表之前知道预期的元素数量，我该如何调整哈希表的参数（存储桶大小等）？

Answer 1

这个问题很广泛也很有趣。

首先，有一个特殊的方法叫做reserve——它允许你在实际插入元素之前预先为它们分配存储空间。预先分配足够的内存（并避免在插入期间重新定位）是一种非常强大的方法，通常用于大型数据集。请注意，它也可用于各种标准集装箱，其中包括vector，unordered_map等等。

其次，如果您使用的是 C++11，则在将元素插入容器时使用移动语义可能会受益（当然，考虑到一旦它们被放入集合中，您就不需要它们在您的提要中，这对于 5 到 25 百万个对象应该是正确的）。

这两种技术是一个好的开始。您可能需要通过设置不同的散列函数，甚至选择 unordered_set 的不同实现来进一步调整它。但是此时，您应该提供更多信息：您的值对象是什么，它们的生命周期是什么；您认为在您的应用中可接受的插入时间是多少。

编辑：当然这都是关于 C++11，因为 unordered_set 在它之前不可用。为我感到羞耻:)