std::set_difference
| 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 InputIt1, class InputIt2,
class OutputIt, class Compare >
OutputIt set_difference( InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2,
OutputIt d_first, Compare comp );
|
(2) | (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 );
|
(3) | (since C++17) |
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) |
Constructs a hypothetical sorted difference from two sorted source ranges [first1, last1) and [first2, last2), the difference consists of the set of elements present in the first range while absent in the second range. Copies all elements of the difference set 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.
operator<(until C++20)std::less{}(since C++20).operator<(until C++20)std::less{}(since C++20), the behavior is undefined.comp.comp, the behavior is undefined.policy.true:
|
|
(until C++20) |
|
|
(since C++20) |
If the destination range overlaps with any of the two source ranges, the behavior is undefined.
Parameters
| first1, last1 | - | the pair of iterators defining the first source range |
| first2, last2 | - | the pair of iterators defining the second source range |
| d_first | - | the beginning of the destination range |
| 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:
While the signature does not need to have |
| policy | - | the execution policy to use |
| 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
The past-the-end iterator of the destination range.
Complexity
Given
- N1 as
std::distance(first1, last1), - N2 as
std::distance(first2, last2):
operator<(until C++20)std::less{}(since C++20).comp.operator<(until C++20)std::less{}(since C++20).comp.Exceptions
- 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
| 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;
}
|
Example
#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:
{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 source ranges | specified |