Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Vector intersection in C++

I have this function

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

I have two vectors of strings and I want to find the strings that are present in both, which then fills a third vector with the common elemnts.

If my vectors are...

v1 = <"a","b","c">
v2 = <"b","c">
like image 444
Tyler Avatar asked Oct 20 '13 22:10

Tyler


People also ask

How do you find the intersection of two vectors in C++?

std::set_intersection in C++ The intersection of two sets is formed only by the elements that are present in both sets. The elements copied by the function come always from the first range, in the same order. The elements in the both the ranges shall already be ordered.

What is intersection C++?

C++ Algorithm set_intersection() function is used to find the intersection of two sorted ranges[first1, last1) and [first2, last2), which is formed only by the elements that are present in both sets.


3 Answers

Try std::set_intersection, for example:

#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 << ' ';
}
like image 152
masoud Avatar answered Oct 23 '22 07:10

masoud


You need to sort just the smaller vector. Then do a single pass over the bigger vector and test a presence of its items in a smaller vector by using a binary search.

like image 35
Mikhail Volskiy Avatar answered Oct 23 '22 05:10

Mikhail Volskiy


Instead of sorting, consider trading memory for time by making a hash set out of the smaller vector, and then looping over the larger vector checking for those elements, as suggested here. That would be faster than sorting and using std::set_intersection.

like image 3
Eric Auld Avatar answered Oct 23 '22 06:10

Eric Auld