【C++】list,vector,map,unordered_mapの違いと使い分け

【まえおき】

list,vector,map,unordered_mapは動的な可変長配列データを保管するのに使用されているコンテナです。
しかしどう使い分けるべきなのか、メリットデメリットを僕自身があまり理解できていなかったので調べて僕なりにまとめてみることにしました。
もしかしたら間違えているところがあるかもしれないので、指摘していただけると幸いです。

【前提知識】

C++にはデータ構造を効率的に扱うためのコンテナがいくつか用意されています。
SLTコンテナ型（SLT:Standard Template Libraryの略称）と呼ばれており、
大きく３種類に分けられています。

1:シーケンスコンテナ

要素の順序を追加/削除した通りに保つ。
つまりデータの順序をつけて格納するコンテナです。

今回の題材であるlist型とvector型がこれに該当します。
この２つの説明は後程...

2:連想コンテナ

要素の追加/削除するとき、要素のキーの基づいて順序が自動的にソートされる。
キーと呼ばれるものと、値をペアで保管かつ管理されています。
シーケンスコンテナのように 先頭（または最後から）何番目と指定してアクセスすることができないですが、キーを使用して検索するので迅速に値にアクセスすることができます。

今回でいうmap型が該当します。
こちらも説明は後程...

3:非順序連想コンテナ（ハッシュコンテナ）

要素の追加/削除するとき、要素のキーの基づいて順序が自動的にソートされない。
C++11以降に追加された、ハッシュテーブルを使用してデータを管理しています。

やっていることは順序に意味を持っていない連想コンテナだと考えてもらえば良いです。

そして、ハッシュテーブルやハッシュ関数については、
僕があんまりよくわかっていない為今回は説明を省かせていただきます。

unordered_mapがこれに該当されています。

【本題】

さてここからはlist,vector,map,unordered_mapの違いやどういったタイミングで使うべきか書いていきます。

List型

双方向リンクリストを実装したコンテナで、各要素が前後の要素へのポインタを持っています。
これにより効率よく要素の挿入/削除を行うことができ、要素の順序を保ったまま動的にサイズを変えることができます。
一方で高速なランダムアクセス¹はできないので、常にシーケンシャルアクセス²を行わなければなりません。

大規模なデータを頻繁かつ動的に追加/削除するときに活躍します。
後に説明するVector型よりも要素の挿入/削除が早いからですね。
ただ、頻繁に要素の呼び出しや置き換えをするときはやっぱりVector型が良いでしょう。
ゲームプログラムで使うならイベントシーンの管理が良いでしょう。

必要なインクルードファイルと宣言方法

list.cp

  #include <list>
  std::list<"型"> num;
  /*型には　int float などの整数のほかに
  自分で作成した構造体やクラスなども入れることができます。*/

Vector型

要素の追加/削除が簡単にでき、ランダムアクセス¹が使えるため高速で要素にアクセスすることができます。一方で、要素の追加/削除をするときは要素を詰めたりして並び替えることに時間がかかってしまいます。

可変長配列で何使うか迷ったらこれ使うってぐらいには便利な関数、というかVectorを使わないところなんて絶対ない　と言い切れるぐらいには使われています。
ちなみにキャラクターの3D Modelのボーンなどの内部データを扱うときにも使われています。
ゲームプログラムで使うなら　敵やアイテムなどの数とか、あとから更に追加していくものとかetc...

必要なインクルードファイルと宣言方法

vector.cp

  #include <vector>
  std::vector<"型"> num;
  /*型には　int float などの整数のほかに
  自分で作成した構造体やクラスなども入れることができます。*/

Map型

キーと値のペアを格納する連想コンテナで、キーを基準に自動的にソートされます。
また、二分探索木³で実装されており、高速でアクセスできるのが特徴です。
このことから辞書型と呼ばれたりもしています。
ちなみに同じキーを持つ要素を追加することはできません。

高速な要素検索は使いたいがソート機能はいらないという場合は下のunorder_mapを使用します。

ゲームプログラムで使うなら、キーをfloatで時間として入れてイベントのタイムラインを管理したり、キャラクターのパラメーターの構造体/クラスを入れておいて使ったりetc...
パッと出てくる使い道はこんなかんじですが、僕の思いつかない使い道とかも絶対あると思うので是非使ってみてください。

必要なインクルードファイルと宣言方法

map.cp

  #include <map>
  std::map<"キー","型"> score;
  /*キー、型には　int float などのほかに
  自分で作成した構造体やクラスなども入れることができます。
  ただキーは構造体やクラスは避けて、
  int型やfloat型、string型などを使用することを個人的にお勧めします。*/

Unorder_map型

格納順がバラバラではあるものの、キーと値のペアを格納している。配列やVector型とは異なり、キーによって要素にアクセスすることができます。
Map型同様、同一のキーを格納することはできません。
Map型が二分探索木で実装されているのに対して、これはキーのハッシュ値に基づいてハッシュテーブルに格納されているので決められた順序で並んでいるわけではありません。
一般的にはhash mapと呼ばれるコンテナであるものの、C++標準への採用が遅かったことから、既に存在する各種コンテナとの名前の衝突を避けるためにunordered_mapと名付けられたそうです。

ゲームプログラムで使うなら、プレイヤーIDからプレイヤー情報を高速で検索するために使用したり、コンポーネント指向で作るためにコンポーネントクラスをGameObjectクラスで名前と一緒に持つなど、要素が連続している必要がないものに使うとよいでしょう。

必要なインクルードファイルと宣言方法

unordered_map.cp

  #include <unordered_map>
  std::unordered_map<"キー"、"型"> component;
  /*キー、型には　int float などのほかに
  自分で作成した構造体やクラスなども入れることができます。
  ただキーは構造体やクラスは避けて、
  int型やfloat型、string型などを使用することを個人的にお勧めします。*/

【おまけ】

Array型
固定長のシーケンスコンテナです。要素が連続して格納されており、動的なリサイズを行うことができません。通常の配列と異なりメンバー関数を持っており、vectorやlistと同じように検索したりして扱うことができます。

vector型がメジャーだとすればarrayは定規　だと思ってもらえればいいです。
（メジャーは長さを自由に変えられるのに対し、定規は作成時点で決められた長さでしか扱うことができない）

Vectorの要素をArrayに簡単に移動させることもできるので汎用性が高いです。

必要なインクルードファイルと宣言方法

array.cp

  #include <array>
  std::array<"型","要素の数"> num;
  //型には　int float などのほかに自分で作成した構造体やクラスなども入れることができます。

【おわりに】

ここまで読んでいただきありがとうございます。
本当は詳しい使い方なども書けたらよかったのですが、これ以上はさすがに長すぎてしまうので省かせていただきます。また、初投稿なのもあり文章が下手だったり誤字っていたり、Qiitaの機能を把握していないのもあってぐちゃぐちゃかもしれないですが、温かい目で見てくださるとありがたいです。
次に書く時はいつなのかわかりませんが、僕がわからなくなったことなどをまとめていこうと思います。
読了おつかれさまです。ありがとうございました。

1. アクセスする場所を特定し、一発でそこにアクセスするやり方。
   例えるなら、付箋が大量についている辞書でVectorと調べるときにVectorと書かれたしおりのページを開けて見るようなこと。 ↩ ↩²

2. 別名　順次アクセス。コンテナの先頭から順に検索してアクセスする方式。
   例えるなら、辞書でListと調べるときに最初のページのAから順に見ていくようなこと。 ↩

3. これを説明するためにはまず木構造を知ってもらう必要がありますが、説明が長くなってしまうので参考にしたサイトのリンクを張っておきます。
   https://medium-company.com/%e4%ba%8c%e5%88%86%e6%8e%a2%e7%b4%a2%e6%9c%a8/#i ↩