Quelles performances peut-on attendre du c_str () de std :: string? Toujours un temps constant?

13

J'ai fait quelques optimisations nécessaires récemment. Une chose que j'ai faite est de changer certains ostringstreams -> sprintfs. Je sprintf'ing un tas de chaînes std :: strings to ac style array, ala

char foo[500];
sprintf(foo, "%s+%s", str1.c_str(), str2.c_str());

Il s'avère que l'implémentation std :: string :: c_str () de Microsoft s'exécute en temps constant (elle renvoie simplement un pointeur interne). Il semble que libstdc ++ fasse de même . Je me rends compte que le std ne fait aucune garantie pour c_str, mais il est difficile d'imaginer une autre façon de procéder. Si, par exemple, ils copiaient dans la mémoire, ils devaient soit allouer de la mémoire pour un tampon (laissant à l'appelant le soin de le détruire - NE FAIT PAS partie du contrat STL) OU ils devaient copier sur un statique interne tampon (probablement pas threadsafe, et vous n'avez aucune garantie sur sa durée de vie). Donc, le simple retour d'un pointeur vers une chaîne terminée par un null maintenu en interne semble être la seule solution réaliste.

c++ performance strings Doug T.
la source

Réponses:

9

Si je me souviens bien, la norme permet string::c_str()de renvoyer à peu près tout ce qui satisfait:

  • Stockage suffisamment grand pour le contenu de la chaîne et la terminaison NULL
  • Doit être valide jusqu'à ce qu'un membre non const de l' stringobjet donné soit appelé

Donc, en pratique, cela signifie un pointeur vers le stockage interne; car il n'existe aucun moyen de suivre en externe la durée de vie du pointeur renvoyé. Je pense que votre optimisation est sûre de supposer qu'il s'agit d'un (petit) temps constant.

Sur une note connexe, si le formatage des chaînes limite les performances; vous aurez peut-être plus de chance de reporter l'évaluation jusqu'à ce qu'elle soit absolument nécessaire avec quelque chose comme Boost.Phoenix .

Boost.Format Je crois que la mise en forme est différée en interne jusqu'à ce que le résultat soit requis, et vous pouvez utiliser le même objet de format à plusieurs reprises sans ré-analyser la chaîne de format, ce que j'ai trouvé pour faire une différence significative pour l'enregistrement à haute fréquence.

rvalue
la source
2
Il peut être possible pour une implémentation de créer un tampon interne nouveau ou secondaire - suffisamment grand pour ajouter le terminateur nul. Même si c_strc'est une méthode const (ou au moins a une surcharge const - j'oublie laquelle), cela ne change pas la valeur logique, donc cela peut être une raison mutable. Il serait briser des pointeurs d' autres appels à c_str, sauf que de tels pointeurs doivent se référer à la même chaîne logique (donc il n'y a pas de nouvelle raison de réallouer - il doit déjà être un terminateur nul) ou bien il doit avoir été un appel à un non -const méthode entre les deux.
Steve314
Si cela est vraiment valide, les c_strappels peuvent être O (n) pour la réallocation et la copie. Mais il est également possible qu'il y ait des règles supplémentaires dans la norme que je ne connais pas qui empêcheraient cela. La raison pour laquelle je le suggère - les appels à c_strne sont pas vraiment destinés à être des AFAIK courants, donc il peut ne pas être considéré comme important de s'assurer qu'ils sont rapides - en évitant cet octet supplémentaire de stockage pour un terminateur nul normalement inutile dans les stringcas où jamais utiliser c_strpeut ont pris le pas.
Steve314
Boost.Formatpasse en interne par des flux qui en interne sprintffinissent par se retrouver avec des frais généraux assez importants. La documentation indique qu'il est environ 8 fois plus lent que ordinaire sprintf. Si vous voulez des performances et une sécurité de type, essayez Boost.Spirit.Karma.
Jan Hudec
Boost.Spirit.Karmaest un bon conseil pour les performances, mais sachez qu'il a une méthodologie très différente qui peut être difficile à adapter le printfcode de style existant (et les codeurs). Je suis en grande partie resté avec Boost.Formatparce que nos E / S sont asynchrones; mais un facteur important est que je peux convaincre mes collègues de l'utiliser de manière cohérente (permet toujours à n'importe quel type avec une ostream<<surcharge - ce qui joliment dérive le .c_str()débat) Les chiffres de performance du Karma .
rvalue
23

Dans la norme c ++ 11 (je lis la version N 3290), le chapitre 21.4.7.1 parle de la méthode c_str ():

const charT* c_str() const noexcept; const charT* data() const noexcept;

Renvoie: Un pointeur p tel que p + i == & opérateur pour chaque i dans [0, taille ()].
Complexité: temps constant.
Requiert: Le programme ne doit modifier aucune des valeurs stockées dans le tableau de caractères.

Alors oui: la complexité à temps constant est garantie par la norme.

Je viens de vérifier la norme c ++ 03, et elle n'a pas de telles exigences, ni ne dit la complexité.

BЈовић
la source
8

En théorie, C ++ 03 n'exige pas cela, et donc la chaîne peut être un tableau de caractères où la présence du terminateur nul est ajoutée juste au moment où c_str () est appelée. Cela peut nécessiter une réallocation (cela ne viole pas la constance, si le pointeur privé interne est déclaré comme mutable).

C ++ 11 est plus strict: il nécessite du temps, donc aucune relocalisation ne peut être effectuée et le tableau doit toujours être suffisamment large pour stocker le null à la fin. c_str (), en soi, peut encore faire " ptr[size()]='\0'" pour s'assurer que le null est bien présent. Il ne viole pas la constance du tableau puisque la plage [0..size())n'est pas modifiée.

Emilio Garavaglia
la source