Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is inserting in the end equivalent to std::copy()?

Consider following two ways to append elements into a vector

std::vector<int> vi1(10,42), vi2;

vi2.insert(vi2.end(),vi1.begin(),vi1.end());
<OR>
std::copy(vi1.begin(),vi1.end(),std::back_inserter(vi2));

std::copy version looks cleaner and I don't have to type vi2 twice. But since it is a generic algorithm while insert is a member function, could insert perform better than std::copy or does it do the same thing?

I can benchmark myself but I have to do it for every vector for every template type. Has anyone done already?

like image 537
balki Avatar asked Jan 17 '13 15:01

balki


1 Answers

There are some subtle differences. In the first case (std::vector<>::insert) you are giving a range to the container, so it can calculate the distance and perform a single allocator to grow to the final required size. In the second case (std::copy) that information is not directly present in the interface, and it could potentially cause multiple reallocations of the buffer.

Note that even if multiple reallocations are needed, the amortized cost of insertion must still be constant, so this does not imply an asymptotic cost change, but might matter. Also note that a particularly smart implementation of the library has all the required information to make the second version as efficient by specializing the behavior of std::copy to handle back insert iterators specially (although I have not checked whether any implementation actually does this).

like image 148
David Rodríguez - dribeas Avatar answered Oct 17 '22 12:10

David Rodríguez - dribeas