Performance - verkettete Liste
-
Hallo alle,
bisher habe ich meine verketteten Listen immer selbst geschrieben und optimiert. Vor kurzem hab ich dann in Java die vorgefertigte linked list Klasse gesehen. Gibts sowas auch in C++?
Jetzt aber meine eigentliche Frage: wenn es diese Klasse gibt, wie ist ihre Performance, auch im Vergleich zu einem Vector? Hat da jemand von euch mal Tests gemacht? Wenn die Performance mies ist schreib ich lieber wieder meine eigene.
Gruß
Oberon
-
Schau dir mal die STL an.
Da gibts list<>, vector<>, map<> usw.Ob nun list oder vector besser ist,
hängt von deinem Anwendungsfall ab.Devil
-
"Besser" vom Handling her oder von der Performance?
-
Beides. In eine Liste kann man gut am Anfang, in der Mitte oder am Ende einfügen und löschen, dafür kann man einzelne Elemente nicht direkt ansprechen, sondern muss die Liste Element für Element durchlaufen. An einen Vektor kann man nur am Ende vernünftig einfügen und löschen (Anfang oder Mitte zieht immer Umkopieren großer Teile des Vektors nach sich), dafür aber jedes Element direkt adressieren. Die std::list bringt dazu noch eine Menge Overhead mit sich, so dass du bei kleinen Datenmengen vielleicht auch dann mit std::vector besser bedient bist, wenn rein theoretisch std::list vorzuziehen wär. Musst du mal nachmessen wenns wichtig ist.
-
Sowohl als auch.
Eine Liste bietet Dir einen Iterator um auf die Elemente zuzugreifen, ein Vector nen Indexzugriff. Aber eine Liste ist bei Änderungen der Größe schneller als ein Vector.
Du mußt hals gucken, was Du brauchst.
Hier findest Du eine kurze Übersicht:
http://www.cppreference.com/
-
daishi schrieb:
Eine Liste bietet Dir einen Iterator um auf die Elemente zuzugreifen, ein Vector nen Indexzugriff.
kleine Anmerkung: ein vector bietet auch Iteratoren an.
-
Ja, ich wollte aber nur Unterschiede zwischen beiden Typen nenen und nicht die Gemeinsamkeiten, die man bei jeder Beschreibung nachlesen kann.
-
Vielen Dank erstmal.
Die Funktionsweise einer Liste ist mir bekannt, mir ging es wirklich drum ob man die aus der STL auch ruhigen Gewissens benutzen kann, oder ob es ein No-No ist, so wie z.B. früher die BGL in Turbo Pascal.
Aber sieht so aus als würd ich es damit mal probieren.
Gruß
Oberon
-
Wenn man die Sachen der STL nicht nutzen sollte, wären sie nicht so weit verbreitet.
Die einzelnen Klassen sind auf Standartprobleme hin zugeschnitten und dafür auch bestens geeignet.