005
18.10.2004, 14:38 Uhr
virtual
Sexiest Bit alive
(Operator)
|
@(un)wissender
Häh?? Meine Listen haben immer eine definierte Ordung.
@Guy
Also der prinzipielle Unterschied ist eigentlich der, daß eine liste eben eine Doppelverkettete Liste ist, wie man sie überall in den Kinderbüchern beschrieben findet: zu jedem Element gibt es einen Verweis auf den Vorgänger und zu dem nachfolger.
Ein vektor braucht diese Verweise nicht, da liegen die Elemente direkt hintereinander, dh es wird ein ziemlich großer Speicherblock für diese Elemente besorgt und da eins nach dem anderen reingeklatscht.
Man kann sich nun überlegen, welche Unterschiede sich daraus ergeben:
1. Einfüge/entfernen Operationen sind bei einer Liste deutlich schneller. Je komplexer die in der Liste/Vektor enthaltenen Objekte sind, desto mehr macht sich dieser Unterschied bemerkbar. Gleiches gilt für die Anzahl der Objekte.
2. Eine Liste hat einen manchmal nicht ganz vernachlässigbaren Speicheroverhead. Wenn Du zB auf einem typischen 32 Bit Rechner arbeitest und einfach nur integer Wert abspeicherst, liegt der Speicherberaf eines Vectors gegenüber einer Liste bei 33%!
3. Das durchlaufen der einzelnen Elemente durch eine Liste ist langsamer und - da man keinen index Zugriff auf die Liste hat (op[]), ist dieser auch umständlicher.
Nichtsdestotrotz (ich liebe dieses Wort!) wird leider std::vector viel zu oft verwendet, an Stellen, wo sich eher eine List empfehlen würde.
Oft ist es auch eine gute Strategie, zunächst eine "Ansammlung" von Objekten als list aufzubauen und erst später, wenn die Sammlung komplett ist, in einen std::vector zu verwandeln. Wir hatten hier mal vor einiger Zeit einen Performancevergleich bzgl. Sortieren, der so manchen std::vector Verfechter das fürchten gelehrt hat....
Das Thema ist komplexer, als man meinen könnte.
--
Gruß, virtual
Quote of the Month
Ich eß' nur was ein Gesicht hat (Creme 21)
Dieser Post wurde am 18.10.2004 um 14:40 Uhr von virtual editiert. |
.