Die relative Performance von std :: vector vs. std :: list vs. std :: slist?

Question

Für eine einfache verknüpfte Liste, in dem Random Access Elemente zur Liste ist keine Voraussetzung, gibt es erhebliche Vorteile (Leistung oder auf andere Weise) zu verwenden std::list statt std::vector? Wenn rückwärts Traversal erforderlich ist, wäre es effizienter sein std::slist zu verwenden und die Liste vor reverse() über seine Elemente iterieren?

Answer 1

Wie üblich die beste Antwort auf die Leistung Fragen ist href="https://stackoverflow.com/questions/61278/quick-and-dirty-way-to-profile-your-code"> Profil beide Implementierungen für Ihren Anwendungsfall und sehen, welche schneller ist.

In der Regel, wenn Sie Einfügungen in die Datenstruktur haben (außer am Ende), dann kann vector langsamer sein, sonst in den meisten Fällen vector erwartet wird, eine bessere Leistung als list wenn auch nur für

Answer 2

Standarddatenstruktur zu denken, in C ++ ist die Vector .

Beachten Sie folgende Bedingungen ...

1] Traversal:
Liste Knoten sind überall im Speicher verstreut und somit Liste Traversal führt zu Cache-Misses . Aber Traversal von Vektoren ist glatt.

2] Einfügen und Löschen:
Durchschnittlich 50% der Elemente muß verschoben werden, wenn Sie das zu einem Vektor tun, aber Caches sind sehr gut an! Aber mit Listen, müssen Sie Traverse auf den Punkt der Einfügen / Löschen ... so wieder ... Cache-Misses! Und überraschend Vektoren auch diesen Fall gewinnen!

3] Lagerung:
Wenn Sie eine Liste verwenden, gibt es zwei Zeiger pro Element (vorwärts und rückwärts), so eine Liste ist viel größer als ein Vektor! Vektoren müssen nur ein wenig mehr Speicher als die eigentlichen Elemente benötigen.
Yout sollte einen Grund haben, nicht um einen Vektor zu verwenden.

---

Referenz:
Das erfuhr ich in einem Vortrag des Herrn Bjarne Stroustrup: https://youtu.be/0iWb_qi2-uI ? t = 2680

einfach nicht. Liste hat Vorteile gegenüber Vektor, aber mit sequenziellem Zugriff ist nicht einer von ihnen -. Wenn es das ist alles, was Sie tun, dann ein Vektor ist besser

Allerdings .. ein Vektor ist teurer zusätzliche Elemente als eine Liste hinzuzufügen, vor allem, wenn man in der Mitte ist eingefügt wird.

verstehen, wie diese Sammlungen sind implementiert: ein Vektor eine sequenzielle Anordnung von Daten, eine Liste ist ein Element, das die Daten und Zeiger auf die nächsten Elemente enthält. Sobald Sie das verstehen, werden Sie verstehen, warum Listen für Einsätze gut sind, und schlecht für den Direktzugriff.

(so, Reverse Iteration eines Vektors ist genau die gleiche wie für die Vorwärts Iteration - der Iterator subtrahiert nur die Größe der Datenelemente jedes Mal die Liste noch über den Zeiger auf das nächste Element springen)

Wenn Sie rückwärts brauchen Querung eine slist unwahrscheinlich ist die Datenstruktur für Sie sein.

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

Der beste Weg, dies zu verstehen, ist zu verstehen, wie sie umgesetzt werden. Eine verkettete Liste hat einen nächsten und vorherigen Zeigers für jedes Element. Ein Vektor hat eine Reihe von Elementen durch Index adressiert. siehe Daraus können Sie, dass sowohl effizient vorwärts und rückwärts Traversal tun kann, während nur ein Vektor effizienten Direktzugriff zur Verfügung stellen kann. Sie können auch sehen, dass der Speicher-Overhead einer verknüpften Liste pro Element ist, während für den Vektor es konstant ist. Und Sie können auch sehen, warum Einführungszeit zwischen den beiden Strukturen unterschiedlich ist.

Einige strengen Maßstäbe zum Thema: http://baptiste-wicht.com/posts /2012/12/cpp-benchmark-vector-list-deque.html

Wie andere schon angemerkt wurde, zusammenhängende Speichermittel std :: vector für die meisten Dinge besser. Es gibt praktisch keinen guten Grund, std :: Liste zu verwenden, außer für kleine Datenmengen (wo alles in dem Cache passen) und / oder das Löschen und Wiedereingliederungs sind häufig. Komplexität Garantien beziehen sich nicht auf realen Leistungsfähigkeit aufgrund der Differenz zwischen dem Cache und dem Hauptspeicher Geschwindigkeiten (200x) und wie zusammenhängende Speicherzugriff betrifft Cache-Nutzung. Siehe Chandler Carruth (google) über das Thema sprechen hier: https://www.youtube.com/watch?v=fHNmRkzxHWs

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

Sehen Sie diese Frage für Details zu den Kosten:
Was sind die Komplexität Garantien der Standardcontainer

Wenn Sie eine slist haben, und Sie wollen es jetzt in umgekehrter Reihenfolge zu durchqueren, warum nicht die Art ändern überall zur Liste?

Answer 3

Standarddatenstruktur zu denken, in C ++ ist die Vector .

Beachten Sie folgende Bedingungen ...

1] Traversal:
Liste Knoten sind überall im Speicher verstreut und somit Liste Traversal führt zu Cache-Misses . Aber Traversal von Vektoren ist glatt.

2] Einfügen und Löschen:
Durchschnittlich 50% der Elemente muß verschoben werden, wenn Sie das zu einem Vektor tun, aber Caches sind sehr gut an! Aber mit Listen, müssen Sie Traverse auf den Punkt der Einfügen / Löschen ... so wieder ... Cache-Misses! Und überraschend Vektoren auch diesen Fall gewinnen!

3] Lagerung:
Wenn Sie eine Liste verwenden, gibt es zwei Zeiger pro Element (vorwärts und rückwärts), so eine Liste ist viel größer als ein Vektor! Vektoren müssen nur ein wenig mehr Speicher als die eigentlichen Elemente benötigen.
Yout sollte einen Grund haben, nicht um einen Vektor zu verwenden.

---

Referenz:
Das erfuhr ich in einem Vortrag des Herrn Bjarne Stroustrup: https://youtu.be/0iWb_qi2-uI ? t = 2680

Answer 4

einfach nicht. Liste hat Vorteile gegenüber Vektor, aber mit sequenziellem Zugriff ist nicht einer von ihnen -. Wenn es das ist alles, was Sie tun, dann ein Vektor ist besser

Allerdings .. ein Vektor ist teurer zusätzliche Elemente als eine Liste hinzuzufügen, vor allem, wenn man in der Mitte ist eingefügt wird.

verstehen, wie diese Sammlungen sind implementiert: ein Vektor eine sequenzielle Anordnung von Daten, eine Liste ist ein Element, das die Daten und Zeiger auf die nächsten Elemente enthält. Sobald Sie das verstehen, werden Sie verstehen, warum Listen für Einsätze gut sind, und schlecht für den Direktzugriff.

(so, Reverse Iteration eines Vektors ist genau die gleiche wie für die Vorwärts Iteration - der Iterator subtrahiert nur die Größe der Datenelemente jedes Mal die Liste noch über den Zeiger auf das nächste Element springen)

Answer 5

Wenn Sie rückwärts brauchen Querung eine slist unwahrscheinlich ist die Datenstruktur für Sie sein.

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

Der beste Weg, dies zu verstehen, ist zu verstehen, wie sie umgesetzt werden. Eine verkettete Liste hat einen nächsten und vorherigen Zeigers für jedes Element. Ein Vektor hat eine Reihe von Elementen durch Index adressiert. siehe Daraus können Sie, dass sowohl effizient vorwärts und rückwärts Traversal tun kann, während nur ein Vektor effizienten Direktzugriff zur Verfügung stellen kann. Sie können auch sehen, dass der Speicher-Overhead einer verknüpften Liste pro Element ist, während für den Vektor es konstant ist. Und Sie können auch sehen, warum Einführungszeit zwischen den beiden Strukturen unterschiedlich ist.

Answer 6

Einige strengen Maßstäbe zum Thema: http://baptiste-wicht.com/posts /2012/12/cpp-benchmark-vector-list-deque.html

Wie andere schon angemerkt wurde, zusammenhängende Speichermittel std :: vector für die meisten Dinge besser. Es gibt praktisch keinen guten Grund, std :: Liste zu verwenden, außer für kleine Datenmengen (wo alles in dem Cache passen) und / oder das Löschen und Wiedereingliederungs sind häufig. Komplexität Garantien beziehen sich nicht auf realen Leistungsfähigkeit aufgrund der Differenz zwischen dem Cache und dem Hauptspeicher Geschwindigkeiten (200x) und wie zusammenhängende Speicherzugriff betrifft Cache-Nutzung. Siehe Chandler Carruth (google) über das Thema sprechen hier: https://www.youtube.com/watch?v=fHNmRkzxHWs

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

Answer 7

Sehen Sie diese Frage für Details zu den Kosten:
Was sind die Komplexität Garantien der Standardcontainer

Wenn Sie eine slist haben, und Sie wollen es jetzt in umgekehrter Reihenfolge zu durchqueren, warum nicht die Art ändern überall zur Liste?