Est liste::size() vraiment O(n)?

Question

Récemment, j'ai remarqué que certaines personnes de mentionner que std::list::size() a une complexité linéaire.
Selon certaines sources, c'est en fait dépendant de l'implémentation que le standard ne veut pas dire que la complexité de l'être.
Le commentaire de cette entrée de blog dit:

En fait, cela dépend de la STL vous sont utilisant. Microsoft Visual Studio V6 met en œuvre la taille que () {return (_Size); } alors que gcc (au moins dans les versions 3.3.2 et 4.1.0) faire comme { return std::distance(begin(), end()); } La la première a vitesse constante, la deuxième a o(N) vitesse de

1. Si ma conjecture est que pour le VC++ foule size() a constante de la complexité comme Dinkumware ce ne sera probablement pas changé depuis VC6. Suis-je là?
   
2. A quoi elle ressemble actuellement en gcc? Si elle est vraiment en O(n), pourquoi le les développeurs choisissent de le faire?

Answer 1

En C++11, il est exigé que pour les tout conteneur standard de l' .size() opération doit être achevée en "constante" de la complexité (O(1)). (Tableau 96 - les conditions du Conteneur). Déjà en C++03 .size() devrait avoir de la constante de la complexité, mais n'est pas obligatoire (voir Est std::string taille() O(1) opération?).

Le changement de norme est introduit par n2923: la définition de la complexité de la taille() (Révision 1).

Cependant, la mise en œuvre de l' .size() dans libstdc++ utilise toujours un algorithme O(N) dans gcc jusqu'à 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 en plus sur le c++11? pour plus de détail pourquoi il est resté de cette façon.

---

Par ailleurs, l' .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 2

Il est exact que la norme ne fait pas état de ce que la complexité de la liste::size() doit être - toutefois, il ne recommander qu'il "aurait constante de la complexité" (à Noter qu'Un Tableau 65).

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

• http://home.roadrunner.com/~hinnant/On_list_size.html

Je pense que les points principaux dans le document sont les suivants:

• il y a peu de situations où le maintien d'un compte interne de sorte list::size() peut être: O(1) des causes de la jonction, une fonction linéaire
• il y a probablement beaucoup plus de situations où une personne pourrait ne pas être conscients des effets négatifs qui pourraient survenir en raison de qu'ils appellent un O(N) size() (comme le son d'un exemple où l' list::size() est appelée lors de la tenue d'une serrure).
• qu'au lieu de permettre à size() O(N), dans l'intérêt de la "moindre surprise", la norme devrait exiger de tout récipient qui implémente size() pour la mettre en œuvre dans un O(1) de la mode. Si un conteneur ne peut pas faire cela, il ne faut pas mettre en oeuvre size() à tous. Dans ce cas, l'utilisateur du conteneur sera mis au courant qu' size() n'est pas disponible, et s'ils veulent ou ont besoin pour obtenir le nombre d'éléments dans le conteneur ils peuvent toujours utiliser container::distance( begin(), end()) pour obtenir cette valeur, mais ils doivent être pleinement conscients du fait que c'est un O(N) opérations.

Je pense que j'ai tendance à être d'accord avec la plupart de son raisonnement. Cependant, je n'aime pas sa proposition d'ajout à l' splice() des surcharges. Avoir à passer une n qui doit être égale à distance( first, last) pour obtenir le comportement correct semble être une recette pour les difficile à diagnostiquer des bugs.

Je ne suis pas sûr de ce que devrait ou pourrait être fait aller de l'avant, comme tout changement aurait un impact significatif sur le code existant. Mais en l'état actuel, je pense que le code existant est déjà des répercussions sur le comportement peuvent être sensiblement différentes d'une application à une autre pour quelque chose qu'il aurait été bien définie. Peut-être onebyone du commentaire à propos de la taille mise en cache " et marqué connu/inconnu pourrait bien fonctionner - vous obtenir amorti O(1) le comportement - la seule fois que vous obtenez O(N) le comportement est quand la liste est modifiée par certains splice() opérations. La bonne chose à ce sujet est qu'il peut être fait par des réalisateurs d'aujourd'hui, sans un changement de la norme (à moins que je suis absent quelque chose).

Pour autant que je sais, C++0x n'est pas de changer quoi que ce soit dans ce domaine.

Answer 3

J'ai eu à le regarder dans gcc 3.4 la liste::la taille de l'avant, de sorte que je peux dire ceci:

1. il utilise des std::distance(tête, queue)
2. std::distance a deux implémentations: pour les types qui répondent à RandomAccessIterator, il utilise des "queue-tête", et pour les types qui ne fait que satisfaire InputIterator, il utilise un algorithme O(n) en s'appuyant sur "itérateur++", le comptage jusqu'à ce qu'il touche la queue.
3. std::list n'est pas satsify RandomAccessIterator, de sorte que la taille est O(n).

Quant au "pourquoi", je peux seulement dire que std::list est approprié pour des problèmes qui nécessitent un accès séquentiel. Le stockage de la taille d'une variable de classe permettrait d'introduire de surcharge sur chaque insert, delete, etc., et que les déchets sont un gros no-no par l'intention de la STL. Si vous avez vraiment besoin d'une constante de temps de la taille(), utiliser std::deque.

Answer 4

Personnellement, je ne vois pas le problème avec épissure être O(N) que la seule raison pourquoi la taille est autorisée à O(N). Vous ne payez pas pour ce que vous n'utilisez pas un important C++ devise. Dans ce cas, le maintien de la taille de la liste nécessite une incrémenter/décrémenter à chaque insérer/effacer si vous consultez la liste de taille ou pas. C'est un petit frais fixes, mais il est toujours important de considérer.

Vérification de la taille d'une liste, il est rarement nécessaire. L'itération de commencer à la fin, sans prendre soin de la taille totale est infiniment plus commun.

Answer 5

Je voudrais aller à la source. SGI STL page dit qu'il est autorisé à avoir une complexité linéaire. Je crois que les lignes directrices de conception qu'ils ont suivi était de permettre la liste de mise en œuvre pour être le plus général possible, et donc de permettre plus de souplesse dans l'utilisation des listes.