今回は、C++でよく出てくる「STLコンテナの使い分け」について解説していきます。
「vectorとlist、結局どっちを使えばいいの？」
「mapとunordered_mapの違いは分かったけど、ゲームだとどっち？」
「とりあえず全部vectorで書いてるけど、これでいいの？」
こんな疑問はありませんか？
C++には便利なコンテナがいくつもありますが、選び方を間違えると遅くなります。しかも厄介なことに、「教科書的には速いはずなのに、実際は遅い」という逆転がよく起こります。
この記事を読み終えると、あなたは4つのコンテナの違い・計算量の比較・ゲーム開発での選び方・初心者がハマりやすい勘違いをしっかり理解できると思いますので、ぜひ最後まで読んでいただけると嬉しいです。
まず4つをざっくり整理
細かい話に入る前に、4つの性格を一言でまとめます。
- vector … 連続したメモリに並べる可変長の配列。基本これ
- list … 前後をポインタで繋いだ双方向リスト。途中の挿入削除が得意
- map … キーで引ける。キー順に並ぶ
- unordered_map … キーで引ける。並ばないが速い（ハッシュ）
計算量で比較する
それぞれの得意・不得意を計算量で並べると、こうなります。O(1) は「要素数が増えても時間が変わらない」、O(n) は「要素数に比例して遅くなる」という意味です。
| 操作 | vector | list | map | unordered_map |
|---|---|---|---|---|
| 添字アクセス | O(1) | × | × | × |
| キーで検索 | O(n) | O(n) | O(log n) | O(1)（平均） |
| 末尾に追加 | O(1)（ならし） | O(1) | ― | ― |
| 途中に挿入・削除 | O(n) | O(1)（位置が既知） | O(log n) | O(1)（平均） |
| メモリの並び | 連続 | バラバラ | バラバラ | バラバラ |
この表だけ見ると「途中の挿入削除が多いなら list 一択では？」と思いますよね。ところが実際に測ると vector のほうが速いことがとても多いです。理由は次で説明します。
計算量だけで選んではいけない理由
カギはメモリの並び方です。vector は要素が連続して並んでいます。CPUはメモリを読むとき、その周辺もまとめてキャッシュに載せるので、次の要素がすでに手元にある状態になります。
一方 list は、要素がメモリ上のバラバラな場所に散らばっています。1個読むたびにポインタを辿って別の場所へ飛ぶので、キャッシュが効きません。
結果として、「listはO(1)、vectorはO(n)」でも、実測ではvectorが勝つという逆転が起きます。特にゲームのように毎フレーム全部を回す処理では、この差がそのまま効きます。
ゲーム開発での選び方
実際のゲームでは、次のように考えるとほぼ迷いません。
敵・弾・エフェクトのリスト → vector
毎フレーム全部を回して更新・描画するので、連続メモリの恩恵が最大になります。まずこれを選んでください。
#include <vector>
std::vector<Enemy> enemies;
enemies.reserve(256); // 最大数が読めるなら先に確保しておく
for (auto& e : enemies) {
e.Update();
e.Draw();
}途中で敵が死んで削除したいときも、順番を気にしないなら「最後の要素と入れ替えて末尾を削る」やり方で O(1) にできます。
// 順番不問なら、消したい要素を末尾と入れ替えてpop_back
void RemoveAt(std::vector<Enemy>& v, size_t i) {
v[i] = std::move(v.back());
v.pop_back();
}IDから素早く引きたい → unordered_map
「プレイヤーIDからデータを引く」「テクスチャ名から画像を引く」のようにキーで探す用途はこれです。順番はどうでもよく、とにかく速く引きたいときに使います。
#include <unordered_map>
#include <string>
std::unordered_map<std::string, Texture> textures;
auto it = textures.find("slime");
if (it != textures.end()) {
it->second.Draw();
}キー順に並んでいてほしい → map
スコアランキングのように順番に意味があるときは map です。速度より「並んでいること」が欲しい場合に選びます。詳しい比較はmapとunordered_mapの違いの記事をどうぞ。
listを選ぶのはどんなとき？
正直、ゲームでは出番が少なめです。要素がとても大きくてコピーが重い、かつ途中の挿入削除が本当に多い、さらにポインタや参照が無効化されると困る——この条件が揃ったときの選択肢になります。詳しくはstd::listの記事で解説しています。
【重要】私が実際にコンテナ選びで失敗した体験談
個人開発で弾幕シューティングを作っていたとき、「弾は途中でどんどん消える → 削除が多い → list のほうが速いはず！」と考えて、弾のコンテナを vector から list に書き換えたことがあります。
結果は、書き換える前より明確に重くなりました。理屈では速くなるはずなのに、です。
原因はキャッシュでした。弾は毎フレーム全部を回して座標更新しています。list だとその全走査がメモリ上を飛び回るので、削除で得した以上に走査で損していたわけです。vector に戻して、削除は「末尾と入れ替えて pop_back」にしたら、いちばん速くなりました。計算量の表だけ見て判断したのが敗因です。
STLコンテナ選びのよくある失敗例と対処法
①計算量の表だけで list を選ぶ
体験談のとおりです。迷ったら vector から始めて、遅かったら測ってから変える。これが一番失敗しません。
②vectorの再確保でポインタが無効になる
vector は要素が増えるとメモリを確保し直して引っ越しします。このとき、前の場所を指していたポインタや参照は無効になります。reserve() で先に確保しておくか、ポインタではなく添字で持つと安全です。
③ループ中に要素を消して壊す
回している最中に erase すると、イテレータが壊れてクラッシュします。後ろから回すか、消す印をつけて後でまとめて消すのが定石です。ループの書き方は範囲for文の記事もどうぞ。
注意点
- 基本は vector。困ってから他を検討する
- 速度は推測せず実測する（計算量とキャッシュは別の話）
vectorの再確保によるポインタ無効化に注意
まとめ
- 毎フレーム全部を回すならvector（連続メモリが強い）
- キーで速く引くならunordered_map
- キー順に並んでほしいならmap
- list は条件が揃ったときだけ。計算量の表を鵜呑みにしない
コンテナ選びは「とりあえず vector、困ったら測って考える」で9割うまくいきます。まずは手持ちのコードで、毎フレーム回している部分が何になっているか確認してみてください。
