[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=49561In einem der Kommentare steht noch:
Jonathan Wakely 2014-10-10 16:00:30 UTC
Fixed for 5.0Ergo schließe ich daraus, dass der Fehler erst ab GCC 5 behoben ist, wie Hustbaer bereits vermutet hatte.