Std::list::size() est-il vraiment O(n) dans les implémentations modernes ?

Récemment, certains développeurs ont suggéré que std::list::size() a une complexité temporelle linéaire (O(n)). Cependant, selon le standard C, la complexité n'est pas définie et peut varier en fonction de l'implémentation.

Dans les versions antérieures du standard C (C 03), il était recommandé que l'opération size() ait une complexité constante. (O(1)). Cependant, avec l’introduction du C 11, celui-ci est devenu une exigence pour tous les conteneurs standards. Le tableau 96 de la norme C 11 indique explicitement que .size() doit avoir une complexité constante pour tous les conteneurs.

Historiquement, la bibliothèque libstdc de GCC a implémenté size() avec une complexité O(n) en utilisant std::distance(begin (), end()), comme décrit dans l'entrée de blog que vous avez citée. Cependant, en mode C 11, ce comportement a changé :

size_type
size() const _GLIBCXX_NOEXCEPT
{ return __size_alloc_.first(); }

_LIBCPP_INLINE_VISIBILITY
const size_type& __sz() const _NOEXCEPT
    {return __size_alloc_.first();}

Dans GCC 5.0 et versions ultérieures, la fonction size() utilise une structure de données interne pour suivre le nombre d'éléments, rendant ainsi l'opération O(1). Cela correspond à l'exigence C 11 pour tous les conteneurs standards.

Il est important de noter que certains cas d'utilisation de niche peuvent encore conduire à une complexité O(n) pour size(), mais pour la grande majorité des utilisateurs, le l'opération doit être à temps constant.