stable_sort
Classe les éléments d'une plage spécifiée dans un ordre non décroissant, ou selon un critère de tri spécifié par un prédicat binaire, et conserve l'ordre relatif des éléments équivalents.
template<class BidirectionalIterator>
void stable_sort(
BidirectionalIterator _First,
BidirectionalIterator _Last
);
template<class BidirectionalIterator, class BinaryPredicate>
void stable_sort(
BidirectionalIterator _First,
BidirectionalIterator _Last,
BinaryPredicate _Comp
);
Paramètres
_First
Itérateur bidirectionnel se rapportant à la position du premier élément dans la plage à trier._Last
Itérateur bidirectionnel se rapportant à la position située immédiatement après l'élément final dans la plage à trier._Comp
Objet de la fonction de prédicat définie par l'utilisateur qui définit les critères de comparaison à satisfaire par des éléments consécutifs dans le classement. Un prédicat binaire a besoin de deux arguments. Il renvoie true lorsqu'il est satisfait et false dans le cas contraire.
Notes
La plage source triée référencée doit être valide ; tous les pointeurs doivent être deréférençables et, dans la séquence, la dernière position doit être accessible à partir de la première par incrémentation.
Les éléments sont équivalents, mais pas nécessairement égaux, si aucun n'est inférieur à l'autre. L'algorithme de tri n'est pas stable et garantit que l'ordre relatif des éléments équivalents soit conservé.
La complexité d'exécution de stable_sort dépend de la quantité de mémoire disponible, mais le meilleur cas (si on a suffisamment de mémoire) est O(N log N) et le pire cas est O( N ( log N )2 ), where N = _Last – First. En règle générale, l'algorithme de tri est considérablement plus rapide que stable_sort.
Exemple
// alg_stable_sort.cpp
// compile with: /EHsc
#include <vector>
#include <algorithm>
#include <functional> // For greater<int>( )
#include <iostream>
// Return whether first element is greater than the second
bool UDgreater (int elem1, int elem2 )
{
return elem1 > elem2;
}
int main( )
{
using namespace std;
vector <int> v1;
vector <int>::iterator Iter1;
int i;
for ( i = 0 ; i <= 5 ; i++ )
{
v1.push_back( 2 * i );
}
for ( i = 0 ; i <= 5 ; i++ )
{
v1.push_back( 2 * i );
}
cout << "Original vector v1 = ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")" << endl;
stable_sort(v1.begin( ), v1.end( ) );
cout << "Sorted vector v1 = ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")" << endl;
// To sort in descending order, specify binary predicate
stable_sort(v1.begin( ), v1.end( ), greater<int>( ) );
cout << "Resorted (greater) vector v1 = ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")" << endl;
// A user-defined (UD) binary predicate can also be used
stable_sort(v1.begin( ), v1.end( ), UDgreater );
cout << "Resorted (UDgreater) vector v1 = ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")" << endl;
}
Configuration requise
En-tête : <algorithme>
Espace de noms : std