47
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();
vdenotaris
  • 13,297
  • 26
  • 81
  • 132

4 Answers4

25

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.

Xaqq
  • 4,308
  • 2
  • 25
  • 38
  • And, for instance, using `std::move` on `std::map` to do that? Are there some benefits? – vdenotaris Aug 09 '13 at 13:25
  • 1
    Unlikely, because the types of your map are basics one: integer and pointer. If your map was `std::map` (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. – Xaqq Aug 09 '13 at 13:28
20

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();
Michael Goldshteyn
  • 71,784
  • 24
  • 131
  • 181
  • In my work, I'm using a vector of pointers (`std::vector`) and I would like to have good (avoiding memory leak issues) and safe memory management. – vdenotaris Aug 09 '13 at 13:16
  • 3
    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. – Michael Goldshteyn Aug 09 '13 at 13:19
  • 2
    +1 for `make_move_iterator`: if you have data that you aren't going to use later, `move` from it. – Yakk - Adam Nevraumont Aug 09 '13 at 13:34
  • 1
    std::vector needs convenience function insert_back :) - insert where first param is fixed to .end() – NoSenseEtAl Aug 09 '13 at 13:41
  • 1
    +1 Best compromise between clarity and allocation performance of `std::vector::insert` and per-element performance of `std::move`. – Christian Rau Aug 09 '13 at 14:51
  • what's so bad about `clear()`? – exa May 14 '18 at 13:07
1

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.

Pete Becker
  • 74,985
  • 8
  • 76
  • 165
0

If you really want to append the data of b and c in vector a, you have to do insertion (which actually is your 1.):

a.reserve( a.size() + b.size() + c.size() ); // preallocate memory (see why)
a.insert( a.end(), b.begin(), b.end() );
a.insert( a.end(), c.begin(), c.end() );

Depending on the compiler std::copy (your 2.) should normally be as fast.

Since a std::vector has always to be contiguous in memory, you can't just move (as defined in C++11) and if you know the end size you have to reserve your vector (it will avoid unnecessary reallocations of your vector). But if you really worry about performance, let this as three std::vector and iterate over them when you have to read their data.

Kyle_the_hacker
  • 1,394
  • 1
  • 11
  • 27
  • 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. – Xaqq Aug 09 '13 at 13:37
  • @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. – Kyle_the_hacker Aug 09 '13 at 13:46
  • 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. – Christian Rau Aug 09 '13 at 14:59
  • @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. – Kyle_the_hacker Aug 09 '13 at 15:18