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">
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.
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.
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 << ' ';
}
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.
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
.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With