Zusammenfassung einiger STL-Datenstrukturen(vector,list,deque)

[Gast]

Hi,

ich werde hier mal bestimmte Verhalten von einigen STL-Containern(vector,list,deque) postet und wann man welche gebrauchen sollte, da die drei eine gewisse Ähnlichkeit haben und man für sich die passendere aussuchen muss.

Bitte mich dann verbessern, was falsch ist und was ergänzt werden könnte.

vector:

• Dynamisches Array.
• Random-Access-Zugriff über op[] oder at().
• Konstante Zugriffszeit(Lesen/Schreiben) O(1) an beliebiger Stelle.
• O(1) beim Einfügen und Löschen am Ende
• O(N) beim Einfügen/Löschen am Anfang oder Mitte
• vector vergrößert beim Einfügen , wenn der Speicher nicht mehr ausreicht den Speicher und das nicht nur für ein Element, sondern für mehrere.
• Bei resize() direkt auf die richtige Größe, ist das Zugriff(Schreiben) auf Element schneller, als bei list.
• Beim Einfügen/Löschen eines Elements, müssen nachfolgende Elemente verschoben werden.
• vector<>::iterator häufig als einfacher Zeiger implementiert.

list:

• Doppelt verkettete Liste.
• Lineare Zugriffszeit O(N) auf ein bestimmtes Element.
• Einfügen/Löschen an beliebige Stelle in konstanter Zeit O(1), aber um zur Position zu kommen O(N).
• Immer soviel Speicher wie nötig.
• Iteratoren werden beim Ändern der list nicht ungültig.

deque:

• Double ended queue ( Schlange mit zwei Enden )
• Random-Access-Zugriff über op[].
• Einfügen/Löschen am Anfang/Ende in O(1).
• Einfügen/Löschen Mitte O(N).
• Zugriffszeit O(1) auf ein bestimmtes Element.

[otze]

KasF schrieb:

vector vergrößert bei jedem Einfügen ( O(N) ? ) den Speicher und das nicht nur für ein Element, sondern für mehrere.

der vector erhöht nicht bei jedem einfügen die größe, sodnern nur dann wenn der platz nicht mehr reicht, deswegen ist einfügen am Ende normalerweise O(1).

[*]vector<>::iterator häufig als einfacher Zeiger implementiert

die tendenz geht aber immer häufiger zur wrapperklasse, damit einige Sachen die sich darauf evrlassen, dass as ding ein zeiger ist nicht funktionieren.

Suchen in ( O(N) ).

Die Komplexität kann man nicht angeben, da dies davon abhängt wie die elemente eingefügt werden oder ob der vector sortiert wird.

zur deque:

Zugriffszeit ( O(?) ) auf ein bestimmtes Element ? ( wie vec oder list implementiert ? ).

O(N) laut standard.

deque vergrößert bei jedem Einfügen ( O(N) ? ) den Speicher und das nicht nur für ein Element, sondern für mehrere.

die deque hat in diesem punkt kein vectorverhalten, bei durch listen verknüpfte Datenblöcke hätte dieses verhalten auch keinen großen Sinn. Zumal die komplexitätsbedingungen etwas anderes sagen.

einfügen ist aber 0(N) in der mitte und 0(1) am anfang und ende(anders als beim vector)

[Gast]

otze schrieb:

der vector erhöht nicht bei jedem einfügen die größe, sodnern nur dann wenn der platz nicht mehr reicht, deswegen ist einfügen am Ende normalerweise O(1).

Ja stimmt, bissl falsch formuliert. Ändere es gleich. Das Einfügen mittendrin ist aber doch O(N) oder, da die Elemente ja verschoben werden müssen ?

otze schrieb:

Die Komplexität kann man nicht angeben, da dies davon abhängt wie die elemente eingefügt werden oder ob der vector sortiert wird.

Achso, meine das hätte ich mal irgendwo in OOP für Dummies gelesen. Werde gleich mal nachschauen und die Stelle posten.

[Gast]

Immer als ich Antworten gedrückt habe, hattest du schon editiert.
Das von vorhin, also wo du meintest das wäre implementationsspezifisch ist also nicht so ?

[Gast]

otze schrieb:

die deque hat in diesem punkt kein vectorverhalten, bei durch listen verknüpfte Datenblöcke hätte dieses verhalten auch keinen großen Sinn. Zumal die komplexitätsbedingungen etwas anderes sagen.

Klingt logisch. Also hat deque auch immer soviel Speiche wie nötig ?

[otze]

erstmal muss ich bissl verwirrung auflösen. grad nochmal auf sgi.com nachgeschaut:

A deque is very much like a vector: like vector, it is a sequence that supports random access to elements, constant time insertion and removal of elements at the end of the sequence, and linear time insertion and removal of elements in the middle.

The main way in which deque differs from vector is that deque also supports constant time insertion and removal of elements at the beginning of the sequence .

Also:
zugriff: O(1)
einfügen/entfernen am anfang/ende: O(1)
einfügen/entfernen in der mitte: O(N)

KasF schrieb:

otze schrieb:

die deque hat in diesem punkt kein vectorverhalten, bei durch listen verknüpfte Datenblöcke hätte dieses verhalten auch keinen großen Sinn. Zumal die komplexitätsbedingungen etwas anderes sagen.

Klingt logisch. Also hat deque auch immer soviel Speiche wie nötig ?

nein, ich denke am anfang/ende sind ein paar elemente frei. immer wenn diese eckblöcke voll sind, wird dann ein neuer block angehängt.

[Gast]

otze schrieb:

nein, ich denke am anfang/ende sind ein paar elemente frei. immer wenn diese eckblöcke voll sind, wird dann ein neuer block angehängt.

?

Und wie fasst man sowas in der O-Notation zusammen:

KasF schrieb:

Einfügen/Löschen an beliebige Stelle in konstanter Zeit O(1), aber um zur Position zu kommen O(N).

[otze]

KasF schrieb:

otze schrieb:

nein, ich denke am anfang/ende sind ein paar elemente frei. immer wenn diese eckblöcke voll sind, wird dann ein neuer block angehängt.

?

da der standard nur vorschreibt was für eigenschaften der container hat, muss ein "ich denke" ausreichen, weil man sowas sicher auf verschiedenen wegen erreichen kann.

[CStoll]

KasF schrieb:

vector:

Bei resize() direkt auf die richtige Größe, ist das Einfügen von Element schneller, als bei list.

Mit resize() vergrößerst du den Speicher, um Speicher vorzureservieren, kannst du reserve() verwenden. Und Einfügen an beliebiger Stelle bleibt trotzdem im Bereich O(n) (list: O(1))

list:

Iterator-Zugriff langsamer, als bei einem vector, da i.d.R eine Klasse die auf einen Knoten zeigt.

Also die Unterschiede, um von einem Iterator zum dahinterliegenden Element zu gelangen, sind eher bedeutungslos (und dank inline-Methoden normalerweise rausoptimiert).

deque:

Allozierte Speicherblöcke nicht an einem Stück, sondern verteilt und mit Liste verknüpft.

Wie die Speicherblöcke angeordnet sind, wird nicht spezifiziert. Aber aus Sicht der Zugriffsgeschwindigkeit ist ein Array von Zeigern wahrscheinlicher als eine Liste.

[Konrad Rudolph]

otze schrieb:

nein, ich denke am anfang/ende sind ein paar elemente frei. immer wenn diese eckblöcke voll sind, wird dann ein neuer block angehängt.

Hmm. Kommt man denn damit aus? Ich denke nicht, dass man damit auf eine amortisiert konstante Laufzeit kommt. Ich bevorzuge immer noch die Implementierung als Ringpuffer, wobei die Deque eben als Ring auf einem Vektor liegt (und der tatsächliche Index per '(i + start) % length' errechnet wird). Beim Vergrößern passiert dann dasselbe wie beim Vektor.

[CStoll]

Konrad Rudolph schrieb:

otze schrieb:

nein, ich denke am anfang/ende sind ein paar elemente frei. immer wenn diese eckblöcke voll sind, wird dann ein neuer block angehängt.

Hmm. Kommt man denn damit aus? Ich denke nicht, dass man damit auf eine amortisiert konstante Laufzeit kommt. Ich bevorzuge immer noch die Implementierung als Ringpuffer, wobei die Deque eben als Ring auf einem Vektor liegt (und der tatsächliche Index per '(i + start) % length' errechnet wird). Beim Vergrößern passiert dann dasselbe wie beim Vektor.

Ja, das wäre auch eine Lösung.

*mal die <deque> meines Compilers angesehen habe* Also die Version der MSVC verwendet einen T** als interne Datenstruktur und rechnet den Index um zu data[_Block][_Off] (_Block=(i+_Offset)/BLOCKSIZE, _Off=(i+_Offset)%BLOCKSIZE).

[Gast]

CStoll schrieb:

Und Einfügen an beliebiger Stelle bleibt trotzdem im Bereich O(n) (list: O(1))

Stimmt, wollte schon was andere schreiben ist mir aber gerade klar geworden. Auf die richtige Größe bringen und dann mit op[] oder *it an diese Stelle schreiben, ist wesentlich schneller als zB ein insert und das sollte dann ja O(1) sein. Das dachte ich die ganze Zeit, habe aber was falsches geschrieben.

KasF schrieb:

Einfügen/Löschen an beliebige Stelle in konstanter Zeit O(1), aber um zur Position zu kommen O(N).

Und der letzte Teil ist ja auch wohl falsch, da dies ja eine doppelt verkette List ist und ich ein prev-Zeiger habe, womit das durchlaufen zum Knoten ja überflüssig wäre.

CStoll schrieb:

Also die Unterschiede, um von einem Iterator zum dahinterliegenden Element zu gelangen, sind eher bedeutungslos (und dank inline-Methoden normalerweise rausoptimiert).

OK, das habe ich hier irgendwo auf nem Kritzel-Blatt stehen, wo "tntnet" druntersteht. Er hatte mich mal vor langer Zeit bissl belehrt Suche mal gleich die Stelle.

CStoll schrieb:

Wie die Speicherblöcke angeordnet sind, wird nicht spezifiziert.

Jo, habe gerade bissl im Standard gesucht und nirgends etwas davon gefunden.

Edit: http://c-plusplus.net/forum/viewtopic-var-p-is-1063366.html#1063366

[CStoll]

KasF schrieb:

KasF schrieb:

Einfügen/Löschen an beliebige Stelle in konstanter Zeit O(1), aber um zur Position zu kommen O(N).

Und der letzte Teil ist ja auch wohl falsch, da dies ja eine doppelt verkette List ist und ich ein prev-Zeiger habe, womit das durschlaufen zum Knoten ja überflüssig wäre.

Nicht unbedingt - das kommt ganz darauf an, womit du beginnst. Wenn du schon einen Iterator auf die Zielposition hast, geht Einfügen in O(1) (neuen Knoten anlegen und ein par Zeiger umbiegen). Wenn du die Einfügeposition als Index gegeben hast, mußt du erstmal dahin gelangen.

CStoll schrieb:

Also die Unterschiede, um von einem Iterator zum dahinterliegenden Element zu gelangen, sind eher bedeutungslos (und dank inline-Methoden normalerweise rausoptimiert).

OK, das habe ich hier irgendwo auf nem Kritzel-Blatt stehen, wo "tntnet" druntersteht. Er hatte mich mal vor langer Zeit bissl belehrt Suche mal gleich die Stelle.

Nur Zur Klarstellung: Ich will nicht behaupten, daß verschiedene Container-Iteratoren völlig gleichwertig sind. Aber die Laufzeitunterschiede fallen bestenfalls in den Bereich Mikro-Optimierung.

CStoll schrieb:

Wie die Speicherblöcke angeordnet sind, wird nicht spezifiziert.

Jo, habe gerade bissl im Standard gesucht und nirgends etwas davon gefunden.

Der ANSI-Standard gibt ja auch keinen exakten Aufbau vor, sondern nur Laufzeitgrenzen. Wie diese Grenzwerte erreicht werden können, ist Sache der Compilerbauer (genauso legen die Laufzeibedingungen für set<> und Co. nahe, einen balancierten Baum zu verwenden - aber welcher da letztlich in Frage kommt, ist aus ANSI-Sicht egal (ja, es gibt verschiedene Lösungsansätze, um Bäume balanciert zu halten)).

[Gast]

CStoll schrieb:

Nur Zur Klarstellung: Ich will nicht behaupten, daß verschiedene Container-Iteratoren völlig gleichwertig sind. Aber die Laufzeitunterschiede fallen bestenfalls in den Bereich Mikro-Optimierung.

OK.

P.S. Mein Edit und dein Post sind auf die Sekunde gleich, vielleicht hat ja deswegen das Absenden bei mir ne halbe Ewigkeit gebraucht

[Gast]

CStoll schrieb:

Wenn du die Einfügeposition als Index gegeben hast, mußt du erstmal dahin gelangen.

Es gibt doch nur die Möglichkeit bei der list über einen Iterator ein Element einzufügen, oder meinst du etwas anderes ?

[CStoll]

KasF schrieb:

CStoll schrieb:

Wenn du die Einfügeposition als Index gegeben hast, mußt du erstmal dahin gelangen.

Es gibt doch nur die Möglichkeit bei der list über einen Iterator ein Element einzufügen, oder meinst du etwas anderes ?

Genau - deshalb mußt du ja erst den richtigen Iterator finden, wenn du ihn noch nicht in der Hand hast

int idx = ...;
list<...>::iterator pos = myList.begin();
advance(pos,idx);//dieser Schritt benötigt O(n) Laufzeit
myList.insert(pos,...);

[Gast]

Achso, das war gemeint.