Vektorschnittpunkt in C++

Ich habe diese Funktion

vector<string> instersection(const vector<string> &v1, const vector<string> &v2);

Ich habe zwei Vektoren von Zeichenfolgen und möchte die Zeichenfolgen finden, die in beiden vorhanden sind, die dann einen dritten Vektor mit den gemeinsamen Elementen füllen.

Wenn meine Vektoren…

v1 = <"a","b","c">
v2 = <"b","c">

Versuchen std::set_intersectionzum Beispiel:

#include <algorithm> //std::sort
#include <iostream> //std::cout
#include <string> //std::string
#include <vector> //std::vector

std::vector<std::string> intersection(std::vector<std::string> v1,
                                      std::vector<std::string> v2){
    std::vector<std::string> v3;

    std::sort(v1.begin(), v1.end());
    std::sort(v2.begin(), v2.end());

    std::set_intersection(v1.begin(),v1.end(),
                          v2.begin(),v2.end(),
                          back_inserter(v3));
    return v3;
}

int main(){
    std::vector<std::string> v1 {"a","b","c"};
    std::vector<std::string> v2 {"b","c"};

    auto v3 = intersection(v1, v2);

    for(std::string n : v3)
        std::cout << n << ' ';
}

Sie müssen nur den kleineren Vektor sortieren. Führen Sie dann einen einzigen Durchgang über den größeren Vektor durch und testen Sie das Vorhandensein seiner Elemente in einem kleineren Vektor, indem Sie eine binäre Suche verwenden.

Anstatt zu sortieren, sollten Sie den Speicher gegen Zeit eintauschen, indem Sie einen Hash-Satz aus dem kleineren Vektor erstellen und dann den größeren Vektor durchlaufen, um nach diesen Elementen zu suchen, wie vorgeschlagen hier. Das ginge schneller als sortieren und verwenden std::set_intersection.