[beantwortet] STL list size
-
Okay, okay.
Ich gebe mich geschlagen.
Viele Grüße,
-- Klaus.
-
Mir wurde das früher mal so erklärt, dass manche std:list Implementationen ein O(1) std::list::splice() hätten, was etwas ganz tolles wäre aber nicht gleichzeitig mit einem O(1) std::list::size() ginge. Was da jetzt zum Paradigmenwechsel geführt hat würde ich gerne wissen.
-
Ganz einfach, da haben sich Leute durchgesetzt, die in ihrem Leben noch nie wirklich eine Liste gebraucht haben und haben deshalb die falsche Entscheidung getroffen. Zum Glück gibts boost::intrusive
-
Hier ist die Abstimmung:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2009/n2921.html
Der Punkt über N2923.
-
Jester schrieb:
Ganz einfach, da haben sich Leute durchgesetzt, die in ihrem Leben noch nie wirklich eine Liste gebraucht haben und haben deshalb die falsche Entscheidung getroffen. Zum Glück gibts boost::intrusive
Die hatten sich ja schon lange vorher durchgesetzt, als sie die Liste mit einem O(1) size implementiert haben...
-
Ich verstehe den Sinn von size() mit O(1) irgendwie nicht so recht. In den seltenen Fällen in denen ich eine Liste eingesetzt habe, habe ich noch nie size() benötigt. Und auch beim allgemeinen Umgang mit einer Liste fällt mir außer debugging kein sinnvoller Use-Case für size() ein. Wieso also die Änderung?
-
Ich verstehe den Sinn von size() mit O(1) irgendwie nicht so recht. In den seltenen Fällen in denen ich eine Liste eingesetzt habe, habe ich noch nie size() benötigt. Und auch beim allgemeinen Umgang mit einer Liste fällt mir außer debugging kein sinnvoller Use-Case für size() ein. Wieso also die Änderung?
-
Hier wir ja eine Begründung geliefert, wobei ich sie auch nicht so ganz überzeugend finde: http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2009/n2923.pdf
-
Die Situation ist jetzt sicher besser als zuvor, schliesslich konnte man sich zuvor auf keine der beiden Varianten verlassen.
Besser wäre imo aber gewesen, gleichzeitig einen zweiten Listentyp in den Standard einzufügen, der eben konstantes splice anbietet.
-
camper schrieb:
Die Situation ist jetzt sicher besser als zuvor, schliesslich konnte man sich zuvor auf keine der beiden Varianten verlassen.
Besser wäre imo aber gewesen, gleichzeitig einen zweiten Listentyp in den Standard einzufügen, der eben konstantes splice anbietet.Ich weiß nicht ob das nur dafür gerechtfertigt wäre einen eigenen Listentyp einzuführen. Ich denke, wenn man solch starke Anforderung an die Performance in speziellen Fällen hat, versucht man eh am besten eine stl Implementation zu finden, die da am besten passt, ähnlich wie es welche gibt die eher auf Codegröße optimiert sind, während andere eher auf Geschwindigkeit optimiert sind. Früher hatten die Bibliothekshersteller in dem Punkt mit Splice noch die Wahl.
Ich finde dabei das O(1) splice eigentlich sehr sinnvol:.Es gibt wenig gute Gründe ausgerechnet eine std::list als container zu wählen. Einer ist, wenn man so etwas wie ein effizientes Splice wirklich braucht. Dann sollte es aber auch wirklich effizient sein.
-
TNA schrieb:
Ich finde dabei das O(1) splice eigentlich sehr sinnvol:.Es gibt wenig gute Gründe ausgerechnet eine std::list als container zu wählen. Einer ist, wenn man so etwas wie ein effizientes Splice wirklich braucht. Dann sollte es aber auch wirklich effizient sein.
Die offiziellen Gründe entkräftet:
- size() is heavily used -- von wem denn und wozu?
- average programmer expect it to be constant -- ah, vom Durchschnittsprogger. Der erwartet aber auch, dass list effizienter als vector ist, wenn kein random access gebraucht wird. Was ein average programmer (was auch immer das heissen soll) erwartet (es ist ja nicht so, dass der das nicht lernen kann), kann mir vollkommen egal sein.
- splicing is most important when the contained element types are expensive or impossible to copy -- Das Problem wird durch vector<unique_ptr<Objekt>> gelöst. Splicing ist genau dann wichtig, wenn ich ein schnelles splice will!!!11
- traversing a range is O(n) but very fast -- blarg? vector<unique_ptr> ist dann sogar "very very fast".Gegenargumente:
- vector, deque und vector<unique_ptr<>> decken fast alle Use-Cases ab, bei denen List ohne splice verwendet wird.
- Wer ein konstantes size() will, kann das mit einer normalen list ganz leicht mitcachen.
- Wer ein konstantes splice() will, kann das nicht mit einer C++11-list machen.Mir kommt die ganze Aktion sehr unprofessionell vor. forward_list ist nicht immer eine Alternative. std::list ist so absolut nutzlos und ohne Existenzgrundlage, ich wüsste wichtigere Kleinigkeiten für die Standardbibliothek.
Bleibt einem Selbstbau oder Boost.Intrusive.
-
Ganz einfach: Listen implementieren macht soooo viel Spaß und endlich hat man dafür ne Ausrede.
"Hey du! Warum implementierst du die Liste selbst und nimmst nicht std::list ?" - "Öhhh ... öhhh ... weil ich vielleicht mal ein O(1) splice brauche!" - "Gut, weitermachen!" :p