Sollte ich std :: set oder std :: unordered_set für eine Reihe von Zeigern verwenden?

Ich habe eine Reihe von Zeigern. Im ersten Schritt füge ich Datenzeiger ein, und im zweiten Schritt iteriere ich über den ganzen Satz und mache etwas mit den Elementen. Die Reihenfolge ist nicht wichtig, ich muss nur Duplikate vermeiden, was beim Zeigervergleich gut funktioniert.Sollte ich std :: set oder std :: unordered_set für eine Reihe von Zeigern verwenden?

Meine Frage ist, ob es vorteilhaft sein könnte, ein ungeordnetes Set für den gleichen Zweck zu verwenden. Ist die Einfügung für einen ungeordneten Satz schneller?

Quelle

2016-02-19 Fabian

"Die Reihenfolge ist nicht wichtig" - Sobald Sie sich dazu entschieden haben, verwenden Sie 'unordered_set'. Der einzige Vorteil von bestellten Containern ist .. Bestellung. –

Wie viele Elemente sprechen wir? Und arbeiten Sie rechenintensiv an jedem Gegenstand oder ist es eher so, dass alle Elemente summiert/multipliziert werden? – MikeMB

Geordnete Behälter haben einen weiteren wichtigen Vorteil, kann es garantieren, dass die Zeit für jede Operation ist O (Ig n), während ungeordnete O (n) im schlimmsten Fall erfordert. Also, wenn Sie Versprechen über Komplizen machen wollen, verwenden Sie std :: set. – James

Wie Ami Tavory kommentierte, wenn Sie keine Bestellung benötigen, dann ist es normalerweise am besten, für ungeordnete Behälter zu gehen. Der Grund dafür ist, dass, wenn die Reihenfolge die Leistung irgendwie verbessert, ungeordnete Container immer noch frei sind, sie zu verwenden, und daher die gleiche oder eine bessere Komplexität sowieso erhalten.

Ein Nachteil von ungeordneten Sammlungen besteht darin, dass sie normalerweise eine Hash-Funktion für den Schlüsseltyp benötigen. Wenn es zu schwer oder zu teuer ist, einen Behälter herzustellen, sind Behälter, die keine Hashes verwenden, möglicherweise besser.

In C++ ist Standard-Bibliothek, die durchschnittliche Einfügungs Komplexität für std::set ist O (log (N)), während für std::unordered_set es O (1) ist. Abgesehen davon gibt es wahrscheinlich weniger Cache-Fehler im Durchschnitt, wenn std::unordered_set verwendet wird.

Am Ende des Tages ist dies jedoch nur Theorie. Sie sollten etwas versuchen, das gut genug klingt und es profilieren, um zu sehen, ob es wirklich ist.

Quelle

2016-02-19 12:32:36

Für Zeiger, worum es sich handelt, gibt es eine Spezialisierung von '' std :: hash'' in der Standard-Bibliothek, so dass Sie sich keine Sorgen machen müssen. –

Eine andere Sache, die zu beachten ist, ist, dass das Verhalten des Vergleichs von nicht verwandten Zeigern (die nicht auf dasselbe Array oder in dasselbe Objekt zeigen) nicht definiert ist. Also, streng genommen ist es unsicher, Zeiger in 'std :: set' zu speichern. –

Da Sie Komplexität erwähnen: Worst-Case-Lookup ist nicht relevant für die ursprüngliche Frage, aber O (N) für ungeordnete_set kann ein Grund sein, ein zu wählen geordnete Menge stattdessen. Ein weiteres Argument für das Nicht-Ordnen ist der Ausdruck der Absicht: Der Leser sieht, dass Ihnen die Ordnung egal ist. – peterchen

Sollte ich std :: set oder std :: unordered_set für eine Reihe von Zeigern verwenden?

Antwort

Verwandte Themen