std::set_difference

`<algorithm>`
	(1)
`template< class InputIt1, class InputIt2, class OutputIt > OutputIt set_difference( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first );`			(C++20)
`template< class InputIt1, class InputIt2, class OutputIt > constexpr OutputIt set_difference( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first );`			(C++20)
`template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class ForwardIt3 > ForwardIt3 set_difference( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2, ForwardIt3 d_first );`		(2)	(C++17)
		(3)
`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 );`				(C++20)
`template< class InputIt1, class InputIt2, class OutputIt, class Compare > constexpr OutputIt set_difference( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first, Compare comp );`				(C++20)
`template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class ForwardIt3, class Compare > ForwardIt3 set_difference( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2, ForwardIt3 d_first, Compare comp );`			(4)	(C++17)

[first1, last1) [first2, last2) d_first

[first1, last1) m [first2, last2) n d_first std::max(m-n, 0)

1) operator< operator<

3) comp comp

2,4) (1,3) policy std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> true

first1, last1	-
first2, last2	-
policy	-
comp	-	2 () `true` (Compare ) `bool cmp(const Type1 &a, const Type2 &b);` `const &` `Type1` `Type2` ( const ) ( `Type1 &` `Type1` `Type1` (C++11)) `Type1` `Type2` `InputIt1` `InputIt2` `Type1` `Type2`

- `InputIt1, InputIt2` LegacyInputIterator
- `OutputIt` LegacyOutputIterator
- `ForwardIt1, ForwardIt2, ForwardIt3` LegacyForwardIterator

$2\cdot(N1+N2-1)$ $N1$ = std::distance(first1, last1) $N2$ = std::distance(first2, last2)

ExecutionPolicy

ExecutionPolicy std::terminate ExecutionPolicy
std::bad_alloc

1

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;
}

2

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;
}

Run this code

#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';
}

:

1 2 5 5 5 9 minus 2 5 7 is: 1 5 5 9

includes	() [edit]
set_symmetric_difference	2 () [edit]






(C++20)





(C++20)




(C++17)
(C++11)
(C++11)
(C++11)

cppreference.com

std::set_difference