2

Например у меня есть два multiset< int > a, b; и я хочу воссоединить их в один multiset< int > c; Можно ли это сделать? Если можно то пожалуйста напишите пример. Спасибо заранее :)

5
  • В зависимости от того, насколько нужна скорость. И нужны ли контейнеры a и b. Есть просто merge (с++17) https://en.cppreference.com/w/cpp/container/multiset/merge, работает за nlog(n + m). Хорош, если a и b больше не нужны и один из контейнеров сильно больше другого. Иначе можно сделать за n + m. Дело в том, что если строить multiset из у порядочного массива, он строится линейно от размера массива. Взять например конструктор template< class InputIterator > multiset( InputIterator first, InputIterator last) 11 июл 2019 в 5:18
  • Остаётся только написать класс итератора, который принимает 2 диапазона итераторов с обоих multiset, но мержит их не сразу, а по ходу вызова операторов ++ и * двигает и возвращает наибольшее значение. Сменить 2 отсортированных массива О (n + m) 11 июл 2019 в 5:31
  • Если лень писать итератор, то можно с помощью std::merge смержить 2 multiset сначала в vector, и в конструктор multiset передавать vector.begin(), vector.end() 11 июл 2019 в 5:38
  • Функции merge вполне достаточно для моих целей и оказался легок в использовании, а контейнеры a и b мне нужны для дальнейшего использования. Спасибо огромное)
    – Anushervon
    11 июл 2019 в 5:41
  • merge - не самый эффективный и не самый короткий в смысле текста способ. Но, конечно, если устраивает, то никаких вопросов :)
    – Harry
    11 июл 2019 в 6:51

2 ответа 2

2

Функция insert контейнера multiset умеет вставлять в него произвольные диапазоны элементов, задаваемые начальным и конечным итератором. Но такая вставка рассчитана но более общий случай: произвольный, никак не упорядоченный диапазон.

В вашем же случае оба multiset упорядочены по тому же компаратору. В такой ситуации заманчиво было бы воспользоваться этой упорядоченностью для повышения эффективности вставки. Такую возможность предоставляет метод insert для вставки одного элемента с хинтом. Если новый элемент вставляется в multiset непосредственно перед хинт-позицией, то вставка выполняется за амортизированное константное время. В простейшем виде это будет выглядеть так

multiset<int> c = a;

auto it_hint = c.begin();
for (const int &src : b)
{
  it_hint = c.insert(it_hint, src);
  ++it_hint;
}

Но еще лучше было бы применить обычный алгоритм слияния двух упорядоченных последовательностей

multiset<int> c;
std::merge(a.begin(), a.end(), b.begin(), b.end(), std::inserter(c, c.end()));

Каков будет эффект от такой оптимизации - зависит от тяжести единичной операции сравнения, повторяемости элементов multiset, взаимного распределения элементов двух исходных наборов, от накладных расходов, определяемых качеством реализации, и т.п. Я замечаю, что доступные мне стандартные реализации std::merge (или std::insert_iterator?) где-то тратят на что-то время и вариант с std::merge оказывается немножко медленнее варианта с прямым insert.

Но достаточно ту же идею реализовать явно

void my_merge(const S& a, const S& b, S& c)
{
  auto ita = a.begin(), itae = a.end();
  auto itb = b.begin(), itbe = b.end();
  auto itce = c.end();

  if (ita != itae && itb != itbe)
    do
      if (*ita <= *itb)
      {
        c.insert(itce, *ita);
        if (++ita == itae)
          break;
      }
      else
      {
        c.insert(itce, *itb);
        if (++itb == itbe)
          break;
      }
    while (true);

  for (; ita != itae; ++ita)
    c.insert(itce, *ita);

  for (; itb != itbe; ++itb)
    c.insert(itce, *itb);
}

как вариант со слиянием начинает выигрывать уверенно в MSVC. В GCC такой вариант проигрывает при высокой вариабельности элементов multiset. Но достаточно подавить вариабельность элементов, как вариант со слиянием начинает побеждать и в GCC.

Алгоритмическое превосходство варианта со слиянием основано на уменьшении количества сравнений, поэтому чисто ради эксперимента интересно посмотреть, что произойдет в варианте с более "тяжелым" сравнением. Возьмем multiset из std::array<int, 10> с небольшой вариабельностью элементов - и вот уже вариант со слиянием побеждает намного более явно.

Чего тут действительно не хватает - это возможности прямой вставки в multiset без проверки правильности хинта. На эту проверку тратится время, но метода вставки, в котором multiset бы "верил джентльменам на слово", к сожалению нет. Если бы таковой имелся, то вариант со слиянием был бы очевидным и абсолютным чемпионом.

При этом, как уже сказано выше, работают все хорошо известные классические соображения для выбора алгоритма: слияние двух упорядоченных последовательностей длин N и M делается за время O(N + M), а общая поэлементная вставка одной последовательности в другую делается за время O(N * log M). Для последовательностей "почти одинаковой" длины выигрывает слияние, для последовательностей "очень разной" длины выигрывает вставка более короткой в более длинную.

13
  • 1
    насколько я знаю, c.insert(b.begin(),b.end()) выполняет то же самое 11 июл 2019 в 5:25
  • @AR Hovsepyan: Какое именно "то же самое"? Самый оптимальный вариант - именно std::merge. Но c.insert(b.begin(),b.end()) не может такого делать, ибо для std::merge требуется упорядоченный диапазон, а c.insert об упорядоченности диапазона ничего не знает. Хотя, конечно, может проверять на лету... 11 июл 2019 в 5:31
  • 3
    Не согласен, не может стандартный альгоритм быть оптимальнее метода стандартного контейнера. Каждый метод класса использует свое внутреннее представление, и если этот метод должен использовать другие методы, чтобы быть оптимальным, или если другой альгоритм круче собственного метода, значит метод реализован не достаточно эффективно. Не думаю, что вы сомневаетесь в хорошей реализации методов стандартного контейнера... 11 июл 2019 в 5:43
  • @Дмитрий Зиненко: О чем вы? std::merge всегда сам работает за O(n + m) и критически завязан на отсортированность входных последовательностей. Если, как обещается, вставка с хинтом c.end() будет проходить за O(1), то весь вариант с std::merge дает O(n + m), что является оптимальным вариантом для последовательностей "примерно одинаковой" длины. 11 июл 2019 в 6:27
  • 3
    @ARHovsepyan Вы правы, merge проигрывает - см. мой дополненный ответ...
    – Harry
    11 июл 2019 в 6:53
2

Если очень нужно именно в новый - то сначала скопировать один из исходных, а потом обычный insert.

int main(int argc, const char * argv[])
{
    multiset<int> a = { 1, 2, 3, 3 };
    multiset<int> b = { 2, 3, 4, 4 };

    multiset<int> c = a;
    c.insert(b.begin(),b.end());

    for(auto i: c)
        cout << i << " ";
    cout << "\n";
}

Update

Как обычно, ставим эксперимент...

Код эксперимента вкратце -

multiset<int> HW(const multiset<int>& a, const multiset<int>& b)
{
    multiset<int> c (a);
    c.insert(b.begin(),b.end());
    return c;
}

multiset<int> AnT(const multiset<int>& a, const multiset<int>& b)
{
    multiset<int> c = a;

    auto it_hint = c.begin();
    for (const int &src : b)
    {
        it_hint = c.insert(it_hint, src);
        ++it_hint;
    }
    return c;
}

multiset<int> AnTmerge(const multiset<int>& a, const multiset<int>& b)
{
    multiset<int> c;
    std::merge(a.begin(), a.end(), b.begin(), b.end(), std::inserter(c, c.end()));
    return c;
}

...

multiset<int> a;
multiset<int> b;

for(int i = 0; i < 1000'000; ++i)
{
    a.insert(rand());
    b.insert(rand());
}

multiset<int> c, d, e;

{
    muTimer mt;
    c = HW(a,b);
    mt.stop();
    cout << mt.duration() << endl;
}

{
    muTimer mt;
    d = AnT(a,b);
    mt.stop();
    cout << mt.duration() << endl;
}

{
    muTimer mt;
    e = AnTmerge(a,b);
    mt.stop();
    cout << mt.duration() << endl;
}

Результаты трех запусков на VC++ 2017 на моей машине:

375749    385684    393137
415450    419331    442624
556450    567419    602691

Результаты на GCC и полный код см. здесь.

Т.е. лучше всего - обычный insert для диапазона, чуть-чуть хуже поэлементно с подпихиванием руками (подсказкой), и еще хуже - merge...

Update 2

Каюсь, обнаружил у себя одну очепятку. Так что на самом деле результат с подсказкой оказывается немного лучшим просто вставки, но merge остается худшим решением... Мои извинения за небольшое введение в заблуждение.

Зато пришла в голову еще одна (реально работающая) оптимизация моего метода - копировать большее множество, а добавлять элементы из меньшего.

3
  • Harry, несущественно, но вы забыли возвращать значение из main 11 июл 2019 в 5:51
  • 3
    @ARHovsepyan Совершенно несущественно, ибо стандарт такое вполне разрешает...
    – Harry
    11 июл 2019 в 6:09
  • @ARHovsepyan собственно, вот
    – αλεχολυτ
    11 июл 2019 в 15:45

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.