std::is_sorted_until

Определён в заголовке `<algorithm>`
template< class ForwardIt > ForwardIt is_sorted_until( ForwardIt first, ForwardIt last );	(1)	(начиная с C++11) (constexpr начиная с C++20)
template< class ExecutionPolicy, class ForwardIt > ForwardIt is_sorted_until( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last );	(2)	(начиная с C++17)
template< class ForwardIt, class Compare > ForwardIt is_sorted_until( ForwardIt first, ForwardIt last, Compare comp );	(3)	(начиная с C++11) (constexpr начиная с C++20)
template< class ExecutionPolicy, class ForwardIt, class Compare > ForwardIt is_sorted_until( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, Compare comp );	(4)	(начиная с C++17)

Исследует диапазон [first, last) и находит наибольший диапазон, начинающийся с first, в котором элементы отсортированы в порядке неубывания.

1) Находит наибольший диапазон, в котором элементы отсортированы относительно operator<(до C++20)std::less{}(начиная с C++20).

3) Находит наибольший диапазон, в котором элементы отсортированы относительно comp.

2,4) То же, что и (1,3), но выполняется согласно policy.

Эти перегрузки участвуют в разрешении перегрузки, только если значение следующего выражения равно true:

`std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>`	(до C++20)
`std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>`	(начиная с C++20)

Параметры

first, last	-	пара итераторов, задающая диапазон исследуемых элементов
policy	-	политика выполнения, которую следует использовать
comp	-	объект функции сравнения (то есть объект, удовлетворяющий требованиям Compare), который возвращает `true`, если первый аргумент меньше второго (то есть расположен перед ним в порядке сортировки). Сигнатура функции сравнения должна быть эквивалентна следующей: boolcmp(constType1&a,constType2&b); Хотя сигнатура не обязана содержать const&, функция не должна изменять переданные ей объекты и должна принимать любые значения типа (возможно, const) `Type1` и `Type2` независимо от категории значения (поэтому `Type1&` не допускается, как и `Type1`, если только для `Type1` перемещение не эквивалентно копированию(начиная с C++11)). Типы Type1 и Type2 должны быть такими, чтобы объект типа ForwardIt можно было разыменовать, а полученное значение — неявно преобразовать в каждый из этих типов.
Требования к типам
-`ForwardIt` должен удовлетворять требованиям LegacyForwardIterator.
-`Compare` должен удовлетворять требованиям Compare.

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

Верхняя граница наибольшего диапазона, начинающегося с first, в котором элементы отсортированы по возрастанию. Иными словами, последний итератор it, для которого диапазон [first, it) отсортирован.

Возвращает last для пустых диапазонов и диапазонов длины один.

Сложность

Пусть \(\scriptsize N\)N — std::distance(first, last):

1,2) \(\scriptsize O(N)\)O(N) сравнений с использованием operator<(до C++20)std::less{}(начиная с C++20).

3,4) \(\scriptsize O(N)\)O(N) вызовов компаратора comp.

Исключения

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

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

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

См. также реализации в libstdc++ и libc++.

is_sorted_until (1)
template<class ForwardIt> constexpr //< since C++20 ForwardIt is_sorted_until(ForwardIt first, ForwardIt last) { return std::is_sorted_until(first, last, std::less<>()); }
is_sorted_until (2)
template<class ForwardIt, class Compare> constexpr //< since C++20 ForwardIt is_sorted_until(ForwardIt first, ForwardIt last, Compare comp) { if (first != last) { ForwardIt next = first; while (++next != last) { if (comp(next, first)) return next; first = next; } } return last; }

is_sorted_until (1)

template<class ForwardIt>
constexpr //< since C++20
ForwardIt is_sorted_until(ForwardIt first, ForwardIt last)
{
    return std::is_sorted_until(first, last, std::less<>());
}

is_sorted_until (2)

template<class ForwardIt, class Compare>
constexpr //< since C++20
ForwardIt is_sorted_until(ForwardIt first, ForwardIt last, Compare comp)
{
    if (first != last)
    {
        ForwardIt next = first;
        while (++next != last)
        {
            if (comp(*next, *first))
                return next;
            first = next;
        }
    }
    return last;
}

Пример

#include <algorithm>
#include <cassert>
#include <iostream>
#include <iterator>
#include <random>
#include <string>

int main()
{
    std::random_device rd;
    std::mt19937 g(rd());
    const int N = 6;
    int nums[N] = {3, 1, 4, 1, 5, 9};
    
    const int min_sorted_size = 4;
    
    for (int sorted_size = 0; sorted_size < min_sorted_size;)
    {
        std::shuffle(nums, nums + N, g);
        int *const sorted_end = std::is_sorted_until(nums, nums + N);
        sorted_size = std::distance(nums, sorted_end);
        assert(sorted_size >= 1);
        
        for (const auto i : nums)
            std::cout << i << ' ';
        std::cout << ": " << sorted_size << " initial sorted elements\n"
                  << std::string(sorted_size * 2 - 1, '^') << '\n';
    }
}

Возможный вывод:

4 1 9 5 1 3 : 1 initial sorted elements
^
4 5 9 3 1 1 : 3 initial sorted elements
^^^^^
9 3 1 4 5 1 : 1 initial sorted elements
^
1 3 5 4 1 9 : 3 initial sorted elements
^^^^^
5 9 1 1 3 4 : 2 initial sorted elements
^^^
4 9 1 5 1 3 : 2 initial sorted elements
^^^
1 1 4 9 5 3 : 4 initial sorted elements
^^^^^^^

См. также

is_sorted (C++11)	проверяет, отсортирован ли диапазон (шаблон функции и функциональный объект алгоритма)
ranges::is_sorted (C++20)
ranges::is_sorted_until (C++20)	находит наибольший отсортированный поддиапазон (функциональный объект алгоритма)

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