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.

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 :

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;
    std::cout << (s1 == s2) << std::endl;
    std::cout << (s1 == s3) << std::endl;
}

affiche :

true
false

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 :

std::cout << (s1 == s2) << std::endl;
std::cout << s1 == (s2 << std::endl);

De la même façon pour les collections, il est possible d'utiliser l’opérateur ==.

main.cpp

#include <iostream>
#include <vector>
 
int main() {
    std::vector<int> const v1 { 1, 2, 3, 4 };
    std::vector<int> const v2 { 1, 2, 3, 4 };
    std::vector<int> const v3 { 4, 3, 2, 1 };
    std::cout << std::boolalpha;
    std::cout << (v1 == v2) << std::endl;
    std::cout << (v1 == v3) << std::endl;
}

affiche :

true
false

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, il est possible d'utiliser l'opérateur de comparaison != (not-equal-to operator).

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;
}

affiche :

false
true

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é” (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, 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.

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).

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.)

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.

Lorsque vous découvrez une nouvelle fonctionnalité, la première chose à faire est de regarder la documentation : std::equal. Cette page peut vous apprendre 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 std::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 ;
  • le second est similaire au premier, avec un prédicat personnalisé ;
  • 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.

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.

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 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 :

#include <iostream>
#include <string>
#include <algorithm>
 
int main() {
    std::string const s1 { "abcd" };
    std::string const s2 { "abcdEF" };
    std::cout << std::boolalpha;
    std::cout << std::equal(begin(s1), end(s1), begin(s2)) << std::endl;
    std::cout << std::equal(begin(s2), end(s2), begin(s1)) << std::endl;
    std::cout << std::endl;
    std::cout << std::equal(begin(s1), end(s1), begin(s2), end(s2)) << std::endl;
    std::cout << std::equal(begin(s2), end(s2), begin(s1), end(s1)) << std::endl;
}

affiche :

true
false

false
false

Par défaut, préférez l'utilisation de la version prenant le début et la fin des deux collections (les versions 3 et 4 de std::equal).

std::equal(begin(s1), end(s2), begin(s2)); // problème, les deux premiers arguments
                                           // ne proviennent pas de la même collection

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 :

main.cpp

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
 
int main() {
    std::string const s { "abcdef" };
    std::vector<char> const v { 'a', 'b', 'c', 'd', 'e', 'f' };
    std::cout << std::boolalpha;
    std::cout << (s == v) << std::endl;
}

affiche l'erreur à la compilation suivante :

main.cpp:10: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 == v) << std::endl;
                  ~ ^  ~
1 error generated.

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++).

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 :

main.cpp

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
 
int main() {
    std::string const s { "abcdef" };
    std::vector<char> const v1 { 'a', 'b', 'c', 'd', 'e', 'f' };
    std::vector<char> const v2 { 'a', 'z', 'e', 'r', 't', 'y' };
    std::cout << std::boolalpha;
    std::cout << std::equal(begin(s), end(s), begin(v1), end(v1)) << std::endl;
    std::cout << std::equal(begin(s), end(s), begin(v2), end(v2)) << std::endl;
}

affiche :

true
false

Ce qui correspond bien a une comparaison des éléments un par un.

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).

Par exemple, pour comparer les quatre premiers éléments de deux collections, vous pouvez écrire :

main.cpp

#include <iostream>
#include <string>
#include <algorithm>
 
int main() {
    std::string const s1 { "abcdef" };
    std::string const s2 { "abcdEF" };
    std::cout << std::boolalpha;
    std::cout << std::equal(begin(s1), end(s1), begin(s2), end(s2)) << std::endl;
    std::cout << std::equal(begin(s1), begin(s1)+4, begin(s2), begin(s2)+4) << std::endl;
}

affiche :

false
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.

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.

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 :

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"

...

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.

bool result_1 = predicat_unaire(argument_1);
bool result_2 = predicat_binaire(argument_1, argument_2);

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 :

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"

...

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 pour convertir tous les caractères en majuscule, avant de faire la comparaison.

…….

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 ?

Comme indiqué dans la documentation (par exemple pour 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.

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.

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.

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 }.

main.cpp

#include <iostream>
#include <string>
#include <vector>
 
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;
    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;
}

affiche :

true
false

true
false

La comparaison “plus petit que” est également un concept (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) ;
• 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) ;
• 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.

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.

main.cpp

#include <iostream>
#include <string>
#include <algorithm>
 
int main() {
    std::string const s1 { "azerty" };
    std::string const s2 { "abcdef" };
    std::string const s3 { "qwerty" };
    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;
}

affiche :

false
true

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é.

• comparer vector<int> et vector<float>
• comparer vector<int> et vector<string> (aide : utilise std::stoi)
• comparer vector<int> et vector<string> (qui contient “un”, “deux”, etc.)
• 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”).

main.cpp

#include <iostream>
#include <string>
#include <algorithm>
 
int main() {
    std::string const s1 { "azerty" }; // non palindromique
    std::string const s2 { "abccba" }; // palindromique
    std::cout << std::boolalpha;
    std::cout << std::equal(begin(s1), end(s1), s1.rbegin()) << std::endl;
    std::cout << std::equal(begin(s2), end(s2), s2.rbegin()) << std::endl;
}

affiche :

false
true

• Tester des collections différentes

main.cpp

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
 
int main() {
    std::string const s { "abcdef" };
    std::vector<char> const a { 'a', 'z', 'e', 'r', 't', 'y' };
    std::cout << std::boolalpha;
    std::cout << std::lexicographical_compare(begin(s), end(s), begin(a), end(a)) << std::endl;
}

affiche :

true

• Comparer des parties de collections

main.cpp

#include <iostream>
#include <string>
#include <algorithm>
 
int main() {
    std::string const s1 { "abcdef" };
    std::string const s2 { "abcdfg" };
    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), begin(s1)+4, begin(s2), begin(s2)+4) << std::endl;
}

affiche :

true
false

• Utiliser un prédicat personnalisé

main.cpp

#include <iostream>
#include <string>
#include <algorithm>
#include <cctype>
 
int main() {
    std::string const s1 { "ABCDEF" };
    std::string const s2 { "azerty" };
    std::cout << std::boolalpha;
    std::cout << std::lexicographical_compare(begin(s1), end(s1), begin(s2), end(s2)) << std::endl;
    std::cout << std::equal(begin(s1), end(s1), begin(s2), end(s2),
        [](auto lhs, auto rhs){ return std::toupper(lhs) < std::toupper(rhs); }) 
        << std::endl;
}

affiche :

true
false

• Utiliser std::equal pour verififer si une chaine est un palindrome.