What is the most efficient way to append one std::vector to the end of another?

Alex_Jenter_22046 0
Viewed 60296

Let v1 be the target vector, v2 needs to be appended to the back of it.

I'm now doing:

v1.reserve(v1.size() + v2.size()); 
copy(v2.begin(), v2.end(), back_inserter(v1));

Is this the most efficient way? Or can it maybe be done just via copying a chunk of memory? Thanks!

vector stl c++ performance
5 Answers

After a lot of arguing (and a reasonable comment from Matthieu M. and villintehaspam), I'll change my suggestion to

v1.insert( v1.end(), v2.begin(), v2.end() );

I'll keep the former suggestion here:

v1.reserve( v1.size() + v2.size() ); 
v1.insert( v1.end(), v2.begin(), v2.end() );

There are some reasons to do it the latter way, although none of them enough strong:

  • there is no guarantee on to what size will the vector be reallocated -- e.g. if the sum size is 1025, it may get reallocated to 2048 -- dependant on implementation. There is no such guarantee for reserve either, but for a specific implementation it might be true. If hunting for a bottleneck it might be rasonable to check that.
  • reserve states our intentions clear -- optimization may be more efficient in this case (reserve could prepare the cache in some top-notch implementation).
  • also, with reserve we have a C++ Standard guarantee that there will be only a single reallocation, while insert might be implemented inefficiently and do several reallocations (also something to test with a particular implementation).
user_2335220

Probably better and simpler to use a dedicated method: vector.insert

v1.insert(v1.end(), v2.begin(), v2.end());

As Michael mentions, unless the iterators are input iterators, the vector will figure out the required size and copy appended data at one go with linear complexity.

user_1556930

If you happen to use Boost you can download the development version of the RangeEx library from the Boost Vault. This lib. was accepted into Boost a while ago but so far it hasn't been integrated with the main distribution. In it you'll find a new range-based algorithm which does exactly what you want:

boost::push_back(v1, v2);

Internally it works like the answer given by UncleBens, but the code is more concise and readable.

user_2445760

If you have a vector of pod-types, and you really need the performance, you could use memcpy, which ought to be faster than vector<>.insert(...):

v2.resize(v1.size() + v2.size());
memcpy((void*)&v1.front(), (void*)&v2[v1.size()], sizeof(v1.front())*v1.size());

Update: Although I would only use this if performance is really, really, needed, the code is safe for pod types.

user_1007240
Related