Ich habe diese Datei (C: \ cygwin \ lib \ gcc \ i686-pc-cygwin \ 3.4.4 \ include \ c ++ \ bitset) auf meinem Computer gelesen.
Siehe diese
BTW, hier ist _Nw angegeben:
%Vor%Also ist es O (n) in der gcc-Implementierung. Wir schließen daraus, dass die Spezifikation es nicht besser als O (n) erfordert. Und niemand, der in seiner rechten Meinung ist, wird es schlimmer umsetzen. Wir können dann sicher annehmen, dass es im schlimmsten Fall O (n) ist. Vielleicht besser, aber darauf können Sie sich nie verlassen.
Ich kann nicht sicher sein, was Sie wirklich mit "STL" hier meinen, aufgrund eines vorherrschenden Missbrauchs des Begriffs in der C ++ - Community.
Der C ++ Standard (2003) macht kein Mandat für die Leistung von std::bitset::count() (oder, soweit ich das sehen kann, Mitglieder von std::bitset ).
Ich kann keinen Hinweis finden, der ein Mandat für die Leistung von STLs bitset::count() vorschlägt.
Ich denke, jede vernünftige Implementierung wird dies in konstanter (oder im schlimmsten Fall linearer) Zeit bereitstellen. Dies ist jedoch nur ein Gefühl. Überprüfen Sie Ihre, um herauszufinden, was Sie tatsächlich bekommen.
"Die Referenzimplementierung von SGI läuft in linearer Zeit in Bezug auf die Anzahl der Bytes zum Speichern der Bits. Es tut dies, indem Sie ein erstellen Statisches Array von 256 ganzen Zahlen. Das Wert gespeichert bei i-ten Index im Array ist die Anzahl der Bits, die im Wert festgelegt sind ich. "
Ich bin nicht sicher, ob Sie eine Spezifikation dafür finden werden, da die STL normalerweise kein bestimmtes Leistungsniveau erfordert. Ich habe Hinweise gesehen, dass es "schnell" ist, etwa 1 Zyklus pro Bit in der Größe des Sets. Sie können natürlich den Code Ihrer speziellen Implementierung lesen, um herauszufinden, was Sie erwarten können.
Tags und Links c++ stl performance bitset