WissensdatenbankPrüfungszentrum
DEDeutsch
Sprache wählen13

CKTIS / C++

std::set_difference — Differenz sortierter Bereiche

std::set_difference kopiert die Differenz zweier sortierter Bereiche in ein separates Ziel. Dabei werden Duplikate berücksichtigt: Jedes äquivalente Element im zweiten Bereich entfernt ein Vorkommen aus dem Ergebnis des ersten Bereichs.

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

Syntax

std::set_difference(first1, last1, first2, last2, result)
std::set_difference(first1, last1, first2, last2, result, comp)

std::set_difference aus dem Header <algorithm> berechnet die gerichtete Differenz A − B, nicht die symmetrische Differenz. Der Algorithmus akzeptiert zwei halboffene Iteratorbereiche und einen Ausgabeiterator; std::set-Container sind nicht erforderlich. Die hier beschriebenen Aufrufe verwenden keine Ausführungsrichtlinie.

Beide Bereiche müssen nach derselben Ordnung sortiert sein: standardmäßig nach std::less{}, in der zweiten Form nach comp. Der Komparator muss eine strikte schwache Ordnung definieren. Äquivalenz bedeutet !comp(a, b) && !comp(b, a) und nicht unbedingt a == b. Wird die Sortiervoraussetzung verletzt, ist das Verhalten undefiniert.

Der Algorithmus erhält Duplikate: Bei m äquivalenten Elementen im ersten und n im zweiten Bereich kopiert er die letzten max(m - n, 0) Elemente aus dem ersten Bereich, in ihrer ursprünglichen Reihenfolge. Das Ergebnis ist sortiert; die Eingaben bleiben unverändert.

Der Zielbereich darf sich nicht mit einem der Eingabebereiche überschneiden. Wenn der Ausgabeiterator Elemente in einem Bereich überschreibt, muss dieser Bereich genügend vorhandene, beschreibbare Elemente enthalten. Ein Ausgabeiterator muss sich jedoch nicht auf vorhandene Elemente beziehen: std::back_inserter hängt Elemente an einen Container an, und std::ostream_iterator schreibt in einen Ausgabestrom. Der zurückgegebene Iterator zeigt hinter das geschriebene Ergebnis. Die Komplexität ist linear in der Summe der Eingabelängen, ohne eine vorherige Sortierung einzurechnen.

Beispiele

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

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

    std::set_difference(a.begin(), a.end(), b.begin(), b.end(),
                        std::back_inserter(difference));

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

Ergebnis

1 2 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