18.4. Opérations de comparaison

Afin de faciliter la comparaison de conteneurs de natures différentes pour lesquels, de surcroît, il n'existe pas forcément d'opérateurs de comparaison, la bibliothèque standard fournit plusieurs algorithmes de comparaison. Ces algorithmes sont capables d'effectuer une comparaison élément à élément des différents conteneurs pour vérifier leur égalité en terme d'éléments contenus, ou de déterminer une relation d'ordre au sens lexicographique. Enfin, il est possible de déterminer les éléments par lesquels deux conteneurs se différencient.

L'algorithme général de comparaison des conteneurs est l'algorithme equal. Cet algorithme est déclaré comme suit dans l'en-tête algorithm :

template <class InputIterator1, class InputIterator2>
bool equal(InputIterator1 premier1, InputIterator1 dernier1,
    InputIterator2 premier2);

template <class InputIterator1, class InputIterator2, class BinaryPredicate>
bool equal(InputIterator1 premier1, InputIterator1 dernier1,
    InputIterator2 premier2, BinaryPredicate p);

Comme vous pouvez le constater d'après cette déclaration, l'algorithme equal prend en paramètre un couple d'itérateurs décrivant la séquence d'éléments qui doivent être pris en compte dans la comparaison ainsi qu'un itérateur sur le premier élément du deuxième conteneur. Les éléments référencés successivement par les itérateurs premier1 et premier2 sont ainsi comparés, jusqu'à ce qu'une différence soit détectée ou que l'itérateur dernier1 du premier conteneur soit atteint. La valeur retournée est true si les deux séquences d'éléments des deux conteneurs sont égales élément à élément, et false sinon. Bien entendu, il est possible de spécifier un foncteur binaire que l'algorithme devra utiliser pour réaliser les comparaisons entre les éléments des deux conteneurs. S'il est spécifié, ce foncteur est utilisé pour déterminer si les éléments comparés sont égaux ou non.

S'il s'avère que les deux conteneurs ne sont pas égaux membre à membre, il peut être utile de déterminer les itérateurs des deux éléments qui ont fait échouer le test d'égalité. Cela peut être réalisé à l'aide de l'algorithme mismatch dont on trouvera la déclaration dans l'en-tête algorithm :

template <class InputIterator1, class InputIterator2>
pair<InputIterator1, InputIterator2>
    mismatch(InputIterator1 premier1, InputIterator1 dernier1,
        InputIterator2 premier2);

template <class InputIterator1, class InputIterator2, class BinaryPredicate>
pair<InputIterator1, InputIterator2>
    mismatch(InputIterator1 premier1, InputIterator1 dernier1,
        InputIterator2 premier2, BinaryPredicate p);

Cet algorithme fonctionne exactement de la même manière que l'algorithme equal. Cependant, contrairement à ce dernier, sa valeur de retour est une paire d'itérateurs des deux conteneurs référençant les éléments respectifs qui ne sont pas égaux au sens de l'opération de comparaison utilisée par l'algorithme (que ce soit l'opérateur d'égalité ou le foncteur fourni en paramètre). Si les deux conteneurs sont effectivement égaux, la valeur retournée est la paire contenant l'itérateur dernier1 et l'itérateur correspondant dans le deuxième conteneur.

#include <iostream>
#include <algorithm>

using namespace std;

int main(void)
{
    int t1[10] = {5, 6, 4, 7, 8, 9, 2, 1, 3, 0};
    int t2[10] = {5, 6, 4, 7, 9, 2, 1, 8, 3, 0};
    // Compare les deux tableaux :
    if (!equal(t1, t1+10, t2))
    {
        // Détermine les éléments différents :
        pair<int *, int *> p =
            mismatch(t1, t1+10, t2);
        cout << *p.first << " est différent de " <<
            *p.second << endl;
    }
    return 0;
}

Enfin, la bibliothèque standard fournit un algorithme de comparaison général permettant de déterminer si un conteneur est inférieur à un autre conteneur selon la relation d'ordre lexicographique induite par l'opérateur d'infériorité du type de leurs éléments. Rappelons que l'ordre lexicographique est celui utilisé par le dictionnaire : les éléments sont examinés un à un et dans leur ordre d'apparition et la comparaison s'arrête dès que deux éléments différents sont trouvés. En cas d'égalité totale, le plus petit des conteneurs est celui qui contient le moins d'éléments.

L'algorithme de comparaison lexicographique est l'algorithme lexicographical_compare. Il est déclaré comme suit dans l'en-tête algorithm :

template <class InputIterator1, class InputIterator2>
bool lexicographical_compare(InputIterator1 premier1, InputIterator1 dernier1,
    InputIterator2 premier2, InputIterator2 dernier2);

template <class InputIterator1, class InputIterator2, class Compare>
bool lexicographical_compare(InputIterator1 premier1, InputIterator1 dernier1,
    InputIterator2 premier2, InputIterator2 dernier2,
    Compare c);

Cet algorithme prend en paramètre deux couples d'itérateurs grâce auxquels le programmeur peut spécifier les deux séquences d'éléments à comparer selon l'ordre lexicographique. Comme à l'accoutumée, il est également possible de fournir un foncteur à utiliser pour les tests d'infériorité entre les éléments des deux conteneurs. La valeur retournée par l'algorithme lexicographical_compare est true si le premier conteneur est strictement plus petit que le deuxième et false sinon.

#include <iostream>
#include <algorithm>

using namespace std;

int main(void)
{
    int t1[10] = {5, 6, 4, 7, 8, 9, 2, 1, 3, 0};
    int t2[10] = {5, 6, 4, 7, 9, 2, 1, 8, 3, 0};
    // Compare les deux tableaux :
    if (lexicographical_compare(t1, t1+10, t2, t2+10))
    {
        cout << "t1 est plus petit que t2" << endl;
    }
    return 0;
}

Tous ces algorithmes de comparaison s'exécutent avec une complexité linéaire en fonction du nombre d'éléments à comparer.