std::set_difference() 算法
- 自 C++20 起
- 自 C++17 起
- 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 );
将已排序范围 [first1; last1) 中未在已排序范围 [first2; last2) 中找到的元素复制到从 d_first 开始的范围。输出范围也是已排序的。
如果 [first1; last1) 包含 m 个彼此等效的元素，并且 [first2; last2) 包含 n 个与它们等效的元素，则将从 [first1; last1) 中复制最终的 std::max(m - n, 0) 个元素到输出范围，并保留顺序。
-
(1) 两个范围都必须根据
operator<进行排序。 -
(2) 两个范围都必须根据
comp进行排序。 -
(3 - 4) 同 (1) 和 (2)，但根据策略执行。
重载解析这些重载仅在
std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>为true时才参与重载解析。 (直到 C++20)std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>为true时才参与重载解析。 (自 C++20 起)
未定义行为
如果任何输入范围未排序（分别使用 operator< 或 comp），或者与输出范围重叠，则行为未定义
参数
first1 last2 | 要检查的第一个已排序元素范围。 |
first2 last3 | 要检查的第二个已排序元素范围。 |
d_first | 目标范围的开头。 |
policy | 要使用的执行策略。详见执行策略。 |
comp | 比较函数对象（即满足 Compare 要求的对象）。比较函数的签名应等同于以下内容：
|
类型要求
InputIt1 InputIt2 | LegacyInputIterator |
ForwardIt1 ForwardIt2 ForwardIt3 | LegacyForwardIterator |
OutputIt1 | LegacyOutputIterator |
返回值
构造范围末尾之后的迭代器。
复杂度
给定 M 为 std::distance(first1, last1)，N 为 std::distance(first2, last2)
- (1, 3) 最多使用
operator<进行 2 * (M + N) - 1 次比较。 - (2, 4) 最多使用
comp进行 2 * (M + N) - 1 次比较。
异常
带有模板参数 ExecutionPolicy 的重载报告错误如下
- 如果作为算法一部分调用的函数执行抛出异常，并且
ExecutionPolicy是标准策略之一，则调用std::terminate。对于任何其他ExecutionPolicy，行为是实现定义的. - 如果算法未能分配内存，则抛出
std::bad_alloc。
可能的实现
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;
}
示例
Main.cpp
#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 }