std::set_union - cppreference.com (original) (raw)

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

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

1. If [first1, last1) or [first2, last2) is not sorted with respect to operator<(until C++20)std::less{}(since C++20), the behavior is undefined.

2. If [first1, last1) or [first2, last2) is not sorted with respect to comp, the behavior is undefined.

2,4) Same as (1,3), but executed according to policy.

These overloads participate in overload resolution only if all following conditions are satisfied:

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

Contents

• 1 Parameters
• 2 Return value
• 3 Complexity
• 4 Exceptions
• 5 Possible implementation
• 6 Notes
• 7 Example
• 8 Defect reports
• 9 See also

[edit] Parameters

[edit] Return value

Iterator past the end of the constructed range.

[edit] Complexity

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

1,2) At most \(\scriptsize 2 \cdot (N_1+N_2)-1\)2⋅(N1+N2)-1 comparisons using operator<(until C++20)std::less{}(since C++20).

3,4) At most \(\scriptsize 2 \cdot (N_1+N_2)-1\)2⋅(N1+N2)-1 applications of the comparison function comp.

[edit] Exceptions

The overloads with a template parameter named ExecutionPolicy report errors as follows:

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

[edit] Possible implementation

[edit] Notes

This algorithm performs a similar task as std::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 on LessThanComparable). If any equivalent values appeared n times in the first range and m times in the second, std::merge would output all n + m occurrences whereas std::set_union would output std::max(n, m) ones only. So std::merge outputs exactly std::distance(first1, last1) + std::distance(first2, last2) values and std::set_union may produce fewer.

[edit] Example

#include #include #include #include   void println(const std::vector& v) { for (int i : v) std::cout << i << ' '; std::cout << '\n'; }   int main() { std::vector 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); }

Output:

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