C++中的矢量交集
C++中的矢量交集
提问于 2013-10-21 06:33:31
我有这个功能
vector<string> instersection(const vector<string> &v1, const vector<string> &v2);我有两个字符串向量，我想找到这两个向量中都存在的字符串，然后用公共元素填充第三个向量。
如果我的向量是...
v1 = <"a","b","c">
v2 = <"b","c">回答 3
Stack Overflow用户
回答已采纳
发布于 2013-10-21 06:43:14
尝试使用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 << ' ';
}Stack Overflow用户
发布于 2016-02-04 03:32:42
你只需要对较小的向量进行排序。然后对较大的向量执行一次遍历，并使用二进制搜索来测试其项目在较小的向量中的存在。
Stack Overflow用户
发布于 2019-04-15 03:32:18
不是排序，而是考虑用内存来换取时间，方法是从较小的向量中生成一个哈希集，然后按照here的建议，在较大的向量上循环检查这些元素。这将比排序和使用std::set_intersection更快。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/19483663
复制相关文章
相似问题