Constructs a sorted union beginning atd_first consisting of the set of elements present in one or both sorted ranges[first1, last1) and[first2, last2).

If[first1, last1) containsm elements that are equivalent to each other and[first2, last2) containsn elements that are equivalent to them, then allm elements will be copied from[first1, last1) to the output range, preserving order, and then the finalstd::max(n- m,0) elements will be copied from[first2, last2) to the output range, also preserving order.

If the output range overlaps with[first1, last1) or[first2, last2), the behavior is undefined.

[edit]Parameters

[edit]Return value

Iterator past the end of the constructed range.

[edit]Complexity

Given\(\scriptsize N_1\)N1 asstd::distance(first1, last1) and\(\scriptsize N_2\)N2 asstd::distance(first2, last2):

[edit]Exceptions

The overloads with a template parameter namedExecutionPolicy report errors as follows:

• If execution of a function invoked as part of the algorithm throws an exception andExecutionPolicy is one of thestandard policies,std::terminate is called. For any otherExecutionPolicy, the behavior is implementation-defined.
• If the algorithm fails to allocate memory,std::bad_alloc is thrown.

[edit]Possible implementation

template<class InputIt1,class InputIt2,class OutputIt>OutputIt set_union(InputIt1 first1, InputIt1 last1,                   InputIt2 first2, InputIt2 last2, OutputIt d_first){for(; first1!= last1;++d_first){if(first2== last2)returnstd::copy(first1, last1, d_first); if(*first2<*first1)*d_first=*first2++;else{*d_first=*first1;if(!(*first1<*first2))++first2;++first1;}}returnstd::copy(first2, last2, d_first);}

template<class InputIt1,class InputIt2,class OutputIt,class Compare>OutputIt set_union(InputIt1 first1, InputIt1 last1,                   InputIt2 first2, InputIt2 last2, OutputIt d_first, Compare comp){for(; first1!= last1;++d_first){if(first2== last2)// Finished range 2, include the rest of range 1:returnstd::copy(first1, last1, d_first); if(comp(*first2,*first1))*d_first=*first2++;else{*d_first=*first1;if(!comp(*first1,*first2))// Equivalent => don't need to include *first2.++first2;++first1;}}// Finished range 1, include the rest of range 2:returnstd::copy(first2, last2, d_first);}

[edit]Notes

This algorithm performs a similar task asstd::merge does. Both consume two sorted input ranges and produce a sorted output with elements from both inputs. The difference between these two algorithms is with handling values from both input ranges which compare equivalent (see notes onLessThanComparable). If any equivalent values appearedn times in the first range andm times in the second,std::merge would output alln+ m occurrences whereasstd::set_union would outputstd::max(n, m) ones only. Sostd::merge outputs exactlystd::distance(first1, last1)+std::distance(first2, last2) values andstd::set_union may produce fewer.

[edit]Example

#include <algorithm>#include <iostream>#include <iterator>#include <vector> void println(conststd::vector<int>& v){for(int i: v)std::cout<< i<<' ';std::cout<<'\n';} int main(){std::vector<int> v1, v2, dest;     v1={1,2,3,4,5};    v2={3,4,5,6,7};     std::set_union(v1.cbegin(), v1.cend(),                   v2.cbegin(), v2.cend(),std::back_inserter(dest));    println(dest);     dest.clear();     v1={1,2,3,4,5,5,5};    v2={3,4,5,6,7};     std::set_union(v1.cbegin(), v1.cend(),                   v2.cbegin(), v2.cend(),std::back_inserter(dest));    println(dest);}

1 2 3 4 5 6 7 1 2 3 4 5 5 5 6 7

[edit]Defect reports

The following behavior-changing defect reports were applied retroactively to previously published C++ standards.

[edit]See also

• In other languages

• Deutsch
• Español
• Français
• Italiano
• 日本語
• Português
• Русский
• 中文