Was ist der Leistungsunterschied zwischen der Verwendung eines Iterators zum Durchlaufen einer STL-Map im Vergleich zu einem Vektor? Ich möchte den Kartenschlüssel für das Einfügen, Löschen und einige Zugriffe verwenden, aber ich muss auch regelmäßige Zugriffe auf alle Element in der Karte.Iteratorzugriffsleistung für STL-Karte vs. Vektor?
Sowohl die Karte als auch der Vektor durchlaufen die gesamte Sammlung mit O (N). Allerdings speichert der Vektor (wie Liste gegen Vektor) Elemente zusammenhängend, so dass das Zugreifen auf das nächste Element viel billiger ist, da es den Cache optimal nutzt, während die Karte dies nicht tut.
Aber da Sie müssen haben Lookup basierend auf Schlüsseln, gibt es nicht wirklich eine Alternative. Sie könnten einen Vektor von Paaren verwenden, die nach dem ersten Element sortiert sind, aber wenn die Sammlung änderbar sein soll, wird dies sehr langsam sein. Benutze einfach eine Karte.
Verwenden Sie die Karte, wenn Sie schnellen Zugriff auf den Schlüssel benötigen. Andernfalls verwenden Sie den Vektor die ganze Zeit, es sei denn, einige Leistungsprobleme werden mit Profiler entdeckt.
Iteration durch jedes Element einer Karte dauert O (n) Zeit. wikipedia
Ich weiß nicht, warum jemand abgelehnt hat. Es ist wahrlich O (N), um den ganzen Baum zu transversieren. –
Ich wäre nett, wenn es zeigen würde, wer gewählt hat. –
Sich blutig rächen? :) –
Durchsuchen der Baum ist nicht teuer (grosso modo wie folgt einer verknüpften Liste), Sie werden nicht von dem Cache so viel mit einem Vektor profitieren, aber im Allgemeinen ist es das, was Sie tun, wenn Sie iterieren, das ist teuer, nicht die Iteration selbst.
Können Sie uns mehr darüber erzählen, was Sie bei der Iteration der gesamten Karte erwarten?
This link hat eine schöne Tabelle der Leistung für verschiedene Operationen auf allen STL-Containern.
Im Allgemeinen, wenn Sie eine Menge von Einfügen, Entfernen oder Suchen auf der Grundlage eines Schlüssels tun müssen, dann ist die Karte der Weg zu gehen.
Wenn Sie den Container nur einmal einrichten und dann wie ein Array darauf zugreifen müssen, verwenden Sie einen Vektor.
EDIT: Leistungstabelle von STL-Container-Operationen:
Es gibt eine Feinheit in der Frage. Der Benutzer möchte nicht auf ein Element zugreifen, sondern auf _alle_ Elemente in der Karte. Die amortisierte Kostenanalyse liefert O (N) für die gesamte Querrichtung der Karte (jede Kante im Baum wird nur zweimal durchquert, einmal nach unten, einmal nach oben). –
Der Link ist unterbrochen. Ich denke, es sollte sein: http://devmentor.org/references/stl/stl.php –
Warum einfügen Kopf für Vektor ist n/a und entfernen Kopf für Vektor ist O (1)? Beide sollten O (n) sein. Und Vektorfind ist O (log n)? Da stimmt etwas nicht. – Slava
Iterieren über eine Karte kann linear sein, aber praktisch ist es nicht so effizient von den Implementierungen in C++. Mein Rat ist also, einen Vektor zu verwenden und eine andere Karte zu verwenden, um die Elemente in dem Vektor in linearer Zeit zu lokalisieren.
Der Zugriff auf jedes Element in der Karte ist etwas wichtiger, da es häufig abfeuern wird, aber ich brauche immer noch eine relativ schnelle key-basierte Suche (ich kann diese Anforderung herausnehmen, aber die Dinge werden unvernünftig haarig werden). Laut Greg Rogers Antwort scheint Map besser zu passen. –