Namespaces
Variants

std:: is_sorted_until

From cppreference.net
C++
Algorithm library
Constrained algorithms and algorithms on ranges (C++20)
Constrained algorithms, e.g. ranges::copy , ranges::sort , ...
Execution policies (C++17)
Non-modifying sequence operations
Batch operations
(C++17)
Search operations
Modifying sequence operations
Copy operations
(C++11)
(C++11)
(C++11)
Swap operations
Transformation operations
Generation operations
Removing operations
Order-changing operations
(until C++17) (C++11)
(C++20) (C++20)
Sampling operations
(C++17)

Sorting and related operations
Partitioning operations
Sorting operations
(C++11)
is_sorted_until
(C++11)

Binary search operations
(on partitioned ranges)
Set operations (on sorted ranges)
Merge operations (on sorted ranges)
Heap operations
Minimum/maximum operations
Lexicographical comparison operations
(C++20)
Permutation operations
C library
Numeric operations
Operations on uninitialized memory
Défini dans l'en-tête <algorithm>
template < class ForwardIt >
ForwardIt is_sorted_until ( ForwardIt first, ForwardIt last ) ;
(1) (depuis C++11)
(constexpr depuis C++20)
template < class ExecutionPolicy, class ForwardIt >

ForwardIt is_sorted_until ( ExecutionPolicy && policy,

ForwardIt first, ForwardIt last ) ;
(2) (depuis C++17)
template < class ForwardIt, class Compare >

ForwardIt is_sorted_until ( ForwardIt first, ForwardIt last,

Compare comp ) ;
(3) (depuis C++11)
(constexpr depuis C++20)
template < class ExecutionPolicy, class ForwardIt, class Compare >

ForwardIt is_sorted_until ( ExecutionPolicy && policy,
ForwardIt first, ForwardIt last,

Compare comp ) ;
(4) (depuis C++17)

Examine la plage [ first , last ) et trouve la plus grande plage commençant à first dans laquelle les éléments sont triés en ordre non décroissant.

1) Trouve la plus grande plage où les éléments sont triés par rapport à operator < (jusqu'en C++20) std:: less { } (depuis C++20) .
3) Trouve la plus grande plage où les éléments sont triés par rapport à comp .
2,4) Identique à (1,3) , mais exécuté selon la policy .
Ces surcharges participent à la résolution de surcharge seulement si toutes les conditions suivantes sont satisfaites :

std:: is_execution_policy_v < std:: decay_t < ExecutionPolicy >> est true .

(jusqu'à C++20)

std:: is_execution_policy_v < std:: remove_cvref_t < ExecutionPolicy >> est true .

(depuis C++20)

Table des matières

Paramètres

first, last - la paire d'itérateurs définissant la plage d'éléments à examiner
policy - la politique d'exécution à utiliser
comp - objet fonction de comparaison (c'est-à-dire un objet qui satisfait aux exigences de Compare ) qui retourne ​ true si le premier argument est inférieur à (c'est-à-dire est ordonné avant ) le second.

La signature de la fonction de comparaison doit être équivalente à ce qui suit :

bool cmp ( const Type1 & a, const Type2 & b ) ;

Bien que la signature n'ait pas besoin d'avoir const & , la fonction ne doit pas modifier les objets qui lui sont passés et doit être capable d'accepter toutes les valeurs de type (éventuellement const) Type1 et Type2 indépendamment de la catégorie de valeur (ainsi, Type1& n'est pas autorisé , pas plus que Type1 sauf si pour Type1 un déplacement est équivalent à une copie (depuis C++11) ).
Les types Type1 et Type2 doivent être tels qu'un objet de type ForwardIt puisse être déréférencé puis implicitement converti vers les deux. ​

Exigences de type
-
ForwardIt doit satisfaire aux exigences de LegacyForwardIterator .
-
Compare doit satisfaire aux exigences de Compare .

Valeur de retour

La limite supérieure de la plus grande plage commençant à first dans laquelle les éléments sont triés par ordre croissant. C'est-à-dire, le dernier itérateur it pour lequel la plage [ first , it ) est triée.

Retourne last pour les plages vides et les plages de longueur un.

Complexité

Étant donné N comme std:: distance ( first, last ) :

1,2) O(N) comparaisons en utilisant operator < (jusqu'en C++20) std:: less { } (depuis C++20) .
3,4) O(N) applications du comparateur comp .

Exceptions

Les surcharges avec un paramètre de modèle nommé ExecutionPolicy signalent les erreurs comme suit :

  • Si l'exécution d'une fonction invoquée dans le cadre de l'algorithme lève une exception et que ExecutionPolicy fait partie des politiques standard , std::terminate est appelé. Pour tout autre ExecutionPolicy , le comportement est défini par l'implémentation.
  • Si l'algorithme ne parvient pas à allouer de la mémoire, std::bad_alloc est levé.

Implémentation possible

Voir également les implémentations dans libstdc++ et 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;
}

Exemple

Exécuter ce code 
#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';
    }
}

Sortie possible : 

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

Voir aussi

(C++11)
vérifie si une plage est triée par ordre croissant
(modèle de fonction)
(C++20)
trouve la plus grande sous-plage triée
(objet fonction algorithme)