std::lexicographical_compare

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

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

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

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

2,4) Аналогично (1,3), но выполняется в соответствии с policy. Эти перегрузки участвуют в разрешении перегрузки только в том случае, если значение следующего выражения равно true:

`std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>`	(until C++20)
`std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>`	(since C++20)

Лексикографическое сравнение обладает следующими свойствами:

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

Параметры

first1, last1	-	пара итераторов, определяющая первый диапазон элементов для проверки
first2, last2	-	пара итераторов, определяющая второй диапазон элементов для проверки
policy	-	политика выполнения, которую следует использовать
comp	-	объект-функция сравнения (то есть объект, удовлетворяющий требованиям Compare), который возвращает `true`, если первый аргумент меньше второго. Сигнатура функции сравнения должна быть эквивалентна следующей: boolcmp(constType1&a,constType2&b); Хотя сигнатура не обязана иметь `const&`, функция не должна изменять переданные ей объекты и должна принимать любые значения типа (возможно, const) `Type1` и `Type2` независимо от категории значения (таким образом, `Type1&` не допускается; также не допускается `Type1`, кроме случая, когда для `Type1` перемещение эквивалентно копированию(since 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 2\min(N_1,N_2)\)2min(₁,N₂) сравнений с использованием operator<.

3,4) Не более \(\scriptsize 2\min(N_1,N_2)\)2min(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(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

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

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

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

См. также

equal	определяет, совпадают ли два набора элементов (шаблон функции и функциональный объект-алгоритм)
ranges::equal (C++20)
lexicographical_compare_three_way (C++20)	сравнивает два диапазона с помощью трёхстороннего сравнения (шаблон функции)
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