std::set_symmetric_difference
| Defined in header <algorithm>
|
||
template< class InputIt1, class InputIt2, class OutputIt >
OutputIt set_symmetric_difference
( InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2,
OutputIt d_first );
|
(1) | (constexpr since C++20) |
template< class InputIt1, class InputIt2,
class OutputIt, class Compare >
OutputIt set_symmetric_difference
( InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2,
OutputIt d_first, Compare comp );
|
(2) | (constexpr since C++20) |
template< class ExecutionPolicy,
class ForwardIt1, class ForwardIt2, class ForwardIt3 >
ForwardIt3 set_symmetric_difference
( ExecutionPolicy&& policy,
ForwardIt1 first1, ForwardIt1 last1,
ForwardIt2 first2, ForwardIt2 last2,
ForwardIt3 d_first );
|
(3) | (since C++17) |
template< class ExecutionPolicy,
class ForwardIt1, class ForwardIt2,
class ForwardIt3, class Compare >
ForwardIt3 set_symmetric_difference
( ExecutionPolicy&& policy,
ForwardIt1 first1, ForwardIt1 last1,
ForwardIt2 first2, ForwardIt2 last2,
ForwardIt3 d_first, Compare comp );
|
(4) | (since C++17) |
Constructs a hypothetical sorted symmetric difference from two sorted source ranges [first1, last1) and [first2, last2), the difference consists of the set of elements present in exactly one of the source ranges. Copies all elements of the symmetric difference set to the destination range beginning at d_first.
For each group of equivalent elements to be included in the symmetric difference, let n1 and n2 be the numbers of elements from the two source ranges respectively:
- The first
std::min(n1, n2)elements from the first source range will be skipped, and all remaining elments will be included in the symmetric difference in order. - The first
std::min(n1, n2)elements from the second source range will be skipped, and all remaining elments will be included in the symmetric difference in order.
operator<(until C++20)std::less{}(since C++20).operator<(until C++20)std::less{}(since C++20), the behavior is undefined.comp.comp, the behavior is undefined.policy.true:
|
|
(until C++20) |
|
|
(since C++20) |
If the destination range overlaps with any of the two source ranges, the behavior is undefined.
Parameters
| first1, last1 | - | the pair of iterators defining the first source range |
| first2, last2 | - | the pair of iterators defining the second source range |
| d_first | - | the beginning of the destination range |
| comp | - | comparison function object (i.e. an object that satisfies the requirements of Compare) which returns true if the first argument is less than (i.e. is ordered before) the second. The signature of the comparison function should be equivalent to the following:
While the signature does not need to have |
| policy | - | the execution policy to use |
| Type requirements | ||
-InputIt1, InputIt2 must meet the requirements of LegacyInputIterator.
| ||
-OutputIt must meet the requirements of LegacyOutputIterator.
| ||
-ForwardIt1, ForwardIt2, ForwardIt3 must meet the requirements of LegacyForwardIterator.
| ||
-Compare must meet the requirements of Compare.
| ||
Return value
The past-the-end iterator of the destination range.
Complexity
Given
- N1 as
std::distance(first1, last1), - N2 as
std::distance(first2, last2):
operator<(until C++20)std::less{}(since C++20).comp.operator<(until C++20)std::less{}(since C++20).comp.Exceptions
- If the temporary memory resources required for parallelization are not available, std::bad_alloc is thrown.
- If an uncaught exception is thrown while accessing objects via an algorithm argument, the behavior is determined by the execution policy (for standard policies, std::terminate is invoked).
Possible implementation
| set_symmetric_difference (1) |
|---|
template<class InputIt1, class InputIt2, class OutputIt>
OutputIt set_symmetric_difference(InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2, OutputIt d_first)
{
while (first1 != last1)
{
if (first2 == last2)
return std::copy(first1, last1, d_first);
if (*first1 < *first2)
*d_first++ = *first1++;
else
{
if (*first2 < *first1)
*d_first++ = *first2;
else
++first1;
++first2;
}
}
return std::copy(first2, last2, d_first);
}
|
| set_symmetric_difference (2) |
template<class InputIt1, class InputIt2, class OutputIt, class Compare>
OutputIt set_symmetric_difference(InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2,
OutputIt d_first, Compare comp)
{
while (first1 != last1)
{
if (first2 == last2)
return std::copy(first1, last1, d_first);
if (comp(*first1, *first2))
*d_first++ = *first1++;
else
{
if (comp(*first2, *first1))
*d_first++ = *first2;
else
++first1;
++first2;
}
}
return std::copy(first2, last2, d_first);
}
|
Example
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
int main()
{
std::vector<int> v1{1, 2, 3, 4, 5, 6, 7, 8};
std::vector<int> v2{5, 7, 9, 10};
std::sort(v1.begin(), v1.end());
std::sort(v2.begin(), v2.end());
std::vector<int> v_symDifference;
std::set_symmetric_difference(v1.begin(), v1.end(), v2.begin(), v2.end(),
std::back_inserter(v_symDifference));
for (int n : v_symDifference)
std::cout << n << ' ';
std::cout << '\n';
}
Output:
1 2 3 4 6 8 9 10
Defect reports
The following behavior-changing defect reports were applied retroactively to previously published C++ standards.
| DR | Applied to | Behavior as published | Correct behavior |
|---|---|---|---|
| LWG 291 | C++98 | it was unspecified how to handle equivalent elements in the source ranges | specified |