std::set_difference() algorithm
- since C++20
- since C++17
- until C++17
// (1)
template< class InputIt1, class InputIt2, class OutputIt >
constexpr OutputIt set_difference( InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2, OutputIt d_first );
// (2)
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 );
// (3)
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 );
// (4)
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 );
// (1)
template< class InputIt1, class InputIt2, class OutputIt >
OutputIt set_difference( InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2, OutputIt 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 );
// (3)
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 );
// (4)
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 );
// (1)
template< class InputIt1, class InputIt2, class OutputIt >
OutputIt set_difference( InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2, OutputIt 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 );
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) Both ranges must be sorted with respect to
operator<
. -
(2) Both ranges must be sorted with respect to
comp
. -
(3 - 4) Same as (1) and (2), but executed according to policy.
Overload ResolutionThese overloads participate in overload resolution only if
std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>
istrue
. (until C++20)std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>
istrue
. (since C++20)
If either of the input ranges is not sorted (using operator<
or comp
, respectively) or overlaps with the output range,
the behavior is undefined
Parameters
first1 last2 | The first sorted range of elements to examine. |
first2 last3 | The second sorted range of elements to examine. |
d_first | The beginning of the destination range. |
policy | The execution policy to use. See execution policy for details. |
comp | Comparison function object (i.e. an object that satisfies the requirements of Compare). The signature of the comparison function should be equivalent to the following:
|
Type requirements
InputIt1 InputIt2 | LegacyInputIterator |
ForwardIt1 ForwardIt2 ForwardIt3 | LegacyForwardIterator |
OutputIt1 | LegacyOutputIterator |
Return value
Iterator past the end of the constructed range.
Complexity
Given M
std::distance(first1, last1) and N
as std::distance(first2, last2)
:
- (1, 3) at most 2 * (M + N) - 1 comparisons using
operator<
. - (2, 4) at most 2 * (M + N) - 1 comparison with
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 otherExecutionPolicy
, the behavior is implementation-defined. - If the algorithm fails to allocate memory,
std::bad_alloc
is thrown.
Possible implementation
set_difference(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;
}
set_difference(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;
}
Examples
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
template<typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T> const& v)
{
for (os << "{ "; auto const& e : v)
os << e << ' ';
return os << '}';
}
struct Order // a struct with some 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';
// 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';
}
{ 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 }
Hover to see the original license.