Kreuzung von Vektoren

Question

Ich habe ein paar Vektor. für zB 4

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

Ich möchte einen resultierenden Vektor, der das Objekt haben wird, das in allen Vektor vorhanden ist. Für z. wenn

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

Ich möchte resultierende Vektor C1 haben.

Ich kann eine Schleife ausführen und vergleichen und den resultierenden Vektor herausfinden, aber ich würde gerne wissen, ob es einen direkten Weg dazu gibt. Wie ein Operator oder eine Datenstruktur.

Answer 1

1. Sortieren der Vektoren.
2. Verwenden Sie std::set_intersection() dreimal (so viele Vektoren haben Sie - 1).

---

Zeitkomplexität Analyse:

• 4 * O (n log n) = O (n log n)
• linear in 2 * (firstSize + secondSize) - 1
• linear in 2 * (firstSecondInterSize + thirdSize) - 1
• linear in 2 * (erste SekundeThirdInterSize + vierteSize) - 1

ist durch O (nlogn) begrenzt, was bedeutet, dass die Sortierung der Flaschenhals des Algorithmus ist.

---

Vollcodebeispiel:

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

Ausgang:

Der Schnitt hat 2 Elemente: 10 20

Answer 2

Das ist eine Kreuzung , kein Superset (dass die Union bedeuten würde, oder eine Sammlung von allen Elementen in jedem der vier Vektoren enthalten). Wenn Sie die Vektoren sortieren können, ist der direkte Weg std::set_intersection zu verwenden.

Du musst es dreimal verwenden, Zwischenergebnisse bekommen A = Kreuzung (v1, v2) und B = Schnittpunkt (3,4) bevor das Endergebnis von Kreuzung bekommen (A, B).

Mit dieser linked answer wird effizienter (überspringen die zwei Zwischenbehälter), erfordert aber mehr manuelle Codierung (und Tests).

Answer 3

Was ist damit? Sie müssen in Ihrer Klasse den Operator <() hinzufügen (und den Hilfsoperator < <()). Form std :: set von jedem Vektor, dann Berechnung der Schnittmenge dieser Mengen. Erneut - mache den Vektor aus der resultierenden Menge.

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

Output: [1,]