[C++] STLの型の使い分け

先日Ohotech 特盛 #10で話した、「C++のSTLのコンテナ型を概観する」の内容を単独記事としてまとめたものです。

追記（2019.02.02）

本記事から大幅加筆し動画講座化したものを公開しました。
C++ STLのコンテナ型を動作効率を考えて使いこなす！ | Udemy
有料ですが、一部の節は無料で視聴可能です。

• 2月いっぱいまでは、上記のリンクから辿っていただけると有効のキャンペーン価格になります。なお、もしキャンペーン価格（￥3600→￥1200）が表示されていない場合はお問い合わせください（offkaiあっとまーくhhiro.net）。

追記（2014.10.22）

10月18日の札幌C++勉強会にて、この記事のダイジェスト版を発表しました。
なぜこの記事のような考え方が必要なのか、という紹介です。
STLの型の使い分け(ダイジェスト版) @ Sapporo.cpp 第7回勉強会 (2014.10.18)

これは何ですか

• C++の標準ライブラリの一部を構成する**STL (Standard Template Library)**に定義されている
• コンテナ型（配列などのように「型を指定して、その型の値を複数個格納する」ようなデータ構造）について
• それらの使い分けの指針をまとめたものです。

STLのコンテナ型

C++の標準ライブラリの一部を構成するSTL (Standard Template Library)は、基本的なデータ構造やアルゴリズムを、型に非依存な形で提供してくれます（例えば、intであろうとdoubleであろうと自前のクラスであろうと同様に利用できる、という具合）。
それらのデータ構造のうち特に、「型を指定して（例外あり）、その型の値を複数個格納する」ようなデータ構造はコンテナ型と呼ばれています。例えばスクリプト言語などにおける配列はC++のそれと異なり「大きさを自動的に変更できる」という特徴がありますが、C++においてはこのような配列をSTL中のクラスを通じて利用できます。

さて、STLにはコンテナ型がこれだけ用意されています。

vector, list, forward_list#, deque, priority_queue,
set, multiset, unordered_set#, unordered_multiset#,
map, multimap, unordered_map#, unordered_multimap#,
array#, bitset, stack, queue
#：C++11で規格化

しかし、それぞれのコンテナ型にどういう特性があるかの紹介はされていても、どう使い分ければよいかということをまとめた記事というのが見当たらず、今回書くに至りました。

先にまとめを載せると

一つの型の値を格納したい場合、

• 連想配列なら、
  • コンパイラが対応していて、かつ後述の特殊な状況に該当しないならunordered_map・unordered_multimap
  • そうでないならmap・multimap
• 要素数が固定なら、
  • ビット値を格納したいならbitset
  • それ以外の型を格納したいなら、array（コンパイラが対応していない場合は普通の配列）
• 要素数が固定でないなら（連想配列以外で）、
  • 要素数が少ないならとりあえずvector（計算速度もそれほど問題にならない、メモリ効率がよいことのメリットのほうが大きい）
  • メモリ効率を優先したいなら、
    • 先頭・末尾への挿入・削除の頻度も高いならdeque
    • そうでなければvector
  • 速度重視で、ランダムアクセスの頻度が高いなら、
    • ランダムアクセスの速度が最優先されるべきなら、
      • 先頭・末尾への挿入・削除の頻度も高いならdeque
      • そうでなければvector
    • ランダムアクセスの速度を多少妥協してもよいので、要素の挿入・削除の速度も上げたいなら
      • 連想配列を使う。コンパイラが対応していて、かつ「キーを大きさの順序で保持する」必要がないならunordered_map、そうでなければmap
  • 速度重視で、挿入・削除の頻度が高いなら、
    • 要素を任意の順番で格納したいなら、
      • 先頭・末尾のみ挿入・削除の頻度が高いならdeque
      • 途中の要素にも挿入・削除の頻度が高いなら、
        • コンパイラが対応していて、かつ「手前の要素に戻る」という処理を行う必要がないならforward_list
        • そうでなければlist
        • 格納順を番号などで管理できる場合は、連想配列の利用も検討
    • 要素を格納する順番を気にしないなら、
      • あとで格納されている要素を検索する必要がないならdeque
      • あとで格納されている要素を検索する必要があるなら、次の「検索の頻度が高いなら」を参照
  • 速度重視で、検索の頻度が高いなら、
    • コンパイラが対応していて、かつ後述の特殊な状況に該当しないならunordered_set・unordered_multiset
    • そうでないならset・multiset

用途が特殊なstack, queue, priority_queueは省いています（「stack, queue, priority_queue」節で後述）。

計算時間・メモリ量のまとめは「一覧表」節にあります。

補足

"O(n)" などの表記は「O記法」「ランダウの記号」などと呼ばれるもので、簡単に言えば「nに比例する程度である」という意味です。O(1)と書いた場合は「（指定された変数の値に）依存しない」を意味します。
なお本記事では、nは「現時点で当該コンテナ型に格納されている要素の個数」とします。またO(1)と書いた場合は「"nに"依存しない」ことを意味するものとします。

これらのデータ構造を用いる際、計算時間やメモリ量は動作環境に依存するのですが、「要素数に比例する」「要素数には依存しない時間（メモリ量）で計算できる」などといった特性は動作環境に依存しない、という場合は多いです。そのような特性を表現するために上記の記法を用います。

またこの記法を用いる際は、平均評価や最悪評価という用語も現れます。「平均評価」とは起きる場合に対して平均した結果、「最悪評価」とは起きる場合すべてのうちもっとも悪い結果、という意味です。なお本記事では、「償却評価」も広義の「平均評価」とみなし、すべて「平均評価」「平均」と記述しています。

まずはじめに：今回取り扱わないもの

array, bitset, stack, queue, priority_queue
これら5つは深く説明しません。

array, bitset

これらは要素数が固定のため、他のコンテナ型と比較する意義が薄いことから比較の対象に含めていません。

• array：固定長の配列。std::array<TYPE, SIZE>のように使う。
• bitset：固定長のビット列。

stack, queue, priority_queue

これらの型は、(1)可能な操作がかなり限定されており、他のコンテナ型と比較する意義が薄いこと、また(2)デフォルトではこれら単独で動く型ではなく、別のコンテナ型を用いて動く型である（「コンテナアダプタ」と呼ばれる）ためです。

• stack：スタック。残っている要素の中で最も新しく追加された要素のみにアクセス・削除が可能なデータ構造。
• queue：キュー。残っている要素の中で最も古くに追加された要素のみにアクセス・削除が可能なデータ構造。
• priority_queue：優先順序つきキュー。残っている要素の中で最も大きい（小さい）要素のみにアクセス・削除が可能なデータ構造。大小関係は自由に設定することも可能（自前のクラスのインスタンスを格納する場合など）。

(2)の「別のコンテナ型を用いて動く」という点については以下の通りとなっています。なお、自前で作成したコンテナ型であっても一定の要件を満たしていれば使うことが可能です。

• stack：デフォルトでは内部的にdequeを利用。listやvectorへの変更も可能
• queue：デフォルトでは内部的にdequeを利用。listへの変更も可能
• priority_queue：デフォルトでは内部的にvectorを利用。dequeへの変更も可能

よって、以下で比較するのは残った12個の

vector, list, forward_list#, deque,
set, multiset, unordered_set#, unordered_multiset,
map, multimap, unordered_map, unordered_multimap

となります。

それぞれの型の実装

• vector
  • 可変長配列。連続したメモリ領域に要素を格納するため、メモリ効率がよいです。C言語・C++の配列（foo[42]など）に似ていますが、必要に応じて大きさが自動的に拡張されます。
• list
  • 双方向連結リスト。前後の要素同士をポインタで繋いで一列にしたものです。
• forward_list
  • 片方向連結リスト。双方向連結リストと似ていますが、前方の要素にしか進めないです。
• deque
  • 典型的には「固定の大きさのメモリブロックに要素を詰め、それが一杯になったら次にそのサイズのメモリブロックを確保する」「メモリブロックへのポインタ一覧はvectorと類似の構造で確保する」という挙動をします。vectorと比べると、先頭の要素の挿入・削除が高速なのが特長です。（なお規格上、実装方法についての規定は存在せず、計算量等についてのみ規定があるのみです。）メモリブロックのサイズは、gccでは512バイトとなっており、もっと大きいサイズにしている処理系もあるようです。（参考記事：std::deque の実装 - TrickDiary）
• set
  • 集合。多くの場合で平衡二分探索木を実装に用いています。要素間の大小関係を木の形で表現し、自動的に並べ替えて保持します。要素数がnのとき、木の高さがlog nの定数倍（よく用いられる「赤黒木」では2倍）に収まるため、要素の挿入・削除・検索の時間もこの程度で収まるのが特徴です。
    なお大小関係を用いるため、自前のクラスのインスタンスを格納する場合は、それらが'<'演算子で比較できるようになっている必要があります。
• multiset
  • 多重集合。実装はsetと同様。
• unordered_set, unordered_multiset
  • setないしmultisetに似ていますが、ハッシュテーブルを用いて実装されています（そのため、内部的な違いのみならずAPIにも違いがあります）。要素の値から「ハッシュ値」と呼ばれる値を計算し、その値をもって当該要素をメモリ上に分散して格納することで、アクセス時間を削減します。
    なお自前のクラスのインスタンスを格納する場合は、ハッシュ関数を別途指定する必要があります（参考記事：C++ - std::unordered_map のキーに独自の型を使用する - Qiita）。
• map, multimap, unordered_map, unordered_multimap
  • これらは**連想配列**であり、通常の配列が0以上の整数を指定して要素を取り出すのに対し、連想配列では要素を取り出すための値（キー）の型として好きなものを事前に指定できます。（型には上記の'set'・'multiset'などと同様の条件があります。）
  • これらの実装は、「キーの格納において、'map'を'set'に変えた型を使っている」というような形になります（例えばunordered_mapは、unordered_setの方式でキーを格納している）。

比較1：「■番目の要素にアクセスする」ための時間

以下のコード

std::vector<int> v[3] = {2, 6, 7};
std::cout << v[1] << std::endl;

のように、「■番目の要素」という指定をして取り出すための時間です。連想配列（＊＊＊map）については、「キーを指定してアクセスする時間」を記載しています。
おおむね、高速な順に並べています。

型	時間
vector	O(1)
deque	O(1)
unordered_map unordered_multimap	O(1)（平均） O(n)（最悪）
map multimap	O(log n)
list forward_list	O(n)
set multiset unordered_set unordered_multiset	不可能

vectorの場合、要素を取り出すにはメモリ上の特定の位置にアクセスするだけでよいので、時間はvectorに格納されている要素数には依存しません（当然、要素の大きさには依存します）。dequeについても、「メモリ上の特定の位置にアクセスする」ことを2回行えばよいだけなので同様です。

listやforward_listの場合、「■番目の要素」という指定をして取り出すには、先頭要素から一つずつ辿ることを繰り返すしかないので、平均的には格納された要素数に比例する時間がかかることになります。またそのため、そもそも[]演算子は定義されていません。（std::advance関数を使うことで実現できます。）

連想配列（＊＊＊map）における所要時間については、対応する「＊＊＊set」型に対する「比較3：「要素を検索する」ための時間」の時間と同じなので、そちらをご覧下さい。

比較2：「要素を挿入・削除する」ための時間

例えば、{2, 6, 7}という要素が格納されているときに、「5を6の後ろに追加したい」とか「6を削除したい」というような処理です。

型	時間
vector	O(1)（末尾の削除） O(1)（末尾の挿入、平均） O(n)（末尾の挿入、最悪） O(n)（それ以外）
deque	O(1)（先頭か末尾の削除） O(1)（先頭か末尾の挿入、平均） O(n)（先頭か末尾の挿入、最悪） O(n)（それ以外）
list forward_list	O(1)
unordered_set unordered_multiset	O(1)（平均） O(n)（最悪）
set multiset	O(log n)

listやforward_listは高速です。ポインタを繋ぎ替えるだけでよいためです（連結リスト - Wikipediaに図付きの解説があります）。ただしこれは、どこに挿入/削除したい要素があるかわかっている（一般的な用語ではポインタ、C++ではイテレータ）ことが前提であり、どこに挿入/削除したい要素があるか探す必要があるならば、"比較1：「■番目の要素にアクセスする」ための時間"や"比較3：「要素を検索する」ための時間"にあるO(n)の時間がかかります。

vectorについては、挿入・削除は基本的にはO(n)の時間がかかります。その理由は二つあって、

1. 挿入や削除をすると、その後ろの要素をすべて再配置しないとならない（末尾への挿入・削除でない場合）
2. メモリが足りなくなったら、メモリを別の場所に確保してから全要素を移転しないとならない（挿入の場合）

1.については以下の図の通りです。ただしこの処理は末尾への挿入・削除であって、次の2.に該当する場合を除いては必要ありません。（すなわち、末尾の削除は無条件にO(1)時間で済みます。）

2 6 7
      ↓6を削除
2   7
      ↓間を詰める
2 7

2.については、new []演算子を使ったことがある方ならわかるかと思いますが、「すでにnewで確保してある領域を、そのまま後ろに伸ばす」という処理は（基本的には）できません。後ろが別のnewの結果によって詰まっていることもあるためです。そのため、別の場所に必要なメモリを確保して、内容も移転するということになるのです。ただ、vectorはデフォルトではメモリは常にぎりぎりに確保しているわけではないので（「比較4：メモリ利用量」で説明します）、移転の処理回数を抑えることができ、全体を平均すればO(1)時間で可能になります。
ただし現実には後述の通り、末尾の挿入が多いのであれば、vectorよりもdequeのほうが速度でもメモリ利用の観点でも有利です。

dequeについては、メモリブロックを追加で確保したり減らしたりしない場合はO(1)時間ですが、そうでない場合はvectorと同様の処理が必要になります。そのため最悪ではO(n)時間が必要です。ただしメモリブロックのどこから読み出せばよいかを別途保持しているため、先頭の挿入・削除についてはvectorの末尾の場合と同等の時間で処理できます。しかも、vectorのときにあった「メモリを別の場所に確保してから全要素を移転」という処理が「全てのメモリブロックのある場所へのポインタを移転」に変わるので、同じO(1)であってもメモリの書き換えにかかる時間がvectorに比べて大幅に小さいです（参考：そろそろstd::dequeについて語ろうか - kikairoyaの日記）。

setやmultisetは上述の通り平衡二分探索木を用いているため、要素の挿入・削除時にポインタを付け替えないとならない要素数もO(log n)で済みます。

unordered_setやunordered_multisetは、ハッシュテーブルの特性上、挿入や削除の時間は要素検索（次節）と同じで、平均O(1)時間・最悪O(n)時間でのアクセスとなります。ただし挿入の場合はそれに加えて、要素数が一定以上になった場合にハッシュテーブルの再構築が行われるため、この場合にはO(n)時間がかかります（ただし全体で平均すれば、vectorと同様の理由でO(1)時間）。ハッシュテーブルの再構築については、挿入する要素数に見当がついているならば、事前にハッシュテーブルの大きさを指定することで再構築を避けることができます。

比較3：「要素を検索する」ための時間

ここでいう「検索」とは、例えば{2, 6, 7}という要素が格納されているときに、「6が含まれているか否か。含まれているならその要素へのポインタ（イテレータ）」という結果を返す処理です。
連想配列（＊＊＊map）については、キーを基準とした検索ではなく、（キーを与えた結果として）実際に引き出される値を基準とした検索について記載しています。キーを基準とした検索については、「比較1：「■番目の要素にアクセスする」ための時間」に記載した通りですが、「＊＊＊map」を「＊＊＊set」に置き換えたものの時間となります。

型	時間
unordered_set unordered_multiset	O(1)（平均） O(n)（最悪）
set multiset	O(log n)
vector deque list forward_list map multimap unordered_map unordered_map	O(n)

検索されることに特化したset・multiset・unordered_set・unordered_multisetがもちろん高速です。またこれらの型は、メンバ関数としてfindなどの検索用関数が定義されています（他の型にはないので、std::find関数などを使うことになります）。
unordered_set・unordered_multisetでは、最悪でO(n)時間となっていますが、実用上はほぼO(1)とみて差し支えないです。

これら以外については、順番に要素を見ていって該当する要素が見つかるか判定しないとならないため、他よりも遅いです（O(n)時間が必要になります）。ただしvector・dequeについては、任意の順序で要素を並べるということを諦めればO(log n)時間での検索も可能です（二分探索。詳細は後述）。

比較4：メモリ利用量

実装依存なので異なる場合もありますが、私がgccを基準に調べた範囲では以下のようになっていると見ています。
nが要素数です。ST = sizeof(TYPE)（1要素を格納するのに必要なメモリ量。連想配列の場合はST = sizeof(TYPE) + sizeof(KEYTYPE)）、SP = sizeof(void*)（ポインタ変数1つを格納するのに必要なメモリ量）です。
以下、おおむね小さいものから順に並べています。
ソースコードを読みきれてないので、細かい値（特に、最後の加算）については間違いがあるかもしれません。

型	メモリ量
vector<TYPE>	n*ST + 3SP （メモリ量を切り詰めた場合） n***2ST** + 3*SP （メモリ量をgccデフォルトの方式で自動制御した場合）
deque<TYPE>	n*(ST + 2ST/512SP) + 6*SP （手元のGCC4.5.2の場合）
forward_list<TYPE>	(n+1)*(ST+SP) + SP
list<TYPE>	(n+1)*(ST+2*SP) + SP
unordered_set<TYPE> unordered_multiset<KEYTYPE, TYPE> unordered_map<KEYTYPE, TYPE> unordered_multimap<TYPE>	n*(ST+2*SP) + 2SP （平均ケース。おそらく） n***(ST+3SP)** + 2*SP （最悪ケース。おそらく）
set<TYPE> multiset<TYPE> map<KEYTYPE, TYPE> multimap<KEYTYPE, TYPE>	(n+1)*(ST+3*SP) + SP（おそらく）

一番注目していただきたいのは、nないしn+1に何が掛けられているかです。
例えばvectorでnに掛けられたのがSTだけというのは、要素を格納するためのバイト数ぴったりの領域だけあればよいということです（アライメントの影響は無視した）。
一方でforward_listやunordered_setなどの場合、nに掛けられたのがST+SPなので、要素を1つ作るごとにポインタ1つぶんの領域が追加で必要になるという実装になっています。
setなどに至ってはST+3*SPと、要素を1つ作るごとにポインタ3つぶんの領域が必要になります。（これらは上述の通り、多くの実装で「平衡二分探索木」を用いており、各要素につき「親のノード」「左の子のノード」「右の子のノード」を格納するためポインタが3つ必要になる）

• 補足1：2倍の理由（vectorにおける2*ST、dequeにおける2*ST/512*SP、unordered_set・unordered_multisetにおける2*SP）
  • これは、vectorなどで格納したい要素数がすでに確保されているメモリ量を上回った場合、毎度その大きさを格納するちょうどのサイズをメモリ上に確保するのは計算時間がかかるので、ある程度大きめに格納するようになっているためです。その中で典型的なものが「2倍にする」というものであるため（例えば、メモリが8要素分確保されている状況で9要素目を追加しようとすると、メモリは16要素分確保される）、これを考慮して本記事でも「2倍」としています（参考記事：d.y.d.）。
  • なお、サイズの上限がわかっている場合などは、自前でコントロールすることも可能です（参考：std::vector の shrink_to_fit - 野良C++erの雑記帳）。
• 補足2：dequeにおける2*ST/512*SPで「512」という数が現れる理由
  • 前述の「それぞれの型の実装」を参照。
• 補足3：「+ 2SP」「+ 3SP」の理由（vector・unordered_setなど）
  • これは、メモリ領域のどこが先頭でどこが末尾なのかを覚えておく必要があり、そのためにはポインタ型二つぶんの領域が必要なためである。さらにvectorの場合は上記の通り、メモリ領域は大きめに確保されているため、その終端も保持することになるので、全部でポインタ型三つぶんの領域が必要になる。
• 補足4：「+ 6*SP」の理由（deque）
  • これは、dequeが上記の通り「可変長配列<固定長配列>」というデータ構造のため、「メモリ上における可変長配列の先頭・末尾」でポインタ変数2つ、dequeの先頭・末尾がどの可変長配列の要素なのか＆どの固定長配列の要素なのかでポインタ変数2×2=4つが必要になるためです。
• 補足5：「+ SP」の理由（list・forward_list・setなど）
  • これらは要素をポインタで繋ぐタイプのコンテナ型であり、先頭要素のポインタを保持する必要があるためです。
    

一覧表

平均時間計算量・メモリ量のみ記載しています。
メモリ量については、1要素を格納するのに追加で必要なメモリ量（nにかけられている値からSTを引いたもの）で記載しています。

比較結果として有利といえるものを太字で示してあります。

型	1. ランダム アクセスの 時間	2. 挿入・削除の 時間	3. 検索の時間	4. メモリ量
vector	O(1)	O(1)（末尾） O(n)（他）	O(n)	0～ST
deque	O(1)	O(1)（挿入か末尾） O(n)（他）	O(n)	2ST/512SP
list	O(n)	O(1)	O(n)	2*SP
forward_list	O(n)	O(1)	O(n)	SP
unordered_set unordered_multiset	不可能	O(1)	O(1)	2*SP
set multiset	不可能	O(log n)	O(log n)	3*SP
unordered_map unordered_multimap	O(1)	O(1)	O(n)	2*SP
map multimap	O(log n)	O(log n)	O(n)	3*SP

これらをまとめると、冒頭のまとめのようになるわけです。

ちなみに上記の表を見ると、unordered_set・unordered_multisetに対してset・multisetの利点がないです。計算時間でもメモリ量でも。unordered_map・unordered_multimapに対するmap・multimapも同様です。
実際、少なくとも単なる連想配列として使うぶんには、（コンパイラさえ対応していれば）unordered_set・unordered_multisetのほうが有利です。
この点については、後述の「補足：unordered_set・unordered_multisetに対するset・multisetの利点は？」にて補足します。

補足1：vector・dequeからの検索をO(log n)時間で行えるようにする方法（条件付き）

vectorとdequeについては、通常は検索にはO(n)時間がかかりますが、中の要素が大きさの順に並び替えられているのであれば、std::binary_search関数やstd::equal_range関数を用いてO(log n)時間で検索を行うことができます。これは二分探索という原理に基づくものです。
ただし、vectorやdequeを大きさの順に並び替える（ソート）には通常O(n log n)時間が必要なこと、またvectorやdequeの途中への挿入・削除にもO(n)時間がかかることから、内容の修正の頻度が高い場合にはこの方法は不向きです。

補足2：unordered_set・unordered_multisetに対するset・multisetの利点は？

set・multisetについては上述の通り、unordered_set・unordered_multisetに比べて計算速度でもメモリ効率でも多くの場合に劣ります。これは、map・multimapとunordered_map・unordered_multimapについても同じです。
さらにsetやmapなどについては、「全要素を列挙するのが遅い」という欠点もあります（参考記事：mapとunordered_mapのアイテム全走査の比較とmapの存在意義について考える - 睡眠不足？！、std::mapを線形探索してはいけない100の理由）。これらの記事では、「map（＝setと同等の実装による連想配列）をあえて使う意味がない」とまで言っています。

set・multiset（map・multimapも同様）の名誉のために（？）続けておくと、ややトリッキーな使い方をする場合にはこれらも生きてきます（実際、私は助けられました）。

1. setなどは要素の大きさを基準に並べるので、その関係をあとで利用する場合はsetを使う意義があります。
   • この場合は上述した「vector上の二分探索」と競合します。メモリ効率ではvectorが上ですが、一方でsetのほうが挿入・削除が速い（O(log n)時間、vectorだとO(n)時間）という利点があります。
2. setやmapなどのイテレータをコンテナ外部に保存したとき、そのコンテナから（当該イテレータが指す以外の）別の要素を挿入・削除しても、当該イテレータは引き続きその要素を指すことが保証されます。unordered_set・unordered_mapなどではこれが保証されません。
   • 同様の「要素を挿入・削除しても、当該イテレータは引き続きその要素を指すことが保証される」という特性を持っているコンテナ型は、これ以外にはlist・forward_listがあります。

以下に2.の例として、vectorの要素を削除するとイテレータが無効になる場合を示します。（2021.3.2 修正しました。@Estraven様ありがとうございます）

std::vector<int> v = {2, 6, 7};
std::vector<int>::iterator i = v.begin();
++i; // この時点でiは6を指しているのだが
v.erase(v.begin()); // ここでvの先頭を削除すると
// iはもう6を指していない

参考にした資料

本文中でリンクを貼っているもの以外

• cpprefjp - C++ Library Reference
• gccの各コンテナ型のヘッダファイル