std::set_symmetric_difference

Defined in header `<algorithm>`

template< class InputIt1, class InputIt2, class OutputIt > OutputIt set_symmetric_difference( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first );	(1)

template< class InputIt1, class InputIt2, class OutputIt, class Compare > OutputIt set_symmetric_difference( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first, Compare comp );	(2)

ソート範囲[first1, last1)と[first2, last2)でレンジ先頭にソートされた範囲[first2, last2)で発見されていない[first1, last1)ソート範囲の要素で発見されていないソート範囲d_firstから要素がコピーされます。結果として得られる範囲は、またソートされます。最初のバージョンでは、両方の入力がoperator<でソートされている範囲では、2番目のバージョンは、それらが与えられた比較関数compでソートされることを想定して期待しています。いくつかの要素がmで[first1, last1)とn回[first2, last2)倍であることが判明した場合、それは正確にd_firststd::abs(m-n)倍にコピーされます。 m>n場合は、それらの要素の最後m-nが[first1,last1)からコピーされ、そうでなければ最後n-m要素が[first2,last2)からコピーされます。結果の範囲は入力レンジのいずれかと重複することはできません.

first1, last1	-	要素の最初のソート範囲 Original: the first sorted range of elements The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions.
first2, last2	-	要素の第二ソート範囲 Original: the second sorted range of elements The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions.
comp	-	比較関数. 最初の値が二つ目の値より小さい場合、 trueを返します. 比較関数のシグネチャは以下と同等でなければなりません. bool cmp(const Type1 &a, const Type2 &b); シグネチャは`const`を含まなくても構いませんが, 比較関数は渡されたオブジェクトを変更してはなりません. The types Type1 and Type2 must be such that objects of types InputIt1 and InputIt2 can be dereferenced and then implicitly converted to Type1 and Type2 respectively.
型の要件
- `InputIt1` は `InputIterator` の要求を満足しなければなりません。
- `InputIt2` は `InputIterator` の要求を満足しなければなりません。
- `OutputIt` は `OutputIterator` の要求を満足しなければなりません。

[編集] 値を返します

構築範囲の終わり過去イテレータ.

[編集] 複雑性

最も

2\cdot(N 1 +N 2 -1)

の比較で、どこ

N 1

= std::distance(first1, last1)と

N 2

= std::distance(first2, last2).

[編集] 可能な実装

First version

template<class InputIt1, class InputIt2, class OutputIt>
OutputIt set_difference(InputIt1 first1, InputIt1 last1,
                        InputIt2 first2, InputIt2 last2,
                        OutputIt d_first)
{
    while (first1 != last1) {
        if (first2 == last2) return std::copy(first1, last1, d_first);
 
        if (*first1 < *first2) {
            *d_first++ = *first1++;
        } else {
            if (*first2 < *first1) {
                *d_first++ = *first2;
            } else {
                ++first1;
            }
            ++first2;
        }
    }
    return std::copy(first2, last2, d_first);
}

Second version

template<class InputIt1, class InputIt2,
         class OutputIt, class Compare>
OutputIt set_difference(InputIt1 first1, InputIt1 last1,
                        InputIt2 first2, InputIt2 last2,
                        OutputIt d_first, Compare comp)
{
    while (first1 != last1) {
        if (first2 == last2) return std::copy(first1, last1, d_first);
 
        if (comp(*first1, *first2)) {
            *d_first++ = *first1++;
        } else {
            if (comp(*first2, *first1)) {
                *d_first++ = *first2;
            } else {
                ++first1;
            }
            ++first2;
        }
    }
    return std::copy(first2, last2, d_first);
}

[編集] 例

このコードを実行します

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
int main()
{
    std::vector<int> v1{1,2,3,4,5,6,7,8     };
    std::vector<int> v2{        5,  7,  9,10};
    std::sort(v1.begin(), v1.end());
    std::sort(v2.begin(), v2.end());
 
    std::vector<int> v_intersection;
 
    std::set_symmetric_difference(
        v1.begin(), v1.end(),
        v2.begin(), v2.end(),
        std::back_inserter(v_intersection));
 
    for(int n : v_intersection)
        std::cout << n << ' ';
}

出力:

1 2 3 4 6 8 9 10

[編集] 参照


includes	1セットが他のサブセットである場合はtrueを返します Original: returns true if one set is a subset of another The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions. (関数テンプレート) [edit]

set_difference	2つの集合の差分を計算します (関数テンプレート) [edit]

set_union	2つの集合の和を計算します。 (関数テンプレート) [edit]

set_intersection	2つの集合の積を計算します (関数テンプレート) [edit]

言語
コンセプト
ユーティリティライブラリ
ストリングスライブラリ
コンテナライブラリ
アルゴリズムライブラリ
イテレータライブラリ
ニューメリックスライブラリ
入力/出力ライブラリ
ローカライゼーションライブラリ
正規表現ライブラリ (C++11)
アトミック操作ライブラリ (C++11)
スレッドのサポートライブラリ (C++11)

cppreference.com

検索

名前空間

変種

表示

操作