WissensdatenbankPrüfungszentrum
DEDeutsch
Sprache wählen13

CKTIS / C++

std::set_symmetric_difference — symmetrische Differenz sortierter Bereiche

std::set_symmetric_difference schreibt die sortierte symmetrische Differenz zweier sortierter Bereiche. Dabei werden Mehrfachvorkommen berücksichtigt. Der Algorithmus nimmt einen Ausgabeiterator entgegen und gibt einen Iterator hinter den geschriebenen Elementen zurück.

Version: C++23; repository compiler flag, production runtime not attested

Syntax

#include <algorithm>
std::set_symmetric_difference(first1, last1, first2, last2, result);
std::set_symmetric_difference(first1, last1, first2, last2, result, comp);

std::set_symmetric_difference aus <algorithm> kopiert die symmetrische Differenz der Bereiche [first1, last1) und [first2, last2) nach result. Bei Daten ohne Duplikate sind dies die Elemente, die in genau einem der beiden Bereiche vorkommen. Der Algorithmus arbeitet mit Iteratorbereichen und benötigt keinen std::set-Container.

Beide Eingaben müssen nach derselben Ordnung sortiert sein: standardmäßig aufsteigend oder bei der Überladung mit comp gemäß diesem Komparator. comp muss eine strenge schwache Ordnung definieren. Äquivalenz bedeutet !comp(a, b) && !comp(b, a) und nicht notwendigerweise a == b. Auch die Ausgabe ist sortiert.

Duplikate werden nicht einfach entfernt: Bei m und n äquivalenten Elementen enthält die Ausgabe |m-n| Elemente. Das sind die überschüssigen Elemente am Ende des Bereichs mit mehr Vorkommen, wobei ihre Reihenfolge erhalten bleibt. Die gewöhnliche Differenz mit std::set_difference ist dagegen einseitig.

Der Ausgabebereich darf sich mit keiner der Eingaben überschneiden. Stelle genügend beschreibbare Positionen bereit oder verwende std::back_inserter mit einem separaten Vektor; reserve() allein erzeugt keine Elemente, die über begin() beschrieben werden können. Der zurückgegebene Iterator zeigt direkt hinter das letzte geschriebene Element. Die Anzahl der Vergleiche ist linear zur Gesamtlänge der Eingaben.

Beispiele

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <iterator>
#include <vector>

int main() {
    const std::vector<int> a{1, 2, 2, 4};
    const std::vector<int> b{2, 3, 4, 4};
    std::vector<int> result;

    std::set_symmetric_difference(
        a.begin(), a.end(), b.begin(), b.end(),
        std::back_inserter(result));

    for (std::size_t i = 0; i < result.size(); ++i) {
        if (i != 0) std::cout << ' ';
        std::cout << result[i];
    }
    std::cout << '\n';
}

Ergebnis

1 2 3 4

Der angezeigte Code und das angegebene Ergebnis wurden in einer isolierten Umgebung mit der im Prüfnachweis für genau diese Version dokumentierten Methode verifiziert.

Quellen