std :: merge объединяет два std :: vector coredump

Question

следующий код заканчивается дампом ядра.Что я делаю неправильно?

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;

Есть ли какая-либо другая функция слияния в stl или в boost, которую я мог бы использовать?

Спасибо!

Answer 1

Проблема в том, что ваш c пуст, потому что он был инициализирован без элементов, не говоря уже о ненужном вызове clear(). std::merge() принимает выходной итератор в качестве последнего аргумента. Если c.begin() относится к началу std::vector, в котором уже содержит достаточно элементов, то это не проблема - эти элементы будут просто перезаписаны. На самом деле вы вызываете неопределенное поведение, записывая значения в память за концом вектора.

Чтобы в c было достаточно места для элементов, вы можете сделать это:

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

Однако более логично использовать std::back_insert_iterator, выходной итератор, который вызывает push_back(). Для повышения эффективности вы можете заранее вызвать reserve() для вектора. Это гарантирует, что c нужно выделять память только один раз, а не как она увеличивается во время вызова std::merge(). Окончательное решение выглядит так:

#include <iterator>

// ...

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

Answer 2

Вы пытаетесь сохранить результаты в c, который является пустым, и поэтому у него недостаточно места для их хранения (фактически, ему не хватает места для хранения ничего ).Попробуйте использовать back_insert_iterator, что вместо push_back элементов:

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

Answer 3

std::merge(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(c));
                                                   ^^^^^^^^^^^^^^^^^^^^^^^

Дело в том, что если вы передадите c.begin(), функция слияния начнет записывать значения в *c.begin(), *(c.begin() + 1) и т. Д., Что приведет к неопределенному поведению, включая дамп ядра.У вас есть два варианта здесь.

• Убедитесь, что c достаточно большой, чтобы вместить все значения, которые слияние собирается записать в него.Например, вы можете позвонить c.resize(a.size()+b.size()); до вызова merge
• Передать std::back_insert_iterator.Пример этого приведен в начале моего ответа.Каждый раз, когда вы делаете *it = x, где it - это back_insert_iterator, он будет push_back x в базовый контейнер.

Информацию о итераторе обратной вставки можно найти здесь .back_inserter - это просто вспомогательная функция, поэтому вы не пишете много аргументов шаблона.

Answer 4

c недостаточно велик, чтобы удержать слияние.Попробуйте:

#include <iterator>
...
std::merge(a.begin(), a.end(),
           b.begin(), b.end(),
           std::back_inserter(c));