std::lexicographical_compare

template< class InputIt1, class InputIt2 >
bool lexicographical_compare( InputIt1 first1, InputIt1 last1,
                              InputIt2 first2, InputIt2 last2 );

template< class ExecutionPolicy,
          class ForwardIt1, class ForwardIt2 >
bool lexicographical_compare( ExecutionPolicy&& policy,
                              ForwardIt1 first1, ForwardIt1 last1,
                              ForwardIt2 first2, ForwardIt2 last2 );

template< class InputIt1, class InputIt2, class Compare >
bool lexicographical_compare( InputIt1 first1, InputIt1 last1,
                              InputIt2 first2, InputIt2 last2,
                              Compare comp );

template< class ExecutionPolicy,
          class ForwardIt1, class ForwardIt2, class Compare >
bool lexicographical_compare( ExecutionPolicy&& policy,
                              ForwardIt1 first1, ForwardIt1 last1,
                              ForwardIt2 first2, ForwardIt2 last2,
                              Compare comp );

Vérifie si la première plage [first1, last1) est lexicographiquement inférieure à la seconde plage [first2, last2).

La comparaison lexicographique est une opération avec les propriétés suivantes :

• Deux plages sont comparées élément par élément.
• Le premier élément divergent définit quelle plage est lexicographiquement inférieure ou supérieure à l'autre.
• Si une plage est un préfixe de l'autre, la plage la plus courte est lexicographiquement inférieure à l'autre.
• Si deux plages ont des éléments équivalents et sont de même longueur, alors les plages sont lexicographiquement égales.
• Une plage vide est lexicographiquement inférieure à toute plage non vide.
• Deux plages vides sont lexicographiquement égales.

Paramètres

Valeur de retour

true si la première plage est lexicographiquement inférieure à la seconde, sinon false.

Complexité

Soient \(\scriptsize N_1\)N1 comme std::distance(first1, last1) et \(\scriptsize N_2\)N2 comme std::distance(first2, last2):

Exceptions

Les surcharges avec un paramètre de modèle nommé ExecutionPolicy signalent les erreurs comme suit :

• Si l'exécution d'une fonction invoquée dans le cadre de l'algorithme lève une exception et que ExecutionPolicy fait partie des politiques standard, std::terminate est appelé. Pour toute autre ExecutionPolicy, le comportement est défini par l'implémentation.
• Si l'algorithme ne parvient pas à allouer de la mémoire, std::bad_alloc est levé.

Implémentation possible

template<class InputIt1, class InputIt2>
bool lexicographical_compare(InputIt1 first1, InputIt1 last1,
                             InputIt2 first2, InputIt2 last2)
{
    for (; (first1 != last1) && (first2 != last2); ++first1, (void) ++first2)
    {
        if (*first1 < *first2)
            return true;
        if (*first2 < *first1)
            return false;
    }
    
    return (first1 == last1) && (first2 != last2);
}

template<class InputIt1, class InputIt2, class Compare>
bool lexicographical_compare(InputIt1 first1, InputIt1 last1,
                             InputIt2 first2, InputIt2 last2, Compare comp)
{
    for (; (first1 != last1) && (first2 != last2); ++first1, (void) ++first2)
    {
        if (comp(*first1, *first2))
            return true;
        if (comp(*first2, *first1))
            return false;
    }
    
    return (first1 == last1) && (first2 != last2);
}

Exemple

#include <algorithm>
#include <iostream>
#include <random>
#include <vector>

void print(const std::vector<char>& v, auto suffix)
{
    for (char c : v)
        std::cout << c << ' ';
    std::cout << suffix;
}

int main()
{
    std::vector<char> v1{'a', 'b', 'c', 'd'};
    std::vector<char> v2{'a', 'b', 'c', 'd'};
    
    for (std::mt19937 g{std::random_device{}()};
         !std::lexicographical_compare(v1.begin(), v1.end(),
                                       v2.begin(), v2.end());)
    {
        print(v1, ">= ");
        print(v2, '\n');
        
        std::shuffle(v1.begin(), v1.end(), g);
        std::shuffle(v2.begin(), v2.end(), g);
    }
    
    print(v1, "<  ");
    print(v2, '\n');
}

a b c d >= a b c d 
d a b c >= c b d a 
b d a c >= a d c b 
a c d b <  c d a b

Rapports de défauts

Les rapports de défauts modifiant le comportement suivants ont été appliqués rétroactivement aux normes C++ précédemment publiées.

Voir aussi