ベクトルの交点

Question

私はベクトルがほとんどありません。たとえば、4

std::vector1 <CMyClass>; 
std::vector2 <CMyClass>; 
std::vector3 <CMyClass>; 
std::vector4 <CMyClass>; 

すべてのベクトルに存在するオブジェクトを持つベクトルが必要です。 たとえば、 if

Vector1 has C1, C2, C3; 
Vector2 has C1, C2; 
Vector3 has C1, C4; 
Vector has C1, C5; 

結果ベクトルにC1が必要です。

私はループを実行し、結果のベクトルを比較して調べることができますが、それを行う直接的な方法があるかどうかを知りたいと思います。 オペレータまたはデータ構造のように。

Answer 1

1. ベクトルをソート。
2. std::set_intersection()を3回（あなたが持っているベクトルの数が1になります）使用してください。

---

時間複雑度の分析：2 *（firstSize + secondSize）で

• 4 * O（nlogn）= O（nlogn）
• リニア - 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; 
} 

出力：

交点が2つの要素があります：10 20

Answer 2

交差点、ないスーパーセット（つまり労働組合、または4つのベクトルのいずれかに含まれるすべての要素のコレクションを意味します）です。

ベクターを並べ替えることができる場合は、直接std::set_intersectionを使用します。

あなたは交差点（A、Bからの最終的な結果を取得する前A =交差点（V1、V2）とB =交点（3,4）を中間結果を取得し、その3倍を使用する必要があります）。

linked answerを使用する方がより効率的です（2つの中間コンテナをスキップします）が、より手作業でのコーディング（およびテスト）が必要になります。

Answer 3

これはどうですか？あなたのクラス（および補助オペレータ< <（））にオペレータ<（）を追加する必要があります。各ベクトルから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]