stable_sort

Article
03/26/2013

Réorganise les éléments dans une plage spécifiée dans une commande nondescending ou selon un critère de classement spécifié par un attribut binaire et conserve le classement 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
Un itérateur bidirectionnel adressant la position du premier élément dans la plage à trier.
_Last
Un itérateur bidirectionnel adressant une position au delà de le dernier élément dans la plage à trier.
_Comp
Objet défini par l'utilisateur de fonction de prédicat qui définit le critère de comparaison à répondre par des éléments consécutifs dans l'ordre.Un attribut binaire accepte deux arguments et retourne true si satisfaite et false une fois pas de contenu.

Notes

l'intervalle référencé doit être valide ; tous les pointeurs doivent être deréférençables et dans la séquence la dernière position est accessible dès le début par l'augmentation.

Les éléments sont identiques, mais pas nécessairement égales, si aucune n'est inférieure à l'autre.L'algorithme de tri stable et garantit que le classement relatif des éléments équivalents est conservé.

La complexité à l'exécution d' stable_sort dépend de la quantité de mémoire disponible, mais le meilleur cas (donné suffisamment de mémoire) est O(le journal*NN)*et le pire des cas est O( N (log N ) 2), où N = _Last – en premier. Généralement, l'algorithme de tri est nettement 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 : <algorithm>

l'espace de noms : DST

Voir aussi

Référence

Modèles Standard

Partager via