Suchen Sie Set Intersection in C++

  1. Verwenden Sie die Methode std::set_intersection, um Mengenschnittpunkt in C++ zu finden
  2. Verwendung der Methode std::set_symmetric_difference zur Ermittlung der symmetrischen Differenz in C++

In diesem Artikel werden verschiedene Methoden erläutert, wie man die Mengenschnittmenge in C++ findet.

Verwenden Sie die Methode std::set_intersection, um Mengenschnittpunkt in C++ zu finden

Die Methode std::set_intersection ist Teil der C++-Algorithmenbibliothek, die im <algorithm>-Header enthalten ist. Die Operation des set_intersection-Algorithmus ist nicht auf std::set-Objekte beschränkt, sondern kann jedes bereichsbasierte Objekt, z. B. std::vector, verarbeiten. Beachten Sie, dass beide Eingabebereiche sortiert sein müssen, bevor sie an einen set_intersection-Algorithmus übergeben werden.

Im folgenden Beispiel deklarieren wir zwei std::set-Variablen und initialisieren sie mit beliebigen Elementen vom Typ String. Die ersten vier Parameter der Funktion set_intersection sind Bereichs-Iteratoren von entsprechenden Objekten, und das fünfte Argument ist der Beginn des Bereichs, in dem die berechnete Schnittmenge gespeichert wird. In diesem Fall deklarieren wir einen std::vector, um diese Elemente zu halten.

#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <algorithm>

using std::cout; using std::endl;
using std::cin; using std::string;
using std::set; using std::vector;

template<typename T>
void printVectorElements(vector<T> &vec)
{
    cout << "{ ";
    for (const auto &item : vec) {
        cout << item << ", ";
    }
    cout << "\b\b }" << endl;
}

int main() {
    set<string> s1 {"array", "vector",
                    "deque", "list",
                    "set", "map",
                    "multimap", "span"};
    set<string> s2(s1);
    s2.insert("stack");
    s2.insert("queue");

    vector<string> s1s2_intsec;

    std::set_intersection(s1.begin(), s1.end(),
                          s2.begin(), s2.end(),
                          std::back_inserter(s1s2_intsec));

    cout << "s1 ∩ s2: ";
    printVectorElements(s1s2_intsec);

    exit(EXIT_SUCCESS);
}

Ausgabe:

s1 ∩ s2: ( array, deque, list, map, multimap, set, span, vector )

Auch wenn std::set_intersection die vom Benutzer angegebenen Schnittelemente speichert, darf es nicht der Bereich sein, der sich mit einem der Eingabebereiche überschneidet. Ein weiterer wichtiger Punkt, der beachtet werden muss, ist die Angabe des Zielbereichs, der genügend Platz zum Speichern der Schnittelemente hat. Die flexible Methode hierfür wäre, ein dynamisches Array std::vector zu verwenden und die Methode std::back_inserter zu benutzen, um Elemente in das Objekt zu schieben. Wenn Sie den Iterator vector.begin() angeben, ohne den Speicher als Zielparameter zu reservieren, kann der Algorithmus einen Segmentierungsfehler werfen. Das nächste Beispiel demonstriert die Methode set_intersection auf Vektor-Objekten.

#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <algorithm>

using std::cout; using std::endl;
using std::cin; using std::string;
using std::set; using std::vector;

template<typename T>
void printVectorElements(vector<T> &vec)
{
    cout << "{ ";
    for (const auto &item : vec) {
        cout << item << ", ";
    }
    cout << "\b\b }" << endl;
}

int main() {
    vector<int> v1v2_intsec;
    vector<int> v1 {9,7,5,1,2};
    vector<int> v2 {4,3,2,1,7,8};
    std::sort(v1.begin(), v1.end());
    std::sort(v2.begin(), v2.end());

    std::set_intersection(v1.begin(), v1.end(),
                          v2.begin(), v2.end(),
                          std::back_inserter(v1v2_intsec));
    cout << "v1 ∩ v2: ";
    printVectorElements(v1v2_intsec);

    exit(EXIT_SUCCESS);
}

Ausgabe:

v1 ∩ v2: ( 1, 2, 7 )

Verwendung der Methode std::set_symmetric_difference zur Ermittlung der symmetrischen Differenz in C++

Ein weiterer Algorithmus aus der C++-Standardbibliothek ist die Methode std::set_symmetric_difference, die nach den Elementen sucht, die nur in einem der Eingabebereiche gefunden werden. Die Funktionsparameter sind ähnlich wie bei der Methode std::set_intersection. Beide Algorithmen nehmen sortierte Bereiche und speichern die gefundenen Elemente ebenfalls sortiert ab. Beachten Sie, dass der std:set-Container standardmäßig sortierte Elemente enthält. Daher kann er direkt als Eingabebereich übergeben werden. Dagegen muss der Inhalt von std::vector explizit sortiert werden, bevor er von std::set_symmetric_difference verarbeitet wird.

#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <algorithm>

using std::cout; using std::endl;
using std::cin; using std::string;
using std::set; using std::vector;

template<typename T>
void printVectorElements(vector<T> &vec)
{
    cout << "{ ";
    for (const auto &item : vec) {
        cout << item << ", ";
    }
    cout << "\b\b }" << endl;
}

int main() {
    vector<int> v1 {9,7,5,1,2};
    vector<int> v2 {4,3,2,1,7,8};
    std::sort(v1.begin(), v1.end());
    std::sort(v2.begin(), v2.end());

    vector<int> v1v2_symdif;
    std::set_symmetric_difference(v1.begin(), v1.end(),
                          v2.begin(), v2.end(),
                          std::back_inserter(v1v2_symdif));
    cout << "v1 △ v2: ";
    printVectorElements(v1v2_symdif);

    exit(EXIT_SUCCESS);
}

Ausgabe:

v1 △ v2: ( 3, 4, 5, 8, 9 )