Différences

Cette page vous donne les différences entre la révision choisie et la version actuelle de la page.

--- comparer_strings [2014/08/05 09:42]
gbdivers
+++ — (Version actuelle)
@@ Ligne 1: / Ligne 1: @@
-^ [[expressions_regulieres|Chapitre précédent]] ^ [[programmez_avec_le_langage_c|Sommaire principal]] ^ [[rechercher_string|Chapitre suivant]] ^
-====== Comparaison et validations de chaînes ======
-Les chapitres précédents présentaient la syntaxe des expressions régulières. Bien sûr, il faudra pratiquer pour assimiler correctement ce langage. Dans ce chapitre et les suivants, nous allons voir plus en détail l'utilisation des expressions régulières, mais côté C++ cette fois ci. Nous verrons également l'utilisation de plusieurs algorithmes de la bibliothèque standard.
-===== Comparer si deux chaînes sont identiques =====
-==== Les opérateurs de comparaison ====
-Dans les chapitres précédents, vous avez vu l'utilisation de l'opérateur de comparaison ''=='' (//"egal to" operator//). La classe ''string'' fournit également cet opérateur, vous pouvez donc écrire :
-<code cpp main.cpp>
-#include <iostream>
-#include <string>
-int main() {
-    std::string const s1 { "salut" };
-    std::string const s2 { "salut" };
-    std::string const s3 { "hello" };
-    std::cout << std::boolalpha << (s1 == s2) << std::endl;
-    std::cout << (s1 == s3) << std::endl;
-}
-</code>
-affiche :
-<code>
-true
-false
-</code>
-Remarque : ne pas oublier les parenthèses autour du test d'égalité pour ''string''. L'opérateur ''<<'' ayant un sens pour cette classe, le compilateur ne pourra pas savoir si vous souhaitez écrire :
-<code cpp>
-std::cout << std::boolalpha << (s1 == s2) << std::endl;
-std::cout << std::boolalpha << s1 == (s2 << std::endl);
-</code>
-Pour vérifier si deux chaînes sont différentes, il est possible d'utiliser l'opérateur booléen de négation ''!'' : ''!(s1 == s2)''. Pour simplement, on peut directement utiliser l'opérateur de comparaison ''!='' (//"not equal to" operator//).
-<code cpp main.cpp>
-#include <iostream>
-#include <string>
-int main() {
-    std::string const s1 { "salut" };
-    std::string const s2 { "salut" };
-    std::string const s3 { "hello" };
-    std::cout << std::boolalpha << (s1 != s2) << std::endl;
-    std::cout << (s1 != s3) << std::endl;
-}
-</code>
-affiche :
-<code>
-false
-true
-</code>
-On voit ici que les opérateurs ''=='' et ''!='' sont étroitement liés. Lorsque l'un de ces deux opérateurs est utilisable, on peut s'attendre à ce que l'autre opérateur le soit également. On dit qu'une classe qui propose l'opérateur d'égalité ''=='' qu'elle respecte le concept de "comparable par égalité" ([[http://en.cppreference.com/w/cpp/concept/EqualityComparable|EqualityComparable]]). Ce concept précise que l'opérateur d'égalité doit suivre les propriétés suivantes :
-  * réflexivité : quelque soit ''a'', ''a == a'' est toujours vrai ;
-  * commutativité : si ''a == b'', alors ''b == a'' ;
-  * transitivité : si ''a == b'' et ''b == c'', alors ''a == c''.
-Ce concept est assez classique, on le retrouve en mathématique dans la théorie des ensembles. On voit ici un point important : lorsqu'une classe définit un opérateur ''=='', on s'attend à ce qu'elle suive un certain nombre de règles. On dit qu'elle suis une sémantique, cela facilite son utilisation. Du point de vue de l'utilisateur de cette classe, on pourra utiliser n'importe quelle classe respectant cette sémantique de la même façon. Du point de vue du concepteur de la classe (ce que vous apprendrez à faire dans la suite de ce cours), il suffit de définir les sémantiques que l'on souhaite donner à notre classe et l'écriture de cette classe sera simplifié.
-Au contraire, le non respect d'une sémantique sera très perturbant pour l'utilisateur - et une source d'erreur sans fin. Imaginez que l'opérateur ''=='' ne réalise pas un test d'égalité, mais permet de faire la concaténation de deux chaînes ?
-Bien sûr, ces considérations s'appliquent à l'ensemble des sémantiques usuelles, en particulier celle que l'on connait en mathématique (addition avec ''+'', soustraction avec ''-'', etc.)
-==== La sémantique de valeur ====
-Un concept complexe peut être décomposé en une série de concepts plus simple (par exemple "est comparable par égalité" est composé des concepts "est réflexif", "est commutatif" et "est transitif"). De la même façon, il est possible de combiner des concepts pour créer de nouveaux concepts plus complexe. Un concept peut également autorisé ou interdire l'utilisation d'autres concepts (par exemple, le concept "est égal" autorise l'utilisation du concept "est différent").
-C'est la cas du concept "est comparable par égalité", qui fait parti d'un concept plus général : la sémantique de valeur. Cette sémantique s'applique à tout ce qui représente une valeur : un entier, un nombre réel, un nombre complexe, une chaîne de caractères, un tableau de données, etc. La sémantique de valeur autorise les concepts suivants :
-**Constructible** par défaut ([[http://en.cppreference.com/w/cpp/concept/DefaultConstructible|DefaultConstructible]]). On peut initialiser avec une valeur par défaut (on parle aussi de "zero initialization" puisque la valeur par défaut sera 0 ou équivalent).
-<code cpp>
-int const i {}; // construction par défaut
-</code>
-**Copiable** par construction ([[http://en.cppreference.com/w/cpp/concept/CopyConstructible|CopyConstructible]]) et par affectation ([[http://en.cppreference.com/w/cpp/concept/CopyAssignable|CopyAssignable]]). Cela signifie que l'on peut créer une valeur en copiant une autre valeur. Par exemple, pour un entier :
-<code cpp>
-int const i { 123 };
-int j { i }; // construction par copie
-j = i;       // affectation par copie
-</code>
-**Comparable** par égalité ([[http://en.cppreference.com/w/cpp/concept/DefaultConstructible|EqualityComparable]]) ou par "plus petit que" ([[http://en.cppreference.com/w/cpp/concept/LessThanComparable|LessThanComparable]]). Cela signifie que l'on peut utiliser les opérateurs d'égalité ''=='' et "plut petit que" ''<'' (ainsi que les opérateurs dérivés : "différent de" ''!='', "plus petit ou égal à" <html><=</html>, "plus grand que" ''>'' et "plus grand ou égal à" <html>>=</html>) :
-<code cpp>
-int const i { 123 };
-int const j { 456 };
-cout << (i == j) << endl; // égalité
-cout << (i != j) << endl; // différent
-cout << (i < j) << endl;  // plus petit
-cout << (i <= j) << endl; // plus petit ou égal
-cout << (i > j) << endl;  // plus grand
-cout << (i >= j) << endl; // plus grand ou égal
-</code>
-Si cela a un sens, la sémantique de valeur permet également de définir des opérateurs arithmétiques classiques : addition ''+'', soustraction ''-'', multiplication ''*'' et division ''/''. Par exemple, pour les entiers :
-<code cpp>
-int const i { 123 };
-int const j { 456 };
-cout << (i + j) << endl; // addition
-cout << (i - j) << endl; // soustraction
-cout << (i * j) << endl; // multiplication
-cout << (i / j) << endl; // division
-</code>
-Le rôle de ces opérateurs peut varier en fonction du type. Par exemple, l'opérateur ''+'' correspondra à une addition pour les types numériques et à une concaténation pour les chaînes de caractères ''string''.
-<code cpp main.cpp>
-#include <iostream>
-#include <string>
-int main() {
-    int const i1 { 1 };
-    int const i2 { 2 };
-    std::cout << (i1 + i2) << std::endl; // addition
-    std::string const s1 { "1" };
-    std::string const s2 { "2" };
-    std::cout << (s1 + s2) << std::endl; // concaténation
-}
-</code>
-affiche :
-<code>
-</code>
-De plus, selon les types, tous les opérateurs n'ont pas forcement un sens. Par exemple, pour les chaînes ''string'', seul l'opérateur ''+'' a un sens, les autres opérateurs ne sont pas définis.
-<note info>Les deux grands types de classes sont les classes à sémantique de valeur (que vous avez vu dans ce chapitre) et les classes à sémantique d'entité. Vous apprendrez dans la partie "programmation orientée objet" comment créer ces types de classes.</note>
-==== Le type de chaîne char* ====
-Comme vous l'avez vu dans le chapitre sur les littérales, les littérales chaînes de caractères ne sont pas de type ''string'', mais de type ''const char*''. Ce type est un héritage du C++ historique et du langage C. Pourquoi ne pas utiliser ce type en C++ ?
-Faisons un test simple. Essayons de comparer deux chaînes :
-<code cpp main.cpp>
-#include <iostream>
-int main() {
-    std::cout << std::boolalpha << ("b" < "a") << std::endl;
-}
-</code>
-Ce code affiche :
-<code>
-main.cpp: In function 'int main()':
-main.cpp:4:43: warning: comparison with string literal results in unspecified behaviour [-Waddress]
-     std::cout << std::boolalpha << ("b" < "a") << std::endl;
-                                           ^
-true
-</code>
-Premier problème, le compilateur affiche un message d'avertissement pour prévenir que la comparaison de littérales chaînes produit un comportement indéterminé (astuce : si vous ne comprenez pas bien l'anglais, n'hésitez pas à vous servir d'un traducteur en ligne comme [[https://translate.google.fr|Google Translate]] ou de faire une recherche sur internet en copiant le message d'erreur). On parle de comportement indéterminé (//Undefined Behavior// ou //UB//) lorsque le comportement n'est pas défini dans la norme C++. Donc ce code pourra fonctionner différemment selon le compilateur, donner le résultat correct ou un résultat aléatoire, produire une erreur, etc. Dans l'idée d'écrire du code C++ moderne (donc de qualité), on évitera bien sûr d'écrire du code qui produit un comportement indéterminé.
-Le second problème est que le résultat est vrai, alors que la lettre b est supérieur (dans l'ordre alphabétique) à la lettre a. Vous pouvez essayer avec n'importe quelle lettre (avec Clang sur Coliru), le résultat sera toujours vrai. L'explication de ce comportement nécessite de comprendre le fonctionnement des pointeurs (ce qui sort du cadre de ce cours débutant), mais le principal est de comprendre que cela ne donne pas le résultat attendu.
-Le code similaire avec ''string'' ne posera pas de problème :
-<code cpp main.cpp>
-#include <iostream>
-#include <string>
-int main() {
-    std::string const s1 { "b" };
-    std::string const s2 { "a" };
-    std::cout << std::boolalpha << (s1 < s2) << std::endl;
-}
-</code>
-affiche :
-<code>
-false
-</code>
-En effet, la classe ''string'' implémente l'opérateur ''<'' en respectant la sémantique habituelle de cet opérateur (alors que le type ''char*'' utilise la sémantique des pointeurs). L'utilisation de ''char*'' est donc a éviter en C++ moderne.
-Le code précédent fonctionne aussi si l'on déclare qu'une seule variable de type ''string'' :
-<code cpp main.cpp>
-std::string const s { "b" };
-std::cout << std::boolalpha << (s < "a") << std::endl;
-</code>
-Dans ce cas, c'est bien la sémantique de ''string'' qui est utilisée, pas celle de ''char*''. Pourquoi le compilateur utilise correctement l'opérateur ''<'' de ''string'' et le le fait pas lorsque l'on écrit ''"b" < "a"'' ?
-Le compilateur procède de la façon suivante :
-  * Il commence par rechercher s'il existe un opérateur ''<'' qui correspond aux types utilisés. Donc ''string'' et ''char*'' dans un cas et deux ''char*'' dans l'autre cas. Cet opérateur existe pour les deux ''char*'' (mais s'applique sur les pointeurs, pas sur le contenu de la chaîne de caractères) et est donc utilisé. Dans les cas de ''string'' et ''char*'', aucun opérateur ne convient.
-  * S'il n'existe pas d'opérateur, le compilateur essaie de convertir l'un des types pour trouver un opérateur ''<'' qui existe. Toutes les types ne sont pas convertissables dans n'importe quel autre type. Chaque classes spécifient les conversions qui sont autorisée ou non. Elles spécifient également si la conversion peut être implicite (le compilateur décide tout seul s'il réalise la conversion ou non) ou explicite (l'utilisateur doit écrit spécifiquement la conversion).
-Dans le cas qui nous intéresse, il existe une conversion implicite de ''char*'' en ''string''. Cela signifie que lorsque le compilateur rencontre un type ''char*'', il est autorisé à le convertir en ''string'' sans demander l'autorisation à l'utilisateur. Le compilateur résout donc le code ''s < "a"'' en convertissant la littérale chaîne en ''string'', puis appelle l'opérateur ''<'' qui s'applique sur deux ''string''. Le code ''s < "a"'' est donc interprété par le compilateur de la même façon que le code ''s1 < s2''.
-Il est également possible d'écrire explicitement la conversion d'un type dans un autre en initialisant avec le type. Par exemple :
-<code cpp>
-std::string const s { "b" };
-std::cout << std::boolalpha << (s < std::string { "a" }) << std::endl;
-// ou
-std::cout << std::boolalpha << (std::string { "b" } < "a") << std::endl;
-</code>
-Vous apprendrez dans la partie sur la programmation orientée objet comment créer des classes autorisant les conversions implicites et explicites.
-===== Comparer si une chaîne est inférieure à une autre =====
-==== L'ordre lexicographique ====
-Comme indiqué précédemment, la classe ''string'' permet l'utilisation des opérateurs de comparaison habituels. Mais que signifie exactement la comparaison pour les chaînes de caractères ?
-Comme indiqué dans la [[http://en.cppreference.com/w/cpp/string/basic_strin|documentation]] ("lexicographically compares two strings"), les opérateurs de comparaison utilise l'ordre lexicographique. Cet ordre n'est pas compliqué à comprendre, c'est l'ordre que l'on utilise pour ranger les mots dans un dictionnaire par exemple.
-Pour comparaison deux chaînes de caractères, on commence par prendre le premier caractère de chaque chaîne et on les compare. Si le caractère d'une des chaînes est inférieur (en sens du code ASCII) au caractère de l'autre chaîne, la chaîne correspondante est inférieure à l'autre chaîne. Si les deux caractères sont identiques, on compare les caractères suivant de chaque chaîne. Si une chaîne se termine avant une autre, elle est inférieure. Si tous les caractères sont identiques, les chaînes sont égales.
-Voyons quelques exemples pour bien comprendre. Comparons les chaînes "abc" et "acd". Les premiers caractères sont "a" et "a". Ils sont identiques, on passe aux deuxièmes caractères. Ceux-ci sont "b" et "c". Comme "b" est plus petit que "c", la chaîne "abc" est inférieure à la chaîne "acd".
-Autre exemple. Comparons "abc" et ab". Les premiers et deuxièmes caractères sont identiques, il faudrait donc comparer les troisièmes caractères. Cependant, la seconde chaîne ne possède pas de troisième caractère, elle est donc inférieure à la première.
-<code cpp main.cpp>
-#include <iostream>
-#include <string>
-int main() {
-    std::cout << std::boolalpha;
-    std::cout << (std::string { "abc" } < std::string { "acd" }) << std::endl;
-    std::cout << (std::string { "abc" } < std::string { "ab" }) << std::endl;
-}
-</code>
-affiche :
-<code>
-true
-false
-</code>
-La comparaison "plus petit que" est également un concept ([[http://en.cppreference.com/w/cpp/concept/LessThanComparable|LessThanComparable]]), ce qui implique que différentes propriétés doivent être respecté :
-  * n'importe quelle chaîne n'est pas inférieure à elle-même ;
-  * si une chaîne est inférieur à une seconde chaîne, on peut également dire que la seconde chaîne est n'est pas inférieure à la première (elle est supérieure ou égale) ;
-  * transitivité : si une chaîne a est inférieur à une chaîne b et que cette chaîne b est inférieure à une chaîne c, alors la chaîne a est inférieure à la chaîne c.
-Bien sûr, ce concept est valable également pour les autres types du C++ (''int'', ''float'', etc.) et de la bibliothèque standard (''string'', ''complex'', etc.) qui possèdent des opérateurs de comparaison. Lorsqu'une classe définie un opérateur de comparaison, il est logique aussi que les autres opérateurs soient définies (il faudrait que cela ait un sens de ne pas les définir). Vous apprendrez dans la partie sur la programmation orientée objet (en particulier dans la partie sur la sémantique de valeur) comment définir ces opérateurs dans une classe que vous créez.
-==== Les algorithmes de comparaison ====
-Les opérateurs de comparaison utilisés jusque maintenant sont définis en même temps que la classe à laquelle ils s'appliquent (''string'' dans ce chapitre). Comme il n'est pas autorisé de modifier les classes de la bibliothèque standard, il n'est pas possible de modifier les algorithmes utilisés pour la comparaison de chaînes.
-Bien sûr, une solution pour contourner le problème serait de réécrire cette classe ''string'' dans un nouvel espace de nom différent de ''std''. Mais cela serait contraire au principe de réutilisation du code (un développeur intelligent est un développeur fainéant, réécrire une classe complète juste pour modifier le comportement d'un opérateur, c'est beaucoup de travail pour pas grand chose).
-Heureusement, la bibliothèque standard a été conçu pour être réutilisable au maximum (n'hésitez pas à vous en inspirer lorsque vous créerez vos propres classes). L'idée pour rendre ''string'' (et bien d'autres classes de la bibliothèque standard, nous reviendrons dessus plus tard) est de séparer la partie "structure de données" et la partie "algorithmes". De cette façon, il est possible d'écrire facilement de nouveaux algorithmes s'appliquant sur des classes existantes, mais également d'utiliser les algorithmes existants sur les nouvelles classes que vous créez.
-Pour rendre les structures de données utilisables par les différents algorithmes de la bibliothèque standard, elles doivent respecter un nouveau concept : celui de "collection". Une collection est une ensemble d'éléments (''string'' est un ensemble de caractères) qui respecte les propriétés suivantes :
-  * avoir un premier élément, accessible en utilisant la fonction ''begin'' (en fonction libre ou en fonction membre) ;
-  * avoir un dernier élément, accessible en utilisant la fonction ''end'' (également en fonction libre ou en fonction membre) ;
-  * respecter la notion "élément suivant", c'est-à-dire que chaque élément d'une collection possède un et un seul élément suivant. Cette élément est accessible en utilisant l'opérateur ''++'' ou la fonction libre ''next''.
-Il est alors possible de parcourir une collection depuis le premier élément jusqu'au dernier en passant d'un élément au suivant.
-Pour rappel, une fonction membre s'écrit en utilisant l'opérateur ''.'' entre le nom d'une variable et la fonction membre. Une fonction libre s'applique sur une variable en la donnant en argument entre parenthèses. Les deux syntaxes sont identiques en termes de comportement du programme.
-<code cpp>
-std::string const s {};
-// premier élément
-s.begin(); // fonction membre
-begin(s);  // fonction libre
-// dernier élément
-s.end();   // fonction membre
-end(s);    // fonction libre
-</code>
-Les algorithmes de la bibliothèque standard s'appliquent sur une collection en donnant en argument le premier et le dernier élément de la collection sur laquelle on souhaite appliquer l'algorithme. Par exemple, pour appliquer l'algorithme ''sort'' (qui permet de trier les éléments d'une collection), on écrira :
-<code cpp>
-#include <iostream>
-#include <string>
-#include <algorithm>
-int main() {
-	std::string s { "azerty" };
-	std::sort(begin(s), end(s));
-	std::cout << s << std::endl;
-}
-</code>
-affiche :
-<code>
-aertyz
-</code>
-L'inclusion de l'en-tête ''<algorithm>'' permet d'utiliser les algorithmes de la bibliothèques standard.
-<note information>
-On peut se demander pourquoi passer en argument des fonctions le premier et le dernier élément d'une collection, au lieu de passer la collection complète en argument (en écrivant par exemple ''std::sort(s)''). La raison est que cela permet d'utiliser les algorithmes également sur une partie d'une collection au lieu de la collection complète.
-En effet, les algorithmes prennent en paramètre le premier et le dernier élément sur lesquels s'appliquent l'algorithme, qui ne sont pas forcement les premier et dernier élément de la collection. Il est ainsi possible de trier une chaîne à partir du troisième élément en écrivant ''std::sort(begin(s)+3, end(s))''.
-Attention, cette syntaxe nécessite que la chaîne contienne au moins trois caractères, sous peine d'obtenir un comportement indéterminé. La manipulation des collections élément par élément sera vu dans un prochain chapitre.
-</note>
-La bibliothèque standard propose quelques algorithmes de comparaison, dont le comportement est similaire aux opérateurs de comparaison de ''string''. Pour comparer si deux chaines (et plus généralement, deux collections) sont identiques, vous pouvez utiliser la fonction ''equal'', qui prend en paramètre le premier élément et le dernier élément d'une collection et le premier élément d'une autre collection et retourne un booléen qui est vrai si les collections sont identiques.
-<code cpp main.cpp>
-#include <iostream>
-#include <string>
-#include <algorithm>
-int main() {
-	std::string const s1 { "azerty" };
-	std::string const s2 { "azerty" };
-	std::string const s3 { "abcdef" };
-	std::cout << std::boolalpha;
-	std::cout << std::equal(begin(s1), end(s1), begin(s2)) << std::endl;
-	std::cout << std::equal(begin(s1), end(s1), begin(s3)) << std::endl;
-}
-</code>
-affiche :
-<code>
-true
-false
-</code>
-<note warning>
-Attention aux éléments que vous passez en argument dans les fonctions. Le compilateur vérifie que vous passer effectivement trois éléments de collections identiques en argument, pas que ces éléments ont un sens. Par exemple, si vous passer en argument un élément d'une collection puis un élément d'une seconde collection, cela n'a pas de sens de parcourir une collection entre ce deux éléments.
-<code cpp>
-std::equal(begin(s1), end(s2), begin(s2)); // erreur, les deux premiers arguments
-                                           // ne proviennent pas de la même collection
-</code>
-Dans ce cas, ce code ne produit pas d'erreur de compilation, mais un comportement indéterminé (//undefined behavior//). Ce type d'erreur est assez complexe à détecter et à corriger, il faut être très attentif pour les éviter.
-</note>
-Le second algorithme de comparaison permet de réaliser la comparaison par ordre lexicographique. La fonction ''lexicographical_compare'' prend en argument les premiers et derniers éléments de deux collections que l'on souhaite comparer et retourne vrai si la première collection est inférieure à la seconde. Par exemple :
-<code cpp main.cpp>
-#include <iostream>
-#include <string>
-#include <algorithm>
-int main() {
-	std::string const s1 { "azerty" };
-	std::string const s2 { "azerty" };
-	std::string const s3 { "abcdef" };
-	std::cout << std::boolalpha;
-	std::cout << std::lexicographical_compare(begin(s1), end(s1), begin(s2), end(s2)) << std::endl;
-	std::cout << std::lexicographical_compare(begin(s1), end(s1), begin(s3), end(s3)) << std::endl;
-}
-</code>
-affiche :
-<code>
-false
-false
-</code>
-__ rbegin et rend ? __
-===== Valider qu'une chaîne correspond à un motif =====
-Pour terminer ce chapitre sur la comparaison de chaînes, voyons l'utilisation des motifs pour valider une chaîne. La fonction correspondante, ''std::regex_match'', a déjà été utilisée dans les chapitres sur les expressions régulières pour présenter leur syntaxe. Pour rappel, la syntaxe de base prend simplement en arguments la séquence cible et le motif et retourne vrai si la séquence correspond au motif.
-<code>
-std::regex pattern { "abc" };
-std::string target { "abcdef" };
-bool result = std::regex_match(target, pattern);
-</code>
-Il est également possible d'utiliser cette fonction en passant en arguments les premier et dernier éléments de la séquence cible, comme pour les algorithmes.
-<code cpp>
-std::regex_match(begin(target), end(target), pattern);
-</code>
-__ match flags ? http://en.cppreference.com/w/cpp/regex/match_flag_type __
-__ exemples : https://support.google.com/a/answer/1371417?hl=fr __
-===== Résumé des concepts vu dans ce chapitre =====
-Ce chapitre présente plusieurs concepts, qui sont intéressant de retenir :
-  * constructible
-  * copiable
-  * comparable
-  * plus petit que
-Ces différents concepts sont liés à un concept plus globale, la sémantique de valeur.
-Collection
-^ [[expressions_regulieres|Chapitre précédent]] ^ [[programmez_avec_le_langage_c|Sommaire principal]] ^ [[rechercher_string|Chapitre suivant]] ^
-{{tag> Cours C++}}

C++, Qt, OpenGL, CUDA

Outils d'utilisateurs

Outils du Site

Différences

Outils de la Page