J'ai entendu quelques personnes exprimer des inquiétudes concernant l'opérateur "+" dans std :: string et diverses solutions de contournement pour accélérer la concaténation. Certains de ces éléments sont-ils vraiment nécessaires? Si tel est le cas, quelle est la meilleure façon de concaténer des chaînes en C ++?

Le travail supplémentaire n'en vaut probablement pas la peine, sauf si vous avez vraiment besoin d'efficacité. Vous aurez probablement une bien meilleure efficacité simplement en utilisant l'opérateur + = à la place.

Maintenant, après cet avertissement, je vais répondre à votre question réelle ...

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

Vous pouvez garantir l'efficacité et avoir un meilleur contrôle vous-même en effectuant la concaténation manuellement via les fonctions intégrées c.

Pourquoi operator + n'est pas efficace:

Jetez un œil à 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 renvoyé après chaque +. Cela signifie qu'un nouveau tampon est utilisé à chaque fois. Si vous faites une tonne d'opérations + supplémentaires, ce n'est pas efficace.

Pourquoi vous pouvez le rendre plus efficace:

• Vous garantissez l'efficacité au lieu de faire confiance à un délégué pour le faire efficacement pour vous
• la classe std :: string ne sait rien de la taille maximale de votre chaîne, ni de la fréquence à laquelle vous la concaténerez. Vous pouvez avoir ces connaissances et faire des choses en vous basant sur ces informations. Cela conduira à moins de réaffectations.
• Vous contrôlerez les tampons manuellement afin d'être sûr de ne pas copier la chaîne entière dans de nouveaux tampons lorsque vous ne voulez pas que cela se produise.
• Vous pouvez utiliser la pile pour vos tampons au lieu du tas qui est beaucoup plus efficace.
• string + operator créera un nouvel objet string et le retournera donc en utilisant un nouveau tampon.

Considérations pour la mise en œuvre:

• Gardez une trace de la longueur de la chaîne.
• Gardez un pointeur vers la fin de la chaîne et le début, ou simplement le début et utilisez le début + la longueur comme décalage pour trouver la fin de la chaîne.
• Assurez-vous que le tampon dans lequel vous stockez votre chaîne est suffisamment grand pour que vous n'ayez pas besoin de réallouer des données
• Utilisez strcpy au lieu de strcat pour ne pas avoir besoin d'itérer sur la longueur de la chaîne pour trouver la fin de la chaîne.

Structure de données de corde:

Si vous avez besoin vraiment rapide concaténations envisager d' utiliser une structure de données de corde .

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

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

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

Je ne m'en soucierais pas. Si vous le faites en boucle, les chaînes préalloueront toujours la mémoire pour minimiser les réallocations - utilisez simplement operator+=dans ce cas. Et si vous le faites manuellement, quelque chose comme ça ou plus

a + " : " + c

Ensuite, il crée des temporaires - même si le compilateur peut éliminer certaines copies de valeur de retour. En effet, dans un appel successivement, operator+il ne sait pas si le paramètre de référence fait référence à un objet nommé ou à un temporaire renvoyé par un sous- operator+appel. Je préfère ne pas m'en soucier avant de ne pas avoir profilé au préalable. Mais prenons un exemple pour le montrer. Nous introduisons d'abord des parenthèses pour rendre la liaison claire. Je mets les arguments directement après la déclaration de fonction utilisée pour plus de clarté. En dessous, je montre quelle est alors l'expression résultante:

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

Maintenant, dans cet ajout, tmp1est ce qui a été renvoyé par le premier appel à operator + avec les arguments affichés. Nous supposons que le compilateur est vraiment intelligent et optimise la copie de la valeur de retour. Nous nous retrouvons donc avec une nouvelle chaîne contenant la concaténation de aet " : ". Maintenant, cela se produit:

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

Comparez cela à ce qui suit:

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

Il utilise la même fonction pour un temporaire et pour une chaîne nommée! Le compilateur doit donc copier l'argument dans une nouvelle chaîne et l'ajouter à cela et le renvoyer à partir du corps de operator+. Il ne peut pas prendre la mémoire d'un temporaire et y ajouter. Plus l'expression est grande, plus il faut faire de copies de chaînes.

Ensuite, Visual Studio et GCC prendront en charge la sémantique de déplacement de c ++ 1x (complétant la sémantique de copie ) et les références rvalue comme ajout expérimental. Cela permet de savoir si le paramètre fait référence à un temporaire ou non. Cela rendra ces ajouts incroyablement rapides, car tout ce qui précède se terminera dans un "add-pipeline" sans copies.

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

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

Les appendappels ajoutent l'argument à *this, puis renvoient une référence à eux-mêmes. Il n'y a donc pas de copie des temporaires. Ou bien, le operator+=peut être utilisé, mais vous auriez besoin de parenthèses laides pour fixer la priorité.

Pour la plupart des applications, cela n'a pas d'importance. Écrivez simplement votre code, ignorant parfaitement comment fonctionne l'opérateur +, et ne prenez les choses en main que si cela devient un goulot d'étranglement apparent.

Contrairement à .NET System.Strings, les std :: strings de C ++ sont modifiables et peuvent donc être générées par simple concaténation tout aussi rapidement que par d'autres méthodes.

peut-être std :: stringstream à la place?

Mais je suis d'accord avec le sentiment que vous devriez probablement simplement le garder maintenable et compréhensible, puis profiler pour voir si vous rencontrez vraiment des problèmes.

En C ++ imparfait , Matthew Wilson présente un concaténateur de chaîne dynamique qui précalcule la longueur de la chaîne finale afin de n'avoir qu'une seule allocation avant de concaténer toutes les parties. Nous pouvons également implémenter un concaténateur statique en jouant avec des modèles d'expression .

Ce genre d'idée a été implémenté dans l'implémentation STLport std :: string - qui n'est pas conforme à la norme à cause de ce hack précis.

std::string operator+alloue une nouvelle chaîne et copie les deux chaînes d'opérande à chaque fois. répétez plusieurs fois et cela devient cher, O (n).

std::string appendet operator+=d'autre part, augmentez la capacité de 50% à chaque fois que la chaîne doit grossir. Ce qui réduit considérablement le nombre d'allocations de mémoire et d'opérations de copie, O (log n).

Pour les petites cordes, cela n'a pas d'importance. Si vous avez de grosses chaînes, vous feriez mieux de les stocker telles qu'elles sont en vecteur ou dans une autre collection en tant que parties. Et adaptez votre algorithme pour travailler avec un tel ensemble de données au lieu d'une seule grande chaîne.

Je préfère std :: ostringstream pour la concaténation complexe.

Comme pour la plupart des choses, il est plus facile de ne pas faire quelque chose que de le faire.

Si vous souhaitez afficher de grandes chaînes vers une interface graphique, il se peut que tout ce que vous produisez puisse gérer les chaînes en morceaux mieux que comme une grande chaîne (par exemple, concaténer du texte dans un éditeur de texte - généralement, ils gardent les lignes séparées structures).

Si vous souhaitez générer une sortie dans un fichier, diffusez les données plutôt que de créer une grande chaîne et de la générer.

Je n'ai jamais trouvé le besoin de rendre la concaténation plus rapide si je supprimais la concaténation inutile du code lent.

Probablement meilleures performances si vous pré-allouez (réservez) de l'espace dans la chaîne résultante.

template<typename... Args>
std::string concat(Args const&... args)
{
    size_t len = 0;
    for (auto s : {args...})  len += strlen(s);

    std::string result;
    result.reserve(len);    // <--- preallocate result
    for (auto s : {args...})  result += s;
    return result;
}

Usage:

std::string merged = concat("This ", "is ", "a ", "test!");

Un simple tableau de caractères, encapsulé dans une classe qui garde la trace de la taille du tableau et du nombre d'octets alloués, est le plus rapide.

L'astuce consiste à ne faire qu'une seule grande allocation au départ.

à

https://github.com/pedro-vicente/table-string

Benchmarks

Pour Visual Studio 2015, build de débogage x86, amélioration substantielle par rapport à C ++ std :: string.

| API                   | Seconds           
| ----------------------|----| 
| SDS                   | 19 |  
| std::string           | 11 |  
| std::string (reserve) | 9  |  
| table_str_t           | 1  |  

Vous pouvez essayer celui-ci avec des réservations de mémoire pour chaque élément:

namespace {
template<class C>
constexpr auto size(const C& c) -> decltype(c.size()) {
  return static_cast<std::size_t>(c.size());
}

constexpr std::size_t size(const char* string) {
  std::size_t size = 0;
  while (*(string + size) != '\0') {
    ++size;
  }
  return size;
}

template<class T, std::size_t N>
constexpr std::size_t size(const T (&)[N]) noexcept {
  return N;
}
}

template<typename... Args>
std::string concatStrings(Args&&... args) {
  auto s = (size(args) + ...);
  std::string result;
  result.reserve(s);
  return (result.append(std::forward<Args>(args)), ...);
}