矢量push_back over 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是一项代价高昂的操作.所以我认为,如果我创建一个类变量向量并且我继续填充这个向量,当我更新我的集合时,我可以完全避免这个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());

更新:

所有三个版本s1.size()的副本数量都是T.然而,当与GCC测量10^7的元素T = int,它表明了该std::vector::reserve是(因为两倍快范围施工,最快的方法std::distance的ForwardIterator小号具有线性复杂性与std::unordered_set::size具有恒定).处理较少和非常大的物体时,这种差异会减小,但它仍然存在.

第二种方式比第一种方式略慢,因为初始化元素的价值.

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