Wann sollte vector / list verwendet werden?

17

Ich kann verstehen, wann Listen zu verwenden sind, aber ich verstehe nicht, wann es besser ist, Vektoren als Listen in Videospielen zu verwenden: Wann ist es besser, schnellen Direktzugriff zu haben?

(Und ich verstehe, warum es schneller ist, Listen einzufügen / zu löschen, weil es nur Zeiger entfernt / hinzufügt, aber immer noch das entsprechende Element finden muss ...)

jokoon
quelle
Neu hinzugefügter Vektor-Tag - Wenn list ein gültiger Tag ist, ist auch vector dies.
Kylotan
Vermutlich wurde vector entfernt, da es sich um einen mathematischen Vektor handelt, nicht um std :: vector.
1
wie wärs mit nix beiden und put container.
deft_code
@ Kylotan: Es ist wie Joe gesagt hat. Bei dieser Frage ging es definitiv um Vektoren, aber sie gehörte nicht zum Vektor-Tag.
Doppelgreener
1
Entfernen wir also mehrdeutige Tags? Das klingt für mich nach einer falschen Entscheidung - besser, Ihre Suche liefert zu viele Informationen als zu wenig. Das Überspringen unerwünschter Ergebnisse ist einfacher als Brainstorming, um Synonyme zu finden.
Kylotan

Antworten:

29

Meine Faustregel ist, und ich bin sicher, dass es eine Debatte darüber geben wird, niemals Listen zu verwenden (es sei denn, Sie müssen sehr, sehr häufig Dinge aus der Mitte großer Listen entfernen).

Die Geschwindigkeit, die Sie gewinnen, wenn Sie alle Ihre Elemente in Ihrem Container in zusammenhängendem Speicher haben (und daher cachefreundlicher sind), ist den Ausgleich der zusätzlichen Kosten für das Hinzufügen / Entfernen / Ändern der Größe des Vektors wert.

Bearbeiten: Nur um ein bisschen mehr zu verdeutlichen, sollte es selbstverständlich sein, dass jede Art von "was schneller ist" Frage auf welcher Plattform auch immer mit welchen Datensätzen getestet werden sollte, die für Ihre speziellen Bedürfnisse relevant sind. Wenn ich nur eine Sammlung von Elementen benötige, verwende ich nur vector (oder deque, was fast dasselbe ist), es sei denn, es gibt einen guten Grund, dies nicht zu tun .

Tetrade
quelle
1
Ich denke, es hängt stark von Ihren Anforderungen ab. Wenn Sie nie auf ein bestimmtes Element zugreifen müssen und nur alle Elemente lesen müssen und Sie Elemente häufig hinzufügen und entfernen, ist die Liste eine bessere Lösung.
Frédérick Imbeault
11
@ Frédérick: Das ist die Standard-C ++ Weisheit, aber es ist auch fast immer falsch. Vektoren, besonders wenn es sich um Zeigervektoren handelt (die Sie fast immer für Spiele verwenden), sind extrem schnell zu entfernen - es ist lineare Zeit, aber es ist ein sehr sehr geringer Overhead pro Objekt. Es ist auch viel schneller, sequentiell über einen Vektor zu iterieren.
1
Ich bin nicht sicher, um welche Art von Struktur es sich genau handelt - diese Art der Optimierung erfordert konkrete Beispiele, um etwas definitiv auszudrücken. Zum Beispiel wäre meine erste Reaktion auf Ihren Anwendungsfall eine ungeordnete Menge, die das ebenso schnelle Einfügen, Löschen und Nachschlagen ermöglicht. Meiner Erfahrung nach eignen sich Sets hervorragend für Objekte in Editoren. Da die Anforderungen an die Echtzeitleistung der Editoren jedoch viel geringer sind - z. B. ist es in Ordnung, wenn das Reagieren auf einen "Löschen" -Button 1/20-Sekunden oder 1/2-Sekunden-10% der Zeit in Anspruch nimmt - ist diese Optimierungsstufe trifft auch selten auf sie zu.
1
@ Frédérick Imbeault Geändert ist kein großes Problem, es ist Hinzufügen / Entfernen, das Probleme verursacht. Vom hinzugefügten \ entfernten Punkt zum Ende des Vektors wird kopiert, um den Vektor zusammenhängend zu halten. Wenn die Reihenfolge der Elemente keine Rolle spielt, können Sie das gelöschte Element durch das letzte Element ersetzen. Fügen Sie dann das Element zum Löschen hinzu und fügen Sie es zum Hinzufügen hinzu.
Stonemetal
4
Sicher ist es nicht sicher, die Adresse eines Elements in einem Vektor zu nehmen und diese zu speichern. Aber im Allgemeinen tun Sie das kaum, sondern ziehen es vor, einen Vektor von Zeigern von Elementen zu haben und den Zeiger herum (oder etwas Ähnliches) zu kopieren.
Tetrad
8

Verwenden Sie eine Liste, wenn eine durch Ändern der Mitte Ihrer Datenstruktur verursachte Iterator-Invalidierung zu Problemen führt oder Sie Ihre Elemente weiterhin sortieren müssen, damit der Swap- und Pop-Trick für schnelles Löschen der mittleren Sammlung nicht funktioniert und Sie über eine große Anzahl von Elementen verfügen Anzahl der Löschvorgänge in der mittleren Sammlung.

Möglicherweise möchten Sie auch eine Deque verwenden. Es hat ähnliche Leistungsmerkmale wie ein Vektor, benötigt jedoch keinen zusammenhängenden Speicher und ist etwas flexibler.

Steinmetalle
quelle
+1 für die einzige Person, die Deques erwähnt - Sie erhalten die Vorteile von Vektoren in Bezug auf den zusammenhängenden Speicher und die Suchgeschwindigkeit, wobei beide Enden schnell eingefügt / entfernt werden.
5

Ihre Wahl sollte Ihren Bedürfnissen entsprechen. Alle Elemente der Vektoren sind ständig im Speicher und Listen haben Zeiger auf die nächsten / vorherigen Elemente, sodass sie jeweils ihre Vor- / Nachteile haben:

Listen:

  • Jedes Element benötigt zwei Ganzzahlen, um auf vorherige und nächste Elemente zu verweisen. In den meisten Fällen sind das 8 Byte mehr für jedes Element in Ihrer Liste
  • Einfügen ist zeitlich linear: O (n)
  • Entfernen ist eine konstante Operation: O (1)
  • Der Zugriff auf das x-Element erfolgt linear in der Zeit: O (n)

Vektoren:

  • Benötigt weniger Speicher (keine Zeiger auf andere Elemente, es ist ein einfacher mathematischer Algorithmus)
  • Entfernen ist zeitlich linear: O (n)
  • Der Zugriff auf das x-Element ist konstant: O (1) (Das liegt daran, dass die Elemente im Speicher kontinuierlich sind, sodass es sich um eine einfache mathematische Operation handelt. VectorPtr + (x * bytesOfTheType))
  • Das Einfügen kann in linearer Zeit erfolgen, ist jedoch in der Regel eine konstante Operation: O (1) (Dies liegt daran, dass der Vektor in einem Array zwar das Zweifache seiner Kapazität reserviert, das Array aber voll ist, sodass das Kopieren des Arrays nicht häufig vorkommt.)

Daher ist eine Liste besser, wenn Sie Elemente häufig hinzufügen und entfernen müssen, aber niemals auf ein bestimmtes Element zugreifen (oder selten darauf zugreifen), ohne dass die anderen zuvor darauf zugreifen müssen. Der Vektor sollte für eine bessere Zugriffszeit verwendet werden, es mangelt ihm jedoch an Effizienz, wenn Sie Elemente entfernen oder hinzufügen müssen.

Überprüfen Sie diesen Beitrag auf stackoverflow. Er enthält eine sehr schöne Grafik mit grundlegenden Fragen zu Ihren Anforderungen, die Sie abhängig von Ihren Antworten zu einem bestimmten Container führt:

/programming/366432/extending-stdlist

Frédérick Imbeault
quelle
3
Dieses Diagramm muss wirklich mit einem Knoten "Speichern Sie Zeiger und weniger als tausend? Nein -> Vektor" beginnen.
Ja vielleicht hast du recht, ich habe nicht in Betracht gezogen, den gespeicherten Typ auch zu analysieren.
Frédérick Imbeault
2

Normalerweise werden Listen für Strukturen wie Warteschlangen verwendet, in denen zahlreiche Operationen zum Anhängen und Entfernen ausgeführt werden. Beispiel: Eine sich ständig ändernde Liste von Entitäten, die aktualisiert werden sollen. Die Liste selbst enthält nur Entitäten auf dem Bildschirm und ändert sich daher häufig.

Vektoren (oder Arrays) eignen sich besser für eine Sammlung, die sich nicht so stark ändert und bei der Sie schnellen Zugriff auf einzelne Elemente in der Sammlung benötigen. Beispiel: Eine Kachelkarte, in der Sie Kacheln an einem bestimmten Index suchen müssen.

Die Meinung von Tetrads mag stimmen, hängt jedoch von der verwendeten Programmiersprache ab. Ich sehe, dass Sie Ihre Frage markiert haben c++, aber ich habe versucht, eine Antwort zu geben, die nicht sprachspezifisch ist.

Blödmann
quelle
Nun, ich hätte vielleicht auch C hineingeben können, aber es gibt keine solchen Container in C, aber das ist etwas, worüber man nachdenken sollte: Gibt es eine STL-ähnliche Bibliothek für C?
jokoon
Ich habe in der Vergangenheit glib ( library.gnome.org/devel/glib ) verwendet, das eine Reihe von Standarddatenstrukturen für C implementiert. Ich hasste es, weil es normalerweise zu ausführlich ist und dringend C ++ sein möchte, aber es ist ausgereift und stabil.
0

In Konsolenspielen verwenden wir niemals std :: list, weil:

  1. Es nimmt Speicherzuweisungen vor, wenn Sie ein neues Element hinzufügen. Speicherzuweisungen sind langsam.
  2. Es ist voller Zeiger. Zeiger sind schlecht. Ein Zeiger ist ein Cache-Miss. Ein Cache-Miss ist schlecht.

Selbst std :: vector verliert bei Konsolen an Beliebtheit, weil:

  1. Sie interessieren sich oft nur zum Beispiel für die Positionen aller Objekte. Zum Beispiel möchten Sie die Objekte miteinander kollidieren. In diesem Fall ist es Ihnen egal, welche Farbe sie haben. Sie möchten also, dass alle Positionen zusammenhängend im Speicher sind und die Farben an einem anderen, weit entfernten Ort angezeigt werden, um eine Verschmutzung des Caches zu vermeiden. Bei std :: vector müssen Sie jedoch alles für jedes Objekt in einem zusammenhängenden Speicherbereich speichern (z. B. Position und dann Farbe). Wenn Sie also nur die Positionen lesen, müssen Sie auch alle Farben in den Cache einlesen wenn du sie nicht benutzt. das ist verschwenderisch.
bmcnett
quelle
5
@bmcnett "[] .. aber std :: vector erfordert, dass Sie alles für jedes Objekt in einem zusammenhängenden Speicherblock speichern" - das ist keine Frage des Containers, es ist eine Frage Ihres Datenlayouts, Sie können alle Positionen haben in einem ununterbrochenen gedächtnisblock mit einem std :: vektor:struct point{float x, y, z, w}; std::vector<point> positions;
Maik Semder
Meine Schule wird es lieben :)
jokoon
2
-1, weil diese Antwort der Liste noch nichts hinzufügt, und die Behauptung, dass Vektoren den Cache verschmutzen, ist falsch, wie Maik sagt.
Sie haben meine Behauptung falsch verstanden. Ich habe nie gesagt, dass std :: vector unter allen Containern besonders schuldig ist, den Cache zu verschmutzen. Alle Container, und in der Tat sogar Arrays, sind ungefähr gleich schuldig. std :: vector gerät in Ungnade, weil C ++ - Objekte selbst in Ungnade fallen. C ++ verlangt, dass die Daten jedes Objekts im Speicher zusammenhängend sind. Sie können dies umgehen, indem Sie C ++ - Objekte vermeiden, z. B. indem Sie std :: vector <position> wie oben erwähnt verwenden.
bmcnett
3
Ausnahme pointist ein C ++ - Objekt (so std::vectorwie es ist, so einfach wie es ist float). Ich kenne die Unterscheidung, die Sie zu zeichnen versuchen, aber Sie machen einen schlechten Job, es zu erklären.