stable_sort

Articolo
03/26/2013

Dispone gli elementi in un intervallo specificato in un ordine nondescending o come un criterio di ordinamento specificato da un predicato binario e conserva l'ordine degli elementi equivalenti.

template<class BidirectionalIterator>
   void stable_sort(
      BidirectionalIterator _First, 
      BidirectionalIterator _Last
   );
template<class BidirectionalIterator, class BinaryPredicate>
   void stable_sort(
      BidirectionalIterator _First, 
      BidirectionalIterator _Last,
      BinaryPredicate _Comp
   );

Parametri

_First
Un iteratore bidirezionale destinato alla posizione del primo elemento nell'intervallo da ordinare.
_Last
Un iteratore bidirezionale destinato alla posizione una dopo l'elemento finale nell'intervallo da ordinare.
_Comp
Oggetto definito dall'utente di funzione di predicato che definisce i criteri di confronto da soddisfare gli elementi successivi in ordine.Un predicato binario accetta due argomenti e restituisce true una volta soddisfatti e false una volta non soddisfatta.

Note

l'intervallo fatto riferimento deve essere valido; tutti i puntatori devono essere dereferenceable e all'interno della sequenza dell'ultima posizione è raggiungibile da prima dall'aumento.

Gli elementi sono equivalenti, ma non necessariamente a, se non è inferiore all'altro.L'algoritmo di ordinamento diventa stabile e garantisce che l'ordine degli elementi equivalenti verrà mantenuto.

La complessità di runtime stable_sort dipende dalla quantità di memoria disponibile, ma il caso migliore (disponibile memoria sufficiente) è O(il log*N)*e il caso peggiore è O( N (log N ) 2), dove N = _Last – prima. In genere, l'algoritmo di ordinamento è notevolmente più veloce stable_sort.

Esempio

// 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;
}

Requisiti

intestazione: <algorithm>

Spazio dei nomi: deviazione standard

Vedere anche

Riferimenti

Libreria di modelli standard

Condividi tramite