vektor vs. Liste in STL

Vektor:

• Angrenzendes Gedächtnis.
• Ordnet Speicherplatz für zukünftige Elemente im Voraus zu, sodass zusätzlicher Speicherplatz erforderlich ist, der über das hinausgeht, was für die Elemente selbst erforderlich ist.
• Jedes Element benötigt nur den Platz für den Elementtyp selbst (keine zusätzlichen Zeiger).
• Kann den Speicher für den gesamten Vektor jederzeit neu zuweisen, wenn Sie ein Element hinzufügen.
• Einfügungen am Ende sind konstante, amortisierte Zeiten, Einfügungen an anderen Stellen sind jedoch ein kostspieliges O (n).
• Löschungen am Ende des Vektors sind konstante Zeit, für den Rest ist es O (n).
• Sie können zufällig auf die Elemente zugreifen.
• Iteratoren werden ungültig, wenn Sie dem Vektor Elemente hinzufügen oder daraus entfernen.
• Sie können leicht auf das zugrunde liegende Array zugreifen, wenn Sie ein Array der Elemente benötigen.

Liste:

• Nicht zusammenhängender Speicher.
• Kein vorab zugewiesener Speicher. Der Speicheraufwand für die Liste selbst ist konstant.
• Jedes Element benötigt zusätzlichen Platz für den Knoten, der das Element enthält, einschließlich Zeiger auf das nächste und vorherige Element in der Liste.
• Nie muss der Speicher für die gesamte Liste neu zugewiesen werden, nur weil Sie ein Element hinzufügen.
• Einfügungen und Löschungen sind billig, egal wo sie in der Liste aufgeführt sind.
• Es ist billig, Listen mit Spleißen zu kombinieren.
• Sie können nicht willkürlich auf Elemente zugreifen, daher kann es teuer sein, auf ein bestimmtes Element in der Liste zuzugreifen.
• Iteratoren bleiben auch dann gültig, wenn Sie Elemente zur Liste hinzufügen oder daraus entfernen.
• Wenn Sie ein Array der Elemente benötigen, müssen Sie ein neues erstellen und alle Elemente hinzufügen, da sich kein Array darunter befindet.

Im Allgemeinen sollten Sie vector verwenden, wenn Sie sich nicht für den Typ des sequentiellen Containers interessieren, den Sie verwenden. Wenn Sie jedoch viele Einfügungen oder Löschungen an einem anderen Ort als dem Ende ausführen, werden Sie dies wünschen Liste verwenden. Oder wenn Sie einen Direktzugriff benötigen, dann wollen Sie einen Vektor und keine Liste. Abgesehen davon gibt es natürlich Fälle, in denen Sie je nach Anwendung die eine oder andere benötigen werden. Im Allgemeinen sind dies jedoch gute Richtlinien.

Wenn Sie Elemente nicht häufig einfügen müssen, ist ein Vektor effizienter. Es hat eine viel bessere CPU-Cache-Lokalität als eine Liste. Mit anderen Worten, der Zugriff auf ein Element macht es sehr wahrscheinlich, dass das nächste Element im Cache vorhanden ist und abgerufen werden kann, ohne langsamen RAM lesen zu müssen.

Bei den meisten Antworten fehlt ein wichtiges Detail: Wozu?

Was willst du im Container behalten?

Wenn es sich um eine Sammlung von ints handelt, verliert std::list in jedem Szenario, unabhängig davon, ob Sie die Zuweisung neu vornehmen können, Sie nur von vorne entfernen usw. Listen sind langsamer zu durchlaufen, jede Einfügung kostet Sie eine Interaktion mit dem Zuweiser. Es wäre äußerst schwierig, ein Beispiel vorzubereiten, bei dem list<int>vector<int> schlägt. Und selbst dann ist deque<int> vielleicht besser oder näher, nicht nur die Verwendung von Listen, die einen größeren Speicheraufwand verursachen.

Wenn Sie jedoch mit großen, hässlichen Datenblöcken zu tun haben - und nur wenigen -, möchten Sie beim Einfügen keine Gesamtzuordnung vornehmen, und das Kopieren aufgrund einer Neuzuordnung wäre eine Katastrophe - dann sind Sie vielleicht besser dran list<UglyBlob> als vector<UglyBlob>.

Wenn Sie jedoch zu vector<UglyBlob*> oder sogar zu vector<shared_ptr<UglyBlob> > wechseln, bleibt die Liste erneut zurück.

Das Zugriffsmuster, die Anzahl der Zielelemente usw. wirkt sich jedoch immer noch auf den Vergleich aus, aber aus meiner Sicht - die Elementgröße - die Kosten für das Kopieren usw.

Eine besondere Funktion von std :: list ist das Spleißen (Verknüpfen oder Verschieben eines Teils oder einer ganzen Liste in eine andere Liste).

Oder vielleicht, wenn Ihre Inhalte sehr teuer zu kopieren sind. In einem solchen Fall könnte es beispielsweise günstiger sein, die Sammlung mit einer Liste zu sortieren.

Beachten Sie außerdem, dass ein Vektor, wenn die Sammlung klein ist (und der Inhalt nicht besonders teuer zu kopieren ist), eine Liste möglicherweise noch übertrifft, selbst wenn Sie irgendwo einfügen und löschen. Eine Liste ordnet jeden Knoten einzeln zu. Dies kann viel kostenintensiver sein, als einige einfache Objekte zu verschieben.

Ich glaube nicht, dass es sehr strenge Regeln gibt. Dies hängt davon ab, was Sie hauptsächlich mit dem Container tun möchten, sowie davon, wie groß der Container und der enthaltene Typ sind. Ein Vektor übertrumpft im Allgemeinen eine Liste, da er seinen Inhalt als einen zusammenhängenden Block zuordnet (es handelt sich im Wesentlichen um ein dynamisch zugewiesenes Array, und in den meisten Fällen ist ein Array der effizienteste Weg, um mehrere Dinge zu speichern).

Nun, die Schüler meiner Klasse scheinen mir nicht erklären zu können, wann es effektiver ist, Vektoren zu verwenden, aber sie sehen recht glücklich aus, wenn sie mir raten, Listen zu verwenden.

So verstehe ich es

Listen : Jedes Element enthält eine Adresse zum nächsten oder vorherigen Element. Mit dieser Funktion können Sie die Elemente randomisieren, auch wenn sie nicht sortiert sind. Die Reihenfolge ändert sich nicht Ihr Gedächtnis ist fragmentiert . Aber es hat auch einen weiteren sehr großen Vorteil: Sie können Elemente leicht einfügen/entfernen, da Sie lediglich einige Zeiger ändern müssen zufälliger Einzelposten, Sie müssen von einem Artikel zum anderen springen, bis Sie die richtige Adresse finden.

Vektoren : Bei Verwendung von Vektoren ist der Speicher viel mehr wie normale Arrays organisiert: Jedes n-te Element wird unmittelbar nach (n-1) -tem Element und vor (n + 1) -tem Element gespeichert Warum ist es besser als eine Liste? Weil es einen schnellen Direktzugriff ermöglicht So wird es gemacht: Wenn Sie die Größe eines Elements in einem Vektor kennen und im Speicher zusammenhängend sind, können Sie dies leicht vorhersagen wo der n-te Gegenstand ist; Sie müssen nicht das gesamte Element einer Liste durchsuchen, um das gewünschte Element zu lesen. Mit vector lesen Sie es direkt, mit einer Liste, die Sie nicht ... können. Ändern Sie andererseits das Vektor-Array oder ändern Sie es ein Wert ist viel langsamer.

Listen sind besser geeignet, um Objekte nachzuverfolgen, die im Speicher hinzugefügt/entfernt werden können. Vektoren eignen sich besser, wenn Sie von einer großen Anzahl einzelner Elemente auf ein Element zugreifen möchten.

Ich weiß nicht, wie Listen optimiert werden, aber Sie müssen wissen, dass Sie, wenn Sie einen schnellen Lesezugriff wünschen, Vektoren verwenden sollten, denn wie gut die STL-Listen sind, ist beim Lesezugriff nicht so schnell wie bei Vektoren.

Grundsätzlich ist ein Vektor ein Array mit automatischer Speicherverwaltung. Die Daten sind im Speicher zusammenhängend. Der Versuch, Daten in der Mitte einzufügen, ist ein kostspieliger Vorgang. 

In einer Liste werden die Daten in nicht zugehörigen Speicherorten gespeichert. Beim Einfügen in die Mitte müssen Sie nicht einige Daten kopieren, um Platz für die neuen zu schaffen.

Um Ihre Frage genauer zu beantworten, zitiere ich diese Seite

vektoren sind in der Regel zeitlich am effizientesten, um auf Elemente zuzugreifen und Elemente am Ende der Sequenz hinzuzufügen oder zu entfernen. Bei Operationen, bei denen Elemente an anderen Positionen als dem Ende eingefügt oder entfernt werden, sind sie schlechter als Deques und Listen und haben weniger konsistente Iteratoren und Referenzen als Listen.

Jedes Mal, wenn Sie keine Iteratoren ungültig machen können.

Wenn Sie viel Einfügen oder Löschen in der Mitte der Sequenz haben. z.B. ein Speichermanager.

Die Beibehaltung der Gültigkeit von Iteratoren ist ein Grund, eine Liste zu verwenden. Ein anderer ist, wenn Sie nicht möchten, dass ein Vektor beim Pushen von Elementen neu zugewiesen wird. Dies kann durch eine intelligente Verwendung von reserve () verwaltet werden. In manchen Fällen ist es jedoch einfacher oder praktischer, eine Liste zu verwenden.

Wenn Sie Objekte zwischen Containern verschieben möchten, können Sie list::splice verwenden.

Beispielsweise kann ein Graphpartitionierungsalgorithmus eine konstante Anzahl von Objekten aufweisen, die rekursiv auf eine zunehmende Anzahl von Containern aufgeteilt ist. Die Objekte sollten einmalig initialisiert werden und verbleiben immer an denselben Speicherorten. Es ist viel schneller, sie durch Neuverknüpfung neu zu ordnen als durch Neuzuweisung.

Edit: Wenn Bibliotheken sich auf die Implementierung von C++ 0x vorbereiten, wird der allgemeine Fall des Zusammenfügens einer Untersequenz in eine Liste mit der Länge der Sequenz linear. Dies liegt daran, dass splice (jetzt) ​​die Sequenz durchlaufen muss, um die Anzahl der darin enthaltenen Elemente zu zählen. (Weil die Liste ihre Größe aufzeichnen muss.) Das einfache Zählen und erneutes Verknüpfen der Liste ist immer noch schneller als jede andere Alternative. Das Zusammenfügen einer ganzen Liste oder eines einzelnen Elements ist Sonderfälle mit konstanter Komplexität. Wenn Sie jedoch lange Sequenzen zum Spleißen haben, müssen Sie möglicherweise nach einem besseren, altmodischen, nicht kompatiblen Container suchen.

Die einzige schwierige Regel, bei der list verwendet werden muss, ist, wenn Sie Zeiger auf Elemente des Containers verteilen müssen. 

Anders als bei vector wissen Sie, dass der Speicher von Elementen nicht neu zugewiesen wird. Wenn dies der Fall sein könnte, haben Sie möglicherweise Zeiger auf ungenutzten Speicher, der bestenfalls ein großes Nein und im schlimmsten Fall eine SEGFAULT ist.

(Technisch gesehen würde auch eine vector von *_ptr funktionieren, aber in diesem Fall emulieren Sie list, das ist also nur Semantik.)

Andere Softwareregeln beziehen sich auf die möglichen Leistungsprobleme beim Einfügen von Elementen in die Mitte eines Containers, wobei list vorzuziehen wäre.