C++ std:: string ajoute vs push back()
c'est vraiment une question juste pour mon propre intérêt que je n'ai pas été en mesure de déterminer à travers la documentation.
je vois sur http://www.cplusplus.com/reference/string/string/ append a la complexité:
"non spécifié, mais généralement linéaire dans la nouvelle longueur de la chaîne."
push_back() a la complexité:
<!-- 2-non spécifié; généralement constante amortie, mais jusqu'à linéaire dans la nouvelle chaîne longueur."par exemple, supposons que je veuille ajouter les caractères "foo" à une chaîne de caractères. Serait -
myString.push_back('f');
myString.push_back('o');
myString.push_back('o');
et
myString.append("foo");
montant à exactement la même chose? Ou est-il une différence? Vous pourriez penser que l'ajout serait plus efficace parce que le compilateur saurait combien de mémoire est nécessaire pour étendre la chaîne le nombre spécifié de caractères, tandis que push_back peut avoir besoin de sécuriser la mémoire chaque appel?
4 réponses
en C++03 (pour lequel la plupart des "cplusplus.com" 's documentation is written), les complexités n'étaient pas précisées parce que les responsables de la mise en œuvre de la bibliothèque étaient autorisés à faire des représentations internes de type Copie-écriture ou "corde" pour les chaînes. Par exemple, une implémentation de COW peut nécessiter de copier la chaîne entière si un caractère est modifié et qu'il y a partage en cours.
En C++11, de la VACHE et de la corde implémentations sont interdits. Vous devez vous attendre à un temps amorti constant par caractère ajouté ou temps linéaire amorti dans le nombre de caractères ajoutés pour ajouter à une chaîne à la fin. Les réalisateurs peuvent encore faire des choses assez folles avec des chaînes (par rapport à, disons std::vector), mais la plupart des implémentations vont être limitées à des choses comme "l'optimisation des petites chaînes".
En comparant push_back et append, push_back prive la mise en œuvre sous-jacente de l'information potentiellement utile sur la longueur qu'elle pourrait utiliser pour préallouer l'espace. D'autre part, append exige qu'une implémentation marche sur l'entrée deux fois afin de trouver cette longueur, de sorte que le gain ou la perte de performance va dépendre d'un certain nombre de facteurs inconnus tels que la longueur de la chaîne avant de tenter l'ajout. Cela dit, la différence est probablement extrêmement minime. Aller avec append -- c'est beaucoup plus lisible.
ajouter une autre opinion ici.
je considère personnellement qu'il vaut mieux utiliser push_back() en ajoutant des caractères un par un à partir d'une autre chaîne de caractères. Par exemple:
string FilterAlpha(const string& s) {
string new_s;
for (auto& it: s) {
if (isalpha(it)) new_s.push_back(it);
}
return new_s;
}
Si vous utilisez append() ici, je remplacerais push_back(it)append(1,it), qui n'est pas lisible pour moi.
j'avais le même doute, donc j'ai fait un petit test pour vérifier cela (g++ 4.8.5 avec profil C++11 sous Linux, Intel, 64 bits sous VMware Fusion).
Et le résultat est intéressant:
push :19 append :21 ++++ :34
pourrait être possible c'est à cause de la longueur de la chaîne (grande), mais l'opérateur + est très cher comparé avec le push_back et l'annexe.
pour ne pas dépendre de variables pré-attribuées, chaque cycle est défini dans une portée différente.
TimeCounter vCounter;
{
string vTest;
vCounter.start();
for (int vIdx=0;vIdx<1000000;vIdx++) {
vTest.push_back('a');
vTest.push_back('b');
vTest.push_back('c');
}
vCounter.stop();
cout << "push :" << vCounter.elapsed() << endl;
}
{
string vTest;
vCounter.start();
for (int vIdx=0;vIdx<1000000;vIdx++) {
vTest.append("abc");
}
vCounter.stop();
cout << "append :" << vCounter.elapsed() << endl;
}
{
string vTest;
vCounter.start();
for (int vIdx=0;vIdx<1000000;vIdx++) {
vTest += 'a';
vTest += 'b';
vTest += 'c';
}
vCounter.stop();
cout << "++++ :" << vCounter.elapsed() << endl;
}
Oui, je pense également que le append() pour de meilleures performances pour les raisons que vous avez donné, et dans une situation où vous avez besoin d'ajouter une chaîne de caractères, à l'aide de append() (ou operator+=) est certainement préférable (notamment aussi parce que le code est beaucoup plus lisible).
mais ce que la norme spécifie est la complexité de l'opération. Et c'est généralement linéaire même pour append(), parce que finalement chaque caractère de la chaîne étant ajouté (et possible tous les caractères, si réallocation se produit) doit être copié (cela est vrai même si memcpy ou similaires sont utilisés).