Outils d'utilisateurs
comparer
Différences
Cette page vous donne les différences entre la révision choisie et la version actuelle de la page.
|
comparer [2016/02/21 23:31] gbdivers |
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]] ^ |
| ====== Introduction aux algorithmes standards ====== | ====== 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 avances, 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. | + | 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é ===== | ===== L'opérateurs d'égalité ===== | ||
| Ligne 38: | Ligne 39: | ||
| </code> | </code> | ||
| - | De la même façon pour les collections, il est possible d'utiliser l’opérateur ''==''. | + | De la même façon pour les tableaux, il est possible d'utiliser l’opérateur ''==''. |
| <code cpp main.cpp> | <code cpp main.cpp> | ||
| Ligne 95: | Ligne 96: | ||
| 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**. | 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**. | ||
| - | 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 à notre classe, l'écriture de la classe en découlera. | + | 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. |
| 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). | 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). | ||
| Ligne 118: | Ligne 119: | ||
| La page de documentation donne également des codes d'exemple d'utilisation de ces fonctions. | La page de documentation donne également des codes d'exemple d'utilisation de ces fonctions. | ||
| - | 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 a la fin de la premier 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 dernier éléments et ''std::equal'' retournera vrai, alors que ce n'est pas forcement le cas. | + | 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. | 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. | ||
| Ligne 156: | Ligne 157: | ||
| <note warning> | <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> | <code cpp> | ||
| Ligne 195: | Ligne 196: | ||
| </code> | </code> | ||
| - | 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 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 ''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é). | 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é). | ||
| Ligne 229: | Ligne 230: | ||
| ===== Comparer des parties de collections ===== | ===== Comparer des parties de collections ===== | ||
| - | Avec ''std::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 (''std::find'', que vous verrez dans un prochain chapitre). | + | 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 : | Par exemple, pour comparer les quatre premiers éléments de deux collections, vous pouvez écrire : | ||
| Ligne 258: | Ligne 259: | ||
| <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> | <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> | ||
| - | Faites bien attention de ne pas perdre de vue ce que vous comparer. Ce n'est pas parce que vous utiliser ''std::equal'' ("égal" en français) que vos collection son "égales". Seuls les éléments que vous comparer 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. | + | 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. |
| Ligne 291: | Ligne 292: | ||
| <note> | <note> | ||
| - | Ce "quelque chose" n'est volontairement pas défini pour le moment, cela peut correspondre a 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. | + | 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"). | 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> | </note> | ||
| - | Ce prédicat sera utilisée a la place de l’opérateur ''=='' pour la comparaison des éléments un par un. En pseudo-code, cela donnerait : | + | 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> | <code> | ||
| Ligne 318: | Ligne 319: | ||
| La bibliothèque standard fournit quelques prédicats de base, décris dans la documentation ([[http://en.cppreference.com/w/cpp/utility/functional | 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-tete ''<functional>''. Ces prédicats sont simples a 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. | + | |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> | <note>Attention de ne pas confondre l'algorithme ''std::equal'' et le prédicat ''std::equal_to''.</note> | ||
| Ligne 324: | Ligne 325: | ||
| Les autres objets-fonctions seront utiles pour les autres algorithmes de la bibliothèque standard, que vous verrez par la suite. | 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 a n'importe quelle création d'objet. | + | 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> | <code cpp> | ||
| Ligne 396: | Ligne 397: | ||
| ==== Les algorithmes avec prédicats personnalisés ==== | ==== Les algorithmes avec prédicats personnalisés ==== | ||
| - | Les prédicats peuvent être utilisé 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. | + | 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 : | 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 : | ||
| Ligne 436: | Ligne 437: | ||
| **Exercice** | **Exercice** | ||
| - | Est-ce que les deux syntaxes suivantes donnent le même résultat ? C'est a dire de comparer si deux collections sont différentes. (Notez bien l’opérateur de négation logique ''!'' dans la seconde ligne). | + | 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> | <code cpp> | ||
| Ligne 448: | Ligne 449: | ||
| 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. | 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. | ||
| - | Mais quel sens donner a la phrase "une collection est inférieure a une autre collection" ? | + | Mais quel sens donner à la phrase "une collection est inférieure à une autre collection" ? |
| 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). | 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). | ||
| Ligne 457: | Ligne 458: | ||
| * 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 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 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 a l'autre. | + | * 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. | * Si tous les éléments sont identiques, les collections sont égales. | ||
| Ligne 502: | Ligne 503: | ||
| ==== L'algorithme std::lexicographical_compare ==== | ==== L'algorithme std::lexicographical_compare ==== | ||
| - | 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 utilise sur des sous-collections ou des collections de types différents. | + | 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. |
| - | 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 a 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> | <code cpp main.cpp> | ||
| Ligne 534: | Ligne 535: | ||
| * comparer vector<int> et vector<float> | * comparer vector<int> et vector<float> | ||
| * comparer vector<int> et vector<string> (Aide : utilisez ''std::stoi'' dans une fonction lambda) | * 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 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"). | ||
| Ligne 630: | Ligne 630: | ||
| - | ^ 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.1456093910.txt.gz · Dernière modification: 2016/02/21 23:31 par gbdivers
Sauf mention contraire, le contenu de ce wiki est placé sous la licence suivante : CC Attribution-Noncommercial-Share Alike 3.0 Unported
