std::set_symmetric_difference
Defined in header
<algorithm>
|
||
template< class InputIt1, class InputIt2, class OutputIt >
OutputIt set_symmetric_difference( InputIt1 first1, InputIt1 last1, |
(1) | |
template< class InputIt1, class InputIt2,
class OutputIt, class Compare > |
(2) | |
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.
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 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); The signature does not need to have const &, but the function object must not modify the objects passed to it. |
Type requirements | ||
-
InputIt1 must meet the requirements of InputIterator .
|
||
-
InputIt2 must meet the requirements of InputIterator .
|
||
-
OutputIt must meet the requirements of OutputIterator .
|
[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 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); } |
[edit] Example
#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
[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) |
|
(parallelism TS)
|
parallelized version of std::set_symmetric_difference (function template) |