В чем разница между std :: merge и std :: set_union?

Question

Вопрос ясен, мой google- и cplusplus.com/reference-fu меня подводят.

Answer 1

set_union будет содержать элементы, которые присутствуют в обоих наборах только один раз.Объединение будет содержать их дважды.

Оба работают на отсортированных диапазонах и возвращают отсортированный результат.

Answer 2

std::merge сохраняет все элементы из обоих диапазонов, эквивалентные элементы из первого диапазона, предшествующие эквивалентным элементам из второго диапазона в выходных данных.Если в обоих диапазонах появляются эквивалентные элементы, std::set_union берет только элемент из первого диапазона, в противном случае каждый элемент объединяется в порядке, аналогичном std::merge.

Ссылки: ISO / IEC 14882: 2003 25.3.4[lib.alg.merge] и 25.3.5.2 [lib.set.union].

Answer 3

Это проверка, которую я предложил в комментарии, который я разместил к принятому ответу (то есть, если элемент присутствует в одном из входных наборов N раз, он появится N раз в выходных данных set_union - так делает set_union не удаляйте дубликаты эквивалентных элементов так, как мы «естественно» или «математически» ожидаем - если, однако, оба входных диапазона содержат общий элемент только один раз, тогда set_union появится удалить дубликат)

#include <vector>
#include <algorithm>
#include <iostream>
#include <cassert>

using namespace std;

void printer(int i) { cout << i << ", "; }

int main() {
    int mynumbers1[] = { 0, 1, 2, 3, 3, 4 }; // this is sorted, 3 is dupe
    int mynumbers2[] = { 5 };                // this is sorted


    vector<int> union_result(10);
    set_union(mynumbers1, mynumbers1 + sizeof(mynumbers1)/sizeof(int),
              mynumbers2, mynumbers2 + sizeof(mynumbers2)/sizeof(int),
              union_result.begin());
    for_each(union_result.begin(), union_result.end(), printer);

    return 0;
}

Это напечатает: 0, 1, 2, 3, 3, 4, 5, 0, 0, 0,

Answer 4

Чтобы добавить к предыдущим ответам - учтите, что сложность std::set_union вдвое выше, чем std::merge. На практике это означает, что компаратор в std::set_union может быть применен к элементу после того, как был разыменован, в то время как с std::merge это никогда не происходит.

Почему это может быть важно? Рассмотрим что-то вроде:

std::vector<Foo> lhs, rhs;

И вы хотите создать объединение lhs и rhs:

std::set_union(std::cbegin(lhs), std::cend(lhs),
               std::cbegin(rhs), std::cend(rhs),
               std::back_inserter(union));

Но теперь предположим, что Foo не подлежит копированию или копирование очень дорого, и вам не нужны оригиналы. Вы можете подумать использовать:

std::set_union(std::make_move_iterator(std::begin(lhs)),
               std::make_move_iterator(std::end(lhs)),
               std::make_move_iterator(std::begin(rhs)),
               std::make_move_iterator(std::end(rhs)),
               std::back_inserter(union));

Но это неопределенное поведение, так как существует вероятность сравнения перемещенного Foo! Следовательно, правильное решение:

std::merge(std::make_move_iterator(std::begin(lhs)),
           std::make_move_iterator(std::end(lhs)),
           std::make_move_iterator(std::begin(rhs)),
           std::make_move_iterator(std::end(rhs)),
           std::back_inserter(union));
union.erase(std::unique(std::begin(union), std::end(union), std::end(union));

Имеет ту же сложность, что и std::set_union.

Answer 5

std::merge объединяет все элементы без удаления дубликатов, а std::set_union устраняет дубликаты. То есть последний применяет правило объединение операция теория множеств .