std::merge merging two std::vector coredump

Question

the following code ends up with a core dump. What do I do wrong?

std::vector<int> a;
a.push_back(1);
a.push_back(4);
a.push_back(7);
std::vector<int> b;
b.push_back(2);
b.push_back(5);
b.push_back(8);
std::vector<int> c;
c.clear();


std::merge(a.begin(), a.end(), b.begin(), b.end(), c.begin());
for (it=c.begin(); it!=c.end(); ++it)
    std::cout << *it << endl;

Is there any other merging function in the stl or in boost that I could be using?

Thanks!

Answer 1

The problem is that your c is empty because it was initialised with no elements, not to mention the unnecessary call to clear(). std::merge() takes an output iterator as its last argument. If c.begin() refers to the beginning of a std::vector that already contains enough elements, then this isn’t a problem—those elements will just be overwritten. As it is, you’re invoking undefined behaviour by writing values into memory past the end of the vector.

To ensure that c has enough space for the elements, you could do this:

c.resize(a.size() + b.size());
std::merge(a.begin(), a.end(), b.begin(), b.end(), c.begin());

However, it is more idiomatic to use a std::back_insert_iterator, an output iterator that calls push_back(). For better efficiency, you can call reserve() on the vector beforehand. This ensures that c only needs to allocate memory once, rather than as it grows during the call to std::merge(). The final solution looks like this:

#include <iterator>

// ...

c.reserve(a.size() + b.size());
std::merge(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(c));