C++: 主要 STL コンテナのチートシート
概要
vector, list, map, multisetなどなど多くの STL コンテナが存在しますが、データの追加/削除/参照など同じ名前のメソッドだったり微妙に違ったりしていて、時々忘れたり間違ったりしてしまいます。そこで本記事では、主要なコンテナの主要操作をまとめてみました。間違いや抜け、追加要望などありましたらコメント下さい。
基本的にデータの取り出し（pop, pop_back など）では値はリターンされないので忘れないように注意して下さい。
動的配列: vector
| 操作 | vector |
|---|---|
| 追加 (指定した位置) | insert(v.begin(), 値) |
| 追加 (先頭) | - |
| 追加 (末尾) | push_back(値) |
| 参照 | v[インデックス] |
| 参照 (先頭) | front() |
| 参照 (末尾) | back() |
| 取り出し (先頭) | - |
| 取り出し (末尾) | pop_back() |
| 削除 (全ての要素) | clear() |
| 削除 (指定した値を持つ要素全て) | - |
| 削除 (指定したインデックス) | erase(v.begin() + インデックス) |
| 削除 (指定したイテレータ) | erase(itr) |
| 要素数ゼロ (空) の確認 | empty() |
| 要素数の取得 | size() |
| サイズの変更 | resize(サイズ) |
vector型データ同士の比較
for文を使わなくても以下のようにif文一つでシンプルに書くことが出来ます。
if (v1 == v2) {
...
}
ヘッダファイル
#include <vector>
順序付集合: set / 多重集合: multiset
set は平衡二分探索木 (self-balancing binary search tree) と呼ばれるデータ構造で実現されており、O(long N) でデータへのアクセスと追加、削除が可能です。また、重複したデータは捨てられてユニークなデータだけの集合になります。また、データは自動的に昇順ソートされて保存されており、最小値 (begin())と最大値（rbegin()）を O(1) で取得可能です。
似たデータ構造でmultisetがあります。multisetのsetとの差分はデータの重複が可能という点です。使い勝手はどちらも同じです。重複を許可する場合はmultiset、重複したデータを除去したい場合はsetという使い分けです。
なお、イテレータで各データを更新は出来ないため、更新したい場合には一度削除して再度挿入操作が必要です。
| 操作 | set / multiset |
|---|---|
| 追加 | insert(値) |
| 参照 (最小値) | begin() |
| 参照 (最大値) | rbegin() |
| 検索 (値): イテレータ | find(値) |
| 検索 (値): 存在する個数 | count(値) |
| 削除 (全ての要素) | clear() |
| 削除 (指定した値) | erase(値) |
| 削除 (指定したイテレータ) | erase(itr) |
| 要素数ゼロ (空) の確認 | empty() |
| 要素数の取得 | size() |
各要素を順番に確認していく
イテレータをインクリメントして順番に検索することが可能です。
for (auto itr = st.begin(); itr != st.end(); itr++)
cout << *itr << endl;
初期化
vector型のデータなどをset/multiset型の変数に代入（初期化）する時には以下のようにfor文を使わずにシンプルに書くことが可能です。
set<int> st(v.begin(), v.end());
lower_bound が使える
setもmultisetもlower_boundを提供してくれているので、以下のようにバイナリサーチで引数で指定した値以上になる最小のイテレータを探してくれます。
auto itr = st.lower_bound(x);
auto itr = ms.lower_bound(x);
ヘッダファイル
#include <set> // set, multiset
ヒープ: priority_queue
内部的には vector を用いて、ヒープを構築します。デフォルトでは、値が大きいものがキューの先頭に来ます。priority_queueは、popを利用して先頭のノードを取り出すことは可能ですが、値を指定してどこかのノードの削除することは出来ません。そのため、値を削除したい場合には代わりにmultisetを使います。また、ノードの値を変更することも出来ません。
| 操作 | priority_queue |
|---|---|
| 追加 | push(値) |
| 参照 (最大値) | top() |
| 取り出し (先頭) | pop() |
| 要素数ゼロ (空) の確認 | empty() |
| 要素数の取得 | size() |
値が小さいものがツリーの上位（先頭）に来て欲しい場合
変数宣言時にstd::greater<int>を指定することで並び順を昇順（親ノードの値が必ず子ノードの値よりも小さい）にすることが可能です。
std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
ヘッダファイル
#include <queue> // priority_queue
平衡二分木: map
setと同じように平衡二分木で実現され、辞書のように対応するキーとデータをセットにして保存します。なお、平衡二分木のためキーの昇順で保存されており、キーは重複を許しません。
ハッシュテーブルのような使い方が出来ますが、実際には平衡二分木で実装されているため、O(1)でのデータアクセスではなくO(log N)かかります。辞書として使う場合には、後述のunordered_mapを使う方が良いです。
| 操作 | map |
|---|---|
| 追加 | mp[キー] = 値 |
| 参照 (キー) | mp[キー] |
| 参照 (最小値) | begin() |
| 参照 (最大値) | rbegin() |
| 検索 (値): イテレータ | find(値) |
| 検索 (値): 存在する個数 | count(値) ※実質 1 or 0のみ返る |
| 検索 (指定した値以上の最小値のノード): イテレータ | lower_bound(キー) |
| 検索 (指定した値より大きいの最小値のノード): イテレータ | upper_bound(キー) |
| 削除 (全ての要素) | clear() |
| 削除 (指定したキーを持つノード) | erase(キー) |
| 削除 (指定したイテレータ) | erase(itr) |
| 要素数ゼロ (空) の確認 | empty() |
| 要素数の取得 | size() |
| サイズの変更 | - |
ヘッダファイル
#include <map>
スタック: stack
| 操作 | stack |
|---|---|
| 追加 (指定した位置) | - |
| 追加 (先頭) | - |
| 追加 (末尾) | push(値) |
| 参照 (先頭) | - |
| 参照 (末尾) | top() |
| 取り出し (先頭) | - |
| 取り出し (末尾) | pop() |
| 削除 (全ての要素) | - |
| 削除 (指定した値を持つ要素全て) | - |
| 削除 (指定したインデックス) | - |
| 削除 (指定したイテレータ) | - |
| 要素数ゼロ (空) の確認 | empty() |
| 要素数の取得 | size() |
| サイズの変更 | - |
ヘッダファイル
#include <stack>
キュー / 両端キュー: deque / 双方向リスト
dequeと通常のqueueの違いは、dequeは先頭にもO(1)でデータの追加が可能で任意のデータの削除も可能です。また、dequeはバイナリサーチも可能であるため、単調増加なキューイングされたデータに対してバイナリサーチを行う場合にも有効です。
| 操作 | queue | deque | list |
|---|---|---|---|
| 追加 (指定した位置) | - | - | insert(itr, 値) |
| 追加 (先頭) | - | push_front(値) | push_front(値) |
| 追加 (末尾) | push(値) | push_back(値) | push_back(値) |
| 参照 (先頭) | front() | front() | front() |
| 参照 (末尾) | back() | back() | back() |
| 取り出し (先頭) | pop() | pop_front() | pop_front() |
| 取り出し (末尾) | - | pop_back() | pop_back() |
| 削除 (全ての要素) | - | clear() | clear() |
| 削除 (指定した値を持つ要素全て) | - | - | remove(値) |
| 削除 (指定したインデックス) | - | erase(itr + インデックス) | erase(itr + インデックス) |
| 削除 (指定したイテレータ) | - | erase(itr) | erase(itr) |
| 要素数ゼロ (空) の確認 | empty() | empty() | - |
| 要素数の取得 | size() | size() | size() |
| サイズの変更 | - | resize(サイズ) | resize(サイズ) |
リスト型のデータ削除時には注意が必要なので合わせて[C++] 双方向リスト (list) の要素探索と削除操作時の注意を参照してください。
ヘッダファイル
#include <queue> // queue
#include <deque> // deque
#include <list> // list
ハッシュ （連想配列）
set, map と同じ機能を持ち、内部のデータ構造がハッシュになっているのが unordered_set と unordered_map です。O(1)でデータの参照追加などを行う場合にはこれを利用します。
| 操作 | unordered_map | unordered_set |
|---|---|---|
| 追加 | mp[キー] = 値 | insert(値) |
| 参照 (キー) | mp[キー] | <- |
| 検索 (値): イテレータ | find(値) | <- |
| 検索 (値): 存在する個数 | count(値) | <- |
| 削除 (全ての要素) | clear() | <- |
| 削除 (指定したキーを持つノード) | erase(キー) | <- |
| 削除 (指定したイテレータ) | erase(itr) | <- |
| 要素数ゼロ (空) の確認 | empty() | <- |
| 要素数の取得 | size() | <- |
ヘッダファイル
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
bitset
ビットデータ配列のようなものを扱うときにbitsetを利用します。各要素は0もしくは1のみを取ります。
std::bitset<8> bset(0xff);
bset.set(1)
bset.set(2, false)
bset[0] = true;
| 操作 | stack |
|---|---|
| 指定したビットを反転 | flip(対象ビット) |
| 全ビット反転 | flip() |
| ビットが1の数をカウント | count() |
| ビットをセット | set(対象ビット) |
| ビットをクリア | set(対象ビット, false) |
ヘッダファイル
#include <bitset>
Discussion