Ist std::list::size() wirklich O(1) in C?

Ist std::list::size() wirklich O(n)?

Es wurden Bedenken hinsichtlich der zeitlichen Komplexität von std geäußert ::list::size() in C . Einige vermuten, dass es möglicherweise von der Implementierung abhängt, obwohl der Standard seine Komplexität nicht spezifiziert.

Implementierungsspezifisches Verhalten

In früheren Versionen von C war die Komplexität von std: :list::size() variierte je nach verwendeter STL-Implementierung. Microsoft Visual Studio V6 implementierte es mit konstanter Komplexität, während GCC bis 4.1.0 einen distanzbasierten Ansatz verwendete, was zu O(n)-Komplexität führte.

Standardisierung und Komplexität

In C 11 wurde durch n2923 eine Änderung eingeführt, die erfordert, dass alle Standard-Container-.size()-Operationen eine konstante Zeitkomplexität (O(1)) haben müssen. Dies ist jetzt eine explizite Anforderung, die eine konsistente Leistung über alle Implementierungen hinweg gewährleistet.

GCC-Implementierung

Trotz der Standardisierung ist die Implementierung von std::list::size( ) in GCC bis Version 4.8 verwendet weiterhin einen O(n)-Algorithmus. Dies wird im Blogeintrag, der in der ursprünglichen Frage verlinkt ist, ausführlich erläutert.

Update in GCC 5.0

Es ist wichtig zu beachten, dass dieses Problem in GCC 5.0 behoben ist später. Im C 11-Modus wird std::list::size() ordnungsgemäß mit O(1)-Komplexität in GCC 5.0 und höher implementiert.

libc-Implementierung

In Im Gegensatz zum GCC-Ansatz wurde die Implementierung von std::list::size() durch libc seit ihrer Einführung konsequent für die O(1)-Komplexität optimiert.

Das obige ist der detaillierte Inhalt vonIst std::list::size() wirklich O(1) in C?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!