std::ranges::set_symmetric_difference, std::ranges::set_symmetric_difference_result

Definiert in Header `<algorithm>`
Aufruf-Signatur
template< std::input_iterator I1, std::sentinel_for<I1> S1, std::input_iterator I2, std::sentinel_for<I2> S2, std::weakly_incrementable O, class Comp = ranges::less, class Proj1 = std::identity, class Proj2 = std::identity > requires std::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 = {} );	(1)	(seit C++20)
template< ranges::input_range R1, ranges::input_range R2, std::weakly_incrementable O, class Comp = ranges::less, class Proj1 = std::identity, class Proj2 = std::identity > requires std::mergeable<ranges::iterator_t<R1>, ranges::iterator_t<R2>, O, Comp, Proj1, Proj2> constexpr set_symmetric_difference_result<ranges::borrowed_iterator_t<R1>, ranges::borrowed_iterator_t<R2>, O> set_symmetric_difference( R1&& r1, R2&& r2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );	(2)	(seit C++20)
Hilfstypen
template< class I1, class I2, class O > using set_symmetric_difference_result = ranges::in_in_out_result<I1, I2, O>;	(3)	(seit C++20)

Berechnet die symmetrische Differenz zweier sortierter Bereiche: Elemente, die in einem der Bereiche, aber nicht in beiden vorkommen, werden in den Bereich kopiert, der bei result beginnt. Der resultierende Bereich ist ebenfalls sortiert.

Wenn ein Element m Mal in [first1, last1) und n Mal in [first2, last2) gefunden wird, wird es genau │m - n│ Mal nach result kopiert. Wenn m > n, dann werden die letzten m - n dieser Elemente aus [first1, last1) kopiert, andernfalls werden die letzten n - m Elemente aus [first2, last2) kopiert. Der resultierende Bereich darf nicht mit einem der Eingabebereiche überlappen.

Das Verhalten ist undefiniert, wenn

die Eingabebereiche sind nicht sortiert bezüglich comp und proj1 bzw. proj2, oder
der Ergebnisbereich überschneidet sich mit einem der Eingabebereiche.

1) Elemente werden mit der gegebenen binären Vergleichsfunktion comp verglichen.

2) Analog zu (1), verwendet jedoch r1 als ersten Bereich und r2 als zweiten Bereich, als ob ranges::begin(r1) als first1, ranges::end(r1) als last1, ranges::begin(r2) als first2 und ranges::end(r2) als last2 verwendet würden.

Die auf dieser Seite beschriebenen funktionsähnlichen Entitäten sind Algorithmus-Funktionsobjekte (informell als niebloids bekannt), d.h.

Können explizite Template-Argumentlisten bei keinem von ihnen angegeben werden.
Keiner von ihnen ist für Argument-abhängige Suche sichtbar.
Wenn einer von ihnen durch normale unqualifizierte Suche als Name links vom Funktionsaufrufoperator gefunden wird, wird die Argument-abhängige Suche unterdrückt.

[bearbeiten] Parameter

first1, last1	-	das Iterator-Sentinel-Paar, das den ersten sortierten Eingabebereich von Elementen definiert
first2, last2	-	das Iterator-Sentinel-Paar, das den zweiten sortierten Eingabebereich von Elementen definiert
r1	-	der erste sortierte Eingabebereich
r2	-	der zweite sortierte Eingabebereich
Ergebnis	-	der Anfang des Ausgabebereichs
comp	-	Vergleich, der auf die projizierten Elemente angewendet wird
proj1	-	Projektion, die auf die Elemente im ersten Bereich angewendet wird
proj2	-	Projektion, die auf die Elemente im zweiten Bereich angewendet wird

[bearbeiten] Rückgabewert

{last1, last2, result_last}, wobei result_last das Ende des konstruierten Bereichs ist.

[bearbeiten] Komplexität

Höchstens $\scriptsize 2\cdot(N_1+N_2)-1$ $2\cdot(N 1 +N 2)-1$ Vergleiche und Anwendungen jeder Projektion, wobei $\scriptsize N_1$ $N 1$ und $\scriptsize N_2$ $N 2$ ranges::distance(first1, last1) bzw. ranges::distance(first2, last2) sind.

[bearbeiten] Mögliche Implementierung

struct set_symmetric_difference_fn
{
    template<std::input_iterator I1, std::sentinel_for<I1> S1,
             std::input_iterator I2, std::sentinel_for<I2> S2,
             std::weakly_incrementable O, class Comp = ranges::less,
             class Proj1 = std::identity, class Proj2 = std::identity>
    requires std::mergeable<I1, I2, O, Comp, Proj1, Proj2>
    constexpr ranges::set_symmetric_difference_result<I1, I2, O>
        operator()(I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = {},
                   Proj1 proj1 = {}, Proj2 proj2 = {}) const
    {
        while (!(first1 == last1 or first2 == last2))
        {
            if (std::invoke(comp, std::invoke(proj1, *first1), std::invoke(proj2, *first2)))
            {
                *result = *first1;
                ++first1;
                ++result;
            }
            else if (std::invoke(comp, std::invoke(proj2, *first2),
                                       std::invoke(proj1, *first1)))
            {
                *result = *first2;
                ++first2;
                ++result;
            }
            else
            {
                ++first1;
                ++first2;
            }
        }
        auto res1 {ranges::copy(std::move(first1), std::move(last1), std::move(result))};
        auto res2 {ranges::copy(std::move(first2), std::move(last2), std::move(res1.out))};
        return {std::move(res1.in), std::move(res2.in), std::move(res2.out)};
    }
 
    template<ranges::input_range R1, ranges::input_range R2,
             std::weakly_incrementable O, class Comp = ranges::less,
             class Proj1 = std::identity, class Proj2 = std::identity>
    requires std::mergeable<ranges::iterator_t<R1>, ranges::iterator_t<R2>,
                            O, Comp, Proj1, Proj2>
    constexpr ranges::set_symmetric_difference_result<
        ranges::borrowed_iterator_t<R1>, ranges::borrowed_iterator_t<R2>, O>
        operator()(R1&& r1, R2&& r2, O result, Comp comp = {},
                   Proj1 proj1 = {}, Proj2 proj2 = {}) const
    {
        return (*this)(ranges::begin(r1), ranges::end(r1),
                       ranges::begin(r2), ranges::end(r2),
                       std::move(result), std::move(comp),
                       std::move(proj1), std::move(proj2));
    }
};
 
inline constexpr set_symmetric_difference_fn set_symmetric_difference {};

[bearbeiten] Beispiel

Führen Sie diesen Code aus

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
 
void visualize_this(const auto& v, int min = 1, int max = 9)
{
    for (auto i {min}; i <= max; ++i)
    {
        std::ranges::binary_search(v, i) ? std::cout << i : std::cout << '.';
        std::cout << ' ';
    }
    std::cout << '\n';
}
 
int main()
{
    const auto in1 = {1, 3, 4,    6, 7, 9};
    const auto in2 = {1,    4, 5, 6,    9};
 
    std::vector<int> out {};
 
    std::ranges::set_symmetric_difference(in1, in2, std::back_inserter(out));
 
    visualize_this(in1);
    visualize_this(in2);
    visualize_this(out);
}

Ausgabe

1 . 3 4 . 6 7 . 9
1 . . 4 5 6 . . 9
. . 3 . 5 . 7 . .

[bearbeiten] Siehe auch

ranges::set_union (C++20)	Berechnet die Vereinigung zweier Mengen (Algorithmus-Funktionsobjekt)[edit]
ranges::set_difference (C++20)	Berechnet die Differenz zwischen zwei Mengen (Algorithmus-Funktionsobjekt)[edit]
ranges::set_intersection (C++20)	Berechnet den Schnitt zweier Mengen (Algorithmus-Funktionsobjekt)[edit]
ranges::includes (C++20)	Gibt true zurück, wenn eine Sequenz eine Untersequenz einer anderen ist (Algorithmus-Funktionsobjekt)[edit]
set_symmetric_difference	Berechnet die symmetrische Differenz zwischen zwei Mengen (Funktionstemplate) [edit]

Compiler-Unterstützung
Freestanding und gehostet
Sprache
Standardbibliothek
Header der Standardbibliothek
Benannte Anforderungen
Feature-Test-Makros (C++20)
Bibliothek für Sprachunterstützung
Konzepte-Bibliothek (C++20)
Diagnostik-Bibliothek
Speicherverwaltungsbibliothek
Metaprogrammierungsbibliothek (C++11)
Allgemeine Dienstprogramme-Bibliothek
Container-Bibliothek
Iterator-Bibliothek
Ranges-Bibliothek (C++20)
Algorithmen-Bibliothek
Bibliothek für Zeichenketten
Textverarbeitungsbibliothek
Numerik-Bibliothek
Datums- und Zeitbibliothek
Ein-/Ausgabe-Bibliothek
Dateisystembibliothek (C++17)
Unterstützung für nebenläufige Programmierung (C++11)
Ausführungssteuerungsbibliothek (C++26)
Technische Spezifikationen
Symbolverzeichnis
Externe Bibliotheken

cppreference.com

Namensräume

Varianten

Ansichten

Aktionen