26 Algorithms library [algorithms]

26.8 Sorting and related operations [alg.sorting]

26.8.7 Set operations on sorted structures [alg.set.operations]

26.8.7.6 set_symmetric_difference [set.symmetric.difference]

template<class InputIterator1, class InputIterator2,
         class OutputIterator>
  constexpr OutputIterator
    set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
                             InputIterator2 first2, InputIterator2 last2,
                             OutputIterator result);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
         class ForwardIterator>
  ForwardIterator
    set_symmetric_difference(ExecutionPolicy&& exec,
                             ForwardIterator1 first1, ForwardIterator1 last1,
                             ForwardIterator2 first2, ForwardIterator2 last2,
                             ForwardIterator result);

template<class InputIterator1, class InputIterator2,
         class OutputIterator, class Compare>
  constexpr OutputIterator
    set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
                             InputIterator2 first2, InputIterator2 last2,
                             OutputIterator result, Compare comp);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
         class ForwardIterator, class Compare>
  ForwardIterator
    set_symmetric_difference(ExecutionPolicy&& exec,
                             ForwardIterator1 first1, ForwardIterator1 last1,
                             ForwardIterator2 first2, ForwardIterator2 last2,
                             ForwardIterator result, Compare comp);

template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
         weakly_incrementable O, class Comp = ranges::less,
         class Proj1 = identity, class Proj2 = identity>
  requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
  constexpr ranges::set_symmetric_difference_result<I1, I2, O>
    ranges::set_symmetric_difference(I1 first1, S1 last1, I2 first2, S2 last2, O result,
                                     Comp comp = {}, Proj1 proj1 = {},
                                     Proj2 proj2 = {});
template<input_range R1, input_range R2, weakly_incrementable O,
         class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
  requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
  constexpr ranges::set_symmetric_difference_result<borrowed_iterator_t<R1>,
                                                    borrowed_iterator_t<R2>, O>
    ranges::set_symmetric_difference(R1&& r1, R2&& r2, O result, Comp comp = {},
                                     Proj1 proj1 = {}, Proj2 proj2 = {});

template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
         random_access_iterator I2, sized_sentinel_for<I2> S2,
         random_access_iterator O, sized_sentinel_for<O> OutS, class Comp = ranges::less,
         class Proj1 = identity, class Proj2 = identity>
  requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
  ranges::set_symmetric_difference_result<I1, I2, O>
    ranges::set_symmetric_difference(Ep&& exec, I1 first1, S1 last1,
                                     I2 first2, S2 last2, O result, OutS result_last,
                                     Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
template<execution-policy Ep, sized-random-access-range R1, sized-random-access-range R2,
         sized-random-access-range OutR, class Comp = ranges::less,
         class Proj1 = identity, class Proj2 = identity>
  requires mergeable<iterator_t<R1>, iterator_t<R2>, iterator_t<OutR>, Comp, Proj1, Proj2>
  ranges::set_symmetric_difference_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>,
                                  borrowed_iterator_t<OutR>>
    ranges::set_symmetric_difference(Ep&& exec, R1&& r1, R2&& r2, OutR&& result_r,
                                     Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});

Let:

(1.1)
comp be less{}, and proj1 and proj2 be identity{} for the overloads with no parameters by those names;
(1.2)
M be the number of elements in the sorted symmetric difference (see below);
(1.3)
result_last be result + M for the overloads with no parameter result_last or result_r;
(1.4)
N be min(M, result_last - result).

Preconditions: The ranges [first1, last1) and [first2, last2) are sorted with respect to comp and proj1 or proj2, respectively.

The resulting range does not overlap with either of the original ranges.

Effects: Constructs a sorted symmetric difference of the elements from the two ranges; that is, the set of elements that are present in exactly one of [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

| m - n |

of those elements are included in the symmetric difference: the last

m - n

of these elements from [first1, last1), in order, if

m > n

, and the last

n - m

of these elements from [first2, last2), in order, if

m < n

N < M

, a non-copied element is considered skipped if it compares less than or equivalent to the

(N + 1)^{th}

element of the sorted symmetric difference, unless it is from the same range as that element and does not precede it.

Copies the first N elements of the sorted symmetric difference to the range [result, result + N).

Returns:

(4.1)
result_last for the overloads in namespace std.
(4.2)
{last1, last2, result + N} for the overloads in namespace ranges, if N is equal to $M + K$ .
(4.3)
Otherwise, {first1 + A, first2 + B, result_last} for the overloads in namespace ranges, where A and B are the numbers of copied or skipped elements in [first1, last1) and [first2, last2), respectively.

Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1 comparisons and applications of each projection.

Remarks: Stable ([algorithm.stable]).