# std::set_difference

> C++ Atlas: `cppatlas.com/w/cpp/algorithm/set_difference` | Source: https://en.cppreference.com/w/cpp/algorithm/set_difference | Domain: Algorithms | Standards: C++11, C++17, C++20

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.

## Official Specification Summary (cppreference)

```cpp
// 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) (constexpr since 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) (since C++17)

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 ); // (3) (constexpr since 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) (since C++17)
```

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 output range is also sorted.

If `[first1,` `last1)` contains `m` elements that are equivalent to each other and `[first2,` `last2)` contains `n` elements that are equivalent to them, the final `std::max(m - n, 0)` elements will be copied from `[first1,` `last1)` to the output range, preserving order.

1) If `[first1,` `last1)` or `[first2,` `last2)` is not sorted with respect to `operator<` (until C++20) `std::less{}` (since C++20), the behavior is undefined.

3) If `[first1,` `last1)` or `[first2,` `last2)` is not sorted with respect to `comp`, the behavior is undefined.

2,4) Same as (1,3), but executed according to `policy`.

These overloads participate in overload resolution only if all following conditions are satisfied:

   `std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>` is `true`. (until C++20)

   `std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>` is `true`. (since C++20)

If the output range overlaps with `[first1,` `last1)` or `[first2,` `last2)`, the behavior is undefined.

### Parameters

- `first1, last1` - the range of elements to examine
- `first2, last2` - the range of elements to search for
- `d_first` - the beginning of the output range
- `policy` - the execution policy to use
- `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);`

  While the signature does not need to have `const&`, the function must not modify the objects passed to it and must be able to accept all values of type (possibly const) `Type1` and `Type2` regardless of value category (thus, `Type1&` is not allowed, nor is `Type1` unless for `Type1` a move is equivalent to a copy (since C++11)).
  The types `Type1` and `Type2` must be such that objects of types `InputIt1` and `InputIt2` can be dereferenced and then implicitly converted to both `Type1` and `Type2`.

**Type requirements**

- `InputIt1, InputIt2` must meet the requirements of *LegacyInputIterator*.
- `OutputIt` must meet the requirements of *LegacyOutputIterator*.
- `ForwardIt1, ForwardIt2, ForwardIt3` must meet the requirements of *LegacyForwardIterator*.
- `Compare` must meet the requirements of *Compare*.

### Return value

Iterator past the end of the constructed range.

### Complexity

Given N¹ as `std::distance(first1, last1)` and N² as `std::distance(first2, last2)`:

1,2) At most 2⋅(N¹+N²)-1 comparisons using `operator<` (until C++20) `std::less{}` (since C++20).

3,4) At most 2⋅(N¹+N²)-1 applications of the comparison function `comp`.

### Exceptions

The overloads with a template parameter named `ExecutionPolicy` report errors as follows:

- If execution of a function invoked as part of the algorithm throws an exception and `ExecutionPolicy` is one of the standard policies, `std::terminate` is called. For any other `ExecutionPolicy`, the behavior is implementation-defined.
- If the algorithm fails to allocate memory, `std::bad_alloc` is thrown.

### Possible implementation

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

**set_difference (3)**

```cpp
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

```cpp
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v)
{
    os << '{';
    for (auto n{v.size()}; const auto& e : v)
        os << e << (--n ? ", " : "");
    return os << '}';
}

struct Order // a struct with very interesting data
{
    int order_id{};

    friend std::ostream& operator<<(std::ostream& os, const Order& ord)
    {
        return os << ord.order_id;
    }
};

int main()
{
    const std::vector<int> v1{1, 2, 5, 5, 5, 9};
    const 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()));

    std::cout << v1 << " ∖ " << v2 << " == " << diff << "\n\n";

    // we want to know which orders "cut" between old and new states:
    std::vector<Order> old_orders{{1}, {2}, {5}, {9}};
    std::vector<Order> new_orders{{2}, {5}, {7}};
    std::vector<Order> cut_orders;

    std::set_difference(old_orders.begin(), old_orders.end(),
                        new_orders.begin(), new_orders.end(),
                        std::back_inserter(cut_orders),
                        [](auto& a, auto& b) { return a.order_id < b.order_id; });

    std::cout << "old orders: " << old_orders << '\n'
              << "new orders: " << new_orders << '\n'
              << "cut orders: " << cut_orders << '\n';
}
```

Output:

```text
{1, 2, 5, 5, 5, 9} ∖ {2, 5, 7} == {1, 5, 5, 9}

old orders: {1, 2, 5, 9}
new orders: {2, 5, 7}
cut orders: {1, 9}
```

### Defect reports

The following behavior-changing defect reports were applied retroactively to previously published C++ standards.

| DR | Applied to | Behavior as published | Correct behavior |
| --- | --- | --- | --- |
| LWG 291 | C++98 | it was unspecified how to handle equivalent elements in the input ranges | specified |

### See also

- [`includes`](https://en.cppreference.com/w/cpp/algorithm/includes): returns `true` if one sequence is a subsequence of another (function template)
- [`set_symmetric_difference`](https://en.cppreference.com/w/cpp/algorithm/set_symmetric_difference): computes the symmetric difference between two sets (function template)
- [`ranges::set_difference`](https://en.cppreference.com/w/cpp/algorithm/ranges/set_difference) (C++20): computes the difference between two sets (algorithm function object)

---
Attribution: content from https://en.cppreference.com/w/cpp/algorithm/set_difference (cppreference.com), licensed under CC-BY-SA 3.0 and GFDL. Modified: converted to markdown, study notes added. Offline snapshot of 9 February 2025.