merge vector into existing vector

In C++, given vector<T> src, dst, both already sorted, is there a more efficient way to merge the contents of src into dst than

size_t n = dst.size();
dst.insert(dst.end(), src.begin(), src.end());
std::in开发者_JAVA百科place_merge(dst.begin(), dst.begin() + n, dst.end());

? In the case I care about, T is a small (12-16 bytes, depending on ABI) POD structure, but each vector contains millions of elements, so the total amount of memory in play is tens to hundreds of megabytes.

---

It can be done more efficiently if T is heavy to copy and your compiler supports C++0x.

#include <iterator> // for make_move_iterator

size_t n = dst.size();

dst.insert(dst.end(),
    std::make_move_iterator(src.begin()),
    std::make_move_iterator(src.end()));

std::inplace_merge(dst.begin(), dst.begin() + n, dst.end());

Using make_move_iterator() will cause insert() to move the contents of src into dst instead of copying them.

Update:

You're dealing with POD types and you're already resizing/copying everything in the dst vector in the likely case that insert() overflows the reserve, so it could be faster to just use std::merge() into a new vector. This would avoid that initial copy AND have a better worst-case complexity:

inplace_merge() has a best case of O(n) complexity, but degrades into a worst-case O(n log n) depending on your data.

merge() has a worst-case O(n) so it is guaranteed to be at least as fast, potentially much faster. It also has move optimization built-in.

---

I would at least try:

std::vector<T> tmp;
tmp.reserve(src.size() + dst.size()); // commenters are probably right about this
std::merge(src.begin(), src.end(), dst.begin(), dst.end(), std::back_inserter(tmp));
src.swap(tmp);

But I suspect that much depends on the nature of T, the size of src and dst, and why we need to optimize.

---

If default initialization of your elements is a lot cheaper than copying, you could eliminate the insert call and resize your destination vector. Then implement your own merge, going backwards - keep iterators to the end of the source and the old end of the destination, and move or copy to the new end of the destination. When you reach the beginning of the source, you're done.