std::lexicographical_compare_three_way

Определен в заголовке <algorithm>

Определен в заголовке `<algorithm>`
template< class InputIt1, class InputIt2, class Cmp > constexpr auto lexicographical_compare_three_way ( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, Cmp comp ) -> decltype(comp(first1, first2));	(1)	(начиная с C++20)
template< class InputIt1, class InputIt2 > constexpr auto lexicographical_compare_three_way ( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2 );	(2)	(начиная с C++20)

template< class InputIt1, class InputIt2, class Cmp >
constexpr auto lexicographical_compare_three_way
    ( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2,
      Cmp comp ) -> decltype(comp(*first1, *first2));

(1)

(начиная с C++20)

template< class InputIt1, class InputIt2 >
constexpr auto lexicographical_compare_three_way
    ( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2 );

(2)

(начиная с C++20)

Лексикографически сравнивает два диапазона [first1, last1) и [first2, last2) с помощью трехстороннего сравнения и возвращает результат с наиболее сильным подходящим типом категории сравнения.

1) Возвращает порядок первой пары неэквивалентных элементов согласно comp в обоих диапазонах, если такая пара есть; иначе (если один диапазон эквивалентен префиксу другого согласно comp) возвращает порядок, определяемый длинами обоих диапазонов.

2) Эквивалентно return std::lexicographical_compare_three_way(first1, last1, first2, last2, std::compare_three_way());

Если возвращаемый тип не является одним из трех типов категории сравнения, программа некорректна:

Параметры

first1, last1	-	пара итераторов, задающая первый диапазон элементов для проверки
first2, last2	-	пара итераторов, задающая второй диапазон элементов для проверки
comp	-	объект-функция
Требования к типам
-`InputIt1, InputIt2` должен соответствовать требованиям LegacyInputIterator.

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

Значение одного из указанных выше типов категории сравнения.

Сложность

Пусть \(\scriptsize N_1\)N₁ — это std::distance(first1, last1), а \(\scriptsize N_2\)N₂ — это std::distance(first2, last2):

1) Не более \(\scriptsize \min(N_1,N_2)\)min(₁,N₂) вызовов comp.

2) Не более \(\scriptsize \min(N_1,N_2)\)min(N₁,N₂) вызовов std::compare_three_way().

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

template<class I1, class I2, class Cmp>
constexpr auto lexicographical_compare_three_way(I1 f1, I1 l1, I2 f2, I2 l2, Cmp comp)
    -> decltype(comp(*f1, *f2))
{
    using ret_t = decltype(comp(*f1, *f2));
    static_assert(std::disjunction_v<
                      std::is_same<ret_t, std::strong_ordering>,
                      std::is_same<ret_t, std::weak_ordering>,
                      std::is_same<ret_t, std::partial_ordering>>,
                  "The return type must be a comparison category type.");
    
    bool exhaust1 = (f1 == l1);
    bool exhaust2 = (f2 == l2);
    for (; !exhaust1 && !exhaust2; exhaust1 = (++f1 == l1), exhaust2 = (++f2 == l2))
        if (auto c = comp(*f1, *f2); c != 0)
            return c;
    
    return !exhaust1 ? std::strong_ordering::greater:
           !exhaust2 ? std::strong_ordering::less:
                       std::strong_ordering::equal;
}

Пример

#include <algorithm>
#include <cctype>
#include <compare>
#include <iomanip>
#include <iostream>
#include <string_view>
#include <utility>

using namespace std::literals;

void show_result(std::string_view s1, std::string_view s2, std::strong_ordering o)
{
    std::cout << std::quoted(s1) << " is ";
    std::is_lt(o) ? std::cout << "less than ":
    std::is_gt(o) ? std::cout << "greater than ":
                    std::cout << "equal to ";
    std::cout << std::quoted(s2) << '\n';
}

std::strong_ordering cmp_icase(unsigned char x, unsigned char y)
{
    return std::toupper(x) <=> std::toupper(y);
};
    
int main()
{
    for (const auto& [s1, s2] :
    {
        std::pair{"one"sv, "ONE"sv}, {"two"sv, "four"sv}, {"three"sv, "two"sv}
    })
    {
        const auto res = std::lexicographical_compare_three_way(
            s1.cbegin(), s1.cend(), s2.cbegin(), s2.cend(), cmp_icase);
        show_result(s1, s2, res);
    }
}

Вывод:

"one" is equal to "ONE"
"two" is greater than "four"
"three" is less than "two"

Отчеты об ошибках

Следующие отчеты об ошибках, изменяющие поведение, были применены задним числом к ранее опубликованным стандартам C++.

Отчет об ошибке	Применяется к	Опубликованное поведение	Корректное поведение
LWG 3410	C++20	требовались лишние сравнения итераторов	такое требование удалено

См. также

lexicographical_compare	лексикографически сравнивает два диапазона (шаблон функции и объект-функция алгоритма)
ranges::lexicographical_compare (C++20)
compare_three_way (C++20)	ограниченный объект-функция, реализующий `x <=> y` (класс)
ranges::lexicographical_compare (C++20)	лексикографически сравнивает два диапазона (объект-функция алгоритма)

© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/cpp/algorithm/lexicographical_compare_three_way