填充 unordered_set 的更有效方法？

Question

我有一个连续存储在内存中的整数数组，我想将它们全部添加到 unordered_set 集合中。

现在，我正在一次添加它们。

for (int i = 0; i < count; i++)
    collection.insert(pi[i]);

有什么方法可以更有效地做到这一点？

我意识到项目在集合中不是连续存储的，所以它不会像将数组交给集合那样简单。但这可以以某种方式优化吗？

Answer 1

unordered_set 有一个构造函数，它接受一系列元素来初始添加它们：

template< class InputIt >
unordered_set( InputIt first, InputIt last,
           size_type bucket_count = /*implementation-defined*/,
           const Hash& hash = Hash(),
           const key_equal& equal = key_equal(),
           const Allocator& alloc = Allocator() );

所以您可以只做 collection = std::unordered_set{ p, p + count }; 并留待实施。

正如其他用户在评论中指出的那样，insert 也有一个重载，它的取值范围是：

template< class InputIt >
void insert( InputIt first, InputIt last );

所以，就像调用构造函数一样，你可以这样做，collection.insert(p, p + count);

不能保证这种重载会更有效，因为平均而言，这两种重载的复杂度是线性的，而且只是一个接一个地插入元素。

其实，如果我们研究一下insert在MSVC中是如何实现的，其实很简单

template<class _Iter>
void insert(_Iter _First, _Iter _Last)
{   // insert [_First, _Last) at front, then put in place
    _DEBUG_RANGE(_First, _Last);
    for (; _First != _Last; ++_First)
        emplace(*_First);
}

所以没有针对这种情况进行优化。

我认为，最好的方法是调用 reserve，如果您知道要添加的元素的数量，并且如果有很多冲突（不会有对于整数），也许修改 bucket_count.

Answer 2

使用基于范围的构造函数或插入方法将简洁优雅，但可能与您的方法一样高效。原因是传递给这些函数的迭代器是输入迭代器而不是随机迭代器。因此，无法计算范围的长度，当集合的负载因子变高时，必须通过定期重新散列来逐一插入元素。

考虑调用 std::unordered_set 的 reserve 方法。

collection.reserve(pi.size());
collection.insert(pi.begin(), pi.end());

编辑：正如评论中提到的，人们还可能担心将插入的元素一一散列的效率。然后能够执行某种批量插入将是有效的。但是，在 OP 的情况下，元素是整数，在 std::hash 的大多数（如果不是全部）实现中恰好使用恒等函数进行散列，这不会花费那么多；）。实际上，它是随机整数可以获得的最佳哈希函数。在 "organized" 集合的情况下，其他哈希函数可能更合适。

编辑2：评论部分现在正在猜测什么是插入方法的更好实现。我认为基于范围的插入重载需要输入迭代器，所以是的，您实际上可以传递任何非输出迭代器。还要看一下范围插入的最坏情况复杂度：您会看到它被指定为允许一个一个地插入元素。最后，看一下 insert 方法的一些实现，您会发现随机访问迭代器没有特定的重载。这是有道理的，因为没有理由在 insert 方法中强加额外的检查，而 reserve 方法在这里用于我们想要至少将容器设置为给定容量的情况。基于此，上面的答案很可能是基于 stdlib 实际实现的最佳技术。

填充 unordered_set 的更有效方法？

More efficient way to populate unordered_set?

c++

visual-c++

stl

unordered-set