vector push_back over std::copy

问题:

I have a function which has an unordered set as a parameter . Since I am using openmp I am converting this unordered set to vector . I use a std::copy for this conversion .

//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

However I feel std::copy is a costly operation . So what I think is, if I create a class variable vector and I keep populating this vector as and when I am updating my set , I can completely avoid this std::copy operation . Since the time complexity of push_back operation of a vector is amortized O(1). What do you suggest ?

回答1:

std::back_insert_iterator calls std::vector::push_back, so your proposal doesn't improve anything.

What is important, is that you know the size v1 will have beforehand, so make use of that information and make std::vector allocate its storage only once to avoid reallocations std::push_back does when v1.size() == v1.capacity().

Do this:

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

or this:

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

or, as suggested by @CoryKramer, idiomatically constructing v1 from a range:

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

Update:

All three versions do the s1.size() number of copies of T. However, when measured on GCC with 10^7 elements of T = int, it showed up that the std::vector::reserve was the fastest method (twice as fast as range-construction, because of std::distance of ForwardIterators having linear complexity versus std::unordered_set::size having constant). This difference will diminish when dealing with fewer and very large objects, but it'll still exist.

The second way was just slightly slower than the first, because of value-initializing the elements.

Conclusion: use std::vector::reserve.

回答2:

You could boost performance a bit using this:

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

However, the cost of copying your object is a problem you have to deal with it