STL sortソートアルゴリズムの詳細
14415 ワード
C++がこんなに多くの人に好かれているのは、オブジェクト向けの概念を持っているだけでなく、C言語の効率的な特徴を維持しているからです.STLソートアルゴリズムも同様に効率を保つ必要がある.したがって,異なるニーズに対してSTLが提供する異なる関数,異なる関数,実現アルゴリズムは異なる.
1.1すべてのsortアルゴリズムすべてのsortアルゴリズムのパラメータを説明するには、範囲を入力する必要があります.[begin,end].ここで使用する反復器(iterator)は、ランダム反復器(RadomAccessIteraterator)、つまり、it+nなどのランダムアクセス可能な反復器である必要があります.(partitionとstable_partitionを除く)
比較関数を自分で定義する必要がある場合は、定義したシミュレーション関数(functor)をパラメータとして渡すことができます.各アルゴリズムは、転送比較関数をサポートします.以下は、STL sortアルゴリズムのすべての関数の名前のリストです.
関数名
機能の説明
sort
指定した区間のすべての要素をソート
stable_sort
指定された区間のすべての要素を安定してソート
partial_sort
指定した区間のすべての要素の部分をソート
partial_sort_copy
指定した区間をコピーしてソート
nth_element
指定された区間の位置に対応する要素を特定します.
is_sorted
1つの区間が順序付けされているかどうかを判断する
partition
ある条件に合致する要素を前に置く
stable_partition
ある条件に合致する元素を前に置くように相対的に安定している.
ここでnth_elementは最も理解しにくいが,実際には,この関数はいくつかを見つけるために用いられる.たとえば、7つの要素を含む配列の中で真ん中の数の値を見つけます.この場合、私は前に関心がないかもしれませんが、後ろにも関心がありません.私は4番目の要素の値がどれだけあるかだけに関心があります.
1.2 sortの比較関数特定の方法でソートする必要がある場合は、sortに比較関数を指定する必要があります.そうしないと、プログラムは自動的に比較関数を提供します.
1.1すべてのsortアルゴリズムすべてのsortアルゴリズムのパラメータを説明するには、範囲を入力する必要があります.[begin,end].ここで使用する反復器(iterator)は、ランダム反復器(RadomAccessIteraterator)、つまり、it+nなどのランダムアクセス可能な反復器である必要があります.(partitionとstable_partitionを除く)
比較関数を自分で定義する必要がある場合は、定義したシミュレーション関数(functor)をパラメータとして渡すことができます.各アルゴリズムは、転送比較関数をサポートします.以下は、STL sortアルゴリズムのすべての関数の名前のリストです.
関数名
機能の説明
sort
指定した区間のすべての要素をソート
stable_sort
指定された区間のすべての要素を安定してソート
partial_sort
指定した区間のすべての要素の部分をソート
partial_sort_copy
指定した区間をコピーしてソート
nth_element
指定された区間の位置に対応する要素を特定します.
is_sorted
1つの区間が順序付けされているかどうかを判断する
partition
ある条件に合致する要素を前に置く
stable_partition
ある条件に合致する元素を前に置くように相対的に安定している.
ここでnth_elementは最も理解しにくいが,実際には,この関数はいくつかを見つけるために用いられる.たとえば、7つの要素を含む配列の中で真ん中の数の値を見つけます.この場合、私は前に関心がないかもしれませんが、後ろにも関心がありません.私は4番目の要素の値がどれだけあるかだけに関心があります.
1.2 sortの比較関数特定の方法でソートする必要がある場合は、sortに比較関数を指定する必要があります.そうしないと、プログラムは自動的に比較関数を提供します.
vector < int > vect;
//...
sort(vect.begin(), vect.end());
//
sort(vect.begin(), vect.end(), less<int>() );
上記の例では、システム自身がsortにlessシミュレーション関数を提供している.STLには他の擬似関数も用意されています.以下は擬似関数のリストです.
名前
機能の説明
equal_to
等しい
not_equal_to
等しくない
less
より小さい
greater
より大きい
less_equal
以下
greater_equal
以上
注意しなければならないのは、これらの関数があなたのsortアルゴリズムに適用できるわけではありません.どのように選択するかは、あなたの応用によって決まります.また、ダミー関数の名前を直接書き込むのではなく、そのリロードする()関数を書きます.less()
greater()
コンテナ内の要素の場合、いくつかの標準タイプ(int float char)またはstringの場合、これらの関数テンプレートを直接使用することができます.しかし、自分で定義したタイプや、他の方法でソートする必要がある場合は、2つの方法で効果を達成することができます.1つは、自分で比較関数を書くことです.もう1つはリロードタイプの'
#include
#include
#include
#include
#include
using namespace std;
class myclass
{
public:
myclass(int a, int b):first(a),second(b){}
int first;
int second;
bool operator < (const myclass &m)const
{
return first < m.first;
}
};
bool less_second(const myclass &m1, const myclass &m2)
{
return m1.second < m2.second;
}
int main(int argc, char *argv[])
{
QCoreApplication a(argc, argv);
vector< myclass > vect;
for(int i = 0; i < 10; i++)
{
myclass my(10 - i, i * 3);
vect.push_back(my);
}
cout<
Starting /home/jz/test/test...
：
(10,0)
(9,3)
(8,6)
(7,9)
(6,12)
(5,15)
(4,18)
(3,21)
(2,24)
(1,27)
(sort ):
(1,27)
(2,24)
(3,21)
(4,18)
(5,15)
(6,12)
(7,9)
(8,6)
(9,3)
(10,0)
( ):
(10,0)
(9,3)
(8,6)
(7,9)
(6,12)
(5,15)
(4,18)
(3,21)
(2,24)
(1,27)
end
1.3 sort
sortとstableがあることに づきましたsort、そしてpartitionとstable_partition、おかしいでしょう.この いは、stable き が、 しい の の がソート も わらないことを することである.もしかするとあなたは くことができて、 しい 、あなたはまだ の な を して、 が なのか かりませんか?ここでは、あなたが した が2つの が しいことを し、 ずしも じ ではないという を らかにする があります.
たとえば、 を くとします.
bool less_len(const string &str1, const string &str2)
{
return str1.length() < str2.length();
}
この 、「apple」と「winter」は しく、「apple」が「winter」の に され、stable きの でソートされると、 らの は に わりません.「stable」のない でソートされると、ソートが すると、「Winter」が「apple」の になる があります.
1.4フルソートフルソートとは、 された のすべての をサイズ に べ えることです. ソートに される は のとおりです.
template <class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class StrictWeakOrdering>
void sort(RandomAccessIterator first, RandomAccessIterator last,
StrictWeakOrdering comp);
template <class RandomAccessIterator>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class StrictWeakOrdering>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last,
StrictWeakOrdering comp);
1,3の ではsortとstable_sortは を していません.operator<をデフォルトで して [first,last) のすべての をソートします.そのため、あなたが しているタイプの がoperatorクラスに10 の を ロードした 、 らの ランキングを りたいです.
#include
#include
#include
#include
#include
using namespace std;
class student{
public:
student(const string &a, int b):name(a), score(b){}
string name;
int score;
bool operator < (const student &m)const {
return score< m.score;
}
};
int main() {
vector< student> vect;
student st1("Tom", 74);
vect.push_back(st1);
st1.name="Jimy";
st1.score=56;
vect.push_back(st1);
st1.name="Mary";
st1.score=92;
vect.push_back(st1);
st1.name="Jessy";
st1.score=85;
vect.push_back(st1);
st1.name="Jone";
st1.score=56;
vect.push_back(st1);
st1.name="Bush";
st1.score=52;
vect.push_back(st1);
st1.name="Winter";
st1.score=77;
vect.push_back(st1);
st1.name="Andyer";
st1.score=63;
vect.push_back(st1);
st1.name="Lily";
st1.score=76;
vect.push_back(st1);
st1.name="Maryia";
st1.score=89;
vect.push_back(st1);
cout<------before sort..."<for(int i = 0 ; i < vect.size(); i ++) cout<:\t"<());
cout <-----after sort ...."<for(int i = 0 ; i < vect.size(); i ++) cout<:\t"<return 0 ;
}
sort " "( STL ， )。 1， 、 n*log(n)， ， ， n*n， STL ， 。stable_sort " "， ， n*log(n), n*log(n)*log(n)， 。
1.5ローカルソートローカルソートは、 には な を らすために されるソート である. のプロトタイプは のとおりです.
template <class RandomAccessIterator>
void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last);
template <class RandomAccessIterator, class StrictWeakOrdering>
void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last,
StrictWeakOrdering comp);
template <class InputIterator, class RandomAccessIterator>
RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last);
template <class InputIterator, class RandomAccessIterator,
class StrictWeakOrdering>
RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last, Compare comp);
sortとstableを しましたsort 、partial_を します.sortは です.まずその を てみましょう.クラスには10 の がいますが、 が い5 はどんな なのか りたいです.partialがなかったらsort、あなたはsortですべての を に べて、それから の5つを る があります. の 5 を べ えて、 のプログラムを のように するだけです.
stable_sort(vect.begin(), vect.end(),less());
：
partial_sort(vect.begin(), vect.begin()+5, vect.end(),less());
このようなメリットは かりましたか?データ が さいときは が えないかもしれませんが、100 の なら、 が ない5 を したいのですが...
partial_sortは、いかなる においてもn*log(n)の さを するスタックソート(heapsort)を する.partialを いたいならsortは ソートを し、middle=lastだけでいいです.
partial_sort_copyは はcopyとpartial_sortの み わせ. べ えられる(コピーされる) は、[first,last]と[result_first,result_last)の が さいものである.[result_first,result_last) が[first,last) より きい 、partial_sortはcopyとsortの せに する.
1.6 nth_element ソートnth_Elementは かりやすいが が なソートです. を げるともっと です.
クラスには10 の がいます. が の4 の を りたいです.
のニーズを たすにはsortで を めて4 ( さいから きいまで)を って、もっと のいい はpartial_を います.sortは、 4 にとどまり、4 を した. はこれはあなたがまだ して、 の2 はあなたが べ える がないため、この 、あなたはnth_が ですelement:
template <class RandomAccessIterator>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last);
template <class RandomAccessIterator, class StrictWeakOrdering>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last, StrictWeakOrdering comp);
のインスタンスの については、 の に って1.4のプログラムを する があります.
stable_sort(vect.begin(), vect.end(),less());
：
nth_element(vect.begin(), vect.begin()+3, vect.end(),less());
4 は ですか.Andyer、この の いやつ.なぜ+4ではなくbegin()+3なのか. がこの を き めたときも にしなかったが、 で
ilovevcの で、この を しました.begin()は1 、begin()+1は2 、...begin()+3はもちろん4つ です.
1.7 partitionとstable_partitionはこの2つの がソートに われていないようで、「 」アルゴリズムは、より になります.partitionは,1つの の をある に って2つに する. のプロトタイプは のとおりです.
template <class ForwardIterator, class Predicate>
ForwardIterator partition(ForwardIterator first,
ForwardIterator last, Predicate pred)
template <class ForwardIterator, class Predicate>
ForwardIterator stable_partition(ForwardIterator first, ForwardIterator last,
Predicate pred);
を てみましょう.クラスの10 の は、 していない(60 ) をすべて します.1.4のプログラムを の で き えるだけです.
stable_sort(vect.begin(), vect.end(),less());
：
student exam("pass", 60);
stable_partition(vect.begin(), vect.end(), bind2nd(less(), exam));
stable_partition, .
2 Sortと
STLの コンテナの なvector、list、deque、string、set、multiset、map、multimay、set、multiset、map、multimapは、その の をツリー で しています.
STL map,STL setのデータ の を ぶ.したがって、これらの では、 は に されています.
これらのコンテナの タイプはランダム ではないので、 のソート は、これらのコンテナでは できません. sort は、 のコンテナで できます. vector string deque
で したコンテナでもランダム がサポートされている は、ソートアルゴリズムを しても ありません.
listコンテナの 、listはsortメンバー list::sort().アルゴリズム におけるsortとの は ないがlist::sortはポインタに づくソートである、すなわち、すべてのデータの と はポインタによって されるため、ソート の は に である(vectorにおけるsort の は である).
3 なソート の
もしあなたが C のqsortを ったことがあるならば、qsortと らの を りたいならば、 はあなたに えて、qsortとsortは じで、 らはすべて なソートを しているためです. に ると、 のsortアルゴリズムは、 が いものから いもの( の が さいものから きいもの)へのソートです. partion stable_partition nth_element partial_sort sort stable_sort