stable_sort

Rozmieszcza elementy w określonym zakresie do nondescending zamówienia lub kryterium sortowania określony przez predykatu dwuelementowego i zachowuje względna kolejność elementów równoważnych.

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

Parametry

• _First
  Dwukierunkowy iteratora adresowania pozycja pierwszego elementu w zakresie sortowania.

• _Last
  Dwukierunkowy iteratora adresowania jedną pozycję w przeszłości końcowy element w zakresie sortowania.

• _Comp
  Obiektu predykatu funkcję zdefiniowaną przez użytkownika, który definiuje kryterium Porównanie mają być spełnione przez kolejne elementy w kolejności.Predykatu dwuelementowego ma dwa argumenty i zwraca true po stwierdzeniu i false , gdy nie są spełnione.

Uwagi

Zakres odwołania musi być ważny; wszystkie wskaźniki muszą być dereferenceable i w ramach sekwencji ostatniej pozycji jest dostępny z pierwszym przez incrementation.

Elementy są równoważne, ale niekoniecznie równości, jeśli nie jest mniejsza niż inne.Sortowania algorytm jest stabilna i gwarantuje, że względna kolejność elementów równoważnych zostaną zachowane.

Złożoność run-time stable_sort zależy od ilości pamięci, ale jest najlepszym przypadku (podane w wystarczającej ilości pamięci) o(n dziennika n) i najgorszego przypadku jest o( n (dziennika n ) 2), gdzie n = _Last – pierwszy. Zazwyczaj sortowania jest znacznie szybsze niż algorytm stable_sort.

Przykład

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

Wymagania

Nagłówek: <algorithm>

Obszar nazw: std

Zobacz też

Informacje

Standardowa biblioteka szablonu