Defined in header <algorithm> | ||
---|---|---|
template< class InputIt1, class InputIt2, class OutputIt > OutputIt set_difference( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first ); | (1) | |
template< class InputIt1, class InputIt2, class OutputIt, class Compare > OutputIt set_difference( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first, Compare comp ); | (2) |
Copies the elements from the sorted range [first1, last1)
which are not found in the sorted range [first2, last2)
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
. Equivalent elements are treated individually, that is, 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::max(m-n, 0)
times. The resulting range cannot overlap with either of the input ranges.
Parameters
first1, last1 | - | the range of elements to examine |
first2, last2 | - | the range of elements to search for |
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:
The signature does not need to have |
Type requirements | ||
- InputIt1 must meet the requirements of InputIterator . | ||
- InputIt2 must meet the requirements of InputIterator . | ||
- OutputIt must meet the requirements of OutputIterator . |
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)
.
Possible implementation
First version |
---|
template<class InputIt1, class InputIt2, class OutputIt> OutputIt set_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)) { ++first1; } ++first2; } } return d_first; } |
Second version |
template<class InputIt1, class InputIt2, class OutputIt, class Compare> OutputIt set_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)) { ++first1; } ++first2; } } return d_first; } |
Example
#include <iostream> #include <algorithm> #include <vector> #include <iterator> int main() { std::vector<int> v1 {1, 2, 5, 5, 5, 9}; std::vector<int> v2 {2, 5, 7}; std::vector<int> diff; std::set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), std::inserter(diff, diff.begin())); for (auto i : v1) std::cout << i << ' '; std::cout << "minus "; for (auto i : v2) std::cout << i << ' '; std::cout << "is: "; for (auto i : diff) std::cout << i << ' '; std::cout << '\n'; }
Output:
1 2 5 5 5 9 minus 2 5 7 is: 1 5 5 9
See also
returns true if one set is a subset of another (function template) | |
computes the symmetric difference between two sets (function template) | |
std::experimental::parallel::set_difference
(parallelism TS) | parallelized version of std::set_difference (function template) |
Please login to continue.