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 = {} );

Проверяет, является ли первый диапазон [first1, last1) лексикографически меньше второго диапазона [first2, last2).

Лексикографическое сравнение — это операция со следующими свойствами:

• Два диапазона сравниваются поэлементно.
• Первый несовпадающий элемент определяет, какой диапазон лексикографически меньше или больше другого.
• Если один диапазон является префиксом другого, то более короткий диапазон лексикографически меньше другого.
• Если два диапазона имеют эквивалентные элементы и одинаковую длину, то диапазоны лексикографически равны.
• Пустой диапазон лексикографически меньше любого непустого диапазона.
• Два пустых диапазона лексикографически равны.

Описанные на этой странице функциональные объекты являются объектами-функциями алгоритмов (неформально известными как niebloids), то есть:

• При вызове любого из них нельзя указывать явные списки аргументов шаблона.
• Ни один из них не виден при поиске, зависящем от аргументов.
• Когда любой из них находится с помощью обычного неквалифицированного поиска в качестве имени слева от оператора вызова функции, поиск, зависящий от аргументов, подавляется.

Параметры

Возвращаемое значение

true если первая последовательность лексикографически меньше чем вторая.

Сложность

Не более 2·min(N1, N2) применений операции сравнения и соответствующих проекций, где N1 = ranges:: distance ( first1, last1 ) и N2 = ranges:: distance ( first2, last2 ) .

Возможная реализация

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;

Пример

#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

См. также