Nachdem Sie diese Frage gelesen haben und wenn man sich hier einige Ergebnisse anschaut , scheint es so, als müsste man insgesamt Vermeiden Sie vollständig Listen in C ++. Ich habe immer erwartet, dass verknüpfte Listen die Container der Wahl für Fälle sein werden, in denen ich nur über den gesamten Inhalt iterieren muss, da das Einfügen eine Frage der Zeigerbearbeitung ist und nie neu zugewiesen werden muss.
Offensichtlich werden Listen wegen "Cache-Lokalität" sehr langsam durchlaufen, so dass jeder Vorteil, weniger Speicher oder eine schnellere Addition zu verwenden (was vom zweiten Link nicht so viel schneller ist), nicht funktioniert. t scheinen es wert.
Nachdem ich das gesagt habe, wann sollte ich vom Standpunkt der Leistung aus std::list über std::deque oder, wenn möglich, std::vector ?
Nebenbei, hat std::forward_list auch viele Cache-Fehler?
Wann sollte ich vom Standpunkt der Leistung aus
verwenden?std::list
Aus Performance-Sicht selten. Die einzige Situation, die Ihnen in den Sinn kommt, ist, wenn Sie viele Listen haben, die Sie teilen und verbinden müssen, um andere Listen zu erstellen. Eine verknüpfte Liste kann dies tun, ohne Speicher zuzuordnen oder Objekte zu verschieben.
Der wahre Vorteil von list ist Stabilität: Elemente müssen nicht beweglich sein, und Iteratoren und Referenzen werden niemals ungültig gemacht, es sei denn, sie beziehen sich auf ein Element, das gelöscht wurde.
Nebenbei, hat
std::forward_listauch viele Cache-Fehler?
Ja; es ist immer noch eine verknüpfte Liste.
std::list ist in einigen Fällen nützlich.
Die allgemeine Regel von C ++ - sequentiellen Containern lautet jedoch: "Wenn Ihr Algorithmus kompatibel ist, verwenden Sie std::vector . Wenn Ihre Algorithmen nicht kompatibel sind, ändern Sie Ihre Algorithmen so, dass Sie std::vector verwenden können."
Es gibt Ausnahmen, und hier ist ein Versuch, Gründe erschöpfend aufzuführen, dass std::list eine bessere Wahl ist:
Wenn Sie (A) in die Mitte des Containers einfügen müssen und (B) müssen Sie den Speicherort jedes Objekts im Speicher stabil halten. Die Anforderung (B) kann normalerweise entfernt werden, indem Sie einen nicht stabilen Container verwenden, der aus Zeigern für Elemente besteht. Dies ist also kein starker Grund, std::list zu verwenden.
Wenn Sie (A) in der Mitte des Containers (B) größere Mengen einfügen oder löschen müssen, als Sie über den Container iterieren müssen. Dies ist auch ein extremer Eckfall: Um das zu löschende Element aus einem list zu finden, müssen Sie normalerweise iterieren!
Was zu
führtSie müssen (A) einfügen oder löschen in der Mitte des Containers und (B) haben Iteratoren zu allen anderen Elementen gültig bleiben. Dies ist eine versteckte Anforderung von Fall 1 und Fall 2: Es ist schwierig, häufiger zu löschen oder einzufügen, als Sie iterieren, wenn Sie keine persistenten Iteratoren haben, und die Stabilität von Iteratoren und Objekten ist eng miteinander verknüpft.
> der letzte Fall, ist der Fall von Spleißen war einmal ein Grund, std::list zu verwenden.
Zurück in C ++ 03, könnten alle Versionen von std::list::splice (theoretisch) in O (1) Zeit ausgeführt werden. Die extrem effizienten Formen von splice erfordern jedoch, dass size eine O (n) -Operation ist. C ++ 11 erfordert, dass size auf einem list O (1) ist, so dass die extreme Effizienz von splice auf die Fälle "Spleißen einer ganz anderen Liste" und "Selbstspleißen einer Unterliste" beschränkt ist. Bei Single-Element-Spleiß ist dies nur ein Einfügen und Löschen. Im Fall von Unterbereichspleiß muss der Code nun jeden Knoten in dem Spleiß besuchen, nur um sie zu zählen, um size als O (1) beizubehalten (außer beim Selbstspleißen).
Wenn Sie also nur ganze list -Splices oder den selbst aufgelisteten Unterbereich splice s verwenden, kann list diese Operationen viel schneller als andere nicht-list-Container ausführen.
Die größte Verbesserung, die std::list bieten kann, ist, wenn Sie ein oder mehrere Elemente aus der Mitte einer Liste in eine andere Liste verschieben. Diese splice -Operation ist sehr effizient für list , während sie die Zuweisung und Bewegung von Elementen in Random-Access-Containern wie vector beinhalten kann. Das heißt, dies kommt sehr selten und viel Zeit vector ist Ihr bester Container in Bezug auf Leistung und Einfachheit.
Profilieren Sie Ihren Code immer, wenn Sie bei einer Containerauswahl Leistungsprobleme vermuten.
Sie haben std::list über std::deque und std::vector (und andere zusammenhängende Speichercontainer) gewählt, wenn Sie häufig Elemente in der Mitte Ihres Containers hinzufügen / entfernen, siehe auch .
Tags und Links c++ stl containers