Est std::string taille() O(1) opération?

Est std::string taille() O(1) opération?

La mise en œuvre de la STL que j'utilise est celui qui est intégré dans VC++

InformationsquelleAutor Brian R. Bondy | 2008-11-01
  1. 32

    Si vous vous demandez si MSVC de la mise en œuvre de string::size() a constante de la complexité, alors la réponse est oui. Mais Ne Wakefield mentionné Tableau 65 23,1 de la Norme C++ où il est dit que la complexité de size() devrait suivre ce qui est dit dans la Note de l'Un". La Note A dit:

    Les entrées marquées ‘(Note A)’
    doit avoir de la constante de la complexité.

    Toutefois, cela ne signifie pas que ces entrées est avez constante de la complexité. Les normes d'utilisation très spécifique de la terminologie, et "devrait" signifie qu'il n'est pas obligatoire.

    Note de l'Un' a été ajouté à la norme spécifiquement pour apaiser ceux qui ont cru que size() devraient être autorisés à avoir linéaire de la complexité de sorte qu'il ne serait pas nécessaire de garder la taille lorsque les conteneurs ont été modifiés.

    De sorte que vous ne pouvez pas compter sur size() ayant constante de la complexité, mais je suis franchement pas sûr que s'il y a des implémentations qui n'ont pas une constante string::size().

    • Comme une note de côté, il est néanmoins possible de récupérer la taille de la chaîne comme un O(1) opération d'une manière standard: (end() - begin()). Ceci est garanti pour être [amorti] O(1) car les deux begin() et end() doit être O(1) (Conteneur), chaîne itérateurs sont en accès aléatoire (string) et operator- doit être O(1) pour les itérateurs qui le prennent en charge (itérateur exigences).
    • ... et la longueur de la chaîne ne peut pas être calculée à partir du contenu, car il n'y a pas de restriction sur les valeurs qui peuvent être stockés. Ce qui signifie qu'il doit être géré à l'externe pour le contenu, et elle est donc indépendante de N. c'est à dire qu'il doit être O(1). Le fait que O(1) n'est pas une exigence pour tous conteneurs ne signifie pas qu'il peut être O(N) dans les conteneurs, seulement qu'il peut y avoir au moins un conteneur pour lequel il est non constante, par exemple std::list<>.
    • Hmmm, il peut être possible d'utiliser un "codage" d'une chaîne pour éviter explicitement le stockage de la longueur de n'importe où. E. g. utiliser 0 octet comme un caractère d'échappement dont le sens dépend de l'octet suivant: 0 signifie "fin de chaîne", différente de zéro signifie "que beaucoup de 0 octets". Il se peut que d'autres std::string exigences de l'interdit cependant (ce qui semble impliquer des indices de tableaux peuvent ne plus être en O(1)).
    • Vous parlez hypothétique langue ou C++? Dans une hypothétique langue je suppose que vous pourriez. En C++, le 03 standard lors de la description de std::basic_string<>::size() il désigne le récipient contenant les exigences (c'est à dire recommandé de taille constante), dans le 11 standard, la condition est explicite: la Complexité: constante de temps.
    • Vous avez raison! Dans le 03 standard, 21.3/2 dit que "Le modèle de classe basic_string est conforme aux exigences d'une Séquence, comme indiqué dans (23.1.1)", et une Séquence est un type de conteneur (23.1.1/1), et un récipient mandats constante de temps begin() et end() (Tableau 65 23,1) Heureux d'entendre, ils l'ont fait explicite en C++11.
    • les chaînes ne sont pas des conteneurs. c'est un célèbre normalisation caprice. Je ne crois pas que votre point de stands à cause de cela.
    • selon cette stackoverflow.com/a/17259940/893406 je suis dans le mauvais. Peut-être que je suis un peu perdu avec vector<bool>... ne me dérange pas de moi alors.

    InformationsquelleAutor Michael Burr
  2. 7

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

    Écrire un peu de code dans un projet:

    string happy;
happy.size();

    Hilight l' .la taille de l'appel, cliquez-droit, aller à la définition.

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

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

    Donc il semble que la chaîne a un membre appelé _Mysize, et il est juste de retour que.

    En d'autres mots, c'est un O(1) la mise en œuvre.

    InformationsquelleAutor tfinniga
  3. 6

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

    InformationsquelleAutor lacker
  4. 5

    Voir Tableau 65 dans l'Article 23.1 de la Norme. "une.taille()" est répertorié comme "(Note A)", qui dit que "les entrées ... doit avoir de la constante de la complexité".

    Article 21.3 dit que les chaînes sont conformes aux exigences d'une séquence (23.1), ipso facto, de la taille() est la constante de temps.

    • +1 pour l'utilisation du latin!
    • Alors que l'été de l'auto-étude a été quelque chose d'intéressant! ;^)~
    InformationsquelleAutor Don Wakefield
  5. 5

    Pour une chaîne de caractères, la size() opération a être constante pour l'ensemble de la chaîne des implémentations ne pas utiliser cordes(1). Il n'y a aucune exigence explicite dans la norme qui exige que l'opération soit O(1), le plus proche est le générique de l'exigence que les size() devrait être à temps constant, mais qui laisse de la place pour tout les autres de la complexité de la mesure.

    Alors pourquoi doit il O(1)?

    Ceci vient du fait que la taille ne peut pas être calculée à partir du contenu de la chaîne elle-même. Alors qu'en C, vous utilisez un NUL de terminaison pour déterminer la fin de la chaîne, en C++ NUL est aussi valable que n'importe quel autre caractère dans la chaîne. Puisque la taille de la chaîne ne peut pas être calculée à partir du contenu(2), il doit être manipulé de l'extérieur, indépendamment de la taille réelle de la chaîne.

    (1) C++03 standard permet une mise en œuvre à utiliser cordes que la mise en œuvre pour les cordes, mais le fait est qu'aucun des implémentations actuelles de la norme bibliothèques de les utiliser.

    (2) Si la mise en œuvre utilisé des cordes, l'opération dépend de la taille par le nombre de blocs à partir de laquelle la corde a été construit si les blocs étaient liés par une liste chaînée ou similaire construire, ou s'ils ont été autorisés à avoir des tailles différentes. Mais cordes ne sont pas utilisés dans toute la bibliothèque standard de mise en œuvre, que je sache.

    InformationsquelleAutor David Rodríguez - dribeas
  6. 2

    Rendement est garanti par le TSL d'être au moins O(N) pour les conteneurs, cependant, de nombreux conteneurs, y compris std::string peut mettre en œuvre ce que O(1) et de la volonté. Habituellement, il va renvoyer une variable simple ou de faire quelque chose comme _End - _Begin et de retour que.

    InformationsquelleAutor Jasper Bekkers
  7. -2
    size_type __CLR_OR_THIS_CALL size() const
    {   //return length of sequence
    return (_Mysize);
    }

    Donc finalement peut-être comme cela, mais vous ne pouvez jamais être sûr.

    • Je pense que vous ont été rejetés parce que vous n'avez pas répondu à la question, vous avez exigé le lecteur de relier les points. Et aussi votre réponse est cryptique.
    • reformuler votre réponse et jeté dans un upvote.
    • Je ne vois pas du tout de la reformuler. Pour moi, la réponse est encore énigmatique. "... c'est finalement "peut-être "comme ça"? N'était-ce pas le code de prises à partir de la mise en œuvre effective?
    InformationsquelleAutor