Bei Listen: push_back oder push_front?

Bashar

push_front oder push_back sind bei list gleich schonell (es ist jedenfalls vorgeschrieben, dass beides in konstanter Zeit zu geschehen hat). vector hat nur push_back (push_front wär nur in O(n) zu implementieren und wird daher nicht angeboten). deque hat aber auch push_front und push_back in O(1).

Was kann deque besser/schlecter als list?

SirLant

Ich würd dir zu push_back raten, du solltest wenn möglich immer die methoden wählen
die zu den meisten Containern komtapibel sind so kannst du ne liste mal eben schnell
ohne aufwand durch nen vector ersetzen.

Ich hab zwar erst im Struppi das Kapitel über die Container gelesen, aber weiß schon
nicht mehr was der Unterschied war, Optimizer

Bashar

Bei deque kannst du in der Mitte nicht in O(1) einfügen. Dafür hast du Random Access.

Und welche Ordnung hat der Random Access? O(1) oder wie?
@SirLant: Jo, hab ich auch gelesen, aber ich weiss es auch nicht mehr.

EDIT: Gibts da irgendwo ne Übersicht, ich will mir nicht immer deswegen das fette Buch ausleihen.

Bashar

Optimizer schrieb:

Und welche Ordnung hat der Random Access? O(1) oder wie?

Ja klar, sonst wär es kein Random Access.

EDIT: Gibts da irgendwo ne Übersicht, ich will mir nicht immer deswegen das fette Buch ausleihen.

der Standard

Jester

SirLant schrieb:

Ich würd dir zu push_back raten, du solltest wenn möglich immer die methoden wählen
die zu den meisten Containern komtapibel sind so kannst du ne liste mal eben schnell
ohne aufwand durch nen vector ersetzen.

Da hat der Meyers auch mal nen schönen Artikel drüber geschrieben:

Also, nur push_back verwenden und nie in der Mitte einfügen, außerdem keine Random-access-iteratoren benutzen, sonst fällt ja die list flach... wenn wir jetzt noch die Kompatibilität mit set oder map wahren wollen können wir leider garkeine Elemente mehr in unseren Container einfügen. Aber dafür ist er wunderbar austauschbar.

Moral: Vorher nachdenken, was man braucht und sich genaue Gedanken machen. Dann wählt man die passende Datenstruktur und benutzt deren Eigenschaften so vorteilhaft wie möglich. Alles andere ist bestenfalls ineffizient und ein Klotz am Bein.

MfG Jester

Shade Of Mine

Jester schrieb:

Da hat der Meyers auch mal nen schönen Artikel drüber geschrieben:

Seine IMHO beste Aussage dazu findet man in Effective STL:

Scott Meyers: Effective STL: Item 2 schrieb:

Face the truth: it's not worth it. The different containers are different and they have strengths and weaknesses that vary in significant ways

Deswegen sind die algorithmen der Standardlibrary ja auch nicht Containerunabhängig, sondern einfach nur 'Iteratorunabhängig' - wobei dies bei Forward-, Input-, RandomAccess-, ... Iteratoren auch relativ ist.

Jester

Genau das meint ich.

volkard

Optimizer schrieb:

EDIT: Gibts da irgendwo ne Übersicht, ich will mir nicht immer deswegen das fette Buch ausleihen.

übersicht über O(1) und O(n)? das ist blödsinn und unfug und so.
das kann sich doch keine sau alles merken. nee, geh anders vor und lerne noch was dabei:
lies den code!

schau dir einfach an, wie die container bei dir implementeirt sind und geh unverschämterweise davon aus, da0ß sie bei anderen ähnlih sind.
afair siehste dann ungefähr das:
_dllist: normale doppelt verkettete liste, einmal new pro push.
list: wraper um dllist.
deque: lauter 4k große segmente, wobei das erste und das letzte nicht ganz voll sein müssen und ein zeiger-array mit einem zeiger pro segment auf den segmentanfang. einmal new pro segment, also bei deque<int> nur alle 4096 pushs mal.
queue: warpper um deque
stack: warpper um deque
_tree: avl-baum mit lustigen aufwärtszeigern (sünde war nötig, um flache iteratoren zu haben)
set: wrapper um tree
multiset: wrapper um tree
map: wrapper umd tree

haste das, kannste nicht nur die komplexitäten aus dem kopf aufsagen, sondern kannst sogar abschätzen, wie viel speicheroverhead bei 10000 ints sein werden.
_dllist und wrapper: 32 bytes pro new dem ram entnommen, davon 4 bytes nutzdaten, also achtfaches wird benötigt, also 80000 ints dem ram entnommen.
_tree und warpper: dito.
dequeu und wrapper: 10000 ints und zwei halbvolle seiten mit je 500 ints verschnitt.

aber auch andere sachen. macht es sinn, nen vector<queue<int> > zu bauen? nein!. und nen <vector<list<int> >? na, klar!

fazit: lies den code!
und es dürfen dir noch sachen aufallen dabei. und tricks zum abgucken gibts da reichlich.

@die anderen: habt ihr echt die komplexitäten auswendig gelernt oder schließt ihr einfach aus dem modell, was ihr von den containern habt?

Shade Of Mine

volkard schrieb:

@die anderen: habt ihr echt die komplexitäten auswendig gelernt oder schließt ihr einfach aus dem modell, was ihr von den containern habt?

Ich denke einfach daran wie ich es implementieren würde - das trifft es dann oft. Natürlich nicht immer, da muss ich dann nachschauen (zB bei Containern die ich quasi nie verwende wie zB multiset).

Ich mag auswendiglernen nämlich nicht. IMHO bringt das weniger als verstehen. Und die Komplexität der Operationen istja logisch begründbar.

Bashar

Jo. Bei denen die ich implementiert hab oder halbwegs durchblicke kann ich mir die Komplexität selbst herleiten, Ausnahmen sind zB deque.

volkard

Shade Of Mine schrieb:

Natürlich nicht immer, da muss ich dann nachschauen (zB bei Containern die ich quasi nie verwende wie zB multiset).

jo, klar. speichert multiset wirklich jedes reingestopfte element oder nur einen repräsentanten der äquivalenzklasse nebst anzahl? und was will man eigentlich haben? fehlt da nicht in der sprache das fragenkönnen, ob zwei objekte, die == sind, auch austauschbar sind?

EDIT: Gibts da irgendwo ne Übersicht, ich will mir nicht immer deswegen das fette Buch ausleihen.

Ich schau hin und wieder mal hier hin :
http://cpp.programmersbase.net/
Doch steht zwar nicht wie schell ein Container dies und das können muss/sollte jedoch sehr genau was sie können und daraus kann man oft schiesen welches für welchen Zweck am schnellsten ist. Wie schell der schellste ist, ist dann glaub ich nicht so wichtig, da ich ja kaum glaub, dass du deinen eigenen möglicherweise schnelleren Container bastellst und es ohne Container ja wohl oft nicht geht.

queue: warpper um deque
stack: warpper um deque

Hab zwar schon viele Implentationen gesehen dies es nicht so machen aber laut oben geposteten Link sollte das so sein:

stack<Typ, Container = deque<Typ> > 
queue<Typ, Container = deque<Typ> >

Also wer es wirklich will kann auch aus einer list einen stack machen.

SideWinder

@volkard: Nein aber irgendwie ist es klar, dass man in einen Vektor am Ende konstant einfügen kann in der Mitte muss man verschieben, etc. Ist irgendwie meistens logisch welche Zeiten für was benötigt werden - und wenn sogar ich mir das im Kopf ausmalen kann

MfG SideWinder