std::set_intersection
在头文件 <algorithm> 中定义 |
||
template< class InputIt1, class InputIt2, class OutputIt > OutputIt set_intersection( InputIt1 first1, InputIt1 last1, |
(1) | (从 C++20 开始为 constexpr) |
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class ForwardIt3 > |
(2) | (从 C++17 开始) |
template< class InputIt1, class InputIt2, class OutputIt, class Compare > |
(3) | (从 C++20 开始为 constexpr) |
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, |
(4) | (从 C++17 开始) |
构造一个从 d_first 开始的已排序范围,该范围包含在两个已排序范围 [
first1,
last1)
和 [
first2,
last2)
中都找到的元素。
如果 [
first1,
last1)
包含 m 个相互等价的元素,而 [
first2,
last2)
包含 n 个等价于它们的元素,则将从 [
first1,
last1)
中的前 std::min(m, n) 个元素复制到输出范围,保持顺序。
[
first1,
last1)
或 [
first2,
last2)
未根据 comp 排序,则行为未定义。
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 开始) |
如果输出范围与[
first1,
last1)
或[
first2,
last2)
重叠,则行为未定义。
内容 |
[编辑] 参数
first1, last1 | - | 要检查的第一个元素范围 |
first2, last2 | - | 要检查的第二个元素范围 |
d_first | - | 输出范围的开始 |
policy | - | 要使用的执行策略。有关详细信息,请参阅执行策略。 |
comp | - | 比较函数对象(即满足Compare要求的对象),如果第一个参数小于(即按顺序排在前面)第二个参数,则返回true。 比较函数的签名应等效于以下内容 bool cmp(const Type1& a, const Type2& b); 虽然签名不需要具有const&,但该函数不能修改传递给它的对象,并且必须能够接受类型(可能是 const) |
类型要求 | ||
-InputIt1, InputIt2 必须满足LegacyInputIterator的要求。 | ||
-OutputIt 必须满足LegacyOutputIterator的要求。 | ||
-ForwardIt1, ForwardIt2, ForwardIt3 必须满足LegacyForwardIterator的要求。 | ||
-Compare 必须满足Compare的要求。 |
[编辑] 返回值
构造范围末尾的迭代器。
[编辑] 复杂度
给定 N
1 作为 std::distance(first1, last1) 且 N
2 作为 std::distance(first2, last2)
1+N
2)-1 次应用比较函数 comp。
[编辑] 异常
带有名为 ExecutionPolicy
的模板参数的重载会报告以下错误
- 如果作为算法一部分调用的函数的执行抛出异常并且
ExecutionPolicy
是标准策略之一,则调用 std::terminate。对于任何其他ExecutionPolicy
,行为是实现定义的。 - 如果算法无法分配内存,则会抛出 std::bad_alloc。
[编辑] 可能的实现
set_intersection (1) |
---|
template<class InputIt1, class InputIt2, class OutputIt> OutputIt set_intersection(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first) { while (first1 != last1 && first2 != last2) { if (*first1 < *first2) ++first1; else { if (!(*first2 < *first1)) *d_first++ = *first1++; // *first1 and *first2 are equivalent. ++first2; } } return d_first; } |
set_intersection (3) |
template<class InputIt1, class InputIt2, class OutputIt, class Compare> OutputIt set_intersection(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first, Compare comp) { while (first1 != last1 && first2 != last2) { if (comp(*first1, *first2)) ++first1; else { if (!comp(*first2, *first1)) *d_first++ = *first1++; // *first1 and *first2 are equivalent. ++first2; } } return d_first; } |
[编辑] 示例
#include <algorithm> #include <iostream> #include <iterator> #include <vector> int main() { std::vector<int> v1{7, 2, 3, 4, 5, 6, 7, 8}; std::vector<int> v2{5, 7, 9, 7}; std::sort(v1.begin(), v1.end()); std::sort(v2.begin(), v2.end()); std::vector<int> v_intersection; std::set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(v_intersection)); for (int n : v_intersection) std::cout << n << ' '; std::cout << '\n'; }
输出
5 7 7
[编辑] 缺陷报告
以下行为更改的缺陷报告被追溯应用于先前发布的 C++ 标准。
DR | 应用于 | 已发布的行为 | 正确行为 |
---|---|---|---|
LWG 291 | C++98 | 未指定如何处理输入范围中的等效元素 | 指定 |
[编辑] 另请参阅
计算两个集合的并集 (函数模板) | |
(C++20) |
计算两个集合的交集 (niebloid) |