std::lexicographical_compare

Определено в заголовке `<algorithm>`
	(1)
template< class InputIt1, class InputIt2 > bool lexicographical_compare( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2 );		(до C++20)
template< class InputIt1, class InputIt2 > constexpr bool lexicographical_compare( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2 );		(с C++20)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 > bool lexicographical_compare( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2 );	(2)	(с C++17)
	(3)
template< class InputIt1, class InputIt2, class Compare > bool lexicographical_compare( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, Compare comp );		(до C++20)
template< class InputIt1, class InputIt2, class Compare > constexpr bool lexicographical_compare( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, Compare comp );		(с C++20)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class Compare > bool lexicographical_compare( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2, Compare comp );	(4)	(с C++17)

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

1) Элементы сравниваются с помощью operator<.

3) Элементы сравниваются с помощью заданной двоичной функции сравнения comp.

2,4) То же, что и (1,3), но выполняется в соответствии с policy. Эти перегрузки не участвуют в разрешении перегрузки, если

`std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>` является `true`.	(до C++20)
`std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>` является `true`.	(с C++20)

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

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

Параметры

first1, last1	-	первый диапазон элементов для проверки
first2, last2	-	второй диапазон элементов для проверки
policy	-	стратегия выполнения. Подробнее см. стратегия выполнения.
comp	-	объект функции сравнения (т.е. объект, удовлетворяющий требованиям Compare), который возвращает `true`, если первый аргумент меньше второго. Подпись функции сравнения должна быть эквивалентна следующей: `bool cmp(const Type1& a, const Type2& b);` Хотя подпись не обязательно должна содержать `const&`, функция не должна изменять объекты, передаваемые ей, и должна быть способна принимать все значения типа (возможно, const) `Type1` и `Type2` независимо от категории значения (поэтому `Type1&` не допускается, а также `Type1` за исключением случаев, когда для `Type1` перемещение эквивалентно копированию(с C++11)). Типы Type1 и Type2 должны быть такими, чтобы объекты типов InputIt1 и InputIt2 можно было дезаргументировать и затем неявно преобразовать в оба Type1 и Type2.
Требования к типу
-`InputIt1, InputIt2` должен удовлетворять требованиям LegacyInputIterator.
-`ForwardIt1, ForwardIt2` должен удовлетворять требованиям LegacyForwardIterator.
-`Compare` должен удовлетворять требованиям Compare.

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

true , если первый диапазон лексикографически меньше второго, в противном случае false.

Сложность

Дано \(\scriptsize N_1\)N₁ как std::distance(first1, last1) и \(\scriptsize N_2\)N₂ как std::distance(first2, last2):

1,2) Не более \(\scriptsize min(N_1,N_2)\)min(N₁,N₂) сравнений с использованием operator<.

3,4) Не более \(\scriptsize min(N_1,N_2)\)min(N₁,N₂) применений функции сравнения comp.

Исключения

Перегрузки с параметром шаблона под названием ExecutionPolicy сообщают об ошибках следующим образом:

Если выполнение функции, вызываемой в рамках алгоритма, вызывает исключение, и ExecutionPolicy является одной из стандартных стратегий, вызывается std::terminate. Для любой другой ExecutionPolicy, поведение определяется реализацией.
Если алгоритм не может выделить память, выбрасывается std::bad_alloc.

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

lexicographical_compare (1)
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); }
lexicographical_compare (3)
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); }

lexicographical_compare (1)

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

lexicographical_compare (3)

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

Пример

#include <algorithm>
#include <iostream>
#include <random>
#include <vector>
 
void print(std::vector<char> const& 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

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

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

DR	Применён к	Поведение, как опубликовано	Корректное поведение
LWG 142	C++98	Разрешалось не более \(\scriptsize min(N_1,N_2)\)min(N₁,N₂) сравнений, но это невозможно (равенство определяется 2 сравнениями)	Удвоено ограничение
LWG 1205	C++98	Результаты лексикографических сравнений, включающих пустые диапазоны, были неясными	Сделаны ясными

См. также

equal	определяет, являются ли два набора элементов одинаковыми (шаблон функции)
lexicographical_compare_three_way (C++20)	сравнивает два диапазона с помощью трёхстороннего сравнения (шаблон функции)
ranges::lexicographical_compare (C++20)	возвращает `true` , если один диапазон лексикографически меньше другого (niebloid)

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