Best way to append vector to vector

Question

std::vector<int> a;
std::vector<int> b;
std::vector<int> c;

I would like to concatenate these three vectors by appending b's and c's elements to a. Which is the best way to do this, and why?

---

1) By using vector::insert:

a.reserve(a.size() + b.size() + c.size());
a.insert(a.end(), b.begin(), b.end());
a.insert(a.end(), c.begin(), c.end());
b.clear();
c.clear();

2) By using std::copy:

a.reserve(a.size() + b.size() + c.size());
std::copy(b.begin(), b.end(), std::inserter(a, a.end()));
std::copy(c.begin(), c.end(), std::inserter(a, a.end()));
b.clear();
c.clear();

3) By using std::move (from C++11):

a.reserve(a.size() + b.size() + c.size());
std::move(b.begin(), b.end(), std::inserter(a, a.end()));
std::move(c.begin(), c.end(), std::inserter(a, a.end()));
b.clear();
c.clear();

Solution 1

In my opinion, your first solution is the best way to go.

vector<>::insert is designed to add element so it's the most adequate solution.

You could call reserve on the destination vector to reserve some space, but unless you add a lot of vector together, it's likely that it wont provide much benefits: vector<>::insert know how many elements will be added, you will avoid only one reserve call.

Note: If those were vector of more complex type (ie a custom class, or even std::string), then using std::move could provide you with a nice performance boost, because it would avoid the copy-constructor. For a vector of int however, it won't give you any benefits.

Note 2: It's worth mentioning that using std::move will cause your source vector's content to be unusable.

Solution 2

Assuming you want to copy and not move, this would be the best way:

a.reserve(a.size()+b.size()+c.size()); // Reserve space first
a.insert(a.end(),b.begin(),b.end());
a.insert(a.end(),c.begin(),c.end());

If you want to move:

a.reserve(a.size()+b.size()+c.size()); // Reserve space first
a.insert(a.end(),std::make_move_iterator(b.begin()),
         std::make_move_iterator(b.end()));
a.insert(a.end(),std::make_move_iterator(c.begin()),
         std::make_move_iterator(c.end()));
b.swap(std::vector<int>()); // Clear and deallocate space
c.swap(std::vector<int>()); // Clear and deallocate space

Update: You've edited your question several times now making it somewhat of a moving target. Your first option is now very similar to my first suggestion.

Update 2: As of C++11, you may no longer have to use the "swap with empty vector" trick to clear and deallocate space, depending on your library's implementation of vector. The following may do the job in a more intuitive way:

// Empty the vectors of objects
b.clear(); 
c.clear();

// Deallocate the memory allocated by the vectors 
// Note: Unlike the swap trick, this is non-binding and any space reduction
//       depends on the implementation of std::vector
b.shrink_to_fit();
c.shrink_to_fit();

Solution 3

The first is the best choice because insert can figure out how many elements it's adding and resize the vector to fit before it starts copying. The others don't have that information, so could end up resizing after some copying, which would be slower than resizing at the start, or resizing more than once.

However, as @michaelgoldshteyn hints, since you're going to do two insertions, you can also resize the array yourself with the final size, potentially saving one resize.

Comments

[Uman]

I believe move is the best option, as it will also 'move' the object, instead of calling the copy constructor and the destructor upon the clear.

[Michael Goldshteyn]

I see that you added calls to reserve() per my answer...

[vdenotaris]

Yes, I add calls to reverse() to be thorough.

[Christian Rau]

By the way, a std::back_inserter(a) would probably be more convenient and clear than a std::inserter(a, a.end()).

[Tomáš Zato]

I love questions that answer the question I was googling. Thanks for including the source examples!

[vdenotaris]

In my work, I'm using a vector of pointers (std::vector<T_MY_OBJ*>) and I would like to have good (avoiding memory leak issues) and safe memory management.

[Michael Goldshteyn]

Your example gave a vector of ints. If you have a vector of pointers, you may want to consider using std::unique_ptr or std::shared_ptr to hold them depending on your use case, in order to handle proper cleanup.

[vdenotaris]

And, for instance, using std::move on std::map<int, My_Obj*> to do that? Are there some benefits?

[Xaqq]

Unlikely, because the types of your map are basics one: integer and pointer. If your map was std::map<int, My_Obj> (ie, not a pointer to My_Obj) then there would be some benefits, provided that your move-constructor is more efficient that your copy-constructor.

[Yakk - Adam Nevraumont]

+1 for make_move_iterator: if you have data that you aren't going to use later, move from it.

[Xaqq]

Not sure that iterating over 3 vectors would be faster. If all data are packed into one vector, they are, as you said, contiguous and its faster to access contiguous memory. However, this is too much of a micro optimization for me to talk about.

[NoSenseEtAl]

std::vector needs convenience function insert_back :) - insert where first param is fixed to .end()

[Kyle_the_hacker]

@Xaqq: Yeah actually it depends how many times you will iterate over the data... If only one time, then you should let the vectors as three different vectors; if more than two times, you should merge them.

[Christian Rau]

+1 Best compromise between clarity and allocation performance of std::vector::insert and per-element performance of std::move.

[Christian Rau]

Huh? His 2nd and 3rd solution will work, too, he doesn't have to use his 1st solution. In the same way he doesn't have to reserve anything at all, it is just an optimization. And even then, std::vector::insert with random access iterators (as those of std::vector are) will likely do a proper reserve anyway, resulting only in a single reallocation for the whole operation to be avoided by the initial reserve. "Since a std::vector has always to be contiguous in memory, you can't just move the data" - Of course the elements can be moved if the source vectors are cleared afterward anyway.

[Kyle_the_hacker]

@ChristianRau: Since he asked for "the best way to do it", I gave him the most optimized answer... Since he has to do more than one insert, it is likely that two reallocations occur. Of course you can move, but not in the meaning of C++11 (you can't use the allocated memory of your second vector as extension of your first vector): you will most likely move through copy elision.

[exa]

what's so bad about clear()?