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