Vorteile und Nachteile von std::vector und std::list ?

Hi Coder'S ,

Der Titel sagt eigentlich schon alles...hauptsächlich bezüglich:

Sortierung
wuchen
abspeichern/laden
einfügen(Anfang, Ende, Position-n)
Speicherverbrauch

Danke schonmal !!!

mfG Fritz

volkard

Sortierung
vector ist schneller

wuchen
vector ist schneller

abspeichern/laden
vector ist schneller

einfügen(Anfang, Ende, Position-n)
vector ist schneller am ende
liste ist schneller am anfang
position-n tut sich nix.

Speicherverbrauch
vector ist billiger

der allgemeine unterschied ist, daß vector schneller ist und ruckelt.

Danke erstmal!

emm meinte nat. suchen .

Wofür nutzt man dann std::list...die sind doch dann eher nachteilhaft .

volkard

Fritzchen schrieb:

Danke erstmal!

emm meinte nat. suchen .

Wofür nutzt man dann std::list...die sind doch dann eher nachteilhaft .

sie ruckelt nicht.
stell dir vor, bei deinem game muss der vector<KnownEnemy*> mal von 1000000 auf 2000000 wachsen und du stehst 2 sekunden reglos. da biste tot, tot, tot!

die liste ist im durchschnitt um faktor x lahmer, aber ruckelt nicht.

Das heißt:

vector: schneller Zugriff
list: bessere Dynamik (->Wachstum der Liste )

oder wie ?

std::list hat auch den Vorteil das die Iteratoren nicht ungültig werden wenn man neue Elemente einfügt oder welche löscht.

tntnet

volkard schrieb:

einfügen(Anfang, Ende, Position-n)
vector ist schneller am ende
liste ist schneller am anfang
position-n tut sich nix.

Bei Position-n muß ich dir leider wiedersprechen. Das ist genau der Hauptvorteil einer std::list gegenüber std::vector, daß ein Einfügen an einer beliebigen Position in konstanter Zeit möglich ist.

Um ein neues Element in eine Liste einzufügen müssen nur ein paar Zeiger umgebogen werden. Und zwar unabhängig, wo das geschieht.

Bei einem std::vector müssen alle nachfolgenden Elemente um eine Stelle verschoben werden, was bei sehr vielen Elementen relativ lange dauern kann. Ausserdem muß der std::vector möglcherweise den alloziierten Speicher (capacity) erhöhen, was sogar zum kopieren des gesamten Vektors führt.

Tntnet

volkard

tntnet schrieb:

Bei Position-n muß ich dir leider wiedersprechen. Das ist genau der Hauptvorteil einer std::list gegenüber std::vector, daß ein Einfügen an einer beliebigen Position in konstanter Zeit möglich ist.

wenn du ignorierst, daß n zu suchen O(n) kostet, dann ja. wenn du zufällig nen iterator auf stelle N hast, gehts mit der liste *viel* schneller als mit dem vector.

Ausserdem muß der std::vector möglcherweise den alloziierten Speicher (capacity) erhöhen, was sogar zum kopieren des gesamten Vektors führt.

das wachsen ist durchschnittlich aber O(1).

codekasper

Das kommt wohl darauf an, wieviele Elemente man speichern will und wie groß die sind. Es kann durchaus günstiger sein, die Liste jedesmal zu durchlaufen, anstatt im Fall von vector die Objekte im Speicher zu verschieben. Wieso soll die Kapazitätserhöhung O(1) sein? Wenn ich zB 1000 große Objekte drin habe, die alle umkopiert werden müssen, dann macht es durchaus einen Unterschied aus ob ich eben 1000 oder 1 drin habe oder? Und wenn dem so ist, dann ist das ja genau das, was du "ruckeln" nanntest. Nämlich dass sich der vector im Falle einer Kapazitätserhöhung nicht mehr vorhersagbar und schlechter als die Liste verhält. Zumindest schreibt auch Meyers in Effective STL (wenn ich mich nicht irre) dass list besser als vector ist wenn in am Anfang oder in der Mitte oft gelöscht/eingefügt wird.

finix

volkard schrieb:

tntnet schrieb:

Bei Position-n muß ich dir leider wiedersprechen. Das ist genau der Hauptvorteil einer std::list gegenüber std::vector, daß ein Einfügen an einer beliebigen Position in konstanter Zeit möglich ist.

wenn du ignorierst, daß n zu suchen O(n) kostet, dann ja. wenn du zufällig nen iterator auf stelle N hast, gehts mit der liste *viel* schneller als mit dem vector.

Naja, kommt wohl auf die Verwendung an, oder? Wenn man N gleich kennt braucht man wahrscheinlich ohnehin wahlfreien Zugriff, ansonsten aber wird man zumeist tatsächlich gleich den richtigen Iterator zur Hand haben.

Zum Einfügen hilft vielleicht folgende Tabelle weiter:

begin      middle     end
std::vector  linear     linear     amortized constant
std::list    constant   constant   constant

volkard schrieb:

wuchen
vector ist schneller

Wieso genau soll man denn im vector schneller suchen können?

volkard schrieb:

abspeichern/laden
vector ist schneller

Ja? Echt?

volkard schrieb:

abspeichern/laden
vector ist schneller

Kannst du das kurz erklären?

volkard schrieb:

Speicherverbrauch
vector ist billiger

Ohne den Anwendungsfall zu kennen? (Größe der Menge, Fluktuation selbiger, sizeof(container::value_type)...)

MfG, splice

Also ich brauch das für ne Playlist eines kleinen mini players...

Playlist

Schildkroete

Fritzchen schrieb:

Also ich brauch das für ne Playlist eines kleinen mini players...

Ich würd' mal sagen, dass es bei kleinen listen/vectoren, welche nicht oft geändert werden, keine richtigen Unterschiede bei der Performance gibt, also würde ich dir den Vector empfehlen, weil du da random access hast...

volkard

finix schrieb:

volkard schrieb:

wuchen
vector ist schneller

Wieso genau soll man denn im vector schneller suchen können?

erheblich schneller wegen cache-lokalität natürlich.

volkard schrieb:

abspeichern/laden
vector ist schneller

Ja? Echt?

wegen cache-lokalitär umd schnellerem einfügen.

volkard schrieb:

Speicherverbrauch
vector ist billiger

Ohne den Anwendungsfall zu kennen? (Größe der Menge, Fluktuation selbiger, sizeof(container::value_type)...)

bei kleinen elementen.
http://www.c-plusplus.net/forum/viewtopic-var-t-is-157416-and-postdays-is-0-and-postorder-is-asc-and-start-is-0.html
aber große objekte tut man eh nicht in einen container stopfen, sondern zeiger auf diese.

volkard

Fritzchen schrieb:

Wofür nutzt man dann std::list...die sind doch dann eher nachteilhaft .

deswegen nutzt man sie sehr selten. ich nutze sie nie.

volkard

codekasper schrieb:

Wieso soll die Kapazitätserhöhung O(1) sein? Wenn ich zB 1000 große Objekte drin habe, die alle umkopiert werden müssen, dann macht es durchaus einen Unterschied aus ob ich eben 1000 oder 1 drin habe oder?

durchschnittlich O(1).
stellen wir uns vor, der vector beginnt mit größe 1 und jedesmal, wenn beim einfügen die kapazität erschöpft ist, verdoppelt sich die größe, wobei alle bisherigen elemente umkopiert werden müssen.
bei einer endgröße von 2^e (und e=log2(n)) muß er e mal verdoppeln und dabei 1+2+4+8+...+2^(e-1) objekte kopieren. und 1+2+4+8+...+2^(e-1)<2e. also muss er in der gesamtbilanz pro eingefügtem objekt nur zwei objekte im array umkopieren und nur log2(n) mal new aufrufen.
bei der liste muß er n mal new aufrufen. ich gehe wieder von kleinen objekten aus und nem op new, der mindestens 100 takte pro aufruf kostet. klingt nach nem vector, der beim hintenanfügen zehnmal so schnell wie die liste ist.

volkard

Fritzchen schrieb:

Also ich brauch das für ne Playlist eines kleinen mini players...

für meinen alten microplayer benutzte ich vector. aber der konnte auch nichts außer random-shuffle. je nachdem, was deine oberfläche kann, kann liste günsiger sein oder nicht. ich denke, es ist in ordnung, zunächst einfach irgendwas zu nehmen, und später umzusteigen, falls bedarf bestehen sollte.

HumeSikkins

volkard schrieb:

Fritzchen schrieb:

Wofür nutzt man dann std::list...die sind doch dann eher nachteilhaft .

deswegen nutzt man sie sehr selten. ich nutze sie nie.

In meinen Augen ist die Geschichte mit der Iterator-Gültigkeit der einzige wirklich große Vorteil von list. Man kommt zwar nicht sooft in die Situation, dass man "stabile" Referenzen in einen Container braucht, aber wenn, dann ist std::list eine gute Wahl.

Erhard Henkes

Neben std::vector kann man in manchen Fällen auch über std::deque nachdenken.

Ich sage auch, das das Einfügen bei einer Liste IMMER schneller ist als bei einem Vector wenn man die Liste als Schlange verwenden will.

Vector:
Einfügen Vorne,
Entfernen hinten,
jedes Element einzeln verschieben (lesen+schreiben) um das loch zu schließen

Liste:
Einfügen Vorne (ein Objekt erzeugen 2 Zeiger verändern)
Entfernen hinten (Objekt löschen, ein Zeiger verändern)

Will man nur Konstant viele Objekte speichern und darauf zuzugreifen ist der Vector schneller.

Aber wenn man dynamische Daten hat ist die Liste schneller, denn die Zeit, die man beim Vector einspart, verliert man, wenn dieser vergrößert werden muß. Vom Verkleinern will ich erst gar nicht reden, da die Liste hierbei x mal im Vorteil ist.

Also:
Statische Daten (oder wenig zu erwartende Änderungen oder nur wenig Daten) => Vector

Dynamische Daten, Computerspiele(weil man nicht ne Sekunde stehen will) => Liste

Oder was man will, und wenns stört einfach das andere einbauen