was ist schneller std::list, oder eigene verkette Liste?
-
Der grösste Nachteil und die grösste Bremse von C++ Containern ist eben dass sie Container sind - also Kopien speichern. Bei vector tut das noch nicht SO weh, bei list schon mehr.
Falls deine eigene Liste auch Kopien speichern würde: vergiss es und nimm die STL. Falls du evtl. eine intrusive List basteln möchtest: ja, das hat einen Vorteil, man spart sich nämlich einen haufen new/delete. Und new/delete ist langsam.
Hängt also alles vom Anwendungsfall ab.
-
hustbaer schrieb:
Der grösste Nachteil und die grösste Bremse von C++ Containern ist eben dass sie Container sind - also Kopien speichern. Bei vector tut das noch nicht SO weh, bei list schon mehr.
Das kommt wohl auch drauf an was du speicherst, nicht?
-
wiso, das sind doch alles template Container, das heißt, man kann genauso gut auch pointer reinsmeißen oder sonstwas, wenn das die sache so beschleunigen sollte.
-
hustbaer schrieb:
Der grösste Nachteil und die grösste Bremse von C++ Containern ist eben dass sie Container sind - also Kopien speichern. Bei vector tut das noch nicht SO weh, bei list schon mehr.
Falls deine eigene Liste auch Kopien speichern würde: vergiss es und nimm die STL. Falls du evtl. eine intrusive List basteln möchtest: ja, das hat einen Vorteil, man spart sich nämlich einen haufen new/delete. Und new/delete ist langsam.
Hängt also alles vom Anwendungsfall ab.
Warum tut das bei vector weniger weh, als bei list? Das ist eher andersrum. Wenn ich an einen vector ein Element anhänge, dann muß unter umständen der gesamte Vektor umkopiert werden. Das tut weh. Bei list passiert das nicht.
Ansonsten kann ich Krux unterstützen. Wenn Du eine std::list mit Objekten mit einer eigenen Liste mit Zeigern vergleichst, vergleichst Du Äpfel mit Birnen.
-
Aber bei vector kann im optimalen Fall ein Customchip bzw. ein bestimmter CPU-Befehl einen ganzen Speicherblock von A nach B kopieren, ohne das es bedeutend Rechenzeit kostet.
Bei einer verketteten Liste, woe die Elemente nicht sequenziell liegen sondern verteilt, wird das kopieren schwieriger aber auch nicht nötig (ist halt bei list so). Ist meiner Meinung nach heute nicht so relevant.
-
Artchi schrieb:
Aber bei vector kann im optimalen Fall ein Customchip bzw. ein bestimmter CPU-Befehl einen ganzen Speicherblock von A nach B kopieren, ohne das es bedeutend Rechenzeit kostet.
Das gilt aber nur für triviale Objekte ohne speziellen Kopierkonstruktor.
-
OMG es versteht wieder keiner was ich meine.
Ein Container speicher *immer* Kopien. Wenn man natürlich eine list<blah*> macht speichert diese Kopien von Zeigern, das ist doch logisch.Es ändert aber nichts daran dass für diese Kopien dynamisch Speicher angefordert wird, und bei einer list<T> eben für jedes Element welches man reinsteckt einzeln.
Genau deswegen tut das bei vector<T> weniger weh, weil da nicht für jedes Element einzeln Speicher angefordert wird, sondern immer gleich für etliche Elemente am Stück - je grösser der vector vor dem insert/push_back war desto mehr.
Das eigentliche Kopieren eines Elements dauert verglichen mit dem new/delete Aufruf meist nicht lange - vorausgesetzt die Elemente sind nicht extrem riesig und haben keinen Kopierkonstruktor der diverse "teure" Funktionen aufruft.
-
hustbaer schrieb:
Es ändert aber nichts daran dass für diese Kopien dynamisch Speicher angefordert wird, und bei einer list<T> eben für jedes Element welches man reinsteckt einzeln.
Genau deswegen tut das bei vector<T> weniger weh, weil da nicht für jedes Element einzeln Speicher angefordert wird, sondern immer gleich für etliche Elemente am Stück - je grösser der vector vor dem insert/push_back war desto mehr.
das ist aber kein problem von std::list, da sie den speicher über den per template übergebenen allocator anfordert. Theoretisch kann dieser den Speicher im Block anfordern und dann häppchenweise an die List übergeben, nur tut das der standard allocator nicht. Man kann sich aber einen eigenen allocator schreiben oder die von boost nutzen, dann gibt es das von dir angesprochene problem nicht.
Übrigens musst du dich nicht wundern dass du missverstanden wirst, da du von anfang an von kopien sprichst
-
Ich wollte bloss sagen dass es keinen Sinn macht eine eigene List Klasse zu programmieren wenn die eigene Klasse keine "intrusive list" ist.
Was der Einwand mit dem Allocator soll weiss ich nicht, denn einen eigenen Allocator zu schreiben ist wohl in den seltensten Fällen angebracht, und die Boost.Pool Varianten sind zwar schneller aber immer noch langsamer als wenn garkeine Allokationen benötigt werden.
Was an meinem ersten Posting so schwer zu verstehen war weiss ich auch nicht, steht eigentlich alles da. Aber egal.
-
du sagtest:
Falls deine eigene Liste auch Kopien speichern würde: vergiss es und nimm die STL. Falls du evtl. eine intrusive List basteln möchtest: ja, das hat einen Vorteil, man spart sich nämlich einen haufen new/delete. Und new/delete ist langsam.
...
Es ändert aber nichts daran dass für diese Kopien dynamisch Speicher angefordert wird, und bei einer list<T> eben für jedes Element welches man reinsteckt einzeln.und ich sagte daraufhin: Nein, es ist nicht zwingend so.
Und zwar, weil durch alleiniges ändern des allocators aus einer list eine intrusive list werden kann(bzw etwas was die selben eigenschaften einer intrusive list hat)
