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

Question

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?

Answer 1

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).

Answer 2

You would think that vector::insert might be able to optimize the case where it's inserting multiple items at once, but it's harder than it looks. What if the iterators are output iterators for example - there's no way of knowing ahead of time how many insertions you'll do. It's likely that the code for insert just does multiple push_backs the same as back_inserter.

Answer 3

vector::insert will probably perform better in most cases on most mainstream implementations of the C++ standard library. The reason is that the vector object has internal knowledge of the currently allocated memory buffer, and can pre-allocate enough memory to perform the entire insertion since the number of elements can be computed in advance with random-access iterators. However, std::copy along with std::back_inserter will keep calling vector::push_back, which may trigger multiple allocations.

The GNU implementation of std::vector::insert in libstdc++, for example, pre-allocates a buffer in advance if the iterator category is RandomAccessIterator. With input iterators, vector::insert may be equivalent to std::copy, because you can't determine the number of elements in advance.

Answer 4

It is not equivalent to std::copy. It is equivalent to push_back (in some sense).

Yes, std::back_inserter does the same thing, which you use with std::copy which can insert at the front also if you use std:front_inserter (though you cannot use it with std::vector). It can insert at specified iterator also if you use std::inserter instead. So you see, std::copy does thing based on what you pass as third argument.

Now coming back to the essence of the question. I think you should use insert, as it can perform better, because it may discover the number of elements it is going to insert, so it may allocate that much memory at once (if needed). In your case, it is likely to perform better, because v1 is std::vector which means it is easy to compute the number of elements in O(1) time.