Vektor vs. Liste in STL

237

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 vectoralles kann.

Könnte mir jemand ein Szenario anbieten, in dem dies vectorkeine praktikable Option ist, sondern listverwendet werden muss?

skydoor
quelle
6
Obwohl es nicht das ist, was Sie gefragt haben, sollten Sie darauf hinweisen, dass die Standardeinstellung für Vektor auch bedeutet, dass Sie problemlos mit älterem Code, C-Bibliotheken oder Nicht-Vorlagenbibliotheken interagieren können, da Vektor ein dünner Wrapper um das "traditionelle" dynamische Array eines Zeigers ist und Größe.
17
Bjarne Strostrup machte tatsächlich einen Test, bei dem er Zufallszahlen erzeugte und diese dann einer Liste bzw. einem Vektor hinzufügte. Die Einfügungen wurden so vorgenommen, dass die Liste / der Vektor jederzeit geordnet war. Obwohl dies typischerweise eine "Listendomäne" ist, übertraf der Vektor die Liste um einen GROSSEN Rand. Der Grund dafür ist, dass der Speicherzugriff langsam ist und das Caching für sequentielle Daten besser funktioniert. Es ist alles in seiner Keynote von "GoingNative 2012" verfügbar
Ausweichen
1
Wenn Sie die Keynote von Bjarne Stroustrup sehen möchten, die @evading erwähnt hat, habe ich sie hier gefunden: youtu.be/OB-bdWKwXsU?t=2672
brain56

Antworten:

98

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?

Martin York
quelle
1
Das Einfügen von Elementen am Ende zählt ebenfalls, da dies zu Speicherzuweisungen und Kosten für das Kopieren von Elementen führen kann. Und auch das Einfügen von Elenets am Anfang eines Vektors ist so gut wie unmöglich, listhatpush_front
Notinlist
9
Nein, das Einfügen von Elementen am Ende eines Vektors wird zeitlich konstant abgeschrieben. Die Speicherzuweisungen erfolgen nur gelegentlich, und Sie können den Vektor vorab zuweisen, um dies zu verhindern. Wenn Sie konsistente Einfügungen mit konstanter Zeit garantiert haben MÜSSEN, ist dies natürlich immer noch ein Problem.
Brian
15
@Notinlist - Ist das Folgende für Sie "fast unmöglich"? v.insert (v.begin (), i)
Manuel
4
@Notinlist - Ich stimme Ihnen zu, es ist nur so, dass ich nicht wollte, dass das OP denkt, dass die Schnittstelle nicht vorhanden ist, falls man sich in den (Leistungs-) Fuß schießen möchte.
Manuel
16
Bjarne Strostrup machte tatsächlich einen Test, bei dem er Zufallszahlen erzeugte und diese dann einer Liste bzw. einem Vektor hinzufügte. Die Einfügungen wurden so vorgenommen, dass die Liste / der Vektor jederzeit geordnet war. Obwohl dies typischerweise eine "Listendomäne" ist, übertraf der Vektor die Liste um einen GROSSEN Rand. Der Grund dafür ist, dass der Speicherzugriff langsam ist und das Caching für sequentielle Daten besser funktioniert. Es ist alles in seiner Keynote von "GoingNative 2012" verfügbar
Ausweichen
408

Vektor:

  • Aneinandergrenzende Erinnerung.
  • Weist zukünftigen Elementen vorab Speicherplatz zu, sodass zusätzlicher Speicherplatz erforderlich ist, der über die für die Elemente selbst erforderlichen Werte hinausgeht.
  • 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 Zeit, aber Einfügungen an anderer Stelle sind ein kostspieliges O (n).
  • Löschungen am Ende des Vektors sind konstante Zeit, aber für den Rest ist es O (n).
  • Sie können zufällig auf seine Elemente zugreifen.
  • Iteratoren werden ungültig, wenn Sie Elemente zum oder vom Vektor hinzufügen oder entfernen.
  • Sie können leicht auf das zugrunde liegende Array zugreifen, wenn Sie ein Array der Elemente benötigen.

aufführen:

  • 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 Zeigern auf das nächste und vorherige Element in der Liste.
  • Sie müssen niemals Speicher für die gesamte Liste neu zuweisen, nur weil Sie ein Element hinzufügen.
  • Einfügungen und Löschungen sind billig, egal wo in der Liste sie auftreten.
  • Es ist billig, Listen mit Spleißen zu kombinieren.
  • Sie können nicht zufällig 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 hinzufügen, da kein Array zugrunde liegt.

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.

Jonathan M Davis
quelle
2
Die Zuweisung aus dem kostenlosen Shop ist ebenfalls nicht kostenlos. :) Durch Hinzufügen neuer Elemente zu einem Vektor werden O (log n) -freie Speicherzuordnungen ausgeführt. Sie können 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.
bk1e
7
Eine weitere Überlegung ist, dass listbeim Löschen von Elementen Speicher freigegeben wird, dies jedoch vectornicht. A vectorreduziert seine Kapazität nicht, wenn Sie seine Größe reduzieren, es sei denn, Sie verwenden den swap()Trick.
bk1e
@ bk1e: Ich möchte wirklich wissen, Ihren Trick in Reserve () und Swap () :)
Dzung Nguyen
2
@nXqd: Wenn Sie einem Vektor N Elemente hinzufügen müssen, rufen Sie v.reserve (v.size () + N) auf, damit nur eine freie Speicherzuordnung ausgeführt wird. Der swap () Trick ist hier: stackoverflow.com/questions/253157/how-to-downsize-stdvector
bk1e
1
@simplename Nein. Was es sagt, ist richtig. Der Vektor weist den Elementen, die sich derzeit im Vektor befinden, zusätzlichen Platz über den Platz hinaus zu. Diese zusätzliche Kapazität wird dann verwendet, um den Vektor zu züchten, so dass das Wachsen O (1) amortisiert wird.
Jonathan M Davis
34

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.

Hans Passant
quelle
32

Bei den meisten Antworten fehlt ein wichtiges Detail: Wozu?

Was möchten Sie im Container aufbewahren?

Wenn es sich um eine Sammlung von ints handelt, std::listgeht 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 dem list<int>Beats vector<int>. Und selbst dann deque<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>als vector<UglyBlob>.

Wenn Sie jedoch zu vector<UglyBlob*>oder sogar vector<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.

Tomasz Gandor
quelle
1
Eine weitere Überlegung, die ich beim Lesen von "Effective STL" von Meyers hatte: Eine besondere Eigenschaft von list<T>ist die Möglichkeit splicein O (1) . Wenn Sie zeitlich konstantes Spleißen benötigen, kann Liste auch die Struktur der Wahl sein;)
Tomasz Gandor
1 - Es muss nicht einmal eine 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 von vectorHalteobjekten mit einer Größe von einigen Dutzend Bytes verursachen kann (wenn Sie dies nicht reserveim Voraus tun können ).
Martin Ba
Was vector<smart_ptr<Large>>vs. list<Large>- ich würde sagen, wenn Sie zufälligen Zugriff auf die Elemente benötigen, vectorist dies sinnvoll. Wenn Sie keinen wahlfreien Zugriff benötigen, listscheint dies einfacher zu sein und sollte gleichermaßen funktionieren .
Martin Ba
19

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).

Onkel Bens
quelle
1
+1. Das Spleißen wird übersehen, ist aber leider nicht wie gewünscht konstant. : (((Es kann nicht sein, wenn list :: size eine konstante Zeit ist.)
Ich bin mir ziemlich sicher, dass list :: size genau aus diesem Grund linear ist (sein darf).
Onkel Bens
1
@ Roger: list::sizeist nicht unbedingt konstante Zeit. Siehe stackoverflow.com/questions/228908/is-listsize-really-on und gcc.gnu.org/ml/libstdc++/2005-11/msg00219.html
Potatoswatter
@Potatoswatter: Dass der Standard vage ist und Sie sich folglich nicht auf "konforme" Implementierungen verlassen können, macht ihn noch problematischer. Sie müssen die stdlib buchstäblich meiden, um eine tragbare und zuverlässige Garantie zu erhalten.
@ Roger: ja leider. Mein aktuelles Projekt basiert stark auf Spleißoperationen und diese Struktur ist fast gerade C. Noch bedauerlicher ist, dass in N3000 die Sequenz splicezwischen verschiedenen Listen als lineare Komplexität angegeben wird und sizespezifisch konstant ist. Um Anfängern, die iterieren sizeoder was auch immer, gerecht zu werden , ist eine ganze Klasse von Algorithmen für die STL oder einen "kompatiblen" Containerzeitraum unerreichbar.
Potatoswatter
13

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.

Jokoon
quelle
"Das Ändern des Vektorarrays oder das Ändern eines Werts ist viel langsamer" - wie gelesen, scheint dies dem zu widersprechen, was Sie kurz zuvor gesagt haben, dass der Vektor aufgrund seiner geringen und zusammenhängenden Natur für eine gute Leistung prädisponiert ist. Meinten Sie damit, dass die Neuzuweisung der vectordurch Ändern der Größe verursachten Probleme langsam sein kann? dann vereinbart, aber in Fällen, in denen reserve()verwendet werden kann, vermeidet dies diese Probleme.
underscore_d
10

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

Vektoren sind im Allgemeinen zeitlich am effizientesten, um auf Elemente zuzugreifen und Elemente am Ende der Sequenz hinzuzufügen oder zu entfernen. Bei Vorgängen, 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.

f4.
quelle
9

Iteratoren können jederzeit nicht ungültig gemacht werden.

dirkgently
quelle
2
Aber springen Sie niemals zu dieser Schlussfolgerung über Iteratoren, ohne zu fragen, ob dauerhafte Verweise auf a dequeausreichen würden.
Potatoswatter
8

Wenn Sie in der Mitte der Sequenz viel einfügen oder löschen. zB ein Speichermanager.

AraK
quelle
Der Unterschied zwischen ihnen liegt also nur in der Effizienz und nicht in funktionalen Fragen.
Skydoor
Beide modellieren natürlich eine Folge von Elementen. Es gibt einen kleinen Unterschied in der Verwendung, wie von @dirkgently erwähnt, aber Sie müssen die Komplexität Ihrer "häufig durchgeführten" Operationen betrachten, um zu entscheiden, welche Sequenz Sie wählen möchten (@ Martin-Antwort).
AraK
@skydoor - Es gibt einige funktionale Unterschiede. Beispielsweise unterstützt nur der Vektor den Direktzugriff (dh er kann indiziert werden).
Manuel
2
@skydoor: Effizienz bedeutet Leistung. Eine schlechte Leistung kann die Funktionalität beeinträchtigen. Leistung ist schließlich der Vorteil von C ++.
Potatoswatter
4

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.

John Dibling
quelle
4

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.

Kartoffelklatsche
quelle
2

Die einzige harte Regel, listdie verwendet werden muss, ist, wo Sie Zeiger auf Elemente des Containers verteilen müssen.

Im Gegensatz zu mit vectorwissen 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 ist SEGFAULT.

(Technisch würde ein vectorvon *_ptrauch funktionieren, aber in diesem Fall emulieren Sie list, 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 listdies vorzuziehen wäre.

iPherian
quelle
2

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

xyz xyz
quelle
1

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.

Ritankar Paul
quelle
0

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 .

Ardent Coder
quelle
0

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.

Siddesh Pawar
quelle