# set_symmetric_difference

Category: algorithms | Component type: function

### Prototype

`Set_symmetric_difference` is an overloaded name; there are actually two `set_symmetric_difference` functions.

    template <class InputIterator1, class InputIterator2, class OutputIterator>
    OutputIterator set_symmetric_difference(InputIterator1 first1,
                                            InputIterator1 last1,
                                            InputIterator2 first2,
                                            InputIterator2 last2,
                                            OutputIterator result);

    template <class InputIterator1, class InputIterator2, class OutputIterator,
              class StrictWeakOrdering>
    OutputIterator set_symmetric_difference(InputIterator1 first1,
                                            InputIterator1 last1,
                                            InputIterator2 first2,
                                            InputIterator2 last2,
                                            OutputIterator result,
                                            StrictWeakOrdering comp);

### Description

`Set_symmetric_difference` constructs a sorted range that is the set symmetric difference of the sorted ranges `[first1, last1)` and `[first2, last2)`. The return value is the end of the output range.

In the simplest case, `set_symmetric_difference` performs a set theoretic calculation: it constructs the union of the two sets `A - B` and `B - A`, where `A` and `B` are the two input ranges. That is, the output range contains a copy of every element that is contained in `[first1, last1)` but not `[first2, last2)`, and a copy of every element that is contained in `[first2, last2)` but not `[first1, last1)`. The general case is more complicated, because the input ranges may contain duplicate elements. The generalization is that if a value appears `m` times in `[first1, last1)` and `n` times in `[first2, last2)` (where `m` or `n` may be zero), then it appears `|m-n|` times in the output range. [1] `Set_symmetric_difference` is stable, meaning that the relative order of elements within each input range is preserved.

The two versions of `set_symmetric_difference` differ in how they define whether one element is less than another. The first version compares objects using `operator<`, and the second compares objects using a function object `comp`.

### Definition

Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.

### Requirements on types

For the first version:

- `InputIterator1` is a model of Input Iterator.
- `InputIterator2` is a model of Input Iterator.
- `OutputIterator` is a model of Output Iterator.
- `InputIterator1` and `InputIterator2` have the same value type.
- `InputIterator`'s value type is a model of LessThan Comparable.
- The ordering on objects of `InputIterator1`'s value type is a strict weak ordering, as defined in the LessThan Comparable requirements.
- `InputIterator`'s value type is convertible to a type in `OutputIterator`'s set of value types.

For the second version:

- `InputIterator1` is a model of Input Iterator.
- `InputIterator2` is a model of Input Iterator.
- `OutputIterator` is a model of Output Iterator.
- `StrictWeakOrdering` is a model of Strict Weak Ordering.
- `InputIterator1` and `InputIterator2` have the same value type.
- `InputIterator1`'s value type is convertible to `StrictWeakOrdering`'s argument type.
- `InputIterator`'s value type is convertible to a type in `OutputIterator`'s set of value types.

### Preconditions

For the first version:

- `[first1, last1)` is a valid range.
- `[first2, last2)` is a valid range.
- `[first1, last1)` is ordered in ascending order according to `operator<`. That is, for every pair of iterators `i` and `j` in `[first1, last1)` such that `i` precedes `j`, `*j < *i` is `false`.
- `[first2, last2)` is ordered in ascending order according to `operator<`. That is, for every pair of iterators `i` and `j` in `[first2, last2)` such that `i` precedes `j`, `*j < *i` is `false`.
- There is enough space to hold all of the elements being copied. More formally, the requirement is that `[result, result + n)` is a valid range, where `n` is the number of elements in the symmetric difference of the two input ranges.
- `[first1, last1)` and `[result, result + n)` do not overlap.
- `[first2, last2)` and `[result, result + n)` do not overlap.

For the second version:

- `[first1, last1)` is a valid range.
- `[first2, last2)` is a valid range.
- `[first1, last1)` is ordered in ascending order according to `comp`. That is, for every pair of iterators `i` and `j` in `[first1, last1)` such that `i` precedes `j`, `comp(*j, *i)` is `false`.
- `[first2, last2)` is ordered in ascending order according to `comp`. That is, for every pair of iterators `i` and `j` in `[first2, last2)` such that `i` precedes `j`, `comp(*j, *i)` is `false`.
- There is enough space to hold all of the elements being copied. More formally, the requirement is that `[result, result + n)` is a valid range, where `n` is the number of elements in the symmetric difference of the two input ranges.
- `[first1, last1)` and `[result, result + n)` do not overlap.
- `[first2, last2)` and `[result, result + n)` do not overlap.

### Complexity

Linear. Zero comparisons if either `[first1, last1)` or `[first2, last2)` is empty, otherwise at most `2 * ((last1 - first1) + (last2 - first2)) - 1` comparisons.

### Example

    inline bool lt_nocase(char c1, char c2) { return tolower(c1) < tolower(c2); }

    int main()
    {
      int A1[] = {1, 3, 5, 7, 9, 11};
      int A2[] = {1, 1, 2, 3, 5, 8, 13};
      char A3[] = {'a', 'b', 'b', 'B', 'B', 'f', 'g', 'h', 'H'};
      char A4[] = {'A', 'B', 'B', 'C', 'D', 'F', 'F', 'H' };

      const int N1 = sizeof(A1) / sizeof(int);
      const int N2 = sizeof(A2) / sizeof(int);
      const int N3 = sizeof(A3);
      const int N4 = sizeof(A4);

      cout << "Symmetric difference of A1 and A2: ";
      set_symmetric_difference(A1, A1 + N1, A2, A2 + N2,
                               ostream_iterator<int>(cout, " "));
      cout << endl
           << "Symmetric difference of A3 and A4: ";
      set_symmetric_difference(A3, A3 + N3, A4, A4 + N4,
                               ostream_iterator<char>(cout, " "),
                               lt_nocase);
      cout << endl;
    }

The output is

    Symmetric difference of A1 and A2: 1 2 7 8 9 11 13
    Symmetric difference of A3 and A4: B B C D F g H

### Notes

[1] Even this is not a completely precise description, because the ordering by which the input ranges are sorted is permitted to be a strict weak ordering that is not a total ordering: there might be values `x` and `y` that are equivalent (that is, neither `x < y` nor `y < x`) but not equal. See the LessThan Comparable requirements for a more complete discussion. The output range consists of those elements from `[first1, last1)` for which equivalent elements do not exist in `[first2, last2)`, and those elements from `[first2, last2)` for which equivalent elements do not exist in `[first1, last1)`. Specifically, suppose that the range `[first1, last1)` contains `m` elements that are equivalent to each other and the range `[first2, last2)` contains `n` elements from that equivalence class (where either `m` or `n` may be zero). If `m > n` then the output range contains the last `m - n` of these elements elements from `[first1, last1)`, and if `m < n` then the output range contains the last `n - m` of these elements elements from `[first2, last2)`.

### See also

`includes`, `set_union`, `set_intersection`, `set_difference`, `sort`

Copyright © 1999 Silicon Graphics, Inc. All Rights Reserved. TrademarkInformation