sameer karjatkar sameer karjatkar - 3 months ago 23
C++ Question

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 ?

Answer

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.

Comments