c++ - 填充 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。