std::ranges::is_sorted_until

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 = {} );

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 = {} );

Examina el rango [first, last) y encuentra el rango más grande que comienza en first en el cual los elementos están ordenados en orden no descendente.

Una secuencia está ordenada con respecto a un comparador comp si para cualquier iterador it que apunta a la secuencia y cualquier entero no negativo n tal que it + n es un iterador válido que apunta a un elemento de la secuencia, std::invoke(comp, std::invoke(proj, *(it + n)), std::invoke(proj, *it)) se evalúa a false.

Las entidades similares a funciones descritas en esta página son objetos función de algoritmo (conocidos informalmente como niebloids), es decir:

• No se pueden especificar listas explícitas de argumentos de plantilla al llamar a cualquiera de ellos.
• Ninguno de ellos es visible mediante búsqueda dependiente de argumentos.
• Cuando cualquiera de ellos es encontrado por búsqueda normal no calificada como el nombre a la izquierda del operador de llamada a función, búsqueda dependiente de argumentos se inhibe.

Parámetros

Valor de retorno

El límite superior del rango más grande que comienza en first en el cual los elementos están ordenados de forma no decreciente. Es decir, el último iterador it para el cual el rango [ first , it ) está ordenado.

Complejidad

Lineal en la distancia entre first y last .

Implementación posible

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;

Notas

ranges::is_sorted_until devuelve un iterador igual a last para rangos vacíos y rangos de longitud uno.

Ejemplo

#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)

Véase también