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_difference_result<I1, O>
set_difference(I1 first1,
S1 last1,
I2 first2,
S2 last2,
O result,
Comp comp = {},
Proj1 proj1 = {},
Proj2 proj2 = {}); // (1) C++20
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_difference_result<borrowed_iterator_t<R1>, O>
set_difference(R1&& r1,
R2&& r2,
O result,
Comp comp = {},
Proj1 proj1 = {},
Proj2 proj2 = {}); // (2) C++20
}
概要
2つのソート済み範囲の差集合を得る
- (1): イテレータ範囲を指定する
- (2): Rangeを直接指定する
事前条件
結果の範囲は両方の入力の範囲と重なっていてはならない。
効果
[first1,last1) から、[first2,last2) に存在していない要素を result へコピーする。構築された範囲はソートされている。
戻り値
set_difference_result {
.in = last1,
.out = result_last,
}
ただし、result_last は構築された範囲の終端。
計算量
最大で 2 * ((last1 - first1) + (last2 - first2)) - 1 回の比較を行う
備考
[first1,last1) が m 個、[first2,last2) が n 個の等価な要素を含んでいる場合、[first1,last1) から最後の max(m-n, 0) 要素が出力の範囲へコピーされる。
例
#include <iostream>
#include <set>
#include <algorithm>
#include <iterator>
int main()
{
std::multiset<int> a = {1, 2, 3, 4, 5, 6};
std::multiset<int> b = {2, 3, 4};
std::multiset<int> result;
// a - bの差集合を作る
std::ranges::set_difference(a, b, std::inserter(result, result.end()));
for (int x : result) {
std::cout << x << std::endl;
}
}
19
#include <iostream>#include <set>#include <algorithm>#include <iterator>int main(){ std::multiset<int> a = {1, 2, 3, 4, 5, 6}; std::multiset<int> b = {2, 3, 4}; std::multiset<int> result; // a - bの差集合を作る std::ranges::set_difference(a, b, std::inserter(result, result.end())); for (int x : result) { std::cout << x << std::endl; }}出力
1
5
6
バージョン
言語
- C++20
処理系
- Clang: ??
- GCC: 10.1.0 ✅
- ICC: ??
- Visual C++: 2019 Update 10 ✅