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

Question

Récemment, j'ai remarqué que certaines personnes mentionnaient que std :: list :: size () avait une complexité linéaire.
Selon certains sources , cela dépend en fait de la mise en oeuvre car le standard ne dit pas quelle doit être la complexité.
Le commentaire dans cette entrée de blog dit :

  

En fait, cela dépend de quel STL vous   utilisent. Microsoft Visual Studio V6   implémente size () as {return (_Size);   } alors que gcc (au moins dans les versions   3.3.2 et 4.1.0) le font comme {return std :: distance (begin (), end ()); } Le   le premier a une vitesse constante, le second   a la vitesse o (N)

1. Donc, je suppose que pour la foule VC ++, size () a une complexité constante en tant que Dinkumware n'aura probablement pas changé ce fait depuis VC6. Est-ce que je suis juste là?
   
2. À quoi ressemble-t-il actuellement dans gcc ? Si c’est vraiment O (n), pourquoi le les développeurs choisissent de le faire?

Answer 1

Réponse pré-C ++ 11

Vous avez raison de dire que la norme n'indique pas quelle doit être la complexité de list :: size (). Toutefois, il est recommandé de choisir une "complexité constante". (Remarque A dans le tableau 65).

Voici un article intéressant de Howard Hinnant qui explique pourquoi certaines personnes pensent à list :: size ( ) devrait avoir une complexité de O (N) (essentiellement parce qu'ils croient que O (1) list :: size () rend list :: splice () avoir une complexité de O (N)) et pourquoi une liste de O (1) :: size ( ) est une bonne idée (de l'avis de l'auteur):

• http://howardhinnant.github.io/On_list_size.html

Je pense que les points principaux du document sont les suivants:

• il existe peu de situations dans lesquelles le maintien d'un compte interne afin que list :: size () puisse être O (1) a pour effet de rendre linéaire l'opération d'épissure
• il y a probablement beaucoup d'autres situations dans lesquelles une personne ignore peut-être les effets négatifs qui pourraient en résulter, car elle appelle un O (N) size () (comme son exemple, où liste :: size () est appelé en gardant un verrou).
• qu'au lieu d'autoriser size () à être O (N), dans l'intérêt de la "surprise la moins bonne", le standard devrait exiger que tout conteneur implémentant size () pour le mettre en œuvre de manière O (1). Si un conteneur ne peut pas faire cela, il ne devrait pas implémenter size () . Dans ce cas, l'utilisateur du conteneur sera informé que size () n'est pas disponible, et s'il souhaite ou doit obtenir le nombre d'éléments du conteneur, il peut toujours utiliser . container :: distance (begin (), end ()) pour obtenir cette valeur, mais ils seront parfaitement conscients qu'il s'agit d'une opération O (N).

Je pense que j'ai tendance à être d'accord avec la plupart de ses raisonnements. Cependant, je n'aime pas son ajout proposé aux surcharges splice () . Devoir passer un n qui doit être égal à distance (premier, dernier) pour obtenir le comportement correct semble être une recette pour un diagnostic difficile à réparer.

Je ne suis pas sûr de ce qui devrait ou pourrait être fait pour aller de l'avant, car tout changement aurait un impact significatif sur le code existant. Mais dans l'état actuel des choses, je pense que le code existant est déjà affecté - le comportement peut être assez différent d'une implémentation à une autre pour une chose qui aurait dû être bien définie. Peut-être que le commentaire de onebyone à propos de la taille 'mise en cache' et marqué connue / inconnue pourrait bien fonctionner - vous obtenez un comportement O (1) amorti - le seul moment où vous obtenez un comportement O (N) est lorsque la liste est modifiée par certaines opérations splice () . La bonne chose à propos de cela est que cela peut être fait par les implémenteurs aujourd'hui sans modification de la norme (à moins que quelque chose ne me manque).

Autant que je sache, C ++ 0x ne change rien dans cette zone.

Answer 2

En C ++ 11, il est nécessaire que pour tout conteneur standard , l'opération .size () soit terminée dans le paramètre " constant " complexité (O (1)). (Tableau 96 & Exigences relatives aux conteneurs). Auparavant dans C ++ 03, .size () devrait avoir une complexité constante, mais n'est pas obligatoire (voir std :: string size () est-il une opération O (1)? ).

Le changement de norme est introduit par n2923 : Spécification de la complexité de size () (Révision 1) .

Cependant, l'implémentation de .size () dans libstdc ++ utilise toujours un algorithme O (N) dans gcc jusqu'à la 4.8:

  /**  Returns the number of elements in the %list.  */
  size_type
  size() const _GLIBCXX_NOEXCEPT
  { return std::distance(begin(), end()); }

Voir aussi Pourquoi std :: list est-il plus volumineux sur c ++ 11? pour plus de détails, pourquoi il est conservé de cette façon.

Mise à jour : std :: list :: size () est correctement O (1) lors de l'utilisation de gcc 5.0 en mode C ++ 11 (ou supérieur).

Au fait, le .size () dans libc ++ est correctement O (1):

_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& __sz() const _NOEXCEPT
    {return __size_alloc_.first();}

Answer 3

J'ai déjà eu à regarder dans la liste :: taille de gcc 3.4 :: taille, je peux donc dire ceci:

1. il utilise std :: distance (tête, queue)
2. std :: distance a deux implémentations: pour les types qui satisfont RandomAccessIterator, il utilise "tail-head", et pour les types qui satisfont tout simplement InputIterator, il utilise un algorithme O (n) reposant sur "iterator ++". ; en comptant jusqu’à atteindre la queue donnée.
3. std :: list ne spécifie pas RandomAccessIterator, la taille est donc O (n).

En ce qui concerne le "pourquoi", je peux seulement dire que std :: list est approprié pour les problèmes nécessitant un accès séquentiel. Stocker la taille en tant que variable de classe introduirait des frais généraux sur chaque insertion, suppression, etc., et ce gaspillage est un gros non-non selon l'intention du TSL. Si vous avez vraiment besoin d’une taille constante (), utilisez std :: deque.

Answer 4

Personnellement, je ne vois pas le problème avec l'épissure étant O (N) comme la seule raison pour laquelle la taille est autorisée à être O (N). Vous ne payez pas pour ce que vous n'utilisez pas est une devise importante pour C ++. Dans ce cas, le maintien de la taille de la liste nécessite une incrémentation / réduction supplémentaire à chaque insertion / effacement, que vous vérifiiez ou non la taille de la liste. Il s’agit là d’un petit surcoût fixe, mais qui reste important à prendre en compte.

Il est rarement nécessaire de vérifier la taille d'une liste. Itérer du début à la fin sans se soucier de la taille totale est infiniment plus commun.

Answer 5

Je voudrais aller à la source ( archive ). La page STL de SGI indique qu'il est permis d'avoir une complexité linéaire. Je pense que les directives de conception qu'ils ont suivies visaient à permettre à la mise en oeuvre de la liste d'être aussi générale que possible et donc à permettre plus de souplesse dans l'utilisation des listes.

Answer 6

Ce rapport de bogue: [C ++ 0x] std :: list: : complexité de la taille , décrit avec une extrême précision le fait que la mise en œuvre dans GCC 4.x est linéaire et que la transition vers le temps constant pour C ++ 11 a été lente (disponible dans la version 5.0) en raison de la compatibilité ABI préoccupations.

La page de manuel de la série GCC 4.9 inclut toujours la clause de non-responsabilité suivante:

  

La prise en charge de C ++ 11 est toujours   expérimental, et peut changer de manière incompatible avec les prochaines versions.

Le même rapport de bogue est référencé ici: std :: list :: size doit-il avoir une complexité constante en C ++ 11?

Answer 7

Si vous utilisez correctement les listes, vous ne remarquerez probablement aucune différence.

Les listes conviennent aux structures de données volumineuses que vous souhaitez réorganiser sans copier, aux données pour lesquelles vous souhaitez conserver des pointeurs valides après leur insertion.

Dans le premier cas, cela ne fait aucune différence, dans le second, je préférerais l'ancienne implémentation (plus petite) de size ().

Quoi qu’il en soit, std est plus axé sur la correction et le comportement standard et la convivialité que sur la vitesse brute.