std::set_symmetric_difference
Defined in header <algorithm>
|
||
template< class InputIterator1, class InputIterator2, class OutputIterator > OutputIterator set_symmetric_difference( InputIterator1 first1, InputIterator1 last1, |
(1) | |
template< class InputIterator1, class InputIterator2, class OutputIterator, class Compare > |
(2) | |
Copies the elements from the sorted range [first1, last1) which are not found in the sorted range [first2, last2) and the elements from the sorted range [first2, last2) which are not found in the sorted range [first1, last1) to the range beginning at d_first. The resulting range is also sorted. The first version expects both input ranges to be sorted with operator<, the second version expects them to be sorted with the given comparison function comp. 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.
Contents |
[edit] Parameters
first1, last1 | - | the first sorted range of elements | |||||||||
first2, last2 | - | the second sorted range of elements | |||||||||
comp | - | comparison function which returns true if the first argument is less than the second. The signature of the comparison function should be equivalent to the following:
The signature does not need to have const &, but the function must not modify the objects passed to it. |
[edit] Return value
Iterator past the end of the constructed range.
[edit] Complexity
At most 2·(N1+N2-1) comparisons, where N1 = std::distance(first1, last1) and N2 = std::distance(first2, last2).
[edit] Possible implementation
First version |
---|
template<class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator 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 InputIterator1, class InputIterator2, class OutputIterator, class Compare> OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator 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); } |
[edit] Example
This section is incomplete Reason: no example |
[edit] See also
returns true if one set is a subset of another (function template) | |
computes the difference between two sets (function template) | |
computes the union of two sets (function template) | |
computes the intersection of two sets (function template) |