Intersection de vecteurs

Question

J'ai peu de vecteurs. par exemple 4

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

Je veux un vecteur résultant qui aura l'objet qui est présent dans tout le vecteur. Par exemple. si

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

Je veux que le vecteur résultant ait C1.

Je peux lancer une boucle et comparer et trouver le vecteur résultant, mais je voudrais savoir s'il existe une façon directe de le faire. Comme un opérateur ou une structure de données.

Answer 1

1. Trier les vecteurs. Utilisez std::set_intersection() trois fois (autant de vecteurs que vous avez - 1).

---

Temps de complexité Analyse:

• 4 * O (nlogn) = O (nlogn)
• linéaire 2 * (firstSize + secondSize) - 1
• linéaire 2 * (firstSecondInterSize + thirdSize) - 1
• linéaire en 2 * (firstSecondThirdInterSize + fourthSize) - 1

qui est délimitée par O (nlogn), ce qui signifie que le tri est le goulot d'étranglement de l'algorithme.

---

exemple de code complet:

#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; 
} 

Sortie:

L'intersection a 2 éléments: 10 20

Answer 2

C'est une intersection, pas un surensemble (cela signifierait l'union ou la collecte de tous les éléments contenus dans l'une des quatre vecteurs). Si vous pouvez trier les vecteurs, la méthode directe est std::set_intersection.

Vous devrez utiliser trois fois, d'obtenir des résultats intermédiaires A = intersection (v1, v2) et B = intersection (3,4) avant d'obtenir le résultat final de intersection (A, B.

L'utilisation de ce linked answer sera plus efficace (en ignorant les deux conteneurs intermédiaires), mais nécessite plus de codage manuel (et de test).

Answer 3

Que pensez-vous de cela? Vous devez ajouter l'opérateur <() dans votre classe (et l'opérateur auxiliaire < <()). Formez std :: ensemble à partir de chaque vecteur, puis calculez l'intersection de ces ensembles. Encore une fois - faire le vecteur de l'ensemble résultant.

#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; 
} 

sortie: [1,]