stable_sort

Artikel
06/09/2015

Ordnet die Elemente in einem angegebenen Gültigkeitsbereich in eine nondescending Reihenfolge oder entsprechend einem Sortierkriterium an, das durch ein binäres Prädikat angegeben wird und behält die relative Position von entsprechenden Arbeitsaufgaben beibehalten.

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

Parameter

_First
Ein bidirektionalem Iterator, der die Position des ersten Elements im Bereich behandelt sortiert werden.
_Last
Ein bidirektionalem Iterator, der die Position eine hinter dem letzten Element im Bereich behandelt sortiert werden.
_Comp
Benutzerdefiniertes Prädikatfunktionsobjekt, das definiert durch aufeinander folgende Elemente in der Bestellung erfüllt werden Vergleichskriterium. Ein binärer Prädikat akzeptiert zwei Argumente und gibt bei Erfüllung true zurück und false, wenn es nicht erfüllt wird.

Hinweise

Der Bereich, auf den verwiesen wird, gültig sein; muss alle Zeiger müssen dereferenzierbar befinden der Sequenz ist die letzte Position der ersten von Zunahme erreichbar.

Elemente sind äquivalent, aber entsprechen nicht unbedingt, wenn nicht geringer als die andere. Der sort Algorithmus ist stabil und sichergestellt, dass die relative Position der entsprechenden Elemente beibehalten wird.

Die Ablaufkomplexität von stable_sort hängt vom verfügbaren Arbeitsspeicher ab, der am besten Fall (genügend Arbeitsspeicher vorhanden) ist O(N-Protokoll N) und der schlimmste Fall ist O( n (Protokoll N ) 2), wobei N = _Last - Priorität. Normalerweise ist der sort Algorithmus bedeutend schneller als stable_sort.

Beispiel

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

Anforderungen

Header: <algorithm>

Namespace: std

Siehe auch

Referenz

Standardvorlagenbibliothek

Freigeben über