std::set_intersection

Definiert in Header `<algorithm>`
template< class InputIt1, class InputIt2, class OutputIt > OutputIt set_intersection( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first );	(1)	(constexpr seit C++20)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class ForwardIt3 > ForwardIt3 set_intersection( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2, ForwardIt3 d_first );	(2)	(seit C++17)
template< class InputIt1, class InputIt2, class OutputIt, class Compare > OutputIt set_intersection( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first, Compare comp );	(3)	(constexpr seit C++20)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class ForwardIt3, class Compare > ForwardIt3 set_intersection( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2, ForwardIt3 d_first, Compare comp );	(4)	(seit C++17)

Erzeugt einen sortierten Bereich, der bei d_first beginnt und Elemente enthält, die in beiden sortierten Bereichen [first1, last1) und [first2, last2) gefunden werden.

Wenn [first1, last1) m Elemente enthält, die untereinander äquivalent sind, und [first2, last2) n Elemente enthält, die mit ihnen äquivalent sind, werden die ersten std::min(m, n) Elemente aus [first1, last1) in den Ausgabebereich kopiert, wobei die Reihenfolge beibehalten wird.

1) Wenn [first1, last1) oder [first2, last2) nicht sortiert ist in Bezug auf operator<(until C++20)std::less{}(seit C++20), ist das Verhalten undefiniert.

3) Wenn [first1, last1) oder [first2, last2) nicht sortiert ist bezüglich comp, ist das Verhalten undefiniert.

2,4) Dasselbe wie (1,3), aber ausgeführt gemäß policy.

Diese Überladungen nehmen an der Auflösungsauflösung teil, nur wenn alle folgenden Bedingungen erfüllt sind

std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> ist true.	(bis C++20)
std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>> ist true.	(seit C++20)

Wenn sich der Ausgabebereich mit [first1, last1) oder [first2, last2) überschneidet, ist das Verhalten undefiniert.

[bearbeiten] Parameter

first1, last1	-	das Iteratorpaar, das den ersten sortierten Bereich der zu untersuchenden Elemente definiert
first2, last2	-	das Iteratorpaar, das den zweiten sortierten Bereich der zu untersuchenden Elemente definiert
d_first	-	der Anfang des Ausgabebereichs
policy	-	die Ausführungsrichtlinie, die verwendet werden soll
comp	-	Vergleichsfunktions-Objekt (d.h. ein Objekt, das die Anforderungen an Compare erfüllt), das true zurückgibt, wenn das erste Argument weniger (d.h. vorher) als das zweite geordnet ist. Die Signatur der Vergleichsfunktion sollte äquivalent zu Folgendem sein bool cmp(const Type1& a, const Type2& b); Obwohl die Signatur nicht unbedingt const& haben muss, darf die Funktion die übergebenen Objekte nicht verändern und muss in der Lage sein, alle Werte vom Typ (möglicherweise const) `Type1` und `Type2` unabhängig von der Wertkategorie zu akzeptieren (daher ist `Type1&` nicht erlaubt, ebenso wenig `Type1`, es sei denn, für `Type1` ist ein Move äquivalent zu einem Kopieren(since C++11)). Die Typen Type1 und Type2 müssen so beschaffen sein, dass Objekte der Typen InputIt1 und InputIt2 dereferenziert und dann implizit in sowohl Type1 als auch Type2 konvertiert werden können.
Typanforderungen
- `InputIt1, InputIt2` müssen die Anforderungen an LegacyInputIterator erfüllen.
- `OutputIt` muss die Anforderungen an LegacyOutputIterator erfüllen.
- `ForwardIt1, ForwardIt2, ForwardIt3` müssen die Anforderungen von LegacyForwardIterator erfüllen.
- `Compare` muss die Anforderungen an Compare erfüllen.

[bearbeiten] Rückgabewert

Iterator hinter das Ende des erstellten Bereichs.

[bearbeiten] Komplexität

Gegeben $\scriptsize N_1$ $N 1$ als std::distance(first1, last1) und $\scriptsize N_2$ $N 2$ als std::distance(first2, last2)

1,2) Höchstens

2\cdot(N 1 +N 2)-1

Vergleiche mit operator<(bis C++20)std::less{}(seit C++20).

3,4) Höchstens

2\cdot(N 1 +N 2)-1

Aufrufe der Vergleichsfunktion comp.

[bearbeiten] Ausnahmen

Die Überladungen mit einem Template-Parameter namens ExecutionPolicy berichten Fehler wie folgt

Wenn die Ausführung einer Funktion, die als Teil des Algorithmus aufgerufen wird, eine Ausnahme auslöst und ExecutionPolicy eine der Standardrichtlinien ist, wird std::terminate aufgerufen. Für jede andere ExecutionPolicy ist das Verhalten implementierungsabhängig.
Wenn dem Algorithmus der Speicher zur Neuzuweisung fehlt, wird std::bad_alloc ausgelöst.

[bearbeiten] Mögliche Implementierung

set_intersection (1)

template<class InputIt1, class InputIt2, class OutputIt>
OutputIt set_intersection(InputIt1 first1, InputIt1 last1,
                          InputIt2 first2, InputIt2 last2, OutputIt d_first)
{
    while (first1 != last1 && first2 != last2)
    {
        if (*first1 < *first2)
            ++first1;
        else
        {
            if (!(*first2 < *first1))
                *d_first++ = *first1++; // *first1 and *first2 are equivalent.
            ++first2;
        }
    }
    return d_first;
}

set_intersection (3)

template<class InputIt1, class InputIt2, class OutputIt, class Compare>
OutputIt set_intersection(InputIt1 first1, InputIt1 last1,
                          InputIt2 first2, InputIt2 last2, OutputIt d_first, Compare comp)
{
    while (first1 != last1 && first2 != last2)
    {
        if (comp(*first1, *first2))
            ++first1;
        else
        {
            if (!comp(*first2, *first1))
                *d_first++ = *first1++; // *first1 and *first2 are equivalent.
            ++first2;
        }
    }
    return d_first;
}

[bearbeiten] Beispiel

Führen Sie diesen Code aus

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
 
int main()
{
    std::vector<int> v1{7, 2, 3, 4, 5, 6, 7, 8};
    std::vector<int> v2{5, 7, 9, 7};
    std::sort(v1.begin(), v1.end());
    std::sort(v2.begin(), v2.end());
 
    std::vector<int> v_intersection;
    std::set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(),
                          std::back_inserter(v_intersection));
 
    for (int n : v_intersection)
        std::cout << n << ' ';
    std::cout << '\n';
}

Ausgabe

5 7 7

[bearbeiten] Fehlerberichte

Die folgenden Verhaltensändernden Fehlerberichte wurden rückwirkend auf zuvor veröffentlichte C++-Standards angewendet.

DR	angewendet auf	Verhalten wie veröffentlicht	Korrigiertes Verhalten
LWG 291	C++98	es war nicht spezifiziert, wie äquivalente Elemente in den Eingabebereichen behandelt werden sollen	spezifiziert

[bearbeiten] Siehe auch

set_union	Berechnet die Vereinigung zweier Mengen (Funktionstemplate) [edit]
ranges::set_intersection (C++20)	Berechnet den Schnitt zweier Mengen (Algorithmus-Funktionsobjekt)[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