STL には十数種類のコンテナがあり、vector / array / deque / list / set / map / priority_queue ... と並ぶと最初は圧倒されます。実は「何をしたいか」から選ぶだけでほぼ決まり、迷ったら std::vectorで 8 割の場面は足ります。本ページではコンテナの全体像と用途別フローチャート、比較表を一望できる形で整理し、それぞれの詳細ページへの入口にします。
std::vectorstd::arraystd::map / std::unordered_mapstd::set / std::unordered_setstd::deque / キュー系アダプタstd::liststd::priority_queueSTL のコンテナは大きく 3 系統＋アダプタに分けられます。まずはどの系統に属するかで当たりをつけます。
順番通りに値を詰める系。C の配列の進化版と思えば OK。
int[N] の安全版。push_front / push_back できる動的配列。キュー系の土台。キーでの検索・集合演算・重複排除など。内部はバランス木。
O(log n)＋順序保持。順序はないがアクセスが速い。平均 O(1)。キーが順序付けできない型でも使える。
上記コンテナを裏に敷いて、使える操作を絞ったラッパー。インターフェースがシンプルになる。
push / pop / front だけ。push / pop / top。上から順に質問に答えていくと、使うべきコンテナが 1 つに絞れます。
std::list が出てこないのは？ 現代のマシンではメモリの連続性（キャッシュヒット）が圧倒的に効くため、中間挿入が多くても vector のほうが速いケースがほとんどです。list は「巨大な要素を要素ごと別領域に置きたい」「反復子／参照が絶対に無効化されないことが重要」など特殊事情のときだけ検討します。
主要コンテナの代表的な操作の計算量をまとめました。O(1) は「要素数に関係なく一定時間」、O(log n) は「要素数の対数に比例」、O(n) は「要素数に比例」。
| コンテナ | 系統 | 末尾追加 | 先頭追加 | ランダム アクセス v[i] |
検索 | 順序 |
|---|---|---|---|---|---|---|
std::vector |
Sequence | O(1) 償却 | O(n) | O(1) | O(n) | 挿入順 |
std::array |
Sequence | ―（固定長） | ― | O(1) | O(n) | 挿入順 |
std::deque |
Sequence | O(1) 償却 | O(1) 償却 | O(1) | O(n) | 挿入順 |
std::list |
Sequence | O(1) | O(1) | ―（不可） | O(n) | 挿入順 |
std::set |
Associative | O(log n) | O(log n) | ―（不可） | O(log n) | ソート |
std::unordered_set |
Unordered | O(1) 平均 | O(1) 平均 | ―（不可） | O(1) 平均 | なし |
std::map |
Associative | O(log n) | O(log n) | O(log n) （キー経由） |
O(log n) | キーでソート |
std::unordered_map |
Unordered | O(1) 平均 | O(1) 平均 | O(1) 平均 （キー経由） |
O(1) 平均 | なし |
std::priority_queue |
Adapter | O(log n) (push) |
― | ―（top のみ） | ― | ヒープ |
O(1) 償却 は「ときどき再確保で重くなるけど平均は O(1)」、O(1) 平均 は「ハッシュの衝突次第で最悪 O(n) になるが普段は O(1)」の意味。実戦ではどちらも O(1) と考えて OK。
「用途ごとに最適なコンテナが分かれている」と聞くと難しそうですが、現代のマシンでは std::vector がほとんどの場面で最速です。理由は 3 つ。
list のような細切れメモリより圧倒的に速いv[i] が O(1) ― ランダムアクセスが要る場面では他コンテナに勝つ逆に言うと、vector を捨ててまで他コンテナに乗り換えるべきなのは、計算量クラスが変わるとき。例：
map / unordered_map（O(n) → O(log n) / O(1)）set / unordered_setdeque（vector::insert(begin(), ...) は O(n)）priority_queue（毎回 max_element は O(n)）list の中間挿入が O(1) ですが、挿入位置を見つけるのに O(n) かかるため、結局 O(n)。さらに list はキャッシュ効率が悪いので、実測では vector のほうが速いことが多いです。入門段階では list は「こんなのもある」程度で十分。
このあとの各ページで、それぞれのコンテナを個別に掘り下げます。順に読んでも、必要なところだけつまみ読みしても OK。