Efficacité de C-String par rapport à C++Strings

Question

C++ Primer dit

Pour la plupart des applications, en plus d'être plus sûr, il est aussi plus efficace d'utiliser les chaînes de la bibliothèque plutôt que les chaînes de style C.

La sécurité est comprise. Pourquoi la bibliothèque de chaînes de caractères C++ est-elle plus efficace ? Après tout, au fond, les chaînes de caractères ne sont-elles pas toujours représentées par des tableaux de caractères ?

Pour clarifier, l'auteur parle-t-il de l'efficacité du programmeur (compris) ou de l'efficacité du traitement ?

Answer 1

Les chaînes C sont généralement plus rapides car elles n'appellent pas malloc/new. Mais il y a des cas où std::string est plus rapide. Fonction strlen() est O(N), mais std::string::size() est O(1).

De même, lorsque vous recherchez une sous-chaîne, dans c-string vous devez vérifier que '\0' à chaque cycle, en std::string - vous ne le faites pas. Dans l'algorithme naïf de recherche de sous-chaînes, cela n'a pas beaucoup d'importance, car au lieu de vérifier la présence de '\0' vous devez vérifier si i<s.size() . Mais les algorithmes modernes et performants de recherche de sous-chaîne parcourent la chaîne de caractères par étapes de plusieurs octets. Et il faut '\0' dans chaque octet les ralentit. C'est la raison pour laquelle GLIBC memmem est x2 fois plus rapide que strstr . J'ai fait beaucoup d'analyse comparative des algorithmes de sous-chaîne.

Cela n'est pas seulement vrai pour l'algorithme de recherche par sous-chaîne. De nombreux autres algorithmes de traitement des chaînes sont plus lents pour les chaînes à terminaison nulle.

Answer 2

Pourquoi la bibliothèque de chaînes de caractères C++ est-elle plus efficace ? Après tout, au fond, les chaînes ne sont-elles pas toujours représentées par des tableaux de caractères ?

Parce que le code qui utilise char* ou char[] a plus de chances d'être inefficace s'il n'est pas rédigé avec soin. Par exemple, avez-vous vu boucle comme ça :

char *get_data();

char const *s = get_data(); 

for(size_t i = 0 ; i < strlen(s) ; ++i) //Is it efficent loop? No.
{
   //do something
}

Est-ce efficace ? Non. La complexité temporelle de strlen() est O(N) et de plus, elle est calculée à chaque itération, dans le code ci-dessus.

Maintenant, vous pouvez dire "Je peux le rendre efficace si j'appelle strlen() juste une fois." . Bien sûr, vous le pouvez. Mais vous devez faire toute cette sorte d'optimisation vous-même et consciemment . Si vous avez manqué quelque chose, vous avez manqué des cycles de CPU. Mais avec std::string La plupart de ces optimisations sont effectuées par la classe elle-même. Vous pouvez donc écrire ceci :

std::string get_data();

std::string const & s = get_data(); //avoid copy if you don't need  it

for(size_t i = 0 ; i < s.size() ; ++i) //Is it efficent loop? Yes.
{
   //do something
}

Est-ce efficace ? Oui. La complexité temporelle de size() est O(1) . Il n'est pas nécessaire de l'optimiser manuellement, ce qui rend souvent le code laid et difficile à lire. Le code résultant avec std::string est presque toujours soignée et propre par rapport aux char* .

Notez également que std::string ne rend pas seulement votre code efficace en termes de cycles CPU, mais il augmente également l'efficacité du programmeur !

Answer 3

A std::string connaît sa longueur, ce qui rend de nombreuses opérations plus rapides.

Par exemple, étant donné :

const char* c1 = "Hello, world!";
const char* c2 = "Hello, world plus dog!";
std::string s1 = c1;
std::string s2 = c2;

strlen(c1) est plus lent que s1.length() . Pour les comparaisons, strcmp(c1, c2) doit comparer plusieurs caractères pour déterminer que les chaînes de caractères ne sont pas égales, mais s1 == s2 peut dire que les longueurs ne sont pas les mêmes et retourner immédiatement false.

D'autres opérations bénéficient également de la connaissance de la longueur à l'avance, par ex. strcat(buf, c1) doit trouver le terminateur nul dans buf pour trouver où ajouter des données, mais s1 += s2 connaît la longueur de s1 déjà et peut ajouter les nouveaux caractères au bon endroit immédiatement.

Quand il s'agit de la gestion de la mémoire, std::string alloue de l'espace supplémentaire à chaque fois qu'il grandit, ce qui signifie que les futures opérations d'ajout n'ont pas besoin d'être réallouées.

Answer 4

Il y a sont certains cas dans lesquels un std::string pourrait battre un char[] . Par exemple, les chaînes de caractères de style C n'ont généralement pas de longueur explicite transmise - au lieu de cela, le terminateur NUL définit implicitement la longueur.

Cela signifie qu'une boucle qui continuellement strcat sur un char[] effectue en fait O(n²) travail, parce que chaque strcat doit traiter la chaîne entière afin de déterminer le point d'insertion. En revanche, le seul travail qu'un std::string doit effectuer pour concaténer à la fin d'une chaîne de caractères est de copier les nouveaux caractères (et éventuellement de réallouer l'espace de stockage - mais pour que la comparaison soit équitable, vous devez connaître la taille maximale au préalable et reserve() le).

Answer 5

Il est préférable d'utiliser les chaînes de la bibliothèque des chaînes car elles vous évitent d'allouer et de désallouer de la mémoire, de rechercher les fuites de mémoire et autres dangers liés aux pointeurs. Mais comme les chaînes de caractères sont des objets, elles prennent de l'espace supplémentaire en mémoire.

Les chaînes de caractères sont simplement des tableaux de caractères. Elles DEVRAIENT être utilisées lorsque vous travaillez en temps réel, lorsque vous ne savez pas exactement de combien d'espace mémoire vous disposez. Si vous utilisez des chaînes de caractères, vous devrez vous occuper de l'allocation de la mémoire, puis de la copie des données dans la chaîne via strcpy ou caractère par caractère, puis de la désallocation après utilisation, etc, etc. Il est donc préférable d'utiliser les chaînes de la bibliothèque string si vous voulez éviter tout un tas de maux de tête.

Les chaînes de caractères augmentent l'efficacité du programme mais réduisent l'efficacité du traitement (mais pas nécessairement). L'inverse est vrai pour les cstrings