Std :: string size () est-il une opération O (1)?

StackOverflow https://stackoverflow.com/questions/256033

  •  05-07-2019
  •  | 
  •  

Question

Est-ce que std :: string size () est une opération O (1)?

L’implémentation de STL que j’utilise est celle intégrée à VC ++

Était-ce utile?

La solution

Si vous demandez si l'implémentation de string :: size () par MSVC a une complexité constante, alors la réponse est oui. Mais Don Wakefield a mentionné le tableau 65 en 23.1 de la norme C ++, dans lequel dit que la complexité de size () devrait suivre ce qui est dit dans 'Note A'. Remarque A dit:

  

Les entrées marquées '' (Note A) ''   devrait avoir une complexité constante.

Toutefois, cela ne signifie pas que ces entrées doivent avoir une complexité constante. Les normes utilisent une terminologie très spécifique et "devraient". signifie que ce n'est pas obligatoire.

'Remarque A' a été ajouté à la norme spécifiquement pour apaiser ceux qui pensaient que size () devrait être autorisé à présenter une complexité linéaire. Il n'était donc pas nécessaire de conserver la taille lorsque les conteneurs étaient utilisés. modifié.

Donc, vous ne pouvez pas compter sur size () pour une complexité constante, mais honnêtement, je ne suis pas sûr s'il existe des implémentations qui n'ont pas une constante string :: size ( ) .

Autres conseils

Voici un moyen facile de répondre à cette question pour msvc ++.

Écrire du code dans un projet: 

string happy;
happy.size();

Hilight l'appel .size, clic droit, aller à la définition.

Sur mon installation (vs2005sp1), cela m'envoie à xstring: 1635, qui ressemble à ceci: 

size_type __CLR_OR_THIS_CALL size() const
    {   // return length of sequence
    return (_Mysize);
    }

On dirait donc que la chaîne a un membre appelé _Mysize, et ne fait que le retourner.

En d'autres termes, il s'agit d'une implémentation O (1).

Oui, std :: string :: size () est O (1).

Voir le tableau 65 à la section 23.1 de la norme. "a.size ()" est répertorié sous la forme "(Note A)", qui indique que "Ces entrées ... doivent avoir une complexité constante".

La section 21.3 indique que les chaînes sont conformes aux exigences d’une séquence (23.1), ipso facto, size () est une heure constante.

Pour une chaîne, l'opération size () doit être constante pour toutes les implémentations de chaîne qui n'utilisent pas des cordes (1) . La norme ne spécifie pas explicitement que l'opération doit être O (1) , l'exigence la plus proche étant l'exigence générique selon laquelle size () devrait être à temps constant, mais cela laisse place à toute autre mesure de complexité.

Alors pourquoi doit-il que ce soit O (1)?

Cela vient du fait que la taille ne peut pas être calculée à partir du contenu de la chaîne elle-même. En C, vous utilisez un terminateur NUL pour déterminer la fin de la chaîne. En C ++, NUL est aussi valide que tout autre caractère de la chaîne. La taille de la chaîne ne pouvant être calculée à partir du contenu (2) , elle doit être gérée en externe, quelle que soit la taille réelle de la chaîne.

(1) La norme C ++ 03 permet à une implémentation d'utiliser des cordes comme implémentation de chaînes, mais le fait est qu'aucune des implémentations actuelles de la norme les bibliothèques les utilisent.

(2) Si l'implémentation utilisait des câbles, l'opération pourrait dépendre de la taille en fonction du nombre de blocs à partir desquels le câble a été construit, si les blocs étaient reliés par une liste chaînée ou similaire. construire, ou si elles étaient autorisées à avoir des tailles différentes. Mais les cordes ne sont utilisées dans aucune implémentation de bibliothèque standard que je connaisse.

Les performances sont garanties par le STL au moins égal à O (N) pour les conteneurs, mais de nombreux conteneurs, y compris std :: string, peuvent implémenter cette fonctionnalité sous la forme O (1) et le seront. Habituellement, il retourne une variable simple ou fait quelque chose comme _End - _Begin et le renvoie. 

size_type __CLR_OR_THIS_CALL size() const

{   // return length of sequence

    return (_Mysize);

}

Donc, ça pourrait éventuellement être comme ça, mais vous ne pouvez jamais en être sûr.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top