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) | определяет, совпадают ли два набора элементов (алгоритмический функциональный объект) |
| лексикографически сравнивает два диапазона (шаблон функции) |
© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/cpp/algorithm/ranges/lexicographical_compare
