C++ STL Cheat Sheet

C++ STL のメモ。随時アップデート

• T はvalue_type(要素の型)
• iteratorなどは container_type<value_type>::interator を省略して iterator とか書いてる。
• こまけーこたーいーんだよ

コンテナ（だいたい）共通
void clear(); コンテナをクリア
void push_back(T); 要素を追加
container_type<T>::iterator p; イテレータ p の宣言
typeof(c.begin()) p = c.begin(); ↑が面倒ならtypeofで指定も可(GNU拡張?)。マクロ定義とかに便利。
iterator begin(); 先頭のイテレータ取得。シーケンス系のみ？
iterator end(); 一番後ろのイテレータ。ばんぺい君なので値はたぶん初期値。 while(p != c.end())とかで利用
size_type size(); 要素数を返す。コンテナによってはO(n)なので注意。
bool empty(); 要素があるかどうかのpredicate. ゼロ判定のための size() == 0とかはNGでempty()を使う。

vector
vector(); コンストラクタ
vector(size_type); 指定したサイズの要素数で初期化。初期値を指定したい場合は↓
vector(size_type, T); 要素数と初期値を指定して初期化。
resize(size_type); 要素数を変化。大きくする場合はコンストラクタで指定した初期値で初期化される。小さくする場合は切り捨てられる。
resize(size_type, T); 要素数を変化。大きくした場合の初期値を指定する場合。
reserve(size_type); メモリをアロケート。size()は変わらない。通常push_back()等で足りない場合倍々にアロケートされていくところを予め指定(最大要素数がわかっていれば不要なアロケートを避けられる)。
vector<vector<int> > x; intの二次元ベクタの宣言
vector<vector<int> > x(10, vector<int>(10, 0)); 10x10の二次元ベクタを0で初期化

pair
pair<int, int> x; intとintのペアの型。pairはコンテナ系のヘッダをインクルードすればついてくるっぽい。
P x(1, 2); x.first + x.second;  => 3. ペアの要素にはfirstとsecondでアクセス
pair<int, pair<int, int> >; intと、intとintのペアとのペアのように何でも格納可能。
typedef pair<int, int> P; とか便利なイディオム
P(1, 100) < P(2, 1); 真。first同士をまず比較して同じなら second同士を比較。

???; リストのノードみたいに再帰的な定義が可能かどうか不明。

map
map<T, S> m; 宣言。TをキーとしたRB木で保持されるらしい。
m.insert(pair<T, S>); mapにはpair<T, S>なペアを作ってinsert.
map<T, S>::iterator p; イテレータ。 *p は pair<T, S>
m[T] = S; で代入可能。map<string, int> なら m["hoge"] = 3; とか。アクセスするだけでTをキーとした要素を作成(たぶんsecondはデフォルト値で初期化)してしまうので注意。
m.find(T); キー T のイテレータを返す(O(logN))。合致する要素が無ければ m.end() が返る。
void erase(iterator); イテレータの指すペアを削除
void erase(iterator start, iterator end); start から end まで削除


set
set<T> s; 集合 s の宣言
s.insert(T); sに要素を追加
s.erase(T); 要素を削除
s.size(); 要素数。unsigned注意。
s.find(T); O(logN)な検索。イテレータを返す。

重複要素をinsertしても黙って捨てられる。
setにメンバ関数push_back()はない。
ユーザ定義クラスであってもオペレータ < さえ定義してやれば set の要素として使えるぽい。(メンバ関数 bool operator< (const T &val) const {} が必要)

algorithm
iterator find(iterator, iterator, T); O(N)な検索。開始・終了を指定してTを検索。イテレータを返す。見つからなければ end() が返る。
void sort(iterator, iterator); ソート（非安定）
void sort(iterator, iterator, compare); compare関数にしたがってソート

functional
compare greater<int>(); 比較する関数を返す。ソートで利用。C++てlambda書けるようになったんだっけ？