stable_sort

Artikel
03/26/2013

Ordnet die Elemente in einem angegebenen Bereich in eine nondescending Reihenfolge oder gemäß einem Sortierkriterium an, das durch ein binäres Prädikat angegeben ist und behält die relative Reihenfolge der übereinstimmenden Elemente bei.

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 bidirektionaler Iterator, der die Position des ersten Elements im Bereich behandelt sortiert werden.
_Last
Ein bidirektionaler Iterator, der die Position eine hinter dem letzten Element im Bereich behandelt sortiert werden.
_Comp
Benutzerdefiniertes Prädikatfunktionsobjekt, das das durch aufeinander folgende definiert Elemente in der Reihenfolge erfüllt werden Vergleichskriterium.Ein binäres Prädikat verwendet zwei Argumente und gibt zurück, wenn true erfüllt und false, wenn nicht erfüllt wird.

Hinweise

Der Bereich, der verweist, muss gültig sein; alle Zeiger müssen dereferenzierbar sein und in der Sequenz ist die letzte Position von der ersten durch Zunahme erreichbar.

Elemente sind äquivalent, aber nicht notwendigerweise entsprechen, wenn kein kleiner als das andere ist.Der Algorithmus ist sort stabil und stellt sicher, dass die relative Reihenfolge der entsprechenden Elemente beibehalten wird.

Die Ablaufkomplexität von stable_sort hängt vom verfügbaren Arbeitsspeicher ab, aber der beste Fall (genügend Arbeitsspeicher zugewiesen) ist O( n)N-Protokoll und der schlimmste Fall ist O( n (log n ) 2), wobei n = _Last - zuerst. 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