What is the difference between std :: merge and std :: set_union?

Question

The question is obvious, my google- and cplusplus.com/reference-fu fail.

Answer 1

set_union will only contain elements that are present in both sets once. merge will contain them twice.

Both work in sorted ranges and return a sorted result.

Answer 2

std::merge stores all elements from both ranges, equivalent elements from the first range preceding equivalent elements from the second output range. If equivalent elements are displayed in both ranges, std::set_union accepts only an element from the first range, otherwise each element is combined in order, as in std::merge .

References: ISO / IEC 14882: 2003 25.3.4 [lib.alg.merge] and 25.3.5.2 [lib.set.union].

Answer 3

std::merge merges all elements, not excluding duplicates, and std::set_union eliminates duplicates. That is, the latter applies to the union rule of the set theory operation.

Answer 4

This is the confirmation that I suggested in the comment posted in the accepted answer (i.e. if the element is present in one of the sets N times, it will appear N times at the output of set_union - therefore set_union does not delete duplicate equivalent elements the way we do " naturally "or" mathematically "we expect - if, however, both input ranges contained only one element only once, then set_union would seem to delete the duplicate)

 #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; } 

This will print: 0, 1, 2, 3, 3, 4, 5, 0, 0, 0,

Answer 5

To add to the previous answers - be careful that the complexity of std::set_union is two times less than the complexity of std::merge . In practice, this means that the comparator in std::set_union can be applied to an element after it is dereferenced, and with std::merge this will never happen.

Why can this be important? Consider something like:

 std::vector<Foo> lhs, rhs; 

And you want to create a union of lhs and rhs :

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

But now suppose that Foo not copied, or is very expensive to copy, and you do not need the originals. You might think:

 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)); 

But this behavior is undefined, since there is the possibility of moving the moved Foo ! Therefore, the correct solution:

 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)); 

Which has the same complexity as std::set_union .