namespace std::ranges {
template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2, weakly_incrementable O,
class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
constexpr set_intersection_result<I1, I2, O>
set_intersection(I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // (1)
template<input_range R1, input_range R2, weakly_incrementable O,
class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
constexpr set_intersection_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
set_intersection(R1&& r1, R2&& r2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // (2)
}
概要
2つのソート済み範囲の積集合を得る
- (1): イテレータペアで範囲を指定する
- (2): 範囲を直接指定する
事前条件
結果の範囲は両方の入力の範囲と重なっていてはならない。
効果
2つの範囲からソート済みの intersection を構築する。つまり、両方の範囲のみにある要素の集合を構築する。
戻り値
次のメンバをもつtuple-likeオブジェクト。
set_intersection_result {
.in1 = last1,
.in2 = last2,
.out = result_last,
}
ただし、result_last
は構築された範囲の終端。
計算量
最大で 2 * ((last1 - first1) + (last2 - first2)) - 1
回の比較を行う
備考
[first1,last1)
が m
個、[first2,last2)
が n
個の等価な要素を含んでいる場合、[first1,last1)
から最初の min(m, n)
要素が出力の範囲へ順番にコピーされる。
例
#include <iostream>
#include <set>
#include <algorithm>
#include <iterator>
int main()
{
std::multiset<int> a = {1, 2, 3, 4};
std::multiset<int> b = {4, 5, 6, 2};
std::multiset<int> result;
// aとbの積集合を作る
std::set_intersection(a, b, std::inserter(result, result.end()));
for (int x : result) {
std::cout << x << std::endl;
}
}
出力
2
4
バージョン
言語
- C++20
処理系
- Clang: ??
- GCC: 10.1.0
- ICC: ??
- Visual C++: 2019 Update 10