31項 ソートの選択肢を知っておこう

Effective STL

ソートの選択肢を知っておこう



partial_sortは、比較関数によってソートされたN個の要素をコンテナの先頭に配置します。

bool qualityCompare(const Widget &lhs, const Widget &rhs)
{
　　　　...　　　　//lhsの品質がrhsより高いかどうかを返す
}
...

partial_sort( widgets.begin(),      //widgetsの先頭から順番に
              widgets.begin() + 20, //20個の最高品質の
              widgets.end(),        //要素を入れる
              qualityCompare );

nth_elementは、比較関数によって得られるN個の要素を、順序を規定せずコンテナの先頭に配置します。

nth_element(  widgets.begin(),      //widgetsの先頭から順番を気にせず
              widgets.begin() + 20, //20個の最高品質の
              widgets.end(),        //要素を入れる
              qualityCompare );

通常のsort、partial_sort、nth_elementは不安定です。不安定というのは、等価な値を持つ要素の並び順が決まっていないということです。


安定的(等価な値を持つ要素の並び順は格納されていた順番になる)なソートを行うときは、stable_sortを使います。


条件に合うものをすべて先頭に持ってくるには、partitionを使います。

bool hasAcceptableQuality(const Widget &lhs, const Widget &rhs)
{
　　　　...　　　　//条件に合うかかどうかを返す
}
...

vector<Widget>::iterator goodEnd = 
    partition( widgets.begin(),       //hasAcceptableQualityを満たす要素を先頭に移動
               widgets.end(),         //戻り値は、hasAcceptableQualityを満たさない最初の要素への反復子
               hasAcceptableQuality);

partitionは不安定です。partition_stableは安定的なので、等価な要素の位置関係を保持します。


sort、stable_sort、partical_sort、nth_elementの各アルゴリズムはランダムアクセス反復子を必要とするため、vector、string、deque、配列にしか使えません。
listをソートするときは、list::sortを使います。list::sortは安定的です。
listにpartical_sortやnth_elementを使いたいときは、listのデータをランダムアクセス反復子を持つコンテナに移動してからアルゴリズムを使う方法、list::iteratorのコンテナにアルゴリズムを使ったあと反復子でアクセスする方法、ソートされた反復子のコンテナでlistの要素を希望する位置にspliceする方法などがあります。
partitionとstable_partitionはすべての標準シーケンスコンテナで使用できます。