stable_sort
指定された範囲の要素を nondescending 順序にまたはバイナリ述語によって指定される命令の基準に従って配置し、同等の要素の相対位置ディレクティブを保持します。
template<class BidirectionalIterator>
void stable_sort(
BidirectionalIterator _First,
BidirectionalIterator _Last
);
template<class BidirectionalIterator, class BinaryPredicate>
void stable_sort(
BidirectionalIterator _First,
BidirectionalIterator _Last,
BinaryPredicate _Comp
);
パラメーター
_First
分類される範囲内の先頭の要素の位置を示す双方向反復子。_Last
並べ替えられたする範囲の最後の要素の一つ前の位置 1 に対処双方向反復子。_Comp
順序で連続する要素が適合する比較の基準を定義するユーザー定義の述語関数オブジェクト。バイナリ述語が満たされなかった場合に完了したら 2 個の引数を受け取り、true と false を返します。
解説
参照される範囲が有効である必要があります; すべてのポインターが dereferenceable なり、シーケンス内で最後の位置は incrementation によって最初からアクセスできます。
要素は、いずれも他よりも小さい場合、同等ですが、必ずしも同じです。sort のアルゴリズムは同等の要素の相対的な命令が保存されるという保証安定してです。
stable_sort のランタイムの複雑さは、使用できるメモリの量によって決まりますが、最適な場合は (十分なメモリがある) O (n の ログ N) 、最悪の場合は O ( n (log n )、N = 2)。*最初に _Last – *です。通常、並べ替えのアルゴリズムは stable_sortよりはるかに高速です。
使用例
// 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;
}
必要条件
ヘッダー: <algorithm>
名前空間: std