Est-ce que std::list::size() est vraiment O(1) en C ?

Est-ce que std::list::size() est vraiment O(n) ?

Des inquiétudes ont été soulevées concernant la complexité temporelle de std ::list::size() en C . Certains suggèrent que cela pourrait dépendre de l'implémentation, bien que la norme ne précise pas sa complexité.

Comportement spécifique à l'implémentation

Dans les versions antérieures de C , la complexité de std : :list::size() variait en fonction de l'implémentation STL utilisée. Microsoft Visual Studio V6 l'a implémenté avec une complexité constante, tandis que GCC jusqu'à 4.1.0 utilisait une approche basée sur la distance, ce qui entraînait une complexité O(n).

Standardisation et complexité

En C 11, un changement a été introduit par n2923, exigeant que toutes les opérations standard de conteneur .size() aient une complexité temporelle constante (O(1)). Il s'agit désormais d'une exigence explicite, garantissant des performances cohérentes dans toutes les implémentations.

Implémentation de GCC

Cependant, malgré la standardisation, la mise en œuvre de std::list::size( ) dans GCC jusqu'à la version 4.8 continue d'utiliser un algorithme O(n). Ceci est expliqué en détail dans l'entrée de blog liée à la question d'origine.

Mise à jour dans GCC 5.0

Il est important de noter que ce problème est résolu dans GCC 5.0 et plus tard. En mode C 11, std::list::size() est correctement implémenté avec une complexité O(1) dans GCC 5.0 et supérieur.

Implémentation de la libc

Dans Contrairement à l'approche de GCC, l'implémentation de std::list::size() par la libc a été systématiquement optimisée pour la complexité O(1) depuis sa création.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!