[Solved] C++11 std::list::size() Komplexität



  • Hi zusammen

    ich meine im c++11 Standard mal gelesen zu haben, dass die size()-Funktion aller Container eine Complexity von O(1) haben sollte.

    Nun hab ich das mit meinem MINGW-Compiler ( TDM-GCC 4.9 32bit ) mal nachvollzogen und stelle eher eine O(N) fest... Das gleiche übrigens auch beim Linux-GCC ( 4.9.1 )

    Kann das jemand bestätigen?



  • Welcher Container konkret? Und vor allem: wie hast du gemessen?



  • Es kommt bei std::list auf die C++ Version an (siehe std::list::size).

    Vor C++11: O(1) oder O(n)
    C++11 (und spaeter): O(1)



  • It0101 schrieb:

    Kann das jemand bestätigen?

    Ja, kann ich. GCC ohne extra Switches macht C++98, und in der C++98 STL Implementierung von älteren GCC Versionen war list::size O(N).

    Wie es bei neueren GCC Versionen (5+) aussieht weiss ich nicht sicher - wenn mich meine Erinnerung nicht trügt sollte aber auch die C++98 Variante bei aktuellen GCCs O(1) for list::size haben.



  • icarus2 schrieb:

    Es kommt bei std::list auf die C++ Version an (siehe std::list::size).

    Vor C++11: O(1) oder O(n)
    C++11 (und spaeter): O(1)

    Also mein C++11 Flag war schon gesetzt, beim Build 😉

    Also dieses hier:

    -std=c++11
    

    Das hat aber offensichtlich nichts besser gemacht.

    Hier als Bugreport:
    https://gcc.gnu.org/bugzilla/show_bug.cgi?id=49561

    In einem der Kommentare steht noch:

    Jonathan Wakely 2014-10-10 16:00:30 UTC
    Fixed for 5.0

    Ergo schließe ich daraus, dass der Fehler erst ab GCC 5 behoben ist, wie Hustbaer bereits vermutet hatte.


Log in to reply