std::ranges::is_sorted_until
Определена в заголовке <algorithm> | ||
|---|---|---|
| Сигнатура вызова | ||
template< std::forward_iterator I, std::sentinel_for<I> S,
class Proj = std::identity,
std::indirect_strict_weak_order<std::projected<I, Proj>>
Comp = ranges::less >
constexpr I
is_sorted_until( I first, S last, Comp comp = {}, Proj proj = {} );
| (1) | (начиная с C++20) |
template< std::forward_range R, class Proj = std::identity,
std::indirect_strict_weak_order<
std::projected<ranges::iterator_t<R>, Proj>>
Comp = ranges::less >
constexpr ranges::borrowed_iterator_t<R>
is_sorted_until( R&& r, Comp comp = {}, Proj proj = {} );
| (2) | (начиная с C++20) |
Исследует диапазон [first, last) и находит наибольший диапазон, начинающийся с first, в котором элементы упорядочены по неубыванию.
Последовательность отсортирована относительно компаратора comp, если для любого итератора it, указывающего на последовательность, и любого неотрицательного целого числа n, такого что it + n является допустимым итератором, указывающим на элемент последовательности, выражение std::invoke(comp, std::invoke(proj, *(it + n)), std::invoke(proj, *it)) вычисляется в значение false.
comp.r, как если бы ranges::begin(r) использовался в качестве first, а ranges::end(r) — в качестве last.Описанные на этой странице функциональные объекты являются функциональными объектами алгоритмов (неформально известными как niebloids
Параметры
first, last - пара итератора и сентинела, задающая диапазон элементов, для которого требуется найти верхнюю границу отсортированной части
r - диапазон, для которого требуется найти верхнюю границу отсортированной части
comp - функция сравнения, применяемая к спроецированным элементам
proj - проекция, применяемая к элементам
Возвращаемое значение
Верхняя граница наибольшего диапазона, начинающегося с first, в котором элементы упорядочены по неубыванию. Иными словами, последний итератор it, для которого диапазон [first, it) отсортирован.
Сложность
Линейная относительно расстояния между first и last.
Возможная реализация
struct is_sorted_until_fn
{
template<std::forward_iterator I, std::sentinel_for<I> S,
class Proj = std::identity,
std::indirect_strict_weak_order<std::projected<I, Proj>>
Comp = ranges::less>
constexpr I operator()(I first, S last, Comp comp = {}, Proj proj = {}) const
{
if (first == last)
return first;
for (auto next = first; ++next != last; first = next)
if (std::invoke(comp, std::invoke(proj, *next), std::invoke(proj, *first)))
return next;
return first;
}
template<ranges::forward_range R, class Proj = std::identity,
std::indirect_strict_weak_order<
std::projected<ranges::iterator_t<R>, Proj>> Comp = ranges::less>
constexpr ranges::borrowed_iterator_t<R>
operator()(R&& r, Comp comp = {}, Proj proj = {}) const
{
return (*this)(ranges::begin(r), ranges::end(r), std::ref(comp), std::ref(proj));
}
};
inline constexpr is_sorted_until_fn is_sorted_until;
|
Примечания
ranges::is_sorted_until возвращает итератор, равный last, для пустых диапазонов и диапазонов длины один.
Пример
#include <array>
#include <algorithm>
#include <iostream>
#include <iterator>
#include <random>
int main()
{
std::random_device rd;
std::mt19937 g {rd()};
std::array nums {3, 1, 4, 1, 5, 9};
constexpr int min_sorted_size = 4;
int sorted_size = 0;
do
{
std::ranges::shuffle(nums, g);
const auto sorted_end = std::ranges::is_sorted_until(nums);
sorted_size = std::ranges::distance(nums.begin(), sorted_end);
std::ranges::copy(nums, std::ostream_iterator<int>(std::cout, " "));
std::cout << " : " << sorted_size << " leading sorted element(s)\n";
}
while (sorted_size < min_sorted_size);
}
Возможный вывод:
4 1 9 5 1 3 : 1 leading sorted element(s) 4 5 9 3 1 1 : 3 leading sorted element(s) 9 3 1 4 5 1 : 1 leading sorted element(s) 1 3 5 4 1 9 : 3 leading sorted element(s) 5 9 1 1 3 4 : 2 leading sorted element(s) 4 9 1 5 1 3 : 2 leading sorted element(s) 1 1 4 9 5 3 : 4 leading sorted element(s)
См. также
|
(C++20) | проверяет, отсортирован ли диапазон (функциональный объект алгоритма) |
|
(C++11) | находит наибольшую отсортированную подпоследовательность (шаблон функции) |
© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/cpp/algorithm/ranges/is_sorted_until
