Performing set_difference auf ungeordnete Sätze

Question

set_difference Der Algorithmus erfordert die folgenden

Die Elemente in den Bereichen sind bereits nach dem gleichen Kriterium geordnet werden

die für Hash-Tabellen nicht der Fall ist.

Ich denke, eine Menge Differenz AB in Bezug auf die std::remove_copy der Implementierung, wo die Entfernung Kriterium

Gibt es eine Standard-valid-am schnellsten sichersten die Existenz eines Elements A in der Gruppe B sein würde Weg, es zu tun?

Answer 1

Wenn Sie zwei Hash-Tabellen haben, sollte der effizienteste Weg sein, über einen von ihnen zu iterieren und jedes Element in der anderen Hash-Tabelle nachzuschlagen. Dann fügen Sie diejenigen, die Sie nicht finden, in einen dritten Behälter ein. Eine grobe Skizze könnte wie folgt aussehen:

std::vector<int> result; 
std::copy_if(lhs.begin(), lhs.end(), std::back_inserter(result), 
    [&rhs] (int needle) { return rhs.find(needle) == rhs.end(); }); 

Answer 2

Wenn Sie 2 ungeordnete Mengen A und B die Länge Na und Nb haben und Sie eine Set-Differenz zu tun, das heißt, alle Elemente von A nicht in B erhalten, dann Da das Nachschlagen in B eine konstante Zeit ist, ist Ihre Komplexität, einfach über A zu iterieren und zu prüfen, ob es in B ist, O (Na).

Wenn A eine ungeordnete Menge und B ist eine Gruppe (oder sortiert Vektor usw.), dann würde jedes lookup log (Nb), so dass die volle Komplexität würde O (Na * log (Nb))

be Sorting Ein erster würde es machen (Na * log (Na)), dann Na + Nb zu sortieren, um die Zusammenführung durchzuführen. Wenn Na signifikant kleiner als Nb ist, ist Na * log (Nb) sowieso deutlich kleiner als Na + Nb und wenn Na zu Nb größer wird, dann wird es nicht schneller sein.

Deshalb denke ich, dass Sie nichts gewinnen, indem Sie A zuerst sortieren (indem Sie es zuerst sortieren, ich meine es in eine sortierte Sammlung zu verschieben).