Ich habe das in Effective STL bemerkt
Vektor ist der Sequenztyp, der standardmäßig verwendet werden soll.
Was bedeutet das? Es scheint, dass das Ignorieren der Effizienz vector
alles kann.
Könnte mir jemand ein Szenario anbieten, in dem dies vector
keine praktikable Option ist, sondern list
verwendet werden muss?
Antworten:
Situationen, in denen Sie viele Elemente an einer anderen Stelle als am Ende einer Sequenz wiederholt einfügen möchten.
Überprüfen Sie die Komplexitätsgarantien für jeden Containertyp:
Was sind die Komplexitätsgarantien der Standardcontainer?
quelle
list
hatpush_front
Vektor:
aufführen:
Verwenden Sie im Allgemeinen den Vektor, wenn Sie sich nicht darum kümmern, welche Art von sequentiellem Container Sie verwenden, aber wenn Sie viele Einfügungen oder Löschungen zu und von einer anderen Stelle im Container als dem Ende vornehmen, werden Sie dies wünschen Liste verwenden. Oder wenn Sie einen wahlfreien Zugriff benötigen, möchten Sie einen Vektor, keine Liste. Abgesehen davon gibt es natürlich Fälle, in denen Sie das eine oder andere basierend auf Ihrer Anwendung benötigen, aber im Allgemeinen sind dies gute Richtlinien.
quelle
reserve()
diese jedoch auf O (1) reduzieren. Durch Hinzufügen neuer Elemente zu einer Liste (dh nicht durch Spleißen) werden O (n) freie Speicherzuordnungen ausgeführt.list
beim Löschen von Elementen Speicher freigegeben wird, dies jedochvector
nicht. Avector
reduziert seine Kapazität nicht, wenn Sie seine Größe reduzieren, es sei denn, Sie verwenden denswap()
Trick.Wenn Sie nicht oft Elemente 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.
quelle
Bei den meisten Antworten fehlt ein wichtiges Detail: Wozu?
Was möchten Sie im Container aufbewahren?
Wenn es sich um eine Sammlung von
int
s handelt,std::list
geht sie in jedem Szenario verloren, unabhängig davon, ob Sie sie neu zuweisen können, nur von vorne entfernen usw. Listen sind langsamer zu durchlaufen, jede Einfügung kostet Sie eine Interaktion mit dem Allokator. Es wäre äußerst schwierig, ein Beispiel vorzubereiten, in demlist<int>
Beatsvector<int>
. Und selbst danndeque<int>
kann es besser oder enger sein, die Verwendung von Listen nicht zu rechtfertigen, die einen größeren Speicheraufwand haben.Wenn Sie jedoch mit großen, hässlichen Datenblobs zu tun haben - und nur mit wenigen -, die Sie beim Einfügen nicht insgesamt zuordnen möchten, und das Kopieren aufgrund einer Neuzuweisung eine Katastrophe wäre, sind Sie möglicherweise mit a besser dran
list<UglyBlob>
alsvector<UglyBlob>
.Wenn Sie jedoch zu
vector<UglyBlob*>
oder sogarvector<shared_ptr<UglyBlob> >
wieder wechseln, bleibt die Liste zurück.Das Zugriffsmuster, die Anzahl der Zielelemente usw. wirken sich also immer noch auf den Vergleich aus, aber meiner Ansicht nach - die Größe der Elemente - die Kosten für das Kopieren usw.
quelle
list<T>
ist die Möglichkeitsplice
in O (1) . Wenn Sie zeitlich konstantes Spleißen benötigen, kann Liste auch die Struktur der Wahl sein;)UglyBlob
- auch ein Objekt mit nur ein paar String - Mitglieder leicht zu kopieren unerschwinglich teuer sein können, so dass die Umschichtungen werden kosten. Außerdem: Vernachlässigen Sie nicht den Speicherplatz, den das exponentielle Wachstum vonvector
Halteobjekten mit einer Größe von einigen Dutzend Bytes verursachen kann (wenn Sie dies nichtreserve
im Voraus tun können ).vector<smart_ptr<Large>>
vs.list<Large>
- ich würde sagen, wenn Sie zufälligen Zugriff auf die Elemente benötigen,vector
ist dies sinnvoll. Wenn Sie keinen wahlfreien Zugriff benötigen,list
scheint dies einfacher zu sein und sollte gleichermaßen funktionieren .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 das Kopieren Ihrer Inhalte sehr teuer ist. In einem solchen Fall kann es beispielsweise billiger sein, die Sammlung mit einer Liste zu sortieren.
Beachten Sie auch, dass ein Vektor eine Liste möglicherweise übertrifft, wenn die Sammlung klein ist (und der Inhalt nicht besonders teuer zu kopieren ist), selbst wenn Sie sie irgendwo einfügen und löschen. Eine Liste ordnet jeden Knoten einzeln zu. Dies ist möglicherweise viel teurer als das Verschieben einiger einfacher Objekte.
Ich glaube nicht, dass es sehr strenge Regeln gibt. Dies hängt davon ab, was Sie hauptsächlich mit dem Container tun möchten, wie groß der Container sein soll und welchen Typ er enthält. Ein Vektor übertrumpft im Allgemeinen eine Liste, da er seinen Inhalt als einen einzelnen zusammenhängenden Block zuweist (es handelt sich im Grunde genommen um ein dynamisch zugewiesenes Array, und in den meisten Fällen ist ein Array die effizienteste Methode, um eine Reihe von Dingen zu speichern).
quelle
list::size
ist nicht unbedingt konstante Zeit. Siehe stackoverflow.com/questions/228908/is-listsize-really-on und gcc.gnu.org/ml/libstdc++/2005-11/msg00219.htmlsplice
zwischen verschiedenen Listen als lineare Komplexität angegeben wird undsize
spezifisch konstant ist. Um Anfängern, die iterierensize
oder was auch immer, gerecht zu werden , ist eine ganze Klasse von Algorithmen für die STL oder einen "kompatiblen" Containerzeitraum unerreichbar.Nun, die Schüler meiner Klasse scheinen mir nicht erklären zu können, wann es effektiver ist, Vektoren zu verwenden, aber sie sehen ziemlich 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 zufällig sortieren, auch wenn sie nicht sortiert sind. Die Reihenfolge ändert sich nicht: Es ist effizient, wenn Ihr Speicher fragmentiert ist. Es hat aber auch einen anderen sehr großen Vorteil: Sie können Elemente einfach einfügen / entfernen, da Sie nur einige Zeiger ändern müssen. Nachteil: Um ein zufälliges einzelnes Element zu lesen, müssen Sie von einem Element zum anderen springen, bis Sie die richtige Adresse gefunden haben.
Vektoren : Bei Verwendung von Vektoren ist der Speicher viel besser organisiert als bei regulären Arrays: Jedes n-te Element wird unmittelbar nach dem (n-1) Element und vor dem (n + 1) Element gespeichert. Warum ist es besser als Liste? Weil es einen schnellen Direktzugriff ermöglicht. So geht's: Wenn Sie die Größe eines Elements in einem Vektor kennen und wenn diese im Speicher zusammenhängend sind, können Sie leicht vorhersagen, wo sich das n-te Element befindet. Sie müssen nicht alle Elemente einer Liste durchsuchen, um das gewünschte Element zu lesen. Mit Vektor lesen Sie es direkt und mit einer Liste, die Sie nicht lesen können. Andererseits ist das Ändern des Vektorarrays oder das Ändern eines Werts viel langsamer.
Listen sind besser geeignet, um Objekte zu verfolgen, die im Speicher hinzugefügt / entfernt werden können. Vektoren sind besser geeignet, 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, da die STL-Verbindungslisten beim Lesezugriff nicht so schnell sind wie bei Vektoren.
quelle
vector
durch Ändern der Größe verursachten Probleme langsam sein kann? dann vereinbart, aber in Fällen, in denenreserve()
verwendet werden kann, vermeidet dies diese Probleme.Grundsätzlich ist ein Vektor ein Array mit automatischer Speicherverwaltung. Die Daten sind im Speicher zusammenhängend. Der Versuch, Daten in die Mitte einzufügen, ist eine kostspielige Operation.
In einer Liste werden die Daten an nicht verwandten Speicherorten gespeichert. Beim Einfügen in der Mitte werden einige Daten nicht kopiert, um Platz für die neuen zu schaffen.
Um Ihre Frage genauer zu beantworten, zitiere ich diese Seite
quelle
Iteratoren können jederzeit nicht ungültig gemacht werden.
quelle
deque
ausreichen würden.Wenn Sie in der Mitte der Sequenz viel einfügen oder löschen. zB ein Speichermanager.
quelle
Die Wahrung der Gültigkeit von Iteratoren ist ein Grund, eine Liste zu verwenden. Eine andere Möglichkeit besteht darin, dass beim Verschieben von Elementen kein Vektor neu zugeordnet werden soll. Dies kann durch eine intelligente Verwendung von Reserve () verwaltet werden. In einigen Fällen ist es jedoch möglicherweise einfacher oder praktikabler, nur eine Liste zu verwenden.
quelle
Wenn Sie Objekte zwischen Containern verschieben möchten, können Sie verwenden
list::splice
.Beispielsweise kann ein Graphpartitionierungsalgorithmus eine konstante Anzahl von Objekten aufweisen, die rekursiv auf eine zunehmende Anzahl von Containern aufgeteilt sind. Die Objekte sollten einmal initialisiert werden und immer an denselben Speicherorten verbleiben. Es ist viel schneller, sie durch erneutes Verknüpfen neu anzuordnen, als durch Neuzuweisung.
Bearbeiten: Während sich Bibliotheken auf die Implementierung von C ++ 0x vorbereiten, wird der allgemeine Fall des Spleißens einer Teilsequenz in eine Liste mit der Länge der Sequenz linear komplex. Dies liegt daran, dass
splice
(jetzt) die Sequenz durchlaufen werden muss, um die Anzahl der darin enthaltenen Elemente zu zählen. (Da die Liste ihre Größe aufzeichnen muss.) Das einfache Zählen und erneute Verknüpfen der Liste ist immer noch schneller als jede andere Alternative, und das Zusammenfügen einer gesamten Liste oder eines einzelnen Elements sind 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 konformen Container suchen.quelle
Die einzige harte Regel,
list
die verwendet werden muss, ist, wo Sie Zeiger auf Elemente des Containers verteilen müssen.Im Gegensatz zu mit
vector
wissen Sie, dass der Speicher von Elementen nicht neu zugewiesen wird. Wenn es sein könnte, dann könnten Sie Zeiger auf unbenutzten Speicher haben, was bestenfalls ein großes Nein-Nein und im schlimmsten Fall ein großes Nein istSEGFAULT
.(Technisch würde ein
vector
von*_ptr
auch funktionieren, aber in diesem Fall emulieren Sielist
, also ist das nur Semantik.)Andere weiche Regeln haben mit den möglichen Leistungsproblemen beim Einfügen von Elementen in die Mitte eines Containers zu tun, woraufhin
list
dies vorzuziehen wäre.quelle
Machen Sie es einfach -
Am Ende des Tages, wenn Sie verwirrt sind, Container in C ++ auszuwählen, verwenden Sie dieses Flussdiagramm (sagen Sie Danke an mich): - Geben Sie hier die Bildbeschreibung ein
Vektor-
1. Vektor basiert auf ansteckendem Speicher
2. Vektor ist der richtige Weg für einen kleinen Datensatz
3. Vektorleistung am schnellsten beim Durchlaufen des Datensatzes
4. Das Löschen der Vektoreinfügung ist bei einem großen Datensatz langsam, bei einem sehr kleinen jedoch schnell
Liste -
1. Liste basiert auf dem Heapspeicher 2. Liste ist der richtige
Weg für sehr große Datenmengen
3. Liste ist vergleichsweise langsam beim Durchlaufen kleiner Datenmengen, aber schnell bei großen Datenmengen
4. Das Löschen von Listeneinfügungen ist schnell großer Datensatz, aber langsam bei kleineren
quelle
Listen sind nur ein Wrapper für eine doppelt verknüpfte Liste in stl und bieten daher eine Funktion, die Sie von einer d-Linkliste erwarten können, nämlich das Einfügen und Löschen von O (1). Während Vektoren ansteckende Datensequenzen sind, die wie ein dynamisches Array funktionieren. PS - einfacher zu durchlaufen.
quelle
Im Fall eines Vektors und einer Liste fallen mir folgende Hauptunterschiede auf:
Vektor
Ein Vektor speichert seine Elemente im zusammenhängenden Speicher. Daher ist ein zufälliger Zugriff innerhalb eines Vektors möglich, was bedeutet, dass der Zugriff auf ein Element eines Vektors sehr schnell ist, da wir einfach die Basisadresse mit dem Elementindex multiplizieren können, um auf dieses Element zuzugreifen. Tatsächlich dauert es für diesen Zweck nur O (1) oder konstante Zeit.
Da ein Vektor ein Array grundsätzlich umschließt, muss er jedes Mal, wenn Sie ein Element in den Vektor einfügen (dynamisches Array), seine Größe ändern, indem er einen neuen zusammenhängenden Speicherblock findet, um die neuen Elemente aufzunehmen, was zeitaufwändig ist.
Es wird kein zusätzlicher Speicher benötigt, um Zeiger auf andere Elemente darin zu speichern.
aufführen
Eine Liste speichert ihre Elemente im nicht zusammenhängenden Speicher. Daher ist ein wahlfreier Zugriff innerhalb einer Liste nicht möglich. Dies bedeutet, dass wir für den Zugriff auf ihre Elemente die Zeiger verwenden und die Liste durchlaufen müssen, die im Vergleich zum Vektor langsamer ist. Dies dauert O (n) oder eine lineare Zeit, die langsamer als O (1) ist.
Da eine Liste nicht zusammenhängenden Speicher verwendet, ist die Zeit, die zum Einfügen eines Elements in eine Liste benötigt wird, viel effizienter als im Fall ihres Vektor-Gegenstücks, da eine Neuzuweisung des Speichers vermieden wird.
Es benötigt zusätzlichen Speicher, um Zeiger auf das Element vor und nach einem bestimmten Element zu speichern.
Unter Berücksichtigung dieser Unterschiede berücksichtigen wir normalerweise den Speicher , den häufigen Direktzugriff und das Einfügen , um den Gewinner von Vektor gegen Liste in einem bestimmten Szenario zu bestimmen .
quelle
Liste ist doppelt verknüpfte Liste, daher ist es einfach, ein Element einzufügen und zu löschen. Wir müssen nur die wenigen Zeiger ändern, während im Vektor, wenn wir ein Element in die Mitte einfügen möchten, jedes Element danach um einen Index verschoben werden muss. Auch wenn die Größe des Vektors voll ist, muss er zuerst seine Größe erhöhen. Es ist also eine teure Operation. Überall dort, wo Einfüge- und Löschvorgänge häufiger ausgeführt werden müssen, sollte eine solche Fallliste verwendet werden.
quelle