競技プログラミングで使えそうなSTLまとめ (Competitive Programming Advent Calendar)

(※この記事はCompetitive Programming Advent Calendar 3日目用の記事です)

「競技プログラミングで利用できそう」なC++のSTLをまとめたいと思います。
すべてを網羅するのではなく、独断と偏見で使えそうなものだけピックアップしています。
またコンテナ系はスキップし、Algorithmを中心にまとめます。

見出しがそのままヘッダの名前になっています。

algorithm

find

ある値を探すときに使う。イテレータが帰ってくる。

// v = { 1, 2, 3, 4, 5 }
find(v.begin(), v.end(), 3); // v.begin() + 2
find(v.begin(), v.end(), 7); // v.end()

count

個数を数える。

// v = { 1, 2, 1, 3, 2 }
count(v.begin(), v.end(), 1); // 2

equal

2つのシーケンスが同じかどうか

// v = { 1, 2, 3 }, w = { 1, 2, 3 }
equal(v.begin(), v.end(), w.begin()); // true
w[0] = 2;
equal(v.begin(), v.end(), w.begin()); // false

search

部分列を検索できる。イテレータが返ってくる。
なお文字列ならfindメソッドで出来る(s.find("hoge")、ただし返り値はインデックス)。

// v = { 1, 2, 3, 4, 5 }, w = { 3, 4 }
search(v.begin(), v.end(), w.begin(), w.end()); // v.begin() + 2

swap

変数の中身を交換する。よく使う。

// a = 1, b = 2
swap(a, b); // a = 2, b = 1

replace

値を置き換える。

// v = { 1, 2, 3, 2, 1 }
replace(v.begin(), v.end(), 2, 4); // v = { 1, 4, 3, 4, 1 }

remove

ある値を消す。新しい末尾位置を示すイテレータが返ってくる。
消した個数分、後ろにゴミがくっついている。
本当に消したい場合はコンテナのeraseなどと併用する必要がある。

// v = { 1, 2, 3, 2, 1 }, w = { 1, 2, 3, 2, 1 }
remove(v.begin(), v.end(), 2);                   // v = { 1, 3, 1, ? , ? }
w.erase(remove(w.begin(), w.end(), 2), w.end()); // w = { 1, 3, 1 }

unique

連続した同じ値を消す。removeと同様新しい末尾位置を示すイテレータが返ってくる。
重複を無視して数え上げるときに、多くの場合setを使うよりもvectorにpush_backしていき、sortしてuniqueしたほうが速い(g++で確認)。

// v = { 1, 1, 2, 2, 3, 3 }
v.erase(unique(v.begin(), v.end()), v.end()); // v = { 1, 2, 3 }

reverse

逆順に並べ替える。
単純に逆にしたい時はもちろん、シーケンスを逆にたどるときにreverseをしておくとインデキシングが楽になるのでたまに使う。

// v = { 1, 2, 3, 4, 5 }
reverse(v.begin(), v.end()); // v = { 5, 4, 3, 2, 1 }

rotate

シーケンスをシフトする。引数がなかなか難しいが、第2引数は操作後に新しく先頭になっている要素のイテレータ。
あまり使うことはないが、自分で実装しようと思うと少しめんどくさいので覚えておくと便利かもしれない。

// v = { 1, 2, 3, 4, 5 }
rotate(v.begin(), v.begin() + 2, v.end()); // v = { 3, 4, 5, 1, 2 }

random_shuffle

その名の通りランダムにシャッフルする。
乱択したい時や、特定の順番の入力に対して弱いアルゴリズムを使う時に入力をシャッフルしておくなどの使い方がある。

// v = { 1, 2, 3, 4, 5 }
random_shuffle(v.begin(), v.end()); // v = { 3, 5, 2, 4, 1 } (例えばこうなる)

sort

超頻出。デフォルトは昇順にソートします。

// v = { 3, 5, 2, 4, 1 }, w = { 3, 5, 2, 4, 1 }
sort(v.begin(), v.end());   // v = { 1, 2, 3, 4, 5 }
sort(w.rbegin(), w.rend()); // w = { 5, 4, 3, 2, 1 } (greaterを使うより楽！)

lower_bound, upper_bound

ソート済みのシーケンスに対して、ある値を入れるときに、最も早い/遅い位置の直後のイテレータを返す。
勝手に二分探索してくれるので便利。
どちらか一方を覚えておけば大体の状況に対応できる。

// v = { 1, 2, 2, 3, 3 }
lower_bound(v.begin(), v.end(), 2); // v.begin() + 1
upper_bound(v.begin(), v.end(), 2); // v.begin() + 3

binary_search

ソート済みのシーケンスに対して、ある値が存在するかを調べる。
他の操作が必要ない場合はsetを使うことで簡単にかけるので使う頻度は少ないかもしれない。

// v = { 1, 2, 2, 3, 3 }
binary_search(v.begin(), v.end(), 2); // true
binary_search(v.begin(), v.end(), 4); // false

max, min

最頻出と言っても過言ではないだろう。2つの値の最大値/最小値を返す。
DPなどで最大値を更新していく時などに特によく使う。

max(2, 3);     // 3
min(2, 3);     // 2
a = max(a, 4); // aが、aと4の大きい方に更新される

max_element, min_element

シーケンス中の最大値/最小値「のイテレータ」を返す。
単純に最大値/最小値が欲しい時のほか、そのインデックスまで分かるため、非常に便利。

// v = { 3, 5, 2, 4, 1 }
max_element(v.begin(), v.end());  // v.begin() + 1
*max_element(v.begin(), v.end()); // 5
max_element(v.begin(), v.end()) - v.begin(); // 1 (5のインデックス)

next_permutation, prev_permutation

辞書順で次の/前のものに並び替える。返り値は、次の/前のものがない場合にfalse、それ以外はtrueになる。
自分で作るとかなりめんどくさいし、非常に便利。
全順列を試す場合、再帰するよりもだいたい速い(ただし、枝刈りは難しくなる)。
99%くらい以下のdo〜whileの形で使う。

// v = { 1, 2, 3 }
do{
  // v は ループごとに
  //  { 1, 2, 3 }, { 1, 3, 2 }, 
  //  { 2, 1, 3 }, { 2, 3, 1 },
  //  { 3, 1, 2 }, { 3, 2, 1 }
  // になっている。
}while(next_permutation(v.begin(), v.end()));
// ループ後は v = { 1, 2, 3 }

// 組み合わせを全部試したいときにも使える
// 3個中2個を選びたい場合は
// w = { 0, 1, 1 } としておき以下のように出来る。
do{
  // w[i] = 1 ならば i 番目のものを選んでいる状態
  // w[i] = 0 ならば i 番目のものは選んでいない状態
}while(next_permutation(w.begin(), w.end()));

numeric

なぜかalgorithmじゃないので、いつもヘッダ名忘れてしまうのは私だけでしょうか・・・

accumulate

総和を簡単に求められる。
初期値の型によって結果の型を決めることが出来るのが地味に便利。

// v = { 1, 2, 3, 4, 5 }
// w = { "Competitive", "Programming", "Advent", "Calendar" }
accumulate(v.begin(), v.end(), 0);   // 15、結果はint
accumulate(v.begin(), v.end(), 0ll); // 15、結果はlong long
accumulate(v.begin(), v.end(), 1, multiplies<int>()); // 120、結果はint
accumulate(w.begin(), w.end(), string()); // "CompetitiveProgrammingAdventCalendar" 

partial_sum

途中までの和を全部求められる
この結果を利用してO(1)で部分和を求めることが出来ることなどから利用する場面がありそう。

// v = { 1, 2, 3, 4, 5 }
// w.size() >= 5 じゃないとダメ
partial_sum(v.begin(), v.end(), w.begin()); // w = { 1, 3, 6, 10, 15 }
partial_sum(v.begin(), v.end(), v.begin()); // vに上書きもできる v = { 1, 3, 6, 10, 15 }

functional

Algorithmの関数に渡せるものが揃っています
意味は名前の通りなので省略。

比較系

equal_to, not_equal_to, greater, less, greater_equal, less_equal

演算系

plus, minus, multiplies, divides, modulus, negate

sort(v.begin(), v.end(), greater<int>()); // 降順ソート

終わりに

調べてみて、知らなかったけど使えそうというものもいろいろあったので勉強になりました。
素晴らしいAdvent Calendarを企画していただいた @_tanzaku_ さんに感謝。
明日以降も素晴らしい方々による記事が続くので楽しみです。

参考サイト: http://www.cplusplus.com/