WissensdatenbankPrüfungszentrum
DEDeutsch
Sprache wählen13

CKTIS / C++

std::set_intersection — Schnittmenge sortierter Bereiche

std::set_intersection kopiert die gemeinsamen Elemente zweier sortierter Bereiche in ein separates Ziel. Duplikate bleiben entsprechend der kleineren Anzahl ihres Vorkommens erhalten; es entstehen also nicht nur eindeutige Werte.

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

Syntax

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

std::set_intersection aus <algorithm> berechnet die Schnittmenge der Bereiche [first1, last1) und [first2, last2). Dafür sind keine std::set-Container erforderlich. Dieser Eintrag behandelt die klassischen Iterator-Überladungen ohne Ausführungsrichtlinie; sie geben einen Iterator hinter dem zuletzt geschriebenen Element zurück.

Beide Bereiche müssen bereits nach derselben Ordnung sortiert sein: standardmäßig nach std::less{}, oder bei der Überladung mit comp nach dem übergebenen Komparator. Der Komparator muss eine strikte schwache Ordnung festlegen. Äquivalenz bedeutet !comp(a, b) && !comp(b, a), nicht zwingend a == b. Nicht sortierte Eingaben verletzen eine Vorbedingung.

Kommt ein äquivalenter Wert im ersten Bereich m-mal und im zweiten n-mal vor, enthält das Ergebnis die ersten min(m, n) entsprechenden Elemente aus dem ersten Bereich. Das Ergebnis bleibt sortiert. Die Anzahl der Vergleiche ist linear zur Gesamtlänge der Eingaben.

Der Ausgabebereich darf sich mit keinem der Eingabebereiche überschneiden. Ein gewöhnlicher Ausgabeiterator benötigt ausreichend viele beschreibbare Elemente; allein reserve() legt diese nicht an. Das Beispiel verwendet std::back_inserter(common), um Elemente an einen separaten Vektor anzuhängen. Die Quelle ist ein fortlaufend überarbeiteter Entwurf; das Beispiel beschränkt sich auf eine in C++23 verfügbare API.

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, 7};
    std::vector<int> common;

    std::set_intersection(a.begin(), a.end(), b.begin(), b.end(),
                          std::back_inserter(common));

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

Ergebnis

2 2 7

Der gezeigte Code und die angegebene Ausgabe wurden in einer isolierten Umgebung mit der Methode überprüft, die im Prüfnachweis für genau diese Version dokumentiert ist.

Quellen