std::ranges::set_difference, std::ranges::set_difference_result, std::ranges::set_difference_truncated_result

Defined in header `<algorithm>`
Call signature
template< std::input_iterator I1, std::sentinel_for<I1> S1, std::input_iterator I2, std::sentinel_for<I2> S2, std::weakly_incrementable O, class Comp = ranges::less, class Proj1 = std::identity, class Proj2 = std::identity > requires std::mergeable<I1, I2, O, Comp, Proj1, Proj2> constexpr ranges::set_difference_result<I1, O> set_difference( I1 first1, S1 last1, I2 first2, S2 last2, O d_first, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );	(1)	(since C++20)
template< ranges::input_range R1, ranges::input_range R2, std::weakly_incrementable O, class Comp = ranges::less, class Proj1 = std::identity, class Proj2 = std::identity > requires std::mergeable<ranges::iterator_t<R1>, ranges::iterator_t<R2>, O, Comp, Proj1, Proj2> constexpr ranges::set_difference_result<ranges::borrowed_iterator_t<R1>, O> set_difference( R1&& r1, R2&& r2, O d_first, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );	(2)	(since C++20)
template< /execution-policy/ Ep, std::random_access_iterator I1, std::sized_sentinel_for<I1> S1, std::random_access_iterator I2, std::sized_sentinel_for<I2> S2, std::random_access_iterator O, sized_sentinel_for<O> OutS, class Comp = ranges::less, class Proj1 = std::identity, class Proj2 = std::identity > requires std::mergeable<I1, I2, O, Comp, Proj1, Proj2> ranges::set_difference_truncated_result<I1, I2, O> set_difference( Ep&& policy, I1 first1, S1 last1, I2 first2, S2 last2, O d_first, OutS d_last, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );	(3)	(since C++26)
template< /execution-policy/ Ep, /sized-random-access-range/ R1, /sized-random-access-range/ R2, /sized-random-access-range/ OutR, class Comp = ranges::less, class Proj1 = std::identity, class Proj2 = std::identity > requires std::mergeable<ranges::iterator_t<R1>, ranges::iterator_t<R2>, ranges::iterator_t<OutR>, Comp, Proj1, Proj2> ranges::set_difference_truncated_result<ranges::borrowed_iterator_t<R1>, ranges::borrowed_iterator_t<R2>, ranges::borrowed_iterator_t<OutR>> set_difference( Ep&& policy, R1&& r1, R2&& r2, OutR&& d_r, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );	(4)	(since C++26)
Helper types
template< class I, class O > using set_difference_result = ranges::in_out_result<I, O>;	(5)	(since C++20)
template< class I, class O > using set_difference_truncated_result = ranges::in_in_out_result<I, I, O>;	(6)	(since C++26)

For the definition of /*execution-policy*/, see this page; for the definition of /*sized-random-access-range*/, see this page.

Constructs a hypothetical sorted difference from two sorted source ranges, the difference consists of the set of elements present at least one of the source ranges. Copies elements of the difference to the destination range.

1,2) All elements of the difference will be copied to the destination range beginning at d_first.

For each group of equivalent elements in the first source range, let n1 be the number of these elements, and n2 be the number of elements from the second source range that are equivalent to these elements:

The first std::min(n1, n2) elements in the group will be skipped.
The remaining elements in the group will be included in the difference in order.

1) The two source ranges are [first1, last1) and [first2, last2).

2) The two source ranges are r1 and r2.

3,4) Same as (1,2), but executed according to policy, and the destination range is [d_first, d_last) or d_r. If the destination range is exhausted, the remaining elements in the first source range will not be copied.

If any of the following conditions is satisfied, the behavior is undefined:

The first source range is not sorted with respect to the comparator comp and projection proj1.
The second source range is not sorted with respect to the comparator comp and projection proj2.
The destination range overlaps with any of the two source ranges.

The function-like entities described on this page are algorithm function objects (informally known as niebloids), that is:

Explicit template argument lists cannot be specified when calling any of them.
None of them are visible to argument-dependent lookup.
When any of them are found by normal unqualified lookup as the name to the left of the function-call operator, argument-dependent lookup is inhibited.

Parameters

first1, last1	-	the iterator-sentinel pair defining the first source range
r1	-	the first source range
first2, last2	-	the iterator-sentinel pair defining the second source range
r2	-	the second source range
d_first	-	the beginning of the destination range
d_last	-	the sentinel of the destination range
d_r	-	the destination range
comp	-	the comparator to be applied to the (projected) elements
proj1	-	the projection to be applied to the elements in the first source range
proj2	-	the projection to be applied to the elements in the second source range
policy	-	the execution policy to use

Return value

1,2) A ranges::set_difference_result object where:

The data member in holds the past-the-end iterator of the first source range.
The data member out holds the past-the-end iterator of the destination range.

3,4) A ranges::set_difference_truncated_result object where:

The data member in1 holds an iterator to the first remaining non-skipped element in the first source range, or the past-the-end iterator of the first source range if all elements of that range are copied or skipped.
For the data member in2:
- If the first source range is empty, in2 holds an iterator to the beginning of the second source range.
- Otherwise, if all elements of the first source range are copied or skipped, let m1 be the number of equivalent elements of the last group encountered in the first source range, and m2 be the number of elements from the second source range that are equivalent to these elements:
  - If m1 is less than m2, in2 holds an iterator to the m1 + 1th element of the equivalent elements from the second source range.
  - Otherwise, in2 holds an iterator to the first element in the second source range that is ordered after all these equivalent elements, or the past-the-end iterator of the second source range if no such element exists.
- Otherwise, in2 holds an iterator to the first element in the second source range that is not ordered before the element pointed to by in1, or the past-the-end iterator of the second source range if no such element exists.
The data member out holds an iterator past the last assigned element in the destination range, or an iterator to the beginning of the destination range if no element is assigned.

Complexity

Given

$\scriptsize N_1$ $N 1$ as ranges::distance(first1, last1) or ranges::distance(r1),
$\scriptsize N_2$ $N 2$ as ranges::distance(first2, last2) or ranges::distance(r2):

1,2) At most

2\cdot(N 1 +N 2)-1

applications of comp, proj1 and proj2.

3,4)

𝓞(N 1 +N 2)

applications of comp, proj1 and proj2.

Exceptions

3,4) During the execution process:

If the temporary memory resources required for parallelization are not available, std::bad_alloc is thrown.
If an uncaught exception is thrown while accessing objects via an algorithm argument, the behavior is determined by the execution policy (for standard policies, std::terminate is invoked).

Possible implementation

struct set_difference_fn
{
    template<std::input_iterator I1, std::sentinel_for<I1> S1,
             std::input_iterator I2, std::sentinel_for<I2> S2,
             std::weakly_incrementable O, class Comp = ranges::less,
             class Proj1 = std::identity, class Proj2 = std::identity>
        requires std::mergeable<I1, I2, O, Comp, Proj1, Proj2>
    constexpr ranges::set_difference_result<I1, O>
        operator()(I1 first1, S1 last1, I2 first2, S2 last2, O d_first,
                   Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}) const
    {
        while (!(first1 == last1 or first2 == last2))
        {
            if (std::invoke(comp, std::invoke(proj1, *first1),
                                  std::invoke(proj2, *first2)))
            {
                *d_first = *first1;
                ++first1;
                ++d_first;
            }
            else if (std::invoke(comp, std::invoke(proj2, *first2),
                                       std::invoke(proj1, *first1)))
                ++first2;
            else
            {
                ++first1;
                ++first2;
            }
        }
        return ranges::copy(std::move(first1), std::move(last1), std::move(d_first));
    }
    
    template<ranges::input_range R>
    constexpr get_end(R&& r)
    {
        return ranges::end(r);
    }
    
    template<ranges::forward_range R>
    constexpr get_end(R&& r)
    {
        return ranges::next(ranges::begin(r), ranges::end(r));
    }
    
    template<ranges::input_range R1, ranges::input_range R2,
             std::weakly_incrementable O, class Comp = ranges::less,
             class Proj1 = std::identity, class Proj2 = std::identity>
        requires std::mergeable<ranges::iterator_t<R1>, ranges::iterator_t<R2>,
                                O, Comp, Proj1, Proj2>
    constexpr ranges::set_difference_result<ranges::borrowed_iterator_t<R1>, O>
        operator()(R1&& r1, R2&& r2, O d_first,
                   Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}) const
    {
        return (*this)(ranges::begin(r1), get_end(r1),
                       ranges::begin(r2), get_end(r2),
                       std::move(d_first), std::move(comp),
                       std::move(proj1), std::move(proj2));
    }
};

inline constexpr set_difference_fn set_difference{};

Example

Run this code

#include <algorithm>
#include <cassert>
#include <iostream>
#include <iterator>
#include <string_view>
#include <vector>

auto print = [](const auto& v, std::string_view end = "")
{
    std::cout << "{ ";
    for (auto n{v.size()}; auto i : v)
        std::cout << i << (--n ? ", " : " ");
    std::cout << "} " << end;
};

struct Order // a struct with some very interesting data
{
    int order_id{};
    
    friend std::ostream& operator<<(std::ostream& os, const Order& ord)
    {
        return os << '{' << ord.order_id << '}';
    }
};

int main()
{
    const auto v1 = {1, 2, 5, 5, 5, 9};
    const auto v2 = {2, 5, 7};
    std::vector<int> diff{};
    
    std::ranges::set_difference(v1, v2, std::back_inserter(diff));
    print(v1, "∖ ");
    print(v2, "= ");
    print(diff, "\n\n");
    
    // We want to know which orders “cut” between old and new states:
    const std::vector<Order> old_orders{{1}, {2}, {5}, {9}};
    const std::vector<Order> new_orders{{2}, {5}, {7}};
    std::vector<Order> cut_orders(old_orders.size() + new_orders.size());
    
    auto [old_orders_end, cut_orders_last] =
        std::ranges::set_difference(old_orders, new_orders,
                                    cut_orders.begin(), {},
                                    &Order::order_id, &Order::order_id);
    assert(old_orders_end == old_orders.end());
    
    std::cout << "old orders = ";
    print(old_orders, "\n");
    std::cout << "new orders = ";
    print(new_orders, "\n");
    std::cout << "cut orders = ";
    print(cut_orders, "\n");
    cut_orders.erase(cut_orders_last, end(cut_orders));
    std::cout << "cut orders = ";
    print(cut_orders, "\n");
}

Output:

{ 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}, {0}, {0}, {0}, {0}, {0} } 
cut orders = { {1}, {9} }

Compiler support
Freestanding and hosted
Language
Standard library
Standard library headers
Named requirements
Feature test macros (C++20)
Language support library
Concepts library (C++20)
Diagnostics library
Memory management library
Metaprogramming library (C++11)
General utilities library
Containers library
Iterators library
Ranges library (C++20)
Algorithms library
Strings library
Text processing library
Numerics library
Date and time library
Input/output library
Filesystem library (C++17)
Concurrency support library (C++11)
Execution control library (C++26)
Technical specifications
Symbols index
External libraries

set_difference	computes the difference between two sets (function template) [edit]
ranges::set_union (C++20)	computes the union of two sets (algorithm function object)[edit]
ranges::set_intersection (C++20)	computes the intersection of two sets (algorithm function object)[edit]
ranges::set_symmetric_difference (C++20)	computes the symmetric difference between two sets (algorithm function object)[edit]
ranges::includes (C++20)	determines if one sequence is a subsequence of another (algorithm function object)[edit]

cppreference.com

Search

Namespaces

Variants

Views

Actions

std::ranges::set_difference, std::ranges::set_difference_result, std::ranges::set_difference_truncated_result

Contents

Parameters

Return value

Complexity

Exceptions

Possible implementation

Example

See also

Navigation

Tools