std::is_sorted_until

template< class ForwardIt >
ForwardIt is_sorted_until( ForwardIt first, ForwardIt last );

template< class ExecutionPolicy, class ForwardIt >
ForwardIt is_sorted_until( ExecutionPolicy&& policy,
                           ForwardIt first, ForwardIt last );

template< class ForwardIt, class Compare >
ForwardIt is_sorted_until( ForwardIt first, ForwardIt last,
                           Compare comp );

template< class ExecutionPolicy, class ForwardIt, class Compare >
ForwardIt is_sorted_until( ExecutionPolicy&& policy,
                           ForwardIt first, ForwardIt last,
                           Compare comp );

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

Параметры

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

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

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

Сложность

Пусть \(\scriptsize N\)N равно std::distance(first, last):

Исключения

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

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

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

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

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

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
^^^^^^^

Смотрите также