std::ranges::set_intersection, std::ranges::set_intersection_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_intersection_result<I1, I2, O> set_intersection( 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_intersection_result<ranges::borrowed_iterator_t<R1>, ranges::borrowed_iterator_t<R2>, O> set_intersection( 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_intersection_result = ranges::in_in_out_result<I1, I2, O>;	(3)	(seit C++20)

Konstruiert einen sortierten Bereich beginnend bei result, der Elemente enthält, die sowohl im sortierten Eingabebereich [first1, last1) als auch im sortierten Eingabebereich [first2, last2) vorkommen. Wenn ein Element m Mal im Bereich [first1, last1) und n Mal im Bereich [first2, last2) gefunden wird, werden die ersten min(m, n) Elemente aus dem ersten Bereich nach result kopiert. Die Reihenfolge äquivalenter Elemente bleibt erhalten.

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) Entspricht (1), verwendet aber 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.

[edit] 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

[edit] Rückgabewert

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

[edit] 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) und ranges::distance(first2, last2) sind, bzw.

[edit] Mögliche Implementierung

struct set_intersection_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_intersection_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)))
                ++first1;
            else if (std::invoke(comp, std::invoke(proj2, *first2),
                                       std::invoke(proj1, *first1)))
                ++first2;
            else
                *result = *first1, ++first1, ++first2, ++result;
        }
        return {ranges::next(std::move(first1), std::move(last1)),
                ranges::next(std::move(first2), std::move(last2)),
                std::move(result)};
    }
 
    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_intersection_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_intersection_fn set_intersection {};

[edit] Beispiel

Führen Sie diesen Code aus

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
 
void print(const auto& v, const auto& rem)
{
    std::cout << "{ ";
    for (const auto& e : v)
        std::cout << e << ' ';
    std::cout << '}' << rem;
}
 
int main()
{
    const auto in1 = {1, 2, 2, 3, 4, 5, 6};
    const auto in2 = {2, 2, 3, 3, 5, 7};
    std::vector<int> out {};
 
    std::ranges::set_intersection(in1, in2, std::back_inserter(out));
 
    print(in1, " ∩ "), print(in2, " = "), print(out, "\n");
}

Ausgabe

{ 1 2 2 3 4 5 6 } ∩ { 2 2 3 3 5 7 } = { 2 2 3 5 }

[edit] 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_symmetric_difference (C++20)	Berechnet die symmetrische Differenz zwischen zwei Mengen (Algorithmus-Funktionsobjekt)[edit]
ranges::includes (C++20)	Gibt true zurück, wenn eine Sequenz eine Untersequenz einer anderen ist (Algorithmus-Funktionsobjekt)[edit]
set_intersection	Berechnet den Schnitt zweier 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