Efficace de concaténation de chaîne en C++

Question

J'ai entendu quelques personnes exprimant des inquiétudes sur les "+" de l'opérateur en std::string et diverses solutions pour accélérer la concaténation. Sont-elles vraiment nécessaires? Si oui, quel est le meilleur moyen pour concaténer des chaînes de caractères en C++?

Answer 1

Le travail supplémentaire est probablement pas la peine, à moins que vous vraiment besoin de l'efficacité. Vous aurez probablement beaucoup mieux l'efficacité de tout simplement en utilisant l'opérateur += à la place.

Maintenant, après que l'avertissement, je vais répondre à votre question...

L'efficacité de la STL classe string dépend de l'implémentation de la STL que vous utilisez.

Vous pourriez garantir l'efficacité et avoir une plus grande maîtrise de vous-même en faisant de concaténation manuellement par l'intermédiaire de c des fonctions intégrées.

Pourquoi opérateur+ n'est pas efficace:

Jetez un oeil à cette interface:

template <class charT, class traits, class Alloc>
basic_string<charT, traits, Alloc>
operator+(const basic_string<charT, traits, Alloc>& s1,
          const basic_string<charT, traits, Alloc>& s2)

Vous pouvez voir qu'un nouvel objet est retourné après chaque +. Cela signifie qu'une nouvelle mémoire tampon est utilisée à chaque fois. Si vous faites une tonne supplémentaire de + opérations, il n'est pas efficace.

Pourquoi vous pouvez la rendre plus efficace:

• Vous êtes en assurant une efficacité au lieu de faire confiance à un délégué à le faire de manière efficace pour vous
• la classe std::string ne sait rien à propos de la taille maximale de votre chaîne, ni à quelle fréquence vous sera la concaténation. Vous pouvez avoir cette connaissance et peut faire des choses en se basant sur ces informations. Cela conduira à moins de les ré-allocations.
• Vous serez en contrôle de la mémoire manuellement de sorte que vous pouvez être sûr que vous ne copiez pas l'ensemble de la chaîne de nouveaux tampons lorsque vous ne voulez pas que cela se produise.
• Vous pouvez utiliser la pile pour votre tampons au lieu de le tas qui est beaucoup plus efficace.
• chaîne + opérateur de créer une nouvelle chaîne de l'objet et de le retourner par conséquent, avec un nouveau tampon.

Considérations pour la mise en œuvre:

• Garder une trace de la longueur de la chaîne.
• De garder un pointeur à la fin de la chaîne et le début, ou tout simplement le début et le début + la longueur d'un décalage de trouver la fin de la chaîne.
• Assurez-vous que le tampon vous stockez votre chaîne, est assez grand de sorte que vous n'avez pas besoin de ré-allouer de données
• Utiliser la fonction strcpy au lieu de strcat de sorte que vous n'avez pas besoin de parcourir la longueur de la chaîne à trouver la fin de la chaîne.

Corde de la structure de données:

Si vous avez besoin très rapidement les concaténations de considérer l'utilisation d'une corde de structure de données.

Answer 2

Réservez votre espace final avant, puis utiliser la méthode append avec un tampon. Par exemple, disons que vous attendez de votre chaîne finale de la longueur à 1 million de caractères:

std::string s;
s.reserve(1000000);

while (whatever)
{
  s.append(buf,len);
}

Answer 3

Je voudrais vous inquiétez pas à ce sujet. Si vous le faites dans une boucle, les chaînes seront toujours préallouer de la mémoire afin de minimiser les réaffectations - operator+= dans ce cas. Et si vous le faites manuellement, quelque chose comme ceci ou plus

a + " : " + c

Puis c'est la création d'temporaires - même si le compilateur pourrait éliminer certains de la valeur de retour des copies. C'est parce que dans une, successivement appelés operator+ il ne sait pas si le paramètre de référence fait référence à un objet nommé ou temporaire retourné à partir d'un sous - operator+ d'invocation. Je voudrais plutôt vous inquiétez pas à ce sujet avant de ne pas avoir de profilés en premier. Mais prenons un exemple pour montrer que. Nous présentons d'abord les parenthèses pour faire la liaison clair. J'ai mis les arguments directement après la déclaration de la fonction qui est utilisée pour plus de clarté. Ci-dessous, je montrerai que l'expression obtenue est alors:

((a + " : ") + c) 
calls string operator+(string const&, char const*)(a, " : ")
  => (tmp1 + c)

Maintenant, dans cet ajout, tmp1 est ce qui a été renvoyé par le premier appel à l'opérateur+ avec le présenté des arguments. Nous supposons que le compilateur est vraiment intelligent et optimise la valeur de retour de la copie. On se retrouve donc avec une nouvelle chaîne de caractères qui contient la concaténation de a et " : ". Maintenant, ce qui se passe:

(tmp1 + c)
calls string operator+(string const&, string const&)(tmp1, c)
  => tmp2 == <end result>

Comparez-la à la suivante:

std::string f = "hello";
(f + c)
calls string operator+(string const&, string const&)(f, c)
  => tmp1 == <end result>

C'est en utilisant la même fonction pour une durée temporaire et pour une chaîne de! Ainsi, le compilateur a copier l'argument dans une nouvelle chaîne et de l'ajouter à cela et le retourner à partir du corps d' operator+. Il ne peut pas prendre la mémoire temporaire et l'ajouter à cela. Le plus gros de l'expression est, le plus de copies de chaînes ont à faire.

Prochain Visual Studio et de la GCC sera le support c++1x de la sémantique de déplacement (en complétant la sémantique de copie) et les références rvalue expérimental de plus. Qui permet de déterminer si le paramètre références temporaire ou non. Cela permettra de procéder aux ajouts étonnamment rapide, comme tous les ci-dessus prendra fin dans un "pipeline" sans copie.

Si elle s'avère être un goulot d'étranglement, vous pouvez toujours le faire

 std::string(a).append(" : ").append(c) ...

L' append appels d'ajouter l'argument *this puis de retourner une référence à eux-mêmes. Donc pas de copie de temporaires qui s'y fait. Ou, à défaut, operator+= peut être utilisé, mais vous auriez besoin de laide des parenthèses pour fixer la priorité.

Answer 4

Pour la plupart des applications, il ne veut tout simplement pas d'importance. Il suffit d'écrire votre code, au courant de comment exactement l'opérateur + de travaux et de prendre les choses en mains propres si cela devient une apparente goulot d'étranglement.

Answer 5

À la différence .NET Système.Cordes, C++std::les chaînes de caractères sont mutables, et ne peut donc être construite à travers la simple concaténation tout aussi rapide que par d'autres méthodes.