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 ...)
c++
algorithm
data-structure
jokoon
quelle
quelle
container
.Antworten:
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 .
quelle
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.
quelle
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:
Vektoren:
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
quelle
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.quelle
In Konsolenspielen verwenden wir niemals std :: list, weil:
Selbst std :: vector verliert bei Konsolen an Beliebtheit, weil:
quelle
struct point{float x, y, z, w}; std::vector<point> positions;
point
ist ein C ++ - Objekt (sostd::vector
wie es ist, so einfach wie es istfloat
). Ich kenne die Unterscheidung, die Sie zu zeichnen versuchen, aber Sie machen einen schlechten Job, es zu erklären.