Est-ce que `std::list::size()` est toujours O(1) ?

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

Alors qu'il était autrefois vrai que std::list::size () présentait une complexité variable selon les implémentations, C 11 a standardisé son comportement. Le tableau 96 des exigences relatives aux conteneurs impose une complexité constante (O(1)) pour les opérations .size() sur tous les conteneurs standard.

Cependant, une exception notable reste l'implémentation de libstdc de gcc avant la version 5.0. Malgré l'exigence de la norme C 11, sa fonction .size() utilise un algorithme O(N), comme le montre l'extrait suivant :

size_type
size() const _GLIBCXX_NOEXCEPT
{ return std::distance(begin(), end()); }

Cette décision découle de considérations d'optimisation au sein de libstdc . Maintenir un nombre séparé d'éléments plutôt que de parcourir la liste améliore les performances dans certains cas d'utilisation, bien que cela contredise l'exigence de complexité standard.

L'implémentation de Libc, en revanche, adhère correctement à l'O(1) complexité, comme illustré par l'extrait de code suivant :

_LIBCPP_INLINE_VISIBILITY
size_type size() const _NOEXCEPT     {return base::__sz();}

...

__compressed_pair<size_type, __node_allocator> __size_alloc_;

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

En conclusion, alors que la norme C 11 impose une complexité O(1) pour std::list::size(), l'implémentation de libstdc de gcc avant la version 5.0 reste une anomalie, utilisant à la place un algorithme O(N).

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!