そろそろSTLのsortについてまじめに語ろうと思う。
でもごめん。余白が足りないのであんまり書けない。
まず、簡単な使い方。
サンプル１：
#include <vector>
#include <algorithm>
using namespace std;
vector< int > target;
target.push_back(3);
target.push_back(1);
target.push_back(4);
target.push_back(0);
target.push_back(2);
sort(target.begin(), target.end());
結果は0,1,2,3,4になる。sortの引数はランダムアクセスイテレータなら何でもよく、vectorじゃなくてもdaqueでもいいし、配列のポインタでもいい。ただし、ソートの範囲は第2引数の終端を含まないので注意が必要。vectorとかのend()は最終要素の一つ先を指しているから上記で問題ない。（配列でやるときは無理矢理一歩先を入れればいいのかな？？）
サンプル２：
#include <algorithm> // for "sort"
using namespace std;
int target[5];
target[0] = 3;
target[1] = 1;
target[2] = 4;
target[3] = 0;
target[4] = 2;
sort(&(target[0]), &(target[4]));
0,1,3,4,2になる。&(target[4])を&(target[5])にすれば、VC2008ではサンプル１と同じ結果になった。
で、前置きはこれくらいにして、書きたかったのは自前の比較関数について。その前にまず、サンプル１は以下のサンプル３と全く同じであることを押さえておく。
サンプル３：
#include <vector>
#include <algorithm> // for "sort"
#include <functional> // for "less"
std::vector< int > target;
target.push_back(3);
target.push_back(1);
target.push_back(4);
target.push_back(0);
target.push_back(2);
std::sort(target.begin(), target.end(), std::less< int >());
namespaceのstdを復活させてみたのはlessのnamespaceを明示するため。ようするにサンプル１のsortはデフォルトで比較関数にlessを使っているということ。したがって自前の比較関数を使いたい場合はこのlessの代わりになるような物を作ればいい。lessっていうのはつまり<。小なりで比較する。なので、比較関数というとちょっと語弊がある。一般に（C言語とかPHPで）比較関数というと、
int cmp(int a, int b) {
if (a < b) {
return -1;
} else if (a == b) {
return 0;
} else {
return 1;
}
}
というように第1引数が第2引数より小さいときに-1、等しいときに0、大きいときに1を返すのが普通（昇順ソートの場合）。たいてい、
int cmp(int a, int b) {
return a - b;
}
でも間に合う。a、bがint型じゃないときは型にあわせてa-bを定義するようなイメージがある。しかし、stlのsortに対して同じようなイメージで比較関数を作るとハマル。なぜならless< int >(a, b)はa < bの時にtrueを返すから。そもそもlessの戻り値はboolであり、昇順ソートにするためにはa - bが負になるときにtrueを返さないといけなく、a - bが正になるときおよび0になるときにfalseを返さないといけない。降順ソートしたい場合は逆の真偽値にすればよいので、降順ソートにする場合は次のようなtestcmpを定義すればよい。
サンプル４：
bool testcmp(int a, int b) {
if (a > b) {
return true;
} else {
return false;
}
}
std::sort(target.begin(), target.end(), testcmp);
もっとも、本当に降順ソートしたいだけなら自分で定義しなくてもstd::greater< int >()を使った方がいい。
サンプル４だとC言語のqsort使ってるのと同じような感じであるが、せっかくC++、STLなので関数オブジェクトを利用した方がいい。
サンプル５：
struct testcmp {
bool operator()(int a, int b) const {
if (a > b) {
return true;
} else {
return false;
}
}
};
std::sort(target.begin(), target.end(), testcmp());
関数オブジェクトはoperator()をオーバーロードした物で、ソートのための比較オブジェクトを作るためには引数を二つ取るoperator()を作ればいい。関数オブジェクトはオブジェクトでありながらoperator()が定義されているが故に関数みたいに使える物である。関数オブジェクトにすることで比較部分がinline化されるため、より高速にソートできるようになる。上記はstructで作成したが当然classでもいい。ただし、publicをつける（structだと勝手にpublicになる）。
サンプル６：
class testcmp {
public:
bool operator()(int a, int b) const {
if (a > b) {
return true;
} else {
return false;
}
}
};
testcmp mycmp;
bool result1 = mycmp(3, 1); // true
bool result2 = mycmp(1, 2); // false
std::sort(target.begin(), target.end(), mycmp);
サンプル６のようにインスタンス化してからsortの第3引数に渡すこともできるが、これだとたぶんinline化されないんじゃないかと思う（よく知らない）。
たぶん、すぐ忘れるので今のうちにメモっておいた。
以上
