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

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