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

Untersucht den Bereich [first, last) und findet den größten Bereich, der bei first beginnt, in dem die Elemente in nicht-absteigender Reihenfolge sortiert sind.

Parameter

erfüllen.

RückgabewertfirstDie obere Schranke des größten Bereichs, der bei it beginnt und in dem die Elemente in aufsteigender Reihenfolge sortiert sind. Das ist der letzte Iterator [first, it), für den der Bereich

sortiert ist. lastGibt

für leere Bereiche und Bereiche der Länge eins zurück.

KomplexitätGegeben \(\scriptsize N\)Nstd::distance(first, last) als

.

AusnahmenExecutionPolicyDie Überladungen mit einem Vorlagenparameter namens

• melden Fehler wie folgt: ExecutionPolicyWenn die Ausführung einer im Rahmen des Algorithmus aufgerufenen Funktion eine Ausnahme auslöst und eine der Standardrichtlinien ist, wird std::terminateExecutionPolicy aufgerufen. Für jede andere
• ist das Verhalten implementierungsdefiniert.Wenn der Algorithmus keinen Speicher zuweisen kann, wird std::bad_alloc

ausgelöst.

Mögliche ImplementierungSiehe auch die Implementierungen in libstdc++ und 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;
}

is_sorted_until (2)

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

Mögliche Ausgabe: