# std::set_symmetric_difference

From cppreference.com
< cpp‎ | algorithm

Defined in header `<algorithm>` |  |
| (1) |
template< class InputIt1, class InputIt2, class OutputIt > OutputIt set_symmetric_difference( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first ); |  | (until C++20)
template< class InputIt1, class InputIt2, class OutputIt > constexpr OutputIt set_symmetric_difference( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first ); |  | (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 ); | (2) | (since C++17)
| (3) |
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 ); |  | (until C++20)
template< class InputIt1, class InputIt2, class OutputIt, class Compare > constexpr OutputIt set_symmetric_difference( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first, Compare comp ); |  | (since C++20)
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)

Computes symmetric difference of two sorted ranges: the elements that are found in either of the ranges, but not in both of them are copied to the range beginning at `d_first`. The resulting range is also sorted.

If some element is found `m` times in `[first1, last1)` and `n` times in `[first2, last2)`, it will be copied to `d_first` exactly std::abs(m-n) times. If `m>n`, then the last `m-n` of those elements are copied from `[first1,last1)`, otherwise the last `n-m` elements are copied from `[first2,last2)`. The resulting range cannot overlap with either of the input ranges.

1) Elements are compared using `operator<` and the ranges must be sorted with respect to the same.
3) Elements are compared using the given binary comparison function `comp` and the ranges must be sorted with respect to the same.
2,4) Same as (1,3), but executed according to `policy`. This overload only participates in overload resolution if std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> is true

### Parameters

first1, last1 | - | the first sorted range of elements
first2, last2 | - | the second sorted range of elements
policy | - | the execution policy to use. See execution policy for details.
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: bool cmp(const Type1 &a, const Type2 &b); While the signature does not need to have const &, the function must not modify the objects passed to it and must be able to accept all values of type (possibly const) `Type1` and `Type2` regardless of value category (thus, Type1 & is not allowed, nor is Type1 unless for `Type1` a move is equivalent to a copy (since C++11)). The types Type1 and Type2 must be such that objects of types InputIt1 and InputIt2 can be dereferenced and then implicitly converted to both Type1 and Type2. ​
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.

### Return value

Iterator past the end of the constructed range.

### Complexity

At most 2·(N1+N2-1) comparisons, where N1 = std::distance(first1, last1) and N2 = std::distance(first2, last2).

### 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.

### Possible implementation

First version
    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);
    }
Second version
    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

Run this code

    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <iterator>
    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 << ' ';
    }

Output:

    1 2 3 4 6 8 9 10

### See also

includes | returns true if one set is a subset of another (function template)
set_difference | computes the difference between two sets (function template)
set_union | computes the union of two sets (function template)
set_intersection | computes the intersection of two sets (function template)

Retrieved from "https://en.cppreference.com/mwiki/index.php?title=cpp/algorithm/set_symmetric_difference&oldid=103690"