std::set_symmetric_difference – cppreference.com

Aus cppreference.com

definiert 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)

Kopiert die Elemente aus der sortierten Reihe [first1, last1) die nicht in der sortierten Reihe [first2, last2) und die Elemente aus der sortierten Reihe [first2, last2) die nicht in der sortierten Reihe [first1, last1) dem Bereich beginnend bei d_first gefunden wurden gefunden. Das resultierende Spektrum wird auch sortiert. Die erste Version rechnet sowohl Eingangsbereiche mit operator< sortiert werden, rechnet die zweite Version sie mit dem angegebenen Vergleichsfunktion comp sortiert werden. Wenn ein Element ist m mal gefunden [first1, last1) und n Mal in [first2, last2), wird es an d_first genau std::abs(m-n) Mal kopiert werden. Wenn m>n, dann die letzte m-n dieser Elemente aus [first1,last1) kopiert werden, sonst werden die letzten n-m Elemente aus [first2,last2) kopiert. Die daraus resultierende Bereich kann nicht mit einem der Eingangsbereiche überschneiden .

Original:

Copies the elements from the sorted range [first1, last1) which are not found in the sorted range [first2, last2) and the elements from the sorted range [first2, last2) which are not found in the sorted range [first1, last1) to the range beginning at d_first. The resulting range is also sorted. The first version expects both input ranges to be sorted with operator<, the second version expects them to be sorted with the given comparison function comp. If some element is found m times in [first1, last1) and n times in [first2, last2), it will be copied to d_first exactly std::abs(m-n) times. If m>n, then the last m-n of those elements are copied from [first1,last1), otherwise the last n-m elements are copied from [first2,last2). The resulting range cannot overlap with either of the input ranges.

The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

Parameter

first1, last1	-	die erste Reihe von Elementen sortiert 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	-	die zweite sortierten Bereich von Elementen 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	-	comparison function which returns `true` if the first argument is less than the second. The signature of the comparison function should be equivalent to the following: `bool cmp(const Type1 &a, const Type2 &b);` The signature does not need to have `const &`, but the function must not modify the objects passed to it. 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.
Type requirements
-`InputIt1` must meet the requirements of `InputIterator`.
-`InputIt2` must meet the requirements of `InputIterator`.
-`OutputIt` must meet the requirements of `OutputIterator`.

Rückgabewert

Iterator über das Ende der konstruiert Bereich .

Original:

Iterator past the end of the constructed range.

The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

Komplexität

Allenfalls 2·(N₁+N₂-1) Vergleiche, wo N₁ = std::distance(first1, last1) und N₂ = std::distance(first2, last2) .

Original:

At most 2·(N₁+N₂-1) comparisons, where N₁ = std::distance(first1, last1) and N₂ = std::distance(first2, last2).

The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

Mögliche Implementierung

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); }

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);
}

Beispiel

#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 << ' ';
}

Output:

Siehe auch


includes	liefert true, wenn ein Satz ist eine Teilmenge des anderen 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. (Funktions-Template) [edit]

set_difference	berechnet die Differenz zwischen zwei Sätzen Original: computes the difference between two sets The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions. (Funktions-Template) [edit]

set_union	computes the union of two sets (Funktions-Template) [edit]

set_intersection	berechnet den Schnittpunkt von zwei Sätzen Original: computes the intersection of two sets The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions. (Funktions-Template) [edit]