Différences

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

--- comparer [2015/12/23 20:07]
panda_w [Comparer des parties de collections]
+++ comparer [2019/04/11 22:07] (Version actuelle)
foxdry42 [Comparer les éléments un par un]
@@ Ligne 1: / Ligne 1: @@
-^ Chapitre précédent ^ [[programmez_avec_le_langage_c|Sommaire principal]] ^ Chapitre suivant ^
+^ [[collection2|Chapitre précédent]] ^ [[programmez_avec_le_langage_c|Sommaire principal]] ^ [[rechercher|Chapitre suivant]] ^
-====== Comparer des collections ======
-Pour comparer si deux "choses" sont égales, le plus simple sera généralement d'utiliser l'opérateur de comparaison ''=='' que vous avez déjà vu. Cet opérateur fonctionne aussi bien pour les types fondamentaux du C++ (//build-in types//, comme ''int'', ''float'', etc.) que pour certains types de classe (les classes à sémantique de valeur). Il est également possible d'utiliser des algorithmes dans les cas d'utilisation plus spécifiques.
+====== Introduction aux algorithmes standards ======
+Même si les collections offrent plus de fonctionnalités que les concepts de base ''begin'' et ''end'', il est déjà possible d'utiliser plusieurs types d'algorithmes de la bibliothèque standard. Les différents concepts plus avancés, tels que les itérateurs, vont être introduit en même temps que des exemples d'algorithmes (recherche d'un élément, trier les éléments d'une collection, etc). Et pour commencer, ce chapitre détaille les algorithmes de comparaison.
 ===== L'opérateurs d'égalité =====
-Dans les chapitres précédents, vous avez vu l'utilisation de l'opérateur de comparaison ''=='' (//egal-to operator//). Les collections de la bibliothèque standard, comme ''vector'', ''array'' ou ''string'', fournissent également cet opérateur. Vous pouvez donc écrire :
+Dans les chapitres précédents, vous avez vu l'utilisation de l'opérateur de comparaison ''=='' (//egal-to operator//). Les collections de la bibliothèque standard, comme ''std::vector'', ''std::array'' ou ''std::string'', fournissent également cet opérateur. Vous pouvez donc écrire :
 <code cpp main.cpp>
@@ Ligne 31: / Ligne 32: @@
 </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 :
+Il ne faut pas oublier les parenthèses autour du test d'égalité pour ''std::string''. L'opérateur ''<<'' ayant un sens pour cette classe, le compilateur ne pourra pas savoir si vous souhaitez écrire :
 <code cpp>
@@ Ligne 38: / Ligne 39: @@
 </code>
-De même pour les collections :
+De la même façon pour les tableaux, il est possible d'utiliser l’opérateur ''==''.
 <code cpp main.cpp>
@@ Ligne 61: / Ligne 62: @@
 </code>
-Avec les collections, l'opérateur d'égalité compare les éléments de la collection un par un et s'il trouve une différence, il retourne ''false''. S'il arrive à la fin de la collection sans trouver de différence, il retourne ''true''.
+Avec les collections, l'opérateur d'égalité compare les éléments de la collection un par un. S'il trouve une différence, il retourne ''false''. S'il arrive à la fin de la collection sans trouver de différence, il retourne ''true''.
-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)''. Plus simplement, on peut directement utiliser l'opérateur de comparaison ''!='' (//not-equal-to operator//).
+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)''. Plus simplement, il est possible d'utiliser l'opérateur de comparaison ''!='' (//not-equal-to operator//).
 <code cpp main.cpp>
@@ Ligne 85: / Ligne 86: @@
 </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 :
+On voit ici que les opérateurs ''=='' et ''!='' sont étroitement liés. Lorsque l'un de ces deux opérateurs est utilisable, il est habituel de pouvoir utiliser aussi l'autre opérateur.
+Une classe qui propose l'opérateur d'égalité ''=='' 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 ;
@@ Ligne 91: / Ligne 94: @@
   * 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, l'écriture de la classe en découlera.
+Ce concept est assez classique, vous le retrouvez en mathématique dans la théorie des ensembles. vous voyez ici un point important : lorsqu'une classe définit un opérateur ''=='', vous pouvez vous attendre à ce qu'elle suive un certain nombre de règles : elle suit une **sémantique**.
-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 ?
+Du point de vue de l'utilisateur de cette classe, il pourra l'utiliser de la même façon qu'il utilise n'importe quelle classe respectant cette sémantique. 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 vous souhaitez donner à votre classe, l'écriture de la classe en découlera.
-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.)
+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 ? Ou n'importe quoi d'autres, selon la classe ? La cohérence et l'homogénéité des syntaxes sont des notions importantes pour faciliter la lecture d'un code (et donc éviter les erreurs).
-===== La sémantique de valeur =====
+Bien sûr, ces considérations s'appliquent à l'ensemble des sémantiques usuelles, en particulier celle que vous connaissez en mathématique (addition avec ''+'', soustraction avec ''-'', etc.)
-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" que l'on a vu avant). 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 autoriser ou interdire l'utilisation d'autres concepts (par exemple, le concept "est égal" autorise l'utilisation du concept "est différent").
-C'est le 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 :
+===== Comparer les éléments un par un =====
-**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).
+Si vous souhaitez comparer les éléments de deux collections un par un, deux sous-ensembles de collections ou si vous souhaitez utiliser un prédicat différent, il ne sera pas possible d'utiliser l'opérateur d'égalité ''==''. Dans ce cas, la bibliothèque standard fournit l'algorithme ''std::equal'' pour comparer si les éléments de deux collections.
-<code cpp>
+Lorsque vous découvrez une nouvelle fonctionnalité, la première chose à faire est de regarder la documentation : [[http://en.cppreference.com/w/cpp/algorithm/equal|std::equal]]. Cette page peut vous apprendre plusieurs choses :
-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 :
+  * cet algorithme est défini dans le fichier d'en-tête ''<algorithm>'', il faudra donc l'inclure dans votre code pour utiliser ''std::equal'' ;
-<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. Pour les collections (''vector'', ''array'', etc.), l'opérateur ''+'' n'est pas défini (c'est un choix des concepteurs, ils auraient pu définir l'opérateur ''+'' pour fussionner deux collections, mais pour des raisons de sémantique, ce n'est pas le cas).
-<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. Pour les distinguer, le plus simple est de se poser des questions sur ce que peut faire une classe ou non.
-  * Est-ce que cela à un sens de pouvoir copier un objet ?
-  * Est-ce que cela à un sens de tester si deux objets sont égaux ?
-  * Est-ce que cela à un sens d’additionner deux objets ?
-La majorité des classes de la bibliothèque standard sont à sémantique de valeur. Vous verrez dans la partie sur la programmation objet comment identifier et créer des classes à sémantique d'entité.</note>
-===== Les algorithmes d'égalité =====
-Si vous souhaitez comparer deux sous-ensembles de collections ou si vous souhaitez utiliser un prédicat différent, il ne sera pas possible d'utiliser l'opérateur d'égalité ''==''. Dans ce cas, la bibliothèque standard fournit l'algorithme ''std::equal'' pour comparer si deux collections sont identiques ou non.
-Lorsque l'on découvre une nouvelle fonction, la première chose à faire est de jetter un coup d'oeil sur la documentation : [[http://en.cppreference.com/w/cpp/algorithm/equal|std::equal]]. Cette page nous apprend plusieurs choses :
-  * cet algorithme est défini dans le fichier d'en-tête ''<algorithm>'', il faudra donc l'inclure dans votre code pour utiliser ''equal'' ;
   * il existe quatre versions de cet algorithme :
     * le premier prend en argument le début et la fin d'une première collection et le début d'une seconde collection ;
@@ Ligne 186: / Ligne 115: @@
     * la troisième prend en argument le début et la fin de la première collection, puis de la seconde ;
     * le quatrième est similaire au troisième, avec un prédicat personnalisé.
-  * le prédicat doit respecter la signature suivante : ''bool pred(const Type1 &a, const Type2 &b);'' (c'est donc une fonction binaire - une fonction qui prend deux arguments - et retourne un booléen).
+  * le prédicat doit respecter la signature suivante : ''bool pred(const Type1 &a, const Type2 &b);''. C'est donc une fonction binaire - une fonction qui prend deux arguments - et retourne un booléen.
 La page de documentation donne également des codes d'exemple d'utilisation de ces fonctions.
-La première (et deuxième) version de ''equal'' doit être utilisé avec précaution. Si on compare par exemple deux collections de tailles différentes (par exemple les chaînes ''"abcd"'' et ''"abcdEF"''), la comparaison se terminera lorsque l'algorithme atteint la fin de la première collection donnée en argument. Dans ce cas, les deux chaînes seront considérées comme égale, alors que ce sont simplement les premiers caractères de la première chaîne qui sont retrouvé dans la seconde.
+La première et deuxième version de ''std::equal'' doit être utilisé avec précaution. Ces deux fonctions comparent les éléments un par un et s’arrête à la fin de la première collection. Si la seconde collection est plus grande que la première (par exemple les chaînes ''"abcd"'' et ''"abcdEF"''), la comparaison se terminera sans prendre en compte les derniers éléments et ''std::equal'' retournera vrai, alors que ce n'est pas forcément le cas.
+Si la seconde collection est plus petite que la première, ''std::equal'' continuera de travailler après la fin de la seconde collection, ce qui produira un crash, voire un comportement indéfini.
+Dans les deux cas, il est possible de résoudre le problème en comparant les tailles respectives de deux collections avant d'utiliser ''std::equal''. Si les tailles sont différentes, alors il n'est pas nécessaire d'utiliser ''std::equal'' dans ce cas.
-La troisième (et quatrième) version de ''equal'' permet de tester si l'algorithme est arrivé à la fin des deux collections et donc qu'elle sont parfaitement identiques. Voici un code d'exemple pour illustrer ce point :
+La troisième (et quatrième) version de ''std::equal'' permet de tester si l'algorithme est arrivé à la fin des deux collections et donc qu'elle sont parfaitement identiques. Voici un code d'exemple pour illustrer ce problème :
 <code cpp>
@@ Ligne 224: / Ligne 157: @@
 <note warning>
-Attention aux éléments que vous passez en argument dans les fonctions. Le compilateur vérifie que vous passer des collections de types identiques en argument, pas que les informations passées 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.
+Attention aux éléments que vous passez en argument dans les fonctions. Le compilateur vérifie que vous passez des collections de types identiques en argument, pas que les informations passées n'aient aucun sens. Par exemple, si vous passez 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 ces deux éléments.
 <code cpp>
-std::equal(begin(s1), end(s2), begin(s2)); // erreur, les deux premiers arguments
+std::equal(begin(s1), end(s2), begin(s2)); // problème, les deux premiers arguments
                                            // ne proviennent pas de la même collection
 </code>
@@ Ligne 234: / Ligne 167: @@
 </note>
-==== Comparer des collections différentes ====
-Comme cela a été dit auparavant, la classe ''string'' peut être vu comme une collection de caractères (''char''). Cependant, si on essaie de comparer une variable de type ''string'' à un tableau de caractères, on obtient une erreur :
+===== Comparer des collections différentes =====
+Comme cela a été dit auparavant, la classe ''std::string'' peut être vu comme une collection de caractères (''char''). Cependant, si on essaie de comparer une variable de type ''string'' à un tableau de caractères, on obtient une erreur :
 <code cpp main.cpp>
@@ Ligne 242: / Ligne 176: @@
 #include <string>
 #include <vector>
-#include <algorithm>
 int main() {
     std::string const s { "abcdef" };
-    std::vector<char> const a { 'a', 'b', 'c', 'd', 'e', 'f' };
+    std::vector<char> const v { 'a', 'b', 'c', 'd', 'e', 'f' };
     std::cout << std::boolalpha;
-    std::cout << (s == a) << std::endl;
+    std::cout << (s == v) << std::endl;
 }
 </code>
@@ Ligne 255: / Ligne 188: @@
 <code>
-main.cpp:10:21: error: invalid operands to binary expression ('const std::string'
+main.cpp:9:21: error: invalid operands to binary expression ('const std::string'
 (aka 'const basic_string<char, char_traits<char>, allocator<char> >') and
 'const std::vector<char>')
-    std::cout << (s == a) << std::endl;
+    std::cout << (s == v) << std::endl;
                   ~ ^  ~
 error generated.
 </code>
-Cette erreur signifie que le compilateur ne trouve pas d'opérateur d'égalité ''=='' permettant de comparer un type ''string'' avec un type ''vector<char>''. En effet, les opérateurs de comparaison sont définis pour accepter deux arguments de même type, par exemple deux ''string'' ou deux ''vector<char>'', mais pas deux collection de type différents, même si ces deux types correspondent tous deux à des collections de ''char'' (on parle parfois de typage "fort" du C++).
+Cette erreur signifie que le compilateur ne trouve pas d'opérateur d'égalité ''=='' permettant de comparer un type ''std::string'' avec un type ''std::vector<char>''. En effet, les opérateurs de comparaison sont définis pour accepter deux arguments de même type, par exemple deux ''string'' ou deux ''vector<char>'', mais pas deux collections de type différents, même si ces deux types correspondent tous deux à des collections de ''char'' (on parle parfois de typage "fort" du C++).
-Dans cette situation, il est possible d'utiliser la fonction ''equal'' pour tester l'égalité de deux collections. Cet algorithme fonctionne sur des collections de types différents, à partir du moment où les éléments sont comparable par égalité. Par exemple, il sera possible de comparer des ''string'' et des ''vector<char>'' (les éléments sont dans les deux cas des ''char'') ou des ''vector<int>'' et ''vector<float>'' (il est possible de comparer un entier et un nombre réel), mais pas ''vector<int>'' et ''vector<string>'' (''int'' et ''string'' ne sont pas comparable par égalité).
+Dans cette situation, il est possible d'utiliser la fonction ''std::equal'' pour tester l'égalité de deux collections. Cet algorithme fonctionne sur des collections de types différents, à partir du moment où les éléments sont comparable par égalité. Par exemple, il sera possible de comparer des ''std::string'' et des ''std::vector<char>'' (les éléments sont dans les deux cas des ''char'') ou des ''std::vector<int>'' et ''std::vector<float>'' (il est possible de comparer un entier et un nombre réel), mais pas ''std::vector<int>'' et ''std::vector<string>'' (''int'' et ''string'' ne sont pas comparable par égalité).
 En utilisant ''std::equal'', la comparaison devient :
@@ Ligne 292: / Ligne 225: @@
 </code>
-==== Comparer des parties de collections ====
+Ce qui correspond bien a une comparaison des éléments un par un.
-Avec ''equal'', il est possible de comparer un partie d'une collection. Pour cela, il suffit de fournir des positions différentes que le début et la fin d'une collection. Par exemple, vous pouvez incrémenter ou décrémenter les positions de début (avec ''begin(s)+n'') et de fin (avec ''end(s)-n'') en faisant attention de ne pas donner des valeurs en dehors de la collection ou en utilisant des fonctions de recherche (''find'', que vous verrez dans un prochain chapitre).
+===== Comparer des parties de collections =====
+Avec ''std::equal'', il est possible de comparer une partie d'une collection. Pour cela, il suffit de fournir des positions différentes que le début et la fin d'une collection. Par exemple, vous pouvez incrémenter ou décrémenter les positions de début (avec ''begin(s)+n'') et de fin (avec ''end(s)-n'') en faisant attention de ne pas donner des valeurs en dehors de la collection ou en utilisant des fonctions de recherche (''std::find'', que vous verrez dans un prochain chapitre).
 Par exemple, pour comparer les quatre premiers éléments de deux collections, vous pouvez écrire :
@@ Ligne 319: / Ligne 255: @@
 </code>
-La première version compare la totalité des deux chaînes (''"abcdef"'' et ''"abcdEF"'') et retourne ''false''. La seconde version compare le début de la première chaîne (à partir de ''begin(s1)'' donc ''"a"'' jusqu'au quatrième caractère ''begin(s1)+4'' donc ''"d"'') avec le début de la seconde (également ''"abcd"'') et retourne ''true''.
+La première version compare la totalité des deux chaînes (''"abcdef"'' et ''"abcdEF"'') et retourne faux, puisque la chaîne ''s2'' contient des majuscules. La seconde version compare le début de la première chaîne (à partir de ''begin(s1)'' donc ''"a"'' jusqu'au quatrième caractère ''begin(s1)+4'' donc ''"d"'') avec le début de la seconde (également ''"abcd"'') et retourne vrai.
-**Attention** en utilisant la notation ''begin(s)+n'', si vous sortez de la collection, cela produit un comportement indéterminé (//undefined behavior//), donc aucun message d'erreur vous prévenant qu'il y a un problème.
+<note warning>En utilisant la notation ''begin(s)+n'', si vous sortez de la collection, cela produit un comportement indéterminé (//undefined behavior//). Il n'y a aucun message d'erreur vous prévenant qu'il y a un problème.</note>
-==== Utiliser un prédicat personnalisé ====
+Faites bien attention de ne pas perdre de vue ce que vous comparez. Ce n'est pas parce que vous utilisez ''std::equal'' ("égal" en français) que vos collection son "égales". Seuls les éléments que vous comparez sont "egaux" (donc potentiellement des collections de tailles ou de types différents, voire des éléments de type différents). Ce n'est pas une "égalité" stricte.
-Lorsque les collections contiennent des éléments de types non comparables ou lorsque la comparaison d'égalité par défaut ne convient pas, il est possible de fournir un prédicat personnalisé dans ''std::equal''. Par exemple, si vous souhaitez comparer deux chaînes de caractères, sans prendre en compte la casse (c'est-à-dire sans prendre en compte les majuscules ou minuscules), il n'est pas possible d'utiliser l'opérateur ''=='' classique.
-La solution dans ce cas est d'utiliser la fonction de conversion ''std::toupper'' (ou ''std::tolower'') pour convertir tous les caractères en majuscule pour faire la comparaison. Pour écrire ce prédicat, le plus simple dans ce cas est d'écrire une fonction lambda.
+===== Utiliser un prédicat personnalisé =====
-Cette fonction lambda doit faire la comparaison entre deux éléments et retourner un booléen. La signature sera la même que cela que vous avez déjà vu :
+Par défaut, l'algorithme ''std::equal'' compare chaque élément de deux collections en utilisant l’opérateur ''=='' de chaque élément. En pseudo-code, cela donnerait :
+<code>
+si premier élément de collection 1 est différent du premier élément de collection 2
+    alors retourner "les collections sont différentes"
+si deuxième élément de collection 1 est différent du deuxième élément de collection 2
+    alors retourner "les collections sont différentes"
+si troisième élément de collection 1 est différent du troisième élément de collection 2
+    alors retourner "les collections sont différentes"
+...
+Si tous les éléments sont identiques
+    alors retourner "les collections sont identiques"
+</code>
+Lorsque les collections contiennent des éléments de types non comparables ou lorsque la comparaison d'égalité par défaut ne convient pas, il est possible de fournir un prédicat personnalisé dans ''std::equal''.
+Un prédicat est "quelque chose" qui prend des arguments et retourne un booléen. Vous utiliserez principalement des prédicats avec un argument (prédicat unaire) ou deux arguments (prédicat binaire) avec les algorithmes de la bibliothèque standard.
 <code cpp>
-[](auto lhs, auto rhs){ return expression_booléenne_avec_lhs_et_rhs; }
+bool result_1 = predicat_unaire(argument_1);
+bool result_2 = predicat_binaire(argument_1, argument_2);
 </code>
-Les paramètres ''lhs'' et ''rhs'' sont les éléments des collections (des caractères dans cet exemple) qui sont comparés deux à deux. Pour convertir ces deux valeurs en majuscule, il faudra donc écrire : ''std::toupper(lhs)'' et ''std::toupper(rhs)''. Au final, la comparaison s'écrit :
+<note>
+Ce "quelque chose" n'est volontairement pas défini pour le moment, cela peut correspondre à différentes syntaxes que vous verrez plus tard dans ce cours (une fonction libre, une fonction lambda, un foncteur). Le plus important est donc de retenir que c'est "quelque chose" qui peut s'utiliser de la façon donnée dans le code.
+Vous reconnaissez la syntaxe pour appeler une fonction. Plus généralement, il est possible d'utiliser n'importe quel objet qui peut s'utiliser comme une fonction (//callable-object//, "objet appelable").
+</note>
+Ce prédicat sera utilisée à la place de l’opérateur ''=='' pour la comparaison des éléments un par un. En pseudo-code, cela donnerait :
+<code>
+si prédicat(premier élément de collection 1, premier élément de collection 2)
+    alors retourner "les collections sont différentes"
+si prédicat(deuxième élément de collection 1, deuxième élément de collection 2)
+    alors retourner "les collections sont différentes"
+si prédicat(troisième élément de collection 1, troisième élément de collection 2)
+    alors retourner "les collections sont différentes"
+...
+Si tous les éléments sont identiques
+    alors retourner "les collections sont identiques"
+</code>
+==== Les objets-fonctions ====
+La bibliothèque standard fournit quelques prédicats de base, décris dans la documentation ([[http://en.cppreference.com/w/cpp/utility/functional
+|Function objects]]) et inclus dans le fichier d’en-tête ''<functional>''. Ces prédicats sont simples à comprendre, ils correspondent aux opérateurs logiques (''logical_and'', ''logical_or'' et ''logical_not'') et de comparaison (''equal_to'', ''not_equal_to'', ''greater'', ''less'', ''greater_equal'' et ''less_equal'') que vous avez déjà vu.
+<note>Attention de ne pas confondre l'algorithme ''std::equal'' et le prédicat ''std::equal_to''.</note>
+Les autres objets-fonctions seront utiles pour les autres algorithmes de la bibliothèque standard, que vous verrez par la suite.
+Les objets-fonctions peuvent être appelés comme des fonctions, mais sont avant tout des objets. Il est donc nécessaire dans un premier temps de créer l'objet avant de pouvoir l'utiliser. La création d'un objet-fonction est similaire à n'importe quelle création d'objet.
 <code cpp>
-return std::toupper(lhs) == std::toupper(rhs);
+std::equal_to<TYPE>()
+std::equal_to<>()
 </code>
-Le code complet pour la comparaison est (ne pas oublier d'inclure le fichier d'en-tête ''<cctype>'' pour utiliser ''toupper'') :
+Les objets-fonctions de la bibliothèque standard sont des classes template et s’écrivent donc avec des chevrons ''<>''. Il est possible de spécifier le type du prédicat entre les chevrons (ce qui produira une erreur si vous essayez d'utiliser le prédicat avec un type non compatible) ou de laisser les chevrons vides pour accepter n'importe quel type comparable.
+L'objet crée peut ensuite être appelée comme une fonction.
 <code cpp>
+const auto predicat = std::equal_to<>();
+std::cout << predicat(1, 2) << std::endl;
+</code>
+Le code suivant :
+<code cpp main.cpp>
 #include <iostream>
-#include <string>
+#include <functional>
-#include <algorithm>
-#include <cctype>
 int main() {
-    std::string const s1 { "abcdef" };
+    const auto predicat = std::equal_to&lt;&gt;();
-    std::string const s2 { &quot;abcdEF&quot; };
     std::cout << std::boolalpha;
-    std::cout << std::equal(begin(s1), end(s1), begin(s2), end(s2)) << std::endl;
+    std::cout << predicat(1, 2) << std::endl;
-    std::cout << std::equal(begin(s1), end(s1), begin(s2), end(s2),
+    std::cout << predicat(1, 1.0) << std::endl;
-        [](auto lhs, auto rhs){ return std::toupper(lhs) == std::toupper(rhs); })
+    std::cout << predicat('a', 'b') << std::endl;
-        << std::endl;
+    std::cout << predicat('a', 'a') << std::endl;
+    std::cout << predicat("azerty", "abcdef") << std::endl;
+    std::cout << predicat("azerty", "azerty";) << std::endl;
 }
 </code>
-affiche :
+affiche ;
 <code>
 false
 true
+false
+true
+false
+true
+</code>
+Il n'est pas nécessaire de créer une variable intermédiaire pour créer un objet-fonction, mais cela permet d'avoir un code plus lisible.
+Notez bien l'utilisation des parenthèses :
+  * la première paire pour créer l'objet-fonction ;
+  * la seconde pour appeler la fonction.
+Si vous ne souhaitez pas créer de variable intermédiaire, il faut bien mettre les deux paires de parenthèses (cette syntaxe trouble parfois les débutants).
+<code cpp main.cpp>
+#include <iostream>
+#include <functional>
+int main() {
+    std::cout << std::boolalpha;
+    std::cout << std::equal_to<>()(1, 2) << std::endl;
+    std::cout << std::equal_to<>()(1, 1.0) << std::endl;
+    std::cout << std::equal_to<>()('a', 'b') << std::endl;
+    std::cout << std::equal_to<>()('a', 'a') << std::endl;
+    std::cout << std::equal_to<>()("azerty", "abcdef") << std::endl;
+    std::cout << std::equal_to<>()("azerty", "azerty") << std::endl;
+}
+</code>
+==== Les algorithmes avec prédicats personnalisés ====
+Les prédicats peuvent être utilisés avec les algorithmes de la bibliothèque standard. Dans ce cas, les algorithmes appellent directement le prédicat sur les éléments d'une collection. Cela implique qu'il faut donner un objet directement appelable, donc qu'il faut instancier l'objet-fonction avant de la passer en argument d'un algorithme.
+Pour tous les algorithmes de la bibliothèque standard qui acceptent un prédicat, celui-ci est donné en dernier argument. Par exemple, avec ''std::equal'', la syntaxe devient :
+<code cpp>
+std::equal(itérateur, itérateur, itérateur, itérateur)
+std::equal(itérateur, itérateur, itérateur, itérateur, PRÉDICAT)
+</code>
+Il est possible de créer une variable intermédiaire pour le prédicat ou de l'instancier directement dans l'appel de l'algorithme.
+<code cpp>
+#include <iostream>
+#include <vector>
+#include <functional>
+int main() {
+    const std::vector<int> v { 1, 2, 3, 4, 5 };
+    const std::vector<int> w { 2, 4, 3, 1, 5 };
+    std::cout << std::boolalpha;
+    std::cout << std::equal(begin(v), end(v), begin(v), end(v), std::equal_to<>()) << std::endl;
+    std::cout << std::equal(begin(v), end(v), begin(w), end(w), std::equal_to<>()) << std::endl;
+    std::cout << std::equal(begin(v), end(v), begin(v), end(v), std::not_equal_to<>()) << std::endl;
+    std::cout << std::equal(begin(v), end(v), begin(w), end(w), std::not_equal_to<>()) << std::endl;
+}
+</code>
+affiche :
+<code>
+true
+false
+false
+false
+</code>
+**Exercice**
+Est-ce que les deux syntaxes suivantes donnent le même résultat ? C'est-à-dire de comparer si deux collections sont différentes. (Notez bien l’opérateur de négation logique ''!'' dans la seconde ligne).
+<code cpp>
+bool result_1 =   std::equal(begin(v), end(v), begin(w), end(w), std::not_equal_to<>());
+bool result_2 = ! std::equal(begin(v), end(v), begin(w), end(w));
 </code>
-La première version prend en compte la casse et retourne ''false'' alors que la seconde version ne la prend pas en compte et considère que les deux chaînes sont identiques.
 ===== L'ordre lexicographique =====
-Comme indiqué précédemment, la sémantique de valeur autorise l'utilisation des opérateurs de comparaison habituels : ''<'' (plus petit que), ''<='' (plus petit ou égal), ''>'' (plus grand que) et ''>='' (plus grand ou égal). Les collections de la bibliothèque standard respectent la sémantique de valeur, il n'est donc pas étonnant que l'on puisse utiliser ces opérateurs avec les classes comme ''vector'' ou ''string''. Mais que signifie ces comparaisons dans le cas de collections ?
+L’égalité et l’inégalité de deux collections est simple a définir : deux collections sont égales si elles contiennent les mêmes éléments (même nombre d’éléments, dans le même ordre). Elles sont différentes dans le cas contraire.
-Comme indiqué dans la documentation (par exemple pour [[http://en.cppreference.com/w/cpp/string/basic_string|string]] : "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.
+Mais quel sens donner à la phrase "une collection est inférieure à une autre collection" ?
-Pour comparaison deux collections, on commence par prendre le premier élément de chaque collection et on les compare. Si l'un des éléments d'une des chaînes est inférieur à l'élément de l'autre collection, la collection correspondante est inférieure à l'autre. Si les deux éléments sont égaux, on compare les éléments suivants de chaque collection. Si une collection se termine avant l'autre, elle est inférieure. Si tous les éléments sont identiques, les collections sont égales.
+L'ordre lexicographique est une méthode qui permet de comparer deux collections. Même si vous ne connaissez pas le terme, vous connaissez obligatoirement cette méthode : c'est celle qui est utilisée pour trier des mots, en particulier dans un dictionnaire. (N'oubliez pas qu'une chaîne de caractères peut être vue comme une collection de caractères).
-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".
+Pour rappel, voici comment appliquer cette méthode :
-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.
+  * Commencez par prendre le premier élément de chaque collection et comparez les.
+  * Si l'un des éléments d'une des collections est inférieur à l'élément de l'autre collection, la collection correspondante est inférieure à l'autre.
+  * Si les deux éléments sont égaux, comparez les éléments suivants de chaque collection.
+  * Si une collection se termine avant l'autre, elle est inférieure àl'autre.
+  * Si tous les éléments sont identiques, les collections sont égales.
-De même avec une collection d'entiers. On aura par exemple la collection ''{ 1, 2, 3 }'' qui sera inférieure à la collection ''{ 1, 2, 4 }'' et supérieure à la collection ''{ 1, 2 }''.
+Voici un exemple pour bien comprendre, avec les chaînes "abc" et "acd". Les premiers caractères sont "a" et "a". Ils sont identiques, passez 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".
+Un autre exemple, comparez "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.
+De même avec une collection d'entiers. Par exemple, la collection ''{ 1, 2, 3 }'' sera inférieure à la collection ''{ 1, 2, 4 }'' et supérieure à la collection ''{ 1, 2 }''.
 <code cpp main.cpp>
 #include <iostream>
 #include <string>
+#include <vector>
 int main() {
@@ Ligne 391: / Ligne 476: @@
     std::cout << (std::string { "abc" } < std::string { "acd" }) << std::endl;
     std::cout << (std::string { "abc" } < std::string { "ab" }) << std::endl;
-    std::cout << std::endl;
     std::cout << (std::vector<int> { 1, 2, 3 } < std::vector<int> { 1, 2, 4 }) << std::endl;
     std::cout << (std::vector<int> { 1, 2, 3 } < std::vector<int> { 1, 2 }) << std::endl;
@@ Ligne 402: / Ligne 486: @@
 true
 false
 true
 false
@@ Ligne 409: / Ligne 492: @@
 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ées :
-  * identité : n'importe quelle collection n'est pas inférieure à elle-même (elle est égale à elle-même) ;
+  * **identité** : une collection n'est pas inférieure à elle-même (elle est égale à elle-même) ;
-  * inverse : si une collection est inférieur à une seconde collection, on peut également dire que la seconde collection n'est pas inférieure à la première (elle est supérieure ou égale) ;
+  * **inverse** : si une collection est inférieur à une seconde collection, la seconde collection 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.
+  * **transitivité** : si une collection a est inférieur à une collection b et que cette collection b est inférieure à une collection c, alors la collection a est inférieure à la collection c.
+Ce concept "LessThanComparable" est valable pour d'autres types du C++ (''int'', ''float'', etc.) et de la bibliothèque standard (''std::string'', ''std::complex'', ''std::vector'', etc.).
+Lorsqu'une classe définie un opérateur de comparaison, il est logique que les autres opérateurs soient aussi définis (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.
+==== L'algorithme std::lexicographical_compare ====
-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.
+L'algorithme ''std::equal'' permet de comparer si deux collections sont égales ou différentes. L’équivalent pour la comparaison est l'algorithme ''std::lexicographical_compare''. Tout comme ''std::equal'' est une version plus générique de l'opérateur ''=='' (et indirectement de ''!=''), l'algorithme ''std::lexicographical_compare'' est une version plus générique de l’opérateur ''<'' (et donc indirectement des opérateurs ''>'', ''<='' et ''>=''). En particulier, ''std::lexicographical_compare'' pourra être utilisé sur des sous-collections ou des collections de types différents.
-===== Les algorithmes de comparaison =====
-La fonction ''lexicographical_compare'' prend comme arguments le début et la fin des deux collections que l'on souhaite comparer. Elle existe en deux versions, avec ou sans prédicat personnalisé, et retourne vrai si la première collection est inférieure à la seconde.
+La fonction ''std::lexicographical_compare'' ([[http://en.cppreference.com/w/cpp/algorithm/lexicographical_compare|documentation]]) prend comme arguments le début et la fin des deux collections à comparer. Elle existe en deux versions, avec ou sans prédicat personnalisé, et retourne vrai si la première collection est inférieure à la seconde.
 <code cpp main.cpp>
@@ Ligne 440: / Ligne 529: @@
 true
 </code>
-Comme pour la fonction ''std::equal'', on va pouvoir utiliser la fonction ''lexicographical_compare'' pour (voir les exercices) :
-  * tester des collections différentes ;
-  * comparer des parties de collections ;
-  * utiliser un prédicat personnalisé.
@@ Ligne 452: / Ligne 534: @@
   * comparer vector<int> et vector<float>
-  * comparer vector<int> et vector<string> (aide : utilise std::stoi)
+  * comparer vector<int> et vector<string> (Aide : utilisez ''std::stoi'' dans une fonction lambda)
-  * comparer vector<int> et vector<string> (qui contient "un", "deux", etc.)
+  * tester si une chaîne est un palindrome (un palindrome est un mot qui peut être lu de droite à gauche ou de gauche à droite, comme par exemple "kayak" ou "radar").
-  * tester si palindrome (un palindrome est un mot qui peut être lu de droite à gauche ou de gauche à droite, comme par exemple "kayak" ou "radar").
 <code cpp main.cpp>
@@ Ligne 476: / Ligne 557: @@
 true
 </code>
   * Tester des collections différentes
@@ Ligne 549: / Ligne 629: @@
 </code>
-^ Chapitre précédent ^ [[programmez_avec_le_langage_c|Sommaire principal]] ^ Chapitre suivant ^
-{{tag> Cours C++}}
+^ [[collection2|Chapitre précédent]] ^ [[programmez_avec_le_langage_c|Sommaire principal]] ^ [[rechercher|Chapitre suivant]] ^

C++, Qt, OpenGL, CUDA

Outils d'utilisateurs

Outils du Site

Différences

Outils de la Page