C++のalgorithmヘッダとか関数オブジェクトとかの話
明日から3日間，うちの大学で競技プログラマー向けの合宿が行われます．模擬コンテストは，AOJを使ってオンラインから参加できるそうなので是非ご参加ください．
さて，今回のエントリはC++の話です．競技プログラミングをC++でやるとなると，STLのコンテナ類を使いこなすことが大事ですよね．そして，algorithmヘッダで定義されている諸関数も大事だったりします．
競技プログラミング以外でも使うかなと思ってstd::は省略せずに書きます．
また，C++11のものと明示していないところは，C++03でも動くはずです．
fillは配列の初期化に便利ですね．
int array[100]; std::fill(array, array+100, -1); // [array, array+100)の範囲を-1にする．
実は，fill_nという関数もあって，
int array[100]; std::fill_n(array, 100, -1); // arrayから順に100個分の範囲を-1にする．
という風に少しタイプ量が減らせる場合があります．
特に，多次元配列を初期化する場合は効果的ですね．
int array[100][100][100]; std::fill((int*) array, (int*) array+100*100*100, -1); std::fill_n((int*) array, 100*100*100, -1);
そして，おなじみのsort
std::sort(vector.begin(), vector.end())
sortには第三引数に比較関数を与えることができます．上の例は，vectorの型がstd::vector
std::sort(vector.begin(), vector.end(), less<int>());
と同じ意味です．昇順にソートされます．第三引数に与えているのは比較関数を表わすオブジェクトで，引数a, bを取ってa < bを返すような関数です．降順にソートするには，
std::sort(vector.begin(), vector.end(), greater<int>());
とすればいいわけです．大小比較関数を引数に取る場合は，lessがデフォルトで渡されることを覚えておくといいですね．
ちなみに，リバースイテレータがある場合は
std::sort(vector.rbegin(), vector.rend());
とすることでも降順ソートになるかと思います．
第三引数で渡す関数オブジェクトとは一体なんなのかと．
lessは要するにこんな実装らしいです．
template <class T> struct less { bool operator()(const T& x, const T& y) const {return x < y;} };
一方sortの第三引数の型はtemplateで定義されていて，中で()演算子を付けて関数を実行しているようです．
つまり，C++でいう関数オブジェクトとは，後ろに()をつけて関数のように使えるオブジェクトのこと．関数ポインタも関数オブジェクトとして扱えるので，比較関数を自前で書く場合は，普通の関数として書いておいて関数ポインタを渡すという感じになるでしょうか．
bool lessByAbsolute(int a, int b) { return std::abs(a) < std::abs(b); }
std::sort(vector.begin(), vector.end(), lessByAbsolute);
こういうやり方で，名前空間を汚すのは嫌だという方もいるかと思いますが，C++11ではラムダ式が書けるようになったので，今の例は
std::sort(vector.begin(), vector.end(), [](int a, int b) {return std::abs(a) < std::abs(b);});
と書けるようになりました．
algorithmヘッダには関数を引数に与えてこそ効果を発揮する関数が多いので，ラムダ式が一般的に使えるようになればその重要性は増してくることでしょう．C++11では，all_of，any_of，none_of*1，copy_ifといった新しい関数がalgorithmヘッダに追加されたようです．
このイテレータを介したプログラミングではかなり興味深い実装ができます．C++03でも，単純なプログラムであればhttps://gist.github.com/lefb766/5127844のようにアレゲなコードが書けてしまいます．ところが，algorithmヘッダの関数群はデータコンテナの媒介無しでは処理を組み合せることができません．つまり，これらの関数を組み合わた処理を書きたい場合は，データコンテナのインスタンスにに逐次的に副作用を与えていく書き方しかできないわけです．複数回の関数適用が必要な場合は，途中のデータを一旦は全てメモリの上に載せる必要があるので結局効率の悪いプログラムになってしまいます．欲を言えば，コマンドラインみたいにパイプライン実行されるとか，遅延評価されて必要になったときに一気に処理するみたいな機構が作れればいいんですけど．スレッドが言語標準でサポートされた現在ではそんなことも実現可能なのでしょうか．自分のC++力が足りない．
