最終更新日時(UTC):
が更新

履歴 編集

function template
<algorithm>

std::ranges::set_symmetric_difference(C++20)

namespace std::ranges {
  // (1)
  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_symmetric_difference_result<I1, I2, O>
    set_symmetric_difference(I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});

  // (2)
  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_symmetric_difference_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
    set_symmetric_difference(R1&& r1, R2&& r2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
}

概要

2つのソート済み範囲の対称差集合、すなわち2つの範囲の共通しない要素からなる集合を得る。

  • (1): イテレータペアで範囲を指定する
  • (2): 範囲を直接指定する

事前条件

結果の範囲は両方の入力の範囲と重なっていてはならない。

効果

[first1,last1) から [first2,last2) に存在していない要素と、[first2,last2) から [first1,last1) に存在していない要素を result へコピーする。構築された要素はソートされている。

戻り値

set_symmetric_difference_result {
  .in1 = last1,
  .in2 = last2,
  .out = result_last,
}

ただし、result_last は構築された範囲の終端。

計算量

最大で 2 * ((last1 - first1) + (last2 - first2)) - 1 回の比較を行う

備考

[first1,last1)m 個、[first2,last2)n 個の等価な要素を含んでいる場合、

  • m > n なら [first1,last1) から最後の m-n 個の要素を出力の範囲にコピーする。
  • n > m なら [first2,last2) から最後の n-m 個の要素を出力の範囲にコピーする。

#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, 7, 8};
  std::multiset<int> result;

  // 重ならない要素からなる集合を作る
  std::ranges::set_symmetric_difference(a, b, std::inserter(result, result.end()));

  for (int x : result) {
    std::cout << x << std::endl;
  }
}

出力

1
5
6
7
8

バージョン

言語

  • C++20

処理系

参照