Kürzlich habe ich einige Leute bemerkt, die das erwähnenstd::list::size() hat eine lineare Komplexität.
Gemäßetwas QuellenDies ist in der Tat von der Implementierung abhängig, da der Standard nicht sagt, wie komplex er sein muss.
Der Kommentarin diesem Blogeintrag sagt:

Tatsächlich hängt es davon ab, welche STL Sie verwenden. Microsoft Visual Studio V6 implementiert size () als {return (_Size); } in der Erwägung, dass gcc (zumindest in den Versionen 3.3.2 und 4.1.0) dies als {return std :: distance (begin (), end ()) ausführt; } Die erste hat eine konstante Geschwindigkeit, die zweite hat eine Geschwindigkeit von 0 (N)

Ich denke, das ist für die VC ++ - Mengesize() hat eine konstante Komplexität, da Dinkumware diese Tatsache seit VC6 wahrscheinlich nicht mehr geändert hat. Bin ich da richtig
Wie sieht es aktuell in aus?gcc? Wenn es wirklich O (n) ist, warum haben sich die Entwickler dafür entschieden?