Relative Leistung von std::vector vs. std::list vs. std::slist?

Gibt es für eine einfache verkettete Liste, bei der kein wahlfreier Zugriff auf Listenelemente erforderlich ist, wesentliche Vorteile (Leistung oder sonstiges) durch die Verwendung von std::list anstatt std::vector? Wenn ein Rückwärtsdurchlauf erforderlich ist, wäre es effizienter zu verwenden std::slist und reverse() die Liste vor dem Iterieren über ihre Elemente?

Wie üblich besteht die beste Antwort auf Leistungsfragen darin, beide Implementierungen für Ihren Anwendungsfall zu profilieren und zu sehen, welche schneller ist.

Im Allgemeinen, wenn Sie Einfügungen in die Datenstruktur haben (außer am Ende). vector kann langsamer sein, sonst in den meisten Fällen vector wird voraussichtlich besser abschneiden als list wenn auch nur für Probleme mit der Datenlokalitätbedeutet dies, dass, wenn zwei Elemente, die im Datensatz benachbart sind, im Speicher benachbart sind, das nächste Element bereits im Cache des Prozessors ist und den Speicher nicht in den Cache auslagern muss.

Denken Sie auch daran, dass der Platzbedarf für a vector konstant ist (3 Zeiger), während der Raumaufwand für a list für jedes Element bezahlt wird, verringert dies auch die Anzahl vollständiger Elemente (Daten plus Overhead), die sich gleichzeitig im Cache befinden können.

Die Standarddatenstruktur, an die man in C++ denken sollte, ist die Vektor.

Beachten Sie die folgenden Punkte …

1]Durchquerung:

Listenknoten sind überall im Speicher verstreut und daher führt die Listendurchquerung dazu Cache-Fehlschläge. Aber das Durchlaufen von Vektoren ist glatt.

2]Einfügen und Löschen:

Durchschnittlich 50 % der Elemente müssen verschoben werden, wenn Sie das zu einem Vektor machen, aber Caches sind sehr gut darin! Aber mit Listen müssen Sie Traverse bis zum Einfügen/Löschen… also nochmal… cache misses! Und überraschenderweise gewinnen Vektoren auch diesen Fall!

3]Lagerung:

Wenn Sie Listen verwenden, gibt es 2 Zeiger pro Element (vorwärts und rückwärts), sodass eine Liste viel größer ist als ein Vektor! Vektoren benötigen nur etwas mehr Speicher als die eigentlichen Elemente benötigen.

Sie sollten einen Grund haben, keinen Vektor zu verwenden.

Bezug:
Ich habe dies in einem Vortrag von The Lord Bjarne Stroustrup gelernt: https://youtu.be/0iWb_qi2-uI?t=2680

Einfach nein. List hat Vorteile gegenüber Vector, aber sequentieller Zugriff gehört nicht dazu – wenn das alles ist, was Sie tun, dann ist ein Vector besser.

Ein Vektor ist jedoch teurer, um zusätzliche Elemente hinzuzufügen als eine Liste, insbesondere wenn Sie in der Mitte einfügen.

Verstehen Sie, wie diese Sammlungen implementiert werden: Ein Vektor ist ein sequentielles Array von Daten, eine Liste ist ein Element, das die Daten und Zeiger auf die nächsten Elemente enthält. Sobald Sie das verstanden haben, werden Sie verstehen, warum Listen gut für Einfügungen und schlecht für wahlfreien Zugriff sind.

(Die umgekehrte Iteration eines Vektors ist also genau die gleiche wie die Vorwärtsiteration – der Iterator subtrahiert jedes Mal nur die Größe der Datenelemente, die Liste muss immer noch über den Zeiger zum nächsten Element springen.)

Wenn Sie eine Rückwärtstraversierung benötigen, ist eine Slist wahrscheinlich nicht die Datenstruktur für Sie.

Eine herkömmliche (doppelt) verknüpfte Liste gibt Ihnen überall in der Liste eine konstante Einfüge- und Löschzeit; Ein Vektor gibt nur amortisiertes Einfügen und Löschen in konstanter Zeit am Ende der Liste. Für einen Vektor ist die Insertions- und Löschzeit irgendwo anders als am Ende linear. Das ist nicht die ganze Geschichte; es gibt auch konstante Faktoren. Ein Vektor ist eine einfachere Datenstruktur, die je nach Kontext Vor- und Nachteile hat.

Der beste Weg, dies zu verstehen, ist zu verstehen, wie sie implementiert werden. Eine verknüpfte Liste hat einen Weiter- und einen Zurück-Zeiger für jedes Element. Ein Vektor hat ein Array von Elementen, die durch einen Index adressiert werden. Daraus können Sie ersehen, dass beide eine effiziente Vorwärts- und Rückwärtstraversierung durchführen können, während nur ein Vektor einen effizienten Direktzugriff bieten kann. Sie können auch sehen, dass der Speicheraufwand einer verknüpften Liste pro Element ist, während er für den Vektor konstant ist. Und Sie können auch sehen, warum die Einfügungszeit zwischen den beiden Strukturen unterschiedlich ist.

Einige strenge Benchmarks zum Thema:
http://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html

Wie von anderen angemerkt wurde, bedeutet zusammenhängender Speicher, dass std::vector für die meisten Dinge besser ist. Es gibt praktisch keinen guten Grund, std::list zu verwenden, außer bei kleinen Datenmengen (bei denen alles in den Cache passt) und/oder bei häufigen Löschungen und Wiedereinfügungen. Komplexitätsgarantien beziehen sich nicht auf die reale Leistung aufgrund des Unterschieds zwischen Cache- und Hauptspeichergeschwindigkeiten (200x) und wie sich zusammenhängender Speicherzugriff auf die Cache-Nutzung auswirkt. Sehen Sie, wie Chandler Carruth (google) hier über das Problem spricht:
https://www.youtube.com/watch?v=fHNmRkzxHWs

Und Mike Actons Data Oriented Design Vortrag hier:
https://www.youtube.com/watch?v=rX0ItVEVjHc

Siehe diese Frage für Details zu den Kosten:
Was sind die Komplexitätsgarantien der Standardcontainer?

Wenn Sie eine Slist haben und diese nun in umgekehrter Reihenfolge durchlaufen möchten, warum ändern Sie den Typ nicht überall auf list?

• std::vector ist wahnsinnig schneller als std::list, um ein Element zu finden
• std::vector ist bei sehr kleinen Daten immer schneller als std::list
• std::vector schiebt Elemente immer schneller nach hinten als std::list
• std::list kommt sehr gut mit großen Elementen zurecht, insbesondere zum Sortieren oder Einfügen vorne

Notiz: Wenn Sie mehr über Leistung erfahren möchten, würde ich empfehlen, zu sehen Dies