C++中的向量交集
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/19483663/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Vector intersection in C++
提问by Tyler
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">
回答by masoud
Try std::set_intersection, for example:
试试std::set_intersection，例如：
#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 << ' ';
}
回答by Mikhail Volskiy
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.
您只需要对较小的向量进行排序。然后对较大的向量进行一次遍历，并使用二分搜索测试较小向量中是否存在其项。
回答by Eric Auld
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.
相反的排序，可以考虑通过使散列设置较小的矢量出来，然后循环在较大的载体检查这些元素，作为建议交易存储时间在这里。这比排序和使用std::set_intersection.
