std::stable_sort

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

Trie les éléments dans la plage [first, last) dans un ordre non décroissant. L'ordre des éléments équivalents est garanti d'être préservé.

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

3) Les éléments sont triés par rapport à comp.

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

Ces surcharges ne participent à la résolution de surcharge que 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)

Si l'une des conditions suivantes est satisfaite, le comportement est indéfini :

Le type de `*first` n'est pas Échangeable.	(jusqu'à C++11)
`RandomIt` n'est pas ValeurÉchangeable. Le type de `first` n'est pas Constructible par déplacement. Le type de `first` n'est pas Affectable par déplacement.	(depuis C++11)

Paramètres

first, last	-	la paire d'itérateurs définissant la plage d'éléments à trier
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 pouvoir accepter toutes les valeurs du 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 RandomIt puisse être déréférencé puis implicitement converti vers les deux.
Exigences de type
- `RandomIt` doit satisfaire aux exigences de LegacyRandomAccessIterator .
- `Compare` doit satisfaire aux exigences de Compare .

Complexité

Étant donné $\scriptsize N$ $N$ comme last - first :

1,2)

O(N\cdotlog(N))

comparaisons en utilisant operator < (jusqu'à C++20) std:: less { } (depuis C++20) si suffisamment de mémoire supplémentaire est disponible, sinon

O(N\cdotlog 2 (N))

comparaisons.

3,4)

O(N\cdotlog(N))

applications du comparateur comp si suffisamment de mémoire supplémentaire est disponible, sinon

O(N\cdotlog 2 (N))

applications.

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++ .

Notes

Cette fonction tente d'allouer un tampon temporaire de taille égale à celle de la séquence à trier. Si l'allocation échoue, l'algorithme moins efficace est choisi.

Macro de test de fonctionnalité	Valeur	Std	Fonctionnalité
`__cpp_lib_constexpr_algorithms`	`202306L`	(C++26)	constexpr tri stable, surcharges ( 1 ) , ( 3 )

Exemple

Exécuter ce code

#include <algorithm>
#include <array>
#include <iostream>
#include <string>
#include <vector>
struct Employee
{
    int age;
    std::string name; // Ne participe pas aux comparaisons
};
bool operator<(const Employee& lhs, const Employee& rhs)
{
    return lhs.age < rhs.age;
}
#if __cpp_lib_constexpr_algorithms >= 202306L
consteval auto get_sorted()
{
    auto v = std::array{3, 1, 4, 1, 5, 9};
    std::stable_sort(v.begin(), v.end());
    return v;
}
static_assert(std::ranges::is_sorted(get_sorted()));
#endif
int main()
{
    std::vector<Employee> v{{108, "Zaphod"}, {32, "Arthur"}, {108, "Ford"}};
    std::stable_sort(v.begin(), v.end());
    for (const Employee& e : v)
        std::cout << e.age << ", " << e.name << '\n';
}

Sortie :

32, Arthur
108, Zaphod
108, Ford

Voir aussi

sort	trie une plage d'éléments (modèle de fonction & objet fonction d'algorithme)
ranges::sort (C++20)
partial_sort	trie les N premiers éléments d'une plage (modèle de fonction & objet fonction d'algorithme)
ranges::partial_sort (C++20)
stable_partition	divise les éléments en deux groupes tout en préservant leur ordre relatif au sein de chaque groupe (modèle de fonction & objet fonction d'algorithme)
ranges::stable_partition (C++20)
ranges::stable_sort (C++20)	trie une plage d'éléments tout en préservant l'ordre relatif entre éléments équivalents (objet fonction d'algorithme)

Support du compilateur
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 de 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 de plages (C++20)
Bibliothèque d'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 de système de fichiers (C++17)
Bibliothèque de support de 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