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

履歴 編集

function template
<algorithm>

std::set_symmetric_difference

namespace std {
  template <class InputIterator1, class InputIterator2,
            class OutputIterator>
  OutputIterator
    set_symmetric_difference(InputIterator1 first1,
                             InputIterator1 last1,
                             InputIterator2 first2,
                             InputIterator2 last2,
                             OutputIterator result); // (1) C++03

  template <class InputIterator1, class InputIterator2,
            class OutputIterator>
  constexpr OutputIterator
    set_symmetric_difference(InputIterator1 first1,
                             InputIterator1 last1,
                             InputIterator2 first2,
                             InputIterator2 last2,
                             OutputIterator result); // (1) C++20

  template <class InputIterator1, class InputIterator2,
            class OutputIterator, class Compare>
  OutputIterator
    set_symmetric_difference(InputIterator1 first1,
                             InputIterator1 last1,
                             InputIterator2 first2,
                             InputIterator2 last2,
                             OutputIterator result,
                             Compare comp);          // (2) C++03

  template <class InputIterator1, class InputIterator2,
            class OutputIterator, class Compare>
  constexpr OutputIterator
    set_symmetric_difference(InputIterator1 first1,
                             InputIterator1 last1,
                             InputIterator2 first2,
                             InputIterator2 last2,
                             OutputIterator result,
                             Compare comp);          // (2) C++20

  template <class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
            class ForwardIterator>
  ForwardIterator
    set_symmetric_difference(ExecutionPolicy&& exec,
                             ForwardIterator1 first1,
                             ForwardIterator1 last1,
                             ForwardIterator2 first2,
                             ForwardIterator2 last2,
                             ForwardIterator result); // (3) C++17

  template <class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
            class ForwardIterator, class Compare>
  ForwardIterator
    set_symmetric_difference(ExecutionPolicy&& exec,
                             ForwardIterator1 first1,
                             ForwardIterator1 last1,
                             ForwardIterator2 first2,
                             ForwardIterator2 last2,
                             ForwardIterator result,
                             Compare comp);           // (4) C++17
}

概要

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

事前条件

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

効果

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

戻り値

構築された範囲の終端

計算量

最大で 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::set_symmetric_difference(a.begin(), a.end(),
                                b.begin(), b.end(),
                                std::inserter(result, result.end()));

  std::for_each(result.begin(), result.end(), [](int x) {
    std::cout << x << std::endl;
  });
}

出力

1
5
6
7
8

参照