merge vector into existing vector

Question

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::inplace_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.

Answer 1

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.