Wie wird die Schnittmenge zwischen zwei Listen in C++ angewendet?

Question

Ich bin neu in C++ Liste.

Ich habe zwei Listen: list1 und list2. Ich brauche gemeinsame Elemente zwischen diesen Listen. Wie kann ich das bekommen?

Answer 1

können Sie verwenden: std::set_intersection für das, sofern Sie zuerst die beiden Listen sortieren:

Beispiel:

#include <algorithm> 
#include <iostream> 
#include <list> 

int main() { 
    std::list<int> list1{2, 5, 7, 8, -3, 7}; 
    std::list<int> list2{9, 1, 6, 3, 5, 2, 11, 0}; 

    list1.sort(); 
    list2.sort(); 

    std::list<int> out; 
    std::set_intersection(list1.begin(), list1.end(), list2.begin(), list2.end(), 
          std::back_inserter(out)); 

    for(auto k : out) 
     std::cout << k << ' '; 
} 

Ausgang:

2 5 

EDIT:

Die obige Methode wird wahrscheinlich nicht gehen ing optimal zu sein, vor allem, weil das Sortieren ein std::list an die CPU ist nicht schön ...

Für einen Trade-off von Raum, für größere Datenmengen das Verfahren unten sicherlich schneller sein, weil wir iterieren durch jede Liste nur einmal, und alle bei jeder Iteration durchgeführten Operationen nicht über eine O(1) abgeschrieben Komplexität

template<typename T> 
std::list<T> intersection_of(const std::list<T>& a, const std::list<T>& b){ 
    std::list<T> rtn; 
    std::unordered_multiset<T> st; 
    std::for_each(a.begin(), a.end(), [&st](const T& k){ st.insert(k); }); 
    std::for_each(b.begin(), b.end(), 
     [&st, &rtn](const T& k){ 
      auto iter = st.find(k); 
      if(iter != st.end()){ 
       rtn.push_back(k); 
       st.erase(iter); 
      } 
     } 
    ); 
    return rtn; 
} 

I std::unordered_multiset eher verwendet geht als std::unordered_set, weil es die Vorkommen von gemeinsamen Duplikaten in beiden Listen bewahrt

I auf zufällig generierte 9000int s, Das Ergebnis war (weniger ist besser), die eine dirty benchmark für die beiden Methoden lief:

Average timings for 100 runs: 
intersection_of: 8.16 ms 
sortAndIntersect: 18.38 ms 

---

Analyse der Verwendung der std::set_intersection Methode:

• Sortierung Liste 1 der Größe N ist: O(Nlog(N))
• Sortierung Liste 2 der Größe M ist: O(Mlog(M))
• die Kreuzung zu finden ist: O(M + N)
• Total: O(Nlog(N) + Mlog(M) + M + N) ...(Generalisierte als logarithmische)

M und N Unter der Annahme gleich sind, können wir es als verallgemeinern: O(Nlog(N))

Aber wenn wir verwenden, um die intersection_of Methode, die ich gepostet oben:

• Iterieren durch Liste 1 der Größe N und Hinzufügen zu dem Satz ist: O(N) + O(1) = O(N)
• Iterieren durch Liste 2 der Größe M, die Überprüfung der multiset, zusätzlich zu out, das Entfernen von Liste 2: O(M) + O(1) + O(1) + O(1) = O(M)
• Total: O(M + N) ... (verallgemeinert als linear)

Unter der Annahme, M und N sind gleich, können wir es verallgemeinern als: O(N)