[beantwortet] STL list size



  • Hallo ihr Lieben,

    mal wieder eine naive Frage:

    Ich bin gerade verwundert, dass der STL Container list bei dem Aufruf von size() nach dem neuen C++11 Standard eine konstante Komplexität hat.

    Wenn ich das bisher richtig verstanden habe, dann hat list seine Größer immer dadurch bestimmt, dass es bei Aufruf von size() seine Elemente gezählt hat.

    Das wurde scheinbar geändert? Wird jetzt immer ein Integer mitgeführt, der bei einfügen oder entfernen mitzählt? Sodass bei der Abfrage der Größe lediglich der Wert dieses integers ausgegeben wird?

    Gruß,
    -- Klaus.



  • Wenn ich das bisher richtig verstanden habe, dann hat list seine Größer immer dadurch bestimmt, dass es bei Aufruf von size() seine Elemente gezählt hat.

    Nein, auch in pre-C++11 haben die meisten Implementierungen von list::size() eine konstante Laufzeitkomplexitaet gehabt. Aber du kannst gern in die verschieden Templatebibliotheken der einzelnen Kompiler hineinschauen.



  • Nein, auch in pre-C++11 haben die meisten Implementierungen von list::size() eine konstante Laufzeitkomplexitaet gehabt.[/quote]

    Aha, okay.

    Weil hier eben unter Complexity bei C++98 Up to linear steht.

    Gruß,
    -- Klaus.



  • Ja, hier wird es etwas differenzierter dargestellt: http://www.sgi.com/tech/stl/List.html

    size_type size() const: Returns the size of the list. Note: you should not assume that this function is constant time. It is permitted to be O(N), where N is the number of elements in the list. If you wish to test whether a list is empty, you should write L.empty() rather than L.size() == 0.

    D.h. frueher sollte man nicht davon ausgehen, heite kann man davon ausgehen. Up to linear schliesst auch constant mit ein.



  • 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


  • Mod

    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


Log in to reply