向量 push_back 超过 std::copy

Question

我有一个函数，它有一个无序集作为参数。因为我使用的是 openmp，所以我将这个无序集转换为 vector 。我使用 std::copy 进行此转换。

//pseudo code
func( std::unorderedset s1)
begin
    vector v1;
    std::copy(s1.begin,s2.end,std::back_inserter(v1.end());
#openmp scope
    for( i = 0 ; i < v1.size(); i++ )
    {
         //accessing v1(i)
    }
end

不过我觉得 std::copy 是一个代价高昂的操作。所以我的想法是，如果我创建一个 class 变量向量，并且在更新我的集合时不断填充这个向量，我就可以完全避免这个 std::copy 操作。由于向量的 push_back 操作的时间复杂度被分摊为 O(1)。你有什么建议？

Answer 1

std::back_insert_iterator 调用 std::vector::push_back，因此您的提议没有任何改进。

重要的是，您事先知道 v1 的大小 ，因此请利用该信息并让 std::vector 分配其存储空间仅一次 避免重新分配 std::push_back 在 v1.size() == v1.capacity().

时执行

这样做：

std::vector<T> v1;
v1.reserve(s1.size());
std::copy(s1.begin(), s2.end(), std::back_inserter(v1));

或者这个：

std::vector<T> v1(s1.size());
std::copy(s1.begin(), s2.end(), v1.begin());

或者，按照@CoryKramer 的建议，从范围 v1 惯用地构建：

std::vector<T> v1(s1.begin(), s1.end());

更新：

所有三个版本都执行 T 的 s1.size() 份数。但是，当使用 T = int 的 10^7 个元素在 GCC 上进行测量时，结果表明 std::vector::reserve 是最快的方法（速度是 range-construction 的两倍，因为 std::distance 的 ForwardIterator 具有线性复杂度，而 std::unordered_set::size 具有常数）。当处理较少和非常大的对象时，这种差异会减少，但它仍然存在。

由于 value-initializing 个元素，第二种方式比第一种方式稍慢。

结论：使用std::vector::reserve.

Answer 2

您可以使用此方法稍微提高性能：

func( std::unorderedset s1)
begin
    vector v1;
    v1.reserve(s1.size()); // HERE
    std::copy(s1.begin,s2.end,std::back_inserter(v1.end());
#openmp scope
    for( i = 0 ; i < v1.size(); i++ )
    {
         //accessing v1(i)
    }
end

然而，复制你的对象的成本是一个你不得不处理的问题

向量 push_back 超过 std::copy

vector push_back over std::copy

c++

vector

openmp

push-back