Est-ce que std::list::size() est vraiment O(1) dans toutes les implémentations ?

std::list::size() : Truly O(n)?

Malgré certaines personnes affirmant que std : :list::size() possède une complexité linéaire, la vérité concernant sa complexité dépend de l'implémentation. La norme C ne spécifie pas d'exigences de complexité pour cette fonction.

Variations d'implémentation

• Microsoft Visual Studio VC : Dans les anciennes versions (comme VC6), size() avait en effet une complexité constante car il renvoyait simplement la taille stockée dans sa structure de données interne.
• GNU Compiler Collection (GCC) : Historiquement (jusqu'à GCC 4.1.0), size() utilisait une approche O(n) en parcourant la liste pour compter le nombre d'éléments.

État actuel dans GCC

En C 11, la norme C exige que l'opération size() pour tous les conteneurs standard, y compris std::list , doit avoir une complexité constante (O(1)). Il s'agit de garantir un comportement d'exécution cohérent et efficace sur toutes les plates-formes et implémentations.

Implémentation dans Libstdc

Malgré le mandat C 11, la mise en œuvre de size() dans libstdc (la bibliothèque standard utilisée par GCC) est resté O(n) dans les versions de GCC jusqu'à 4.8. Cela a été fait pour des raisons de performances et pour minimiser la surcharge liée à la maintenance d'un champ de taille supplémentaire dans la structure de la liste.

Mise à jour : O(1) Implémentation dans GCC 5.0

Avec la sortie de GCC 5.0, l'implémentation de size() pour std::list a finalement été optimisée pour atteindre la complexité O(1) en mode C 11. Ceci a été réalisé en introduisant un champ de taille interne qui suit le nombre d'éléments dans la liste, fournissant un accès en temps constant aux informations de taille.

Conclusion

Alors que le la complexité de std::list::size() était un sujet de débat dans le passé, la norme C actuelle nécessite une complexité O(1) pour tous les conteneurs standard. L'implémentation dans GCC 5.0 et versions ultérieures adhère à cette exigence, garantissant une exécution efficace et prévisible de size() pour std::list.

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!