向量的交集
Intersection of vectors
我的向量很少。例如 4
std::vector1 <CMyClass>;
std::vector2 <CMyClass>;
std::vector3 <CMyClass>;
std::vector4 <CMyClass>;
我想要一个合成向量,其中包含存在于所有向量中的对象。
例如。如果
Vector1 has C1, C2, C3;
Vector2 has C1, C2;
Vector3 has C1, C4;
Vector has C1, C5;
我希望合成向量具有 C1。
我可以运行循环并比较并找出结果向量,但我想知道是否有任何直接的方法可以做到这一点。
像一些运算符或数据结构。
这是一个 交集,而不是 超集(这意味着任何四个向量)。
如果可以对向量进行排序,直接的方法是使用std::set_intersection
。
你必须使用它三次,得到中间结果 A=intersection(v1,v2) 和 B=intersection(3,4) 在从 intersection(A,B).
得到最终结果之前
使用这个 linked answer 会更有效率(跳过两个中间容器),但确实需要更多的手动编码(和测试)。
这个呢?您必须在 class 中添加运算符<()(以及辅助运算符<<())。从每个向量形成 std::set,然后计算这些集合的交集。再次 - 从结果集中创建矢量。
#include <iostream>
#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
class CMyClass
{
public:
CMyClass(int n){_n=n;}
~CMyClass(){}
bool operator<(const CMyClass a) const{return _n <a._n;}
friend std::ostream& operator<<(std::ostream& s,const CMyClass& a){s<<a._n;return s;}
private:
int _n;
};
vector<CMyClass> find_intersect(vector<vector<CMyClass>>& vecs)
{
vector<CMyClass> res;
if (vecs.empty()) return res;
set<CMyClass> S;
for_each(vecs[0].begin(),vecs[0].end(),[&S](const CMyClass& e){S.insert(e);});
for(auto &vec:vecs)
{
set<CMyClass> s,tmp;
for_each(vec.begin(),vec.end(),[&s](const CMyClass& e){s.insert(e);});
set_intersection(S.begin(),S.end(),s.begin(),s.end(),std::inserter(tmp,tmp.begin()));
S=tmp;
if (S.empty()) break;
}
for_each(S.begin(),S.end(),[&res](const CMyClass& e){res.push_back(e);});
return res;
}
int main()
{
vector<CMyClass> v1={1,2,3};
vector<CMyClass> v2={1,2};
vector<CMyClass> v3={1,4};
vector<CMyClass> v4={1,5};
vector<vector<CMyClass>> vectors;
vectors.push_back(v1);
vectors.push_back(v2);
vectors.push_back(v3);
vectors.push_back(v4);
auto res = find_intersect(vectors);
cout<<"[";
for(auto &elem:res)
cout<<elem<<",";
cout<<"]"<<endl;
}
输出:
[1,]
- 对向量进行排序。
- 使用
std::set_intersection()
三次(与您拥有的向量一样多 - 1)。
时间复杂度分析:
- 4 * O(nlogn) = O(nlogn)
- 线性在 2 * (firstSize + secondSize) - 1
- 线性在 2 * (firstSecondInterSize + thirdSize) - 1
- 线性在 2 * (firstSecondThirdInterSize + fourthSize) - 1
以O(nlogn)为界,意味着排序是算法的瓶颈。
完整代码示例:
#include <iostream> // std::cout
#include <algorithm> // std::set_intersection, std::sort
#include <vector> // std::vector
int main () {
std::vector<int> first = {5,10,15,20,25};
std::vector<int> second = {50,40,30,20,10};
std::vector<int> third = {10,20,3,4,0};
std::vector<int> fourth = {4,20,10,3,6};
std::vector<int> v(first.size() + second.size() + third.size() + fourth.size());
std::vector<int>::iterator it;
std::sort (first.begin(),first.end());
std::sort (second.begin(),second.end());
std::sort (third.begin(),third.end());
std::sort (fourth.begin(),fourth.end());
it=std::set_intersection (first.begin(), first.end(), second.begin(), second.end(), v.begin());
it=std::set_intersection (v.begin(), v.end(), third.begin(), third.end(), v.begin());
it=std::set_intersection (v.begin(), v.end(), fourth.begin(), fourth.end(), v.begin());
v.resize(it-v.begin());
std::cout << "The intersection has " << (v.size()) << " elements: ";
for (it=v.begin(); it!=v.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
return 0;
}
输出:
The intersection has 2 elements: 10 20
我的向量很少。例如 4
std::vector1 <CMyClass>;
std::vector2 <CMyClass>;
std::vector3 <CMyClass>;
std::vector4 <CMyClass>;
我想要一个合成向量,其中包含存在于所有向量中的对象。 例如。如果
Vector1 has C1, C2, C3;
Vector2 has C1, C2;
Vector3 has C1, C4;
Vector has C1, C5;
我希望合成向量具有 C1。
我可以运行循环并比较并找出结果向量,但我想知道是否有任何直接的方法可以做到这一点。 像一些运算符或数据结构。
这是一个 交集,而不是 超集(这意味着任何四个向量)。
如果可以对向量进行排序,直接的方法是使用std::set_intersection
。
你必须使用它三次,得到中间结果 A=intersection(v1,v2) 和 B=intersection(3,4) 在从 intersection(A,B).
得到最终结果之前使用这个 linked answer 会更有效率(跳过两个中间容器),但确实需要更多的手动编码(和测试)。
这个呢?您必须在 class 中添加运算符<()(以及辅助运算符<<())。从每个向量形成 std::set,然后计算这些集合的交集。再次 - 从结果集中创建矢量。
#include <iostream>
#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
class CMyClass
{
public:
CMyClass(int n){_n=n;}
~CMyClass(){}
bool operator<(const CMyClass a) const{return _n <a._n;}
friend std::ostream& operator<<(std::ostream& s,const CMyClass& a){s<<a._n;return s;}
private:
int _n;
};
vector<CMyClass> find_intersect(vector<vector<CMyClass>>& vecs)
{
vector<CMyClass> res;
if (vecs.empty()) return res;
set<CMyClass> S;
for_each(vecs[0].begin(),vecs[0].end(),[&S](const CMyClass& e){S.insert(e);});
for(auto &vec:vecs)
{
set<CMyClass> s,tmp;
for_each(vec.begin(),vec.end(),[&s](const CMyClass& e){s.insert(e);});
set_intersection(S.begin(),S.end(),s.begin(),s.end(),std::inserter(tmp,tmp.begin()));
S=tmp;
if (S.empty()) break;
}
for_each(S.begin(),S.end(),[&res](const CMyClass& e){res.push_back(e);});
return res;
}
int main()
{
vector<CMyClass> v1={1,2,3};
vector<CMyClass> v2={1,2};
vector<CMyClass> v3={1,4};
vector<CMyClass> v4={1,5};
vector<vector<CMyClass>> vectors;
vectors.push_back(v1);
vectors.push_back(v2);
vectors.push_back(v3);
vectors.push_back(v4);
auto res = find_intersect(vectors);
cout<<"[";
for(auto &elem:res)
cout<<elem<<",";
cout<<"]"<<endl;
}
输出: [1,]
- 对向量进行排序。
- 使用
std::set_intersection()
三次(与您拥有的向量一样多 - 1)。
时间复杂度分析:
- 4 * O(nlogn) = O(nlogn)
- 线性在 2 * (firstSize + secondSize) - 1
- 线性在 2 * (firstSecondInterSize + thirdSize) - 1
- 线性在 2 * (firstSecondThirdInterSize + fourthSize) - 1
以O(nlogn)为界,意味着排序是算法的瓶颈。
完整代码示例:
#include <iostream> // std::cout
#include <algorithm> // std::set_intersection, std::sort
#include <vector> // std::vector
int main () {
std::vector<int> first = {5,10,15,20,25};
std::vector<int> second = {50,40,30,20,10};
std::vector<int> third = {10,20,3,4,0};
std::vector<int> fourth = {4,20,10,3,6};
std::vector<int> v(first.size() + second.size() + third.size() + fourth.size());
std::vector<int>::iterator it;
std::sort (first.begin(),first.end());
std::sort (second.begin(),second.end());
std::sort (third.begin(),third.end());
std::sort (fourth.begin(),fourth.end());
it=std::set_intersection (first.begin(), first.end(), second.begin(), second.end(), v.begin());
it=std::set_intersection (v.begin(), v.end(), third.begin(), third.end(), v.begin());
it=std::set_intersection (v.begin(), v.end(), fourth.begin(), fourth.end(), v.begin());
v.resize(it-v.begin());
std::cout << "The intersection has " << (v.size()) << " elements: ";
for (it=v.begin(); it!=v.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
return 0;
}
输出:
The intersection has 2 elements: 10 20