std::set_union() 算法
- 自 C++20 起
- 自 C++17 起
- C++17 之前
// (1)
template< class InputIt1, class InputIt2, class OutputIt >
constexpr OutputIt set_union( InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2, OutputIt d_first );
// (2)
template< class InputIt1, class InputIt2, class OutputIt, class Compare >
constexpr OutputIt set_union( 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_union( 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_union( 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_union( InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2, OutputIt d_first );
// (2)
template< class InputIt1, class InputIt2, class OutputIt, class Compare >
OutputIt set_union( 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_union( 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_union( 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_union( InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2, OutputIt d_first );
// (2)
template< class InputIt1, class InputIt2, class OutputIt, class Compare >
OutputIt set_union( InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2,
OutputIt d_first, Compare comp );
构造一个排序后的并集，始于 d_first，包含两个排序范围 [first1; last1) 和 [first2; last2) 中一个或两个都存在的元素集合。
如果 [first1; last1) 包含 m 个相互等价的元素，并且 [first2; last2) 包含 n 个与它们等价的元素，那么所有 m 个元素将从 [first1; last1) 复制到输出范围，并保留顺序，然后剩余的 std::max(n - m, 0) 个元素将从 [first2; last2) 复制到输出范围，也保留顺序。
-
(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_union(1)
template<class InputIt1, class InputIt2, class OutputIt>
OutputIt set_union(InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2, OutputIt d_first)
{
for (; first1 != last1; ++d_first)
{
if (first2 == last2)
return std::copy(first1, last1, d_first);
if (*first2 < *first1)
*d_first = *first2++;
else
{
*d_first = *first1;
if (!(*first1 < *first2))
++first2;
++first1;
}
}
return std::copy(first2, last2, d_first);
}
set_union(2)
template<class InputIt1, class InputIt2, class OutputIt, class Compare>
OutputIt set_union(InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2, OutputIt d_first, Compare comp)
{
for (; first1 != last1; ++d_first)
{
if (first2 == last2)
// Finished range 2, include the rest of range 1:
return std::copy(first1, last1, d_first);
if (comp(*first2, *first1))
*d_first = *first2++;
else
{
*d_first = *first1;
if (!comp(*first1, *first2)) // Equivalent => don't need to include *first2.
++first2;
++first1;
}
}
// Finished range 1, include the rest of range 2:
return std::copy(first2, last2, d_first);
}
备注
此算法执行的任务与std::merge类似。两者都消耗两个排序的输入范围，并生成一个包含两个输入中元素的排序输出。
这两个算法之间的区别在于处理来自两个输入范围的等价值（参见关于LessThanComparable的说明）。如果任何等价值在第一个范围中出现 n 次，在第二个范围中出现 m 次，std::merge 将输出所有 n + m 次出现，而std::set_union将仅输出 std::max(n, m) 次。
因此std::merge精确输出 std::distance(first1, last1) + std::distance(first2, last2) 个值，而std::set_union可能会产生更少的值。
示例
Main.cpp
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
void println(std::vector<int> const& v)
{
for (int i : v)
std::cout << i << ' ';
std::cout << '\n';
}
int main()
{
std::vector<int> v1, v2, dest;
v1 = {1, 2, 3, 4, 5};
v2 = { 3, 4, 5, 6, 7};
std::set_union(v1.cbegin(), v1.cend(),
v2.cbegin(), v2.cend(),
std::back_inserter(dest));
println(dest);
dest.clear();
v1 = {1, 2, 3, 4, 5, 5, 5};
v2 = { 3, 4, 5, 6, 7};
std::set_union(v1.cbegin(), v1.cend(),
v2.cbegin(), v2.cend(),
std::back_inserter(dest));
println(dest);
}
可能的输出
1 2 3 4 5 6 7
1 2 3 4 5 5 5 6 7