std::ranges::lexicographical_compare
Определено в заголовке <algorithm> | ||
|---|---|---|
| Подпись вызова | ||
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 = {} );
| (1) | (с C++20) |
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 = {} );
| (2) | (с C++20) |
Проверяет, является ли первый диапазон [first1, last1) лексикографически меньше второго диапазона [first2, last2).
1) Элементы сравниваются с помощью заданной бинарной функции сравнения
comp.
2) То же, что (1), но использует
r в качестве исходного диапазона, как если бы использовался ranges::begin(r) в качестве first и ranges::end(r) в качестве last.Лексикографическое сравнение — это операция со следующими свойствами:
- Два диапазона сравниваются по элементу.
- Первый несовпадающий элемент определяет, какой диапазон лексикографически меньше или больше другого.
- Если один диапазон является префиксом другого, то более короткий диапазон лексикографически меньше другого.
- Если два диапазона имеют эквивалентные элементы и одинаковую длину, то диапазоны лексикографически равны.
- Пустой диапазон лексикографически меньше любого непустого диапазона.
- Два пустых диапазона лексикографически равны.
Функциональные сущности, описанные на этой странице, являются niebloids, то есть:
- Явные списки шаблонов аргументов не могут быть указаны при вызове ни одного из них.
- Ни один из них не виден для поиска по аргументам.
- Когда любой из них находится с помощью обычного неопределённого поиска в качестве имени слева от оператора вызова функции, поиск по аргументам запрещён.
На практике они могут быть реализованы в виде объектов-функций или с помощью специальных расширений компилятора.
Параметры
| first1, last1 | - | первый диапазон элементов для проверки |
| r1 | - | первый диапазон элементов для проверки |
| first2, last2 | - | второй диапазон элементов для проверки |
| r2 | - | второй диапазон элементов для проверки |
| comp | - | функция сравнения, применяемая к спроецированным элементам |
| proj1 | - | проекция, применяемая к первому диапазону элементов |
| proj2 | - | проекция, применяемая ко второму диапазону элементов |
Значение результата
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
См. также
|
(C++20) | определяет, являются ли два набора элементов одинаковыми (niebloid) |
возвращает true, если один диапазон лексикографически меньше другого (функция-шаблон) |
© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/w/cpp/algorithm/ranges/lexicographical_compare
