コンテスト系で使える（そうな）関数など

コンテスト系で使えそうなC++のライブラリを適当にあげておきます。
はっきり言って私の備忘録です。
※随時更新予定・・・
※2010/12/29　更新

max、min

2つのうち大きいほう/小さいほうを返すのがこのmax/minです。
まぁ一般的なので普通ですね。
使用ヘッダ：

辞書順に〜

「複数解がある場合は辞書順で最も早いものを返せ」なんてものがよくあります。
その場合に使えそうなのがlexicographical_compareです。
イテレータを渡してやると辞書順で小さければtrueが返ってきます。
使用ヘッダ：

二分探索

二分探索するときはlower_bound/upper_boundがあります。
binary_searchなんてものもありますが、これは指定したキーが存在するかしないかを返すだけなので存在した場合にその値を弄りたい場合は使えません。
で、lower_bound/upper_boundなのですが、lower_boundは指定した値以上の最初の位置を返します。
upper_boundは指定した値よりも大きい値の最初の位置を返します。
図で書くと下のような感じですね。

　 1　 2　 3　 3　 3　 3　 4　 4　 4　 5　 6
　　　　　↑lower_bound　　↑upper_bound
※3を検索キーにした場合

二分探索なので使用する前にはソートしておくのをお忘れなく！
使用ヘッダ：

入力

通常ではcinで問題ないですが、データの項数が増えたときはscanfなどを使うことを考えた方がよさそうです。
cinはscanfなどに比べ低速であるため、場合によっては入力のせいでTLEが起こるといったことがあるようです。
目安は10万程度らしいですが、不安に思ったらscanfを使っておけばまず問題ないかと思います。
使用ヘッダ：

配列の要素をすべて出力

ostream_iteratorでoutput_iteratorを作れば簡単に出力できます。
具体的には以下のコードでできます。

copy( v.begin(), v.end(), ostream_iterator<int>( cout, ", " ) );

ostream_iteratorのテンプレート引数には各要素の型を指定します。
また、コンストラクタの第一引数は出力先ストリームを、第二引数には各要素が出力されるたびに挿入される文字列を指定します。
これでforを使って自分で出力しなくてもよくなります。
ただし注意として各要素が出力されるたびに第二引数に指定した文字列が出力されるので、最後の要素の後にも出力されてしまいます。
参考：http://ideone.com/ofj78
そのため、最後に余計なものの出力が問題ないような場合のみで使いましょう。
＃「スペース区切りで出力しろ」みたいな問題では自分の上記コードで通してきているので最後の空白は問題にならないようです。
＃ただし保証はないので注意です。
使用ヘッダ：copy　
　　　　　　ostream_iterator　

要素を回転

要素を回転させたい場合、例えば下記のようにデータを回転させたデータが欲しい場合があります。

1, 2, 3, 4, 5
2, 3, 4, 5, 1
3, 4, 5, 1, 2
... （以下略） ...

この場合にはrotateが使えます。
使い方は引数が順に回転させるデータの最初のイテレータ、最初の位置に持っていきたい位置を指すイテレータ、データの終端を表すイテレータを与えればいいです。

// 例
// v : { 1, 2, 3, 4, 5 }が入っているとする
copy( v.begin(), v.end(), ostream_iterator<int>( cout, ", " ) );	// 1, 2, 3, 4, 5
rotate( v.begin(), v.begin() + 1, v.end() );				// 1つずらす
copy( v.begin(), v.end(), ostream_iterator<int>( cout, ", " ) );	// 2, 3, 4, 5, 1
rotate( v.begin(), v.begin() + 2, v.end() );				// 2つずらす
copy( v.begin(), v.end(), ostream_iterator<int>( cout, ", " ) );	// 4, 5, 1, 2, 3

実行結果
　http://ideone.com/Ituuu
使用ヘッダ：

順列

要素の順列が欲しい場合、例えば下記のような場合。

1, 2, 3, 4,
1, 2, 4, 3,
1, 3, 2, 4,
... （中略） ...
4, 2, 3, 1,
4, 3, 1, 2,
4, 3, 2, 1,

この場合はnext_permutationを使えば簡単に生成できます。
使い方はいたって簡単。
要素の最初と最後のイテレータを与えれば、その要素の並びよりも辞書順で1つだけ大きい順列を生成してくれます。
また戻り値は新しい順列が生成できたかどうかをboolで返すので大抵は以下のような使い方になるんじゃないでしょうか。

do {
	// vを使った計算
} while( next_permutation( v.begin(), v.end() ) );

実行例
　http://ideone.com/WRzs7
ちなみにnext_permutationは現在よりも1つ大きいものを返しますが、prev_permutationというのもありこれは現在よりも1つ小さいものを返します。
使用ヘッダ：