std::ranges::lexicographical_compare

template< std::input_iterator I1, std::sentinel_for<I1> S1,
          std::input_iterator I2, std::sentinel_for<I2> S2,
          class Proj1 = std::identity, class Proj2 = std::identity,
          std::indirect_strict_weak_order<
              std::projected<I1, Proj1>,
              std::projected<I2, Proj2>> Comp = ranges::less >
constexpr bool
    lexicographical_compare( I1 first1, S1 last1, I2 first2, S2 last2,
                             Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );

template< ranges::input_range R1, ranges::input_range R2,
          class Proj1 = std::identity, class Proj2 = std::identity,
          std::indirect_strict_weak_order<
              std::projected<ranges::iterator_t<R1>, Proj1>,
              std::projected<ranges::iterator_t<R2>, Proj2>> Comp = ranges::less >
constexpr bool
    lexicographical_compare( R1&& r1, R2&& r2, Comp comp = {},
                             Proj1 proj1 = {}, Proj2 proj2 = {} );

Comprueba si el primer rango [first1, last1) es lexicográficamente menor que el segundo rango [first2, last2).

La comparación lexicográfica es una operación con las siguientes propiedades:

• Se comparan dos rangos elemento por elemento.
• El primer elemento que no coincide define qué rango es lexicográficamente menor o mayor que el otro.
• Si un rango es un prefijo de otro, el rango más corto es lexicográficamente menor que el otro.
• Si dos rangos tienen elementos equivalentes y tienen la misma longitud, entonces los rangos son lexicográficamente iguales.
• Un rango vacío es lexicográficamente menor que cualquier rango no vacío.
• Dos rangos vacíos son lexicográficamente iguales.

Las entidades similares a funciones descritas en esta página son objetos de función de algoritmo (conocidos informalmente como niebloids), es decir:

• No se pueden especificar listas de argumentos de plantilla explícitas al llamar a ninguna de ellas.
• Ninguna de ellas es visible para la búsqueda dependiente de argumentos.
• Cuando cualquiera de ellas se encuentra mediante búsqueda no calificada normal como el nombre a la izquierda del operador de llamada de función, la búsqueda dependiente de argumentos se inhibe.

Parámetros

Valor de retorno

true si el primer rango es lexicográficamente menor que el segundo.

Complejidad

Como máximo 2·min(N1, N2) aplicaciones de la comparación y proyecciones correspondientes, donde N1 = ranges:: distance ( first1, last1 ) y N2 = ranges:: distance ( first2, last2 ) .

Implementación posible

struct lexicographical_compare_fn
{
    template<std::input_iterator I1, std::sentinel_for<I1> S1,
             std::input_iterator I2, std::sentinel_for<I2> S2,
             class Proj1 = std::identity, class Proj2 = std::identity,
             std::indirect_strict_weak_order<
                 std::projected<I1, Proj1>,
                 std::projected<I2, Proj2>> Comp = ranges::less>
    constexpr bool operator()(I1 first1, S1 last1, I2 first2, S2 last2,
                              Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}) const
    {
        for (; (first1 != last1) && (first2 != last2); ++first1, (void) ++first2)
        {
            if (std::invoke(comp, std::invoke(proj1, *first1), std::invoke(proj2, *first2)))
                return true;
            if (std::invoke(comp, std::invoke(proj2, *first2), std::invoke(proj1, *first1)))
                return false;
        }
        return (first1 == last1) && (first2 != last2);
    }
    template<ranges::input_range R1, ranges::input_range R2,
             class Proj1 = std::identity, class Proj2 = std::identity,
             std::indirect_strict_weak_order<
                 std::projected<ranges::iterator_t<R1>, Proj1>,
                 std::projected<ranges::iterator_t<R2>, Proj2>> Comp = ranges::less>
    constexpr bool operator()(R1&& r1, R2&& r2, Comp comp = {},
                              Proj1 proj1 = {}, Proj2 proj2 = {}) const
    {
        return (*this)(ranges::begin(r1), ranges::end(r1),
                       ranges::begin(r2), ranges::end(r2),
                       std::ref(comp), std::ref(proj1), std::ref(proj2));
    }
};
inline constexpr lexicographical_compare_fn lexicographical_compare;

Ejemplo

#include <algorithm>
#include <iostream>
#include <iterator>
#include <random>
#include <vector>
int main()
{
    std::vector<char> v1 {'a', 'b', 'c', 'd'};
    std::vector<char> v2 {'a', 'b', 'c', 'd'};
    namespace ranges = std::ranges;
    auto os = std::ostream_iterator<char>(std::cout, " ");
    std::mt19937 g {std::random_device {}()};
    while (not ranges::lexicographical_compare(v1, v2))
    {
        ranges::copy(v1, os);
        std::cout << ">= ";
        ranges::copy(v2, os);
        std::cout << '\n';
        ranges::shuffle(v1, g);
        ranges::shuffle(v2, g);
    }
    ranges::copy(v1, os);
    std::cout << "<  ";
    ranges::copy(v2, os);
    std::cout << '\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

Véase también