Wozu Listen über Vektoren in C ++ verwenden?

Ich habe 3 verschiedene Experimente mit C ++ - Listen und Vektoren durchgeführt.

Diejenigen mit Vektoren erwiesen sich als effizienter, selbst wenn viele Insertionen in der Mitte beteiligt waren.

Daher die Frage: In welchem ​​Fall sind Listen sinnvoller als Vektoren?

Wenn Vektoren in den meisten Fällen effizienter erscheinen und wenn man bedenkt, wie ähnlich ihre Mitglieder sind, welche Vorteile verbleiben dann für Listen?

1. Generieren Sie N Ganzzahlen und legen Sie sie in einen Container, damit der Container sortiert bleibt. Das Einfügen wurde naiv durchgeführt, indem die Elemente einzeln gelesen und die neue unmittelbar vor der ersten größeren eingefügt wurden.
   Mit einer Liste geht die Zeit durch das Dach, wenn die Abmessung im Vergleich zu Vektoren zunimmt.

2. Fügen Sie am Ende des Containers N ganze Zahlen ein.
   Bei Listen und Vektoren erhöhte sich die Zeit um die gleiche Größenordnung, obwohl sie bei Vektoren dreimal schneller war.

3. Fügen Sie N Ganzzahlen in einen Container ein.
   Timer starten.
   Sortieren Sie den Container mit list.sort für Listen und std :: sort für Vektoren. Timer anhalten.
   Auch hier nimmt die Zeit um die gleiche Größenordnung zu, ist jedoch mit Vektoren im Durchschnitt fünfmal schneller.

Ich könnte weiterhin Tests durchführen und ein paar Beispiele herausfinden, bei denen sich Listen als besser erweisen würden.

Aber die gemeinsame Erfahrung von euch, die diese Nachricht liest, könnte produktivere Antworten liefern.

Sie sind möglicherweise auf Situationen gestoßen, in denen Listen bequemer zu verwenden waren oder eine bessere Leistung erbrachten?

Die kurze Antwort lautet, dass es nur wenige Fälle zu geben scheint. Es gibt aber wahrscheinlich ein paar.

Eine Möglichkeit wäre, wenn Sie eine kleine Anzahl großer Objekte speichern müssen - insbesondere Objekte, die so groß sind, dass es unpraktisch ist, auch nur ein paar zusätzliche Objekte unterzubringen. Grundsätzlich gibt es keine Möglichkeit, einen Vektor oder eine Deque daran zu hindern, Speicherplatz für zusätzliche Objekte zuzuweisen - sie werden so definiert (dh sie müssen zusätzlichen Speicherplatz zuweisen, um ihre Komplexitätsanforderungen zu erfüllen). Wenn Sie nicht zulassen können, dass dieser zusätzliche Speicherplatz zugewiesen wird, ist ein Container std::listmöglicherweise der einzige Standardcontainer, der Ihren Anforderungen entspricht.

Eine andere Möglichkeit wäre, wenn Sie einen Iterator über einen längeren Zeitraum an einem "interessanten" Punkt in einer Liste speichern und wenn Sie Einfügungen und / oder Löschungen vornehmen, tun Sie dies (fast) immer von einer Stelle aus, zu der Sie möchten Sie haben bereits einen Iterator, sodass Sie nicht durch die Liste gehen, um zu dem Punkt zu gelangen, an dem Sie das Einfügen oder Löschen vornehmen werden. Dasselbe gilt natürlich auch, wenn Sie mit mehr als einer Stelle arbeiten, aber dennoch einen Iterator an jeder Stelle speichern möchten, an der Sie wahrscheinlich arbeiten, sodass Sie die meisten Stellen manipulieren, die Sie direkt erreichen können, und nur selten durch die Liste gehen, um diese zu erhalten zu diesen Stellen.

Betrachten Sie als erstes Beispiel einen Webbrowser. Möglicherweise wird eine verknüpfte Liste von TabObjekten gespeichert, wobei jedes Registerobjekt auf einem geöffneten Register im Browser dargestellt wird. Jede Registerkarte kann ein paar Dutzend Megabyte Daten umfassen (von mehr, insbesondere wenn es sich um ein Video handelt). Ihre typische Anzahl offener Tabs kann leicht unter einem Dutzend liegen, und 100 liegt wahrscheinlich nahe am oberen Extrem.

Als zweites Beispiel sei ein Textverarbeitungsprogramm betrachtet, in dem Text als verknüpfte Liste von Kapiteln gespeichert wird, von denen jedes eine verknüpfte Liste von (beispielsweise) Absätzen enthalten kann. Wenn der Benutzer etwas bearbeitet, findet er normalerweise eine bestimmte Stelle, an der er etwas bearbeiten möchte, und erledigt dann eine ganze Menge Arbeit an dieser Stelle (oder auf jeden Fall innerhalb dieses Absatzes). Ja, sie wechseln ab und zu von einem Absatz zum nächsten, aber in den meisten Fällen handelt es sich um einen Absatz in der Nähe der Stelle, an der sie bereits gearbeitet haben.

Hin und wieder (Dinge wie globales Suchen und Ersetzen) durchlaufen Sie alle Elemente in allen Listen, aber es ist ziemlich ungewöhnlich, und selbst wenn Sie dies tun, werden Sie wahrscheinlich genug Arbeit beim Suchen in einem Element in erledigen Die Liste, dass die Zeit zum Durchlaufen der Liste nahezu belanglos ist.

Beachten Sie, dass dies in einem typischen Fall wahrscheinlich auch das erste Kriterium erfüllt - ein Kapitel enthält eine relativ kleine Anzahl von Absätzen, von denen jeder wahrscheinlich ziemlich groß ist (zumindest im Verhältnis zur Größe der Zeiger in der Liste) Knoten und so weiter). Ebenso haben Sie eine relativ kleine Anzahl von Kapiteln, von denen jedes mehrere Kilobyte oder so sein kann.

Das heißt, ich muss zugeben, dass beide Beispiele wahrscheinlich ein wenig erfunden sind, und obwohl eine verknüpfte Liste für beide perfekt funktionieren könnte, würde sie in beiden Fällen wahrscheinlich keinen großen Vorteil bringen. In beiden Fällen ist es beispielsweise unwahrscheinlich, dass die Zuweisung von zusätzlichem Speicherplatz in einem Vektor für einige (leere) Webseiten / Registerkarten oder einige leere Kapitel ein echtes Problem darstellt.

Laut Bjarne Stroustrup selbst sollten Vektoren immer die Standardauflistung für Datensequenzen sein. Sie können die Liste auswählen, wenn Sie das Einfügen und Löschen von Elementen optimieren möchten, sollten dies aber normalerweise nicht. Die Kosten der Liste sind langsames Durchlaufen und Speichernutzung.

Darüber spricht er in dieser Präsentation .

Gegen 0:44 spricht er über Vektoren vs. Listen im Allgemeinen.

Kompaktheit ist wichtig. Vektoren sind kompakter als Listen. Und vorhersehbare Nutzungsmuster sind von enormer Bedeutung. Bei Vektoren muss man viele Elemente verschieben, aber Caches sind wirklich sehr gut darin. ... Listen haben keinen zufälligen Zugriff. Wenn Sie jedoch eine Liste durchlaufen, haben Sie weiterhin wahlfreien Zugriff. Hier befindet sich ein Knoten, der sich im Speicher befindet. Sie greifen also zufällig auf Ihren Speicher zu und maximieren Ihre Cache-Fehlschläge, was genau das Gegenteil von dem ist, was Sie möchten.

Gegen 1:08 Uhr erhält er eine Frage zu diesem Thema.

Was wir sehen sollten, ist, dass wir eine Abfolge von Elementen benötigen. Und die Standardsequenz von Elementen in C ++ ist der Vektor. Weil das kompakt und effizient ist. Implementierung, Zuordnung zu Hardware, ist wichtig. Wenn Sie nun das Einfügen und Löschen optimieren möchten, sagen Sie: „Nun, ich möchte nicht die Standardversion einer Sequenz. Ich möchte die spezialisierte, die eine Liste ist. Und wenn Sie das tun, sollten Sie genug wissen, um zu sagen: "Ich akzeptiere einige Kosten und einige Probleme, wie langsames Durchlaufen und mehr Speichernutzung."

Der einzige Ort, an dem ich normalerweise Listen verwende, ist der Ort, an dem ich Elemente löschen und Iteratoren nicht ungültig machen muss. std::vectormacht alle Iteratoren beim Einfügen und Löschen ungültig. std::listgarantiert, dass Iteratoren zu vorhandenen Elementen nach dem Einfügen oder Löschen weiterhin gültig sind.

Zusätzlich zu den anderen bereits bereitgestellten Antworten verfügen Listen über bestimmte Funktionen, die in Vektoren nicht vorhanden sind (da sie wahnsinnig teuer wären). Die Spleiß- und Zusammenführungsvorgänge sind die wichtigsten. Wenn Sie häufig eine Reihe von Listen haben, die angehängt oder zusammengeführt werden müssen, ist eine Liste wahrscheinlich eine gute Wahl.

Wenn Sie diese Vorgänge jedoch nicht ausführen müssen, ist dies wahrscheinlich nicht der Fall.

Das Fehlen einer inhärenten Cache- / Seitenfreundlichkeit von verknüpften Listen führt dazu, dass sie von vielen C ++ - Entwicklern fast gänzlich verworfen werden, und dies mit gutem Grund in dieser Standardform.

Verknüpfte Listen können immer noch wunderbar sein

Verknüpfte Listen können jedoch wunderbar sein, wenn sie von einem festen Zuweiser unterstützt werden, der ihnen die räumliche Lokalität zurückgibt, die ihnen von Natur aus fehlt.

Sie zeichnen sich dadurch aus, dass wir eine Liste in zwei Listen aufteilen können, indem wir beispielsweise einfach einen neuen Zeiger speichern und einen oder zwei Zeiger bearbeiten. Wir können Knoten durch bloße Zeigermanipulation in konstanter Zeit von einer Liste zu einer anderen verschieben, und eine leere Liste kann einfach die Speicherkosten eines einzelnen headZeigers haben.

Simple Grid Accelerator

Als praktisches Beispiel sei eine visuelle 2D-Simulation betrachtet. Es verfügt über einen Bildlaufbildschirm mit einer Karte im Format 400 x 400 (160.000 Gitterzellen), die zur Beschleunigung der Kollisionserkennung zwischen Millionen von Partikeln verwendet wird, die sich in jedem Bild bewegen dynamische Daten). Eine ganze Reihe von Partikeln bewegt sich ständig in jedem Frame, was bedeutet, dass sie sich ständig in einer Gitterzelle in einer anderen befinden.

In diesem Fall kann, wenn jedes Partikel ein einfach verknüpfter Listenknoten ist, jede Gitterzelle als bloßer headZeiger beginnen, der auf zeigt nullptr. Wenn ein neues Partikel geboren wird, setzen wir es einfach in die Gitterzelle, in der es sich befindet, indem wir den headZeiger dieser Zelle so einstellen, dass er auf diesen Partikelknoten zeigt. Wenn sich ein Partikel von einer Gitterzelle zur nächsten bewegt, manipulieren wir einfach die Zeiger.

Dies kann wesentlich effizienter sein, als 160.000 vectorsfür jede Gitterzelle zu speichern und die ganze Zeit Frame für Frame von der Mitte zurückzuschieben und zu löschen.

std :: liste

Dies gilt jedoch für von Hand gerollte, aufdringliche, einfach verknüpfte Listen, die von einem festen Zuweiser unterstützt werden. std::liststellt eine doppelt verknüpfte Liste dar und ist möglicherweise nicht annähernd so kompakt, wenn sie leer ist wie ein einzelner Zeiger (variiert je nach Herstellerimplementierung). Außerdem ist es mühsam, benutzerdefinierte Zuweiser in std::allocatorFormularen zu implementieren .

Ich muss zugeben, ich benutze nie listwas auch immer. Aber verknüpfte Listen können immer noch wunderbar sein! Sie sind jedoch aus den Gründen nicht besonders gut, aus denen Menschen häufig versucht sind, sie zu verwenden, und auch nicht besonders gut, wenn sie nicht von einem sehr effizienten festen Zuweiser unterstützt werden, der zumindest eine Menge der obligatorischen Seitenfehler und Cachefehler, die damit verbunden sind, abschwächt.

Sie sollten die Größe der Elemente im Container berücksichtigen.

int elements vector ist sehr schnell, da die meisten Daten in den CPU-Cache passen (und SIMD-Anweisungen können wahrscheinlich zum Kopieren von Daten verwendet werden).

Wenn das Element größer ist, kann sich das Ergebnis von Test 1 und 3 erheblich ändern.

Aus einem sehr umfassenden Leistungsvergleich :

Daraus ergeben sich einfache Schlussfolgerungen für die Verwendung jeder Datenstruktur:

• Zahlenkalkulation: Verwenden Sie std::vectoroderstd::deque
• Lineare Suche: Verwenden Sie std::vectoroderstd::deque
• Zufälliges Einfügen / Entfernen:
  • Kleine Datenmenge: verwenden std::vector
  • Große Elementgröße: Verwendung std::list(sofern nicht hauptsächlich für die Suche vorgesehen)
• Nicht trivialer Datentyp: Verwenden std::listSie diesen, sofern Sie den Container nicht speziell für die Suche benötigen. Bei mehreren Änderungen am Container ist dies jedoch sehr langsam.
• Nach vorne schieben: mit std::dequeoderstd::list

(als Randnotiz std::dequeeine sehr unterschätzte Datenstruktur).

Aus einer bequemen Sicht std::listbietet dies die Garantie, dass Iteratoren niemals ungültig werden, wenn Sie andere Elemente einfügen oder entfernen. Es ist oft ein Schlüsselaspekt.

Der bekannteste Grund für die Verwendung von Listen ist meiner Meinung nach die Ungültigkeit von Iteratoren : Wenn Sie einem Vektor Elemente hinzufügen / daraus entfernen, können alle Zeiger, Referenzen und Iteratoren, die Sie für bestimmte Elemente dieses Vektors verwendet haben, ungültig werden und zu subtilen Fehlern führen. oder Segmentierungsfehler.

Dies ist bei Listen nicht der Fall.

Die genauen Regeln für alle Standardcontainer finden Sie in diesem StackOverflow-Beitrag .

Kurz gesagt, es gibt keinen guten Grund für die Verwendung von std::list<>:

• Wenn Sie einen unsortierten Container benötigen, std::vector<> Regeln.
  (Löschen Sie Elemente, indem Sie sie durch das letzte Element des Vektors ersetzen.)

• Wenn Sie einen sortierten Behälter benötigen, std::vector<shared_ptr<>> Regeln.

• Wenn Sie einen spärlichen Index benötigen, std::unordered_map<> Regeln.

Das ist es.

Ich finde, dass es nur eine Situation gibt, in der ich normalerweise eine verknüpfte Liste verwende: Wenn ich bereits Objekte habe, die auf irgendeine Weise verbunden werden müssen, um eine zusätzliche Anwendungslogik zu implementieren. In diesem Fall verwende ich jedoch nie std::list<>, sondern greife auf einen (intelligenten) nächsten Zeiger im Objekt zurück, zumal die meisten Anwendungsfälle eher zu einem Baum als zu einer linearen Liste führen. In einigen Fällen ist die resultierende Struktur eine verknüpfte Liste, in anderen Fällen ein Baum oder ein gerichteter azyklischer Graph. Der Hauptzweck dieser Zeiger besteht immer darin, eine logische Struktur aufzubauen und niemals Objekte zu verwalten. Wir haben std::vector<>dafür.

Sie müssen zeigen, wie Sie die Einsätze in Ihrem ersten Test durchgeführt haben. Bei Ihrem zweiten und dritten Test gewinnt vector leicht.

Eine wichtige Verwendung von Listen besteht darin, dass Sie das Entfernen von Elementen während der Iteration unterstützen müssen. Wenn der Vektor geändert wird, sind alle Iteratoren (möglicherweise) ungültig. Bei einer Liste ist nur ein Iterator für das entfernte Element ungültig. Alle anderen Iteratoren bleiben gültig.

Die typische Verwendungsreihenfolge für Container lautet vector, deque, then list. Die Auswahl des Containers basiert normalerweise auf push_back select vector, pop_front choose deque und insert choose list.

Ein Faktor, den ich mir vorstellen kann, ist, dass, wenn ein Vektor wächst, der freie Speicher fragmentiert wird, wenn der Vektor seinen Speicher freigibt und immer wieder einen größeren Block zuweist. Dies wird kein Problem mit Listen sein.

Dies ist zusätzlich zu der Tatsache, dass eine große Anzahl von push_backs ohne Reserve auch eine Kopie während jeder Größenänderung verursacht, was sie ineffizient macht. Das Einfügen in der Mitte bewirkt in ähnlicher Weise eine Verschiebung aller Elemente nach rechts und ist noch schlimmer.

Ich weiß nicht, ob dies ein Hauptanliegen ist, aber es war der Grund, den ich bei meiner Arbeit angegeben habe (Entwicklung von Handyspielen), um Vektoren zu vermeiden.