std::is_sorted

Défini dans l'en-tête `<algorithm>`
template< class ForwardIt > bool is_sorted( ForwardIt first, ForwardIt last );	(1)	(depuis C++11) (constexpr depuis C++20)
template< class ExecutionPolicy, class ForwardIt > bool is_sorted( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last );	(2)	(depuis C++17)
template< class ForwardIt, class Compare > bool is_sorted( ForwardIt first, ForwardIt last, Compare comp );	(3)	(depuis C++11) (constexpr depuis C++20)
template< class ExecutionPolicy, class ForwardIt, class Compare > bool is_sorted( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, Compare comp );	(4)	(depuis C++17)

Vérifie si les éléments dans la plage [first, last) sont triés dans un ordre non décroissant.

1) Vérifie si les éléments sont triés par rapport à operator<(jusqu'à C++20)std::less{}(depuis C++20).

3) Vérifie si les éléments sont triés par rapport à comp.

2,4) Identique à (1,3), mais exécuté selon policy.

Ces surcharges participent à la résolution de surcharge uniquement si la valeur de l'expression suivante est true:

`std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>`	(jusqu'à C++20)
`std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>`	(depuis C++20)

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 les 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 pouvoir 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 équivaut à 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 en chacun d'eux.
Exigences de type
- `ForwardIt` doit satisfaire les exigences de LegacyForwardIterator.
- `Compare` doit satisfaire les exigences de Compare.

Valeur de retour

true si les éléments de la plage sont triés dans un ordre non décroissant, false sinon.

Complexité

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

1,2)

O(N)

comparaisons en utilisant operator<(jusqu'à 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 est l'une des politiques standard, std::terminate est appelée. 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ée.

Implémentation possible

Voir aussi les implémentations dans libstdc++ et libc++.

is_sorted (1)

template<class ForwardIt>
bool is_sorted(ForwardIt first, ForwardIt last)
{
    return std::is_sorted_until(first, last) == last;
}

is_sorted (3)

template<class ForwardIt, class Compare>
bool is_sorted(ForwardIt first, ForwardIt last, Compare comp)
{
    return std::is_sorted_until(first, last, comp) == last;
}

Notes

std::is_sorted retourne true pour les plages vides et les plages de longueur un.

Exemple

Exécuter ce code

#include <algorithm>
#include <cassert>
#include <functional>
#include <iterator>
#include <vector>

int main()
{
    std::vector<int> v;
    assert(std::is_sorted(v.cbegin(), v.cend()) && "an empty range is always sorted");
    v.push_back(42);
    assert(std::is_sorted(v.cbegin(), v.cend()) && "a range of size 1 is always sorted");
    
    int data[] = {3, 1, 4, 1, 5};
    assert(not std::is_sorted(std::begin(data), std::end(data)));
    
    std::sort(std::begin(data), std::end(data));
    assert(std::is_sorted(std::begin(data), std::end(data)));
    assert(not std::is_sorted(std::begin(data), std::end(data), std::greater<>{}));
}

Voir aussi

is_sorted_until (C++11)	trouve la plus grande sous-plage triée (modèle de fonction & objet fonction d'algorithme)
ranges::is_sorted_until (C++20)
ranges::is_sorted (C++20)	vérifie si une plage est triée (objet fonction d'algorithme)

Support du compilateur
Environnement autonome et hébergé
Langage
Bibliothèque standard
En-têtes de la bibliothèque standard
Exigences nommées
Macros de test de fonctionnalités (C++20)
Bibliothèque de support du langage
Bibliothèque des concepts (C++20)
Bibliothèque de diagnostics
Bibliothèque de gestion de la mémoire
Bibliothèque de métaprogrammation (C++11)
Bibliothèque d'utilitaires généraux
Bibliothèque de conteneurs
Bibliothèque d'itérateurs
Bibliothèque des ranges (C++20)
Bibliothèque des algorithmes
Bibliothèque de chaînes
Bibliothèque de traitement de texte
Bibliothèque numérique
Bibliothèque de date et heure
Bibliothèque d'entrée/sortie
Bibliothèque du système de fichiers (C++17)
Bibliothèque de support de la concurrence (C++11)
Bibliothèque de contrôle d'exécution (C++26)
Spécifications techniques
Index des symboles
Bibliothèques externes

fr.cppreference.net

Namespaces

Variants