C++のコンテナクラスとは、複数の値やオブジェクトをまとめて管理するための仕組みです。
配列のように複数のデータを扱えるだけでなく、要素の追加、削除、検索、並び替え、重複排除、キーによる管理など、さまざまな操作を効率よく行えます。
C++標準ライブラリには、多くの標準コンテナが用意されています。
代表的なものには、std::vector、std::map、std::set、std::unordered_map、std::queue などがあります。
コンテナを正しく選ぶことは、C++プログラムの速度、メモリ効率、可読性、保守性に大きく関わります。
C++標準コンテナの主な分類
C++の標準コンテナは、大きく分けると以下のように分類できます。
シーケンスコンテナ
シーケンスコンテナは、要素を順番に並べて保持するコンテナです。
代表的なものには、std::vector、std::array、std::deque、std::list、std::forward_list があります。
順番を持つデータを扱いたい場合に使います。
たとえば、点数の一覧、ユーザーリスト、履歴、座標データ、商品リストなどを管理する場面に向いています。
連想コンテナ
連想コンテナは、キーや値を基準にして要素を管理するコンテナです。
代表的なものには、std::set、std::map、std::multiset、std::multimap があります。
これらは通常、要素がキー順に並ぶように管理されます。
重複を防ぎたい場合や、キーから値を検索したい場合、ソートされた状態を保ちたい場合に使います。
非順序連想コンテナ
非順序連想コンテナは、ハッシュテーブルを使って要素を管理するコンテナです。
代表的なものには、std::unordered_set、std::unordered_map、std::unordered_multiset、std::unordered_multimap があります。
順序は保証されませんが、平均的には高速な検索ができます。
キー順に並べる必要がなく、検索速度を重視したい場合に向いています。
コンテナアダプタ
コンテナアダプタは、既存のコンテナを特定の用途に合わせて使いやすくしたものです。
代表的なものには、std::stack、std::queue、std::priority_queue があります。
これらは内部的に別のコンテナを利用しながら、後入れ先出し、先入れ先出し、優先度順の取り出しといった特定の操作を提供します。
シーケンスコンテナ
std::vector
std::vectorの概要
std::vector は、C++で最もよく使われる標準コンテナのひとつです。
可変長配列のようなもので、要素数を後から増やしたり減らしたりできます。
内部的には連続したメモリ領域に要素を保持するため、添字によるアクセスが非常に高速です。
std::vectorの特徴
std::vector は、末尾への追加が得意です。
ただし、正確には末尾追加は「償却定数時間」です。
通常は高速ですが、内部容量が足りなくなった場合は、より大きなメモリ領域を確保し直すため、一時的に処理が重くなることがあります。
添字アクセスは高速です。
配列のように任意の位置の要素へすぐアクセスできます。
一方で、先頭や途中への挿入・削除はあまり得意ではありません。
途中に要素を追加したり削除したりすると、その後ろにある要素を移動する必要があるためです。
std::vectorが向いている場面
std::vector は、基本的に最初に検討すべきコンテナです。
複数のデータを順番に保持したい場合、末尾に要素を追加していく場合、添字でアクセスしたい場合に向いています。
特別な理由がなければ、まず std::vector を使うと考えて問題ありません。
std::vectorの注意点
std::vector は、内部容量が足りなくなると再確保を行います。
再確保が発生すると、要素が別のメモリ領域へ移動されることがあります。
その結果、既存のイテレータ、参照、ポインタが無効になる場合があります。
要素数があらかじめ分かっている場合は、事前に容量を確保しておくと効率的です。
std::array
std::arrayの概要
std::array は、固定長配列を扱うためのコンテナです。
通常のC言語風配列よりも安全で、標準ライブラリの機能と相性が良いという特徴があります。
サイズはコンパイル時に決まります。
std::arrayの特徴
std::array は、要素数を後から変更できません。
メモリは連続しており、添字アクセスは高速です。
また、サイズは型の一部になります。
つまり、同じ要素型でもサイズが違えば別の型として扱われます。
std::arrayが向いている場面
std::array は、要素数があらかじめ決まっている場合に向いています。
たとえば、3次元座標、曜日ごとの値、月ごとのデータ、固定長のバッファなどに適しています。
動的に要素数を変える必要がないなら、std::array は安全で効率的な選択肢です。
std::deque
std::dequeの概要
std::deque は、先頭と末尾の両方に対して高速に要素を追加・削除できるコンテナです。
名前は「double-ended queue」に由来します。
std::dequeの特徴
std::deque は、先頭への追加、末尾への追加、先頭からの削除、末尾からの削除が得意です。
また、添字アクセスも可能です。
ただし、std::vector のように完全に連続したメモリ領域に要素が並んでいるとは限りません。
多くの実装では、複数のメモリブロックを組み合わせたような構造で管理されています。
そのため、添字アクセスはできますが、メモリ連続性を重視する処理では std::vector の方が向いていることがあります。
std::dequeが向いている場面
std::deque は、先頭と末尾の両方で要素を追加・削除したい場合に向いています。
キューのような処理、履歴管理、前後に伸びるデータ構造などで使いやすいコンテナです。
std::list
std::listの概要
std::list は、双方向連結リストです。
各要素が前後の要素へのリンクを持っており、メモリ上で連続している必要はありません。
std::listの特徴
std::list は、位置が分かっている場所への挿入や削除が高速です。
ただし、この説明には注意が必要です。
挿入・削除したい位置を指すイテレータがすでにある場合は高速ですが、その位置を探す処理は線形時間になります。
つまり、「途中挿入・削除が多いなら必ず std::list が速い」とは限りません。
std::list は添字アクセスができません。
先頭から順番にたどる必要があります。
また、各要素がリンク情報を持つため、メモリ使用量は増えやすく、CPUキャッシュ効率も std::vector より悪くなることがあります。
std::listが向いている場面
std::list は、要素の位置をイテレータで保持しておき、その場所に対して頻繁に挿入・削除を行う場合に向いています。
一方、単純な一覧管理や検索が多い処理では、std::vector の方が速くなることも多いです。
実務では、まず std::vector を検討し、明確な理由がある場合に std::list を使うのが現実的です。
std::forward_list
std::forward_listの概要
std::forward_list は、単方向連結リストです。
std::list が前後に移動できるのに対し、std::forward_list は前方向にしか進めません。
std::forward_listの特徴
std::forward_list は、std::list よりも軽量です。
その代わり、できる操作は少なくなります。
前方向にしか走査できないため、扱いには少し注意が必要です。
また、標準仕様として size() メンバ関数を持ちません。
要素数を知りたい場合は、先頭から数える必要があります。
std::forward_listが向いている場面
std::forward_list は、メモリ使用量を抑えたい場合や、前方向の走査だけで十分な場合に向いています。
ただし、初心者が最初に使う機会は多くありません。
通常は std::vector、std::deque、std::list の方が扱いやすいです。
連想コンテナ
std::set
std::setの概要
std::set は、重複しない値を管理するためのコンテナです。
同じ値を複数入れようとしても、ひとつだけ保持されます。
std::setの特徴
std::set は、要素を一定の順序で管理します。
一般的には「自動的にソートされる」と説明されますが、より正確には、比較関数に基づいた順序を常に保つように管理されています。
検索、挿入、削除は通常、対数時間で行われます。
多くの実装では平衡二分探索木が使われます。
ただし、C++標準規格として特定の木構造が必須と決められているわけではありません。
std::setが向いている場面
std::set は、重複を排除したい場合に向いています。
また、常にソートされた状態で値を保持したい場合、最小値や最大値を取り出したい場合、範囲検索を行いたい場合にも適しています。
順序が必要な集合を扱うなら、std::set は有力な選択肢です。
std::map
std::mapの概要
std::map は、キーと値のペアを管理するコンテナです。
他の言語でいう辞書、連想配列、オブジェクト、マップのような役割を持ちます。
キーは重複できません。ひとつのキーに対して、ひとつの値が対応します。
std::mapの特徴
std::map は、キー順に要素を管理します。
検索、挿入、削除は通常、対数時間で行われます。
キーを基準にして値を取り出せるため、IDから名前を引く、単語ごとの出現回数を数える、商品コードから価格を取得する、といった処理に向いています。
std::mapの注意点
std::map の添字演算子を使うと、存在しないキーにアクセスした場合、そのキーが新しく追加されます。
これは単語カウントのような処理では便利ですが、単に存在確認をしたいだけの場合には注意が必要です。
存在確認には、検索用の関数を使う方が安全です。
また、値型によっては、添字演算子を使うためにデフォルト構築可能である必要があります。
std::multiset
std::multisetの概要
std::multiset は、重複を許す集合です。
std::set は同じ値をひとつしか保持できませんが、std::multiset は同じ値を複数保持できます。
std::multisetが向いている場面
std::multiset は、重複する値を含めて、順序付きで管理したい場合に向いています。
たとえば、同じ点数を取った人が複数いる場合や、同じ値が何回出現したかを順序付きで扱いたい場合に使えます。
std::multimap
std::multimapの概要
std::multimap は、同じキーを複数持てるマップです。
通常の std::map では、ひとつのキーに対してひとつの値しか持てません。
一方、std::multimap では、同じキーに複数の値を対応させることができます。
std::multimapが向いている場面
std::multimap は、ひとつのキーに対して複数の値を紐づけたい場合に使えます。
ただし、実務では std::map の値として std::vector などを持たせる設計の方が扱いやすいこともあります。
そのため、std::multimap は便利ではあるものの、用途をよく考えて選ぶ必要があります。
非順序連想コンテナ
std::unordered_set
std::unordered_setの概要
std::unordered_set は、重複しない値を順序なしで管理するコンテナです。
内部的にはハッシュテーブルを使います。
std::unordered_setの特徴
std::unordered_set は、順序を保証しません。
その代わり、平均的には非常に高速な検索ができます。
ただし、ハッシュ衝突が多い場合などには、最悪で線形時間になることがあります。
std::unordered_setが向いている場面
std::unordered_set は、値が存在するかどうかを高速に調べたい場合に向いています。
順序が不要で、重複を排除したい場合には、std::set よりも適していることがあります。
たとえば、すでに処理済みのIDを記録する、入力値の重複を検出する、特定の単語が登録済みか確認する、といった用途に向いています。
std::unordered_map
std::unordered_mapの概要
std::unordered_map は、キーと値のペアを順序なしで管理するコンテナです。
std::map と似ていますが、キー順には並びません。
内部的にはハッシュテーブルを使います。
std::unordered_mapの特徴
std::unordered_map は、平均的には定数時間で検索できます。
そのため、キーから値を高速に取り出したい場合に非常によく使われます。
ただし、順序は保証されません。キー順に並んでいることを前提にした処理には使えません。
また、ハッシュ衝突が多い場合には、最悪で線形時間になることがあります。
std::unordered_mapが向いている場面
std::unordered_map は、順序が不要で、検索速度を重視したい場合に向いています。
ユーザーIDからユーザー情報を引く、文字列から出現回数を数える、設定名から値を取得する、キャッシュを管理する、といった用途に適しています。
実務では、キー順に並べる必要がなければ std::map より std::unordered_map が選ばれることも多いです。
std::mapとstd::unordered_mapの違い
並び順の違い
std::map はキー順に並びます。
一方、std::unordered_map は順序を保証しません。
キー順に走査したい場合は std::map、順序が不要な場合は std::unordered_map が候補になります。
検索速度の違い
std::map の検索は通常、対数時間です。
std::unordered_map の検索は平均的には定数時間です。
ただし、最悪の場合は線形時間になる可能性があります。
そのため、平均的な高速性を重視するなら std::unordered_map、安定した順序や範囲検索を重視するなら std::map が向いています。
キーに必要な性質の違い
std::map のキーには、順序を決めるための比較が必要です。
std::unordered_map のキーには、ハッシュ関数と等値比較が必要です。
自作型をキーとして使う場合、この違いは重要です。
コンテナアダプタ
std::stack
std::stackの概要
std::stack は、後入れ先出しのデータ構造です。
最後に入れた要素を最初に取り出します。
このような仕組みは、LIFOと呼ばれます。
std::stackが向いている場面
std::stack は、直前の状態を戻す処理や、入れ子構造の解析に向いています。
たとえば、undo機能、括弧の対応チェック、深さ優先探索、再帰処理の代替などに使われます。
std::queue
std::queueの概要
std::queue は、先入れ先出しのデータ構造です。
先に入れた要素を先に取り出します。
このような仕組みは、FIFOと呼ばれます。
std::queueが向いている場面
std::queue は、順番待ちの処理に向いています。
たとえば、タスク処理、メッセージキュー、幅優先探索、リクエスト処理などで使われます。
std::priority_queue
std::priority_queueの概要
std::priority_queue は、優先度が高い要素から取り出すためのコンテナアダプタです。
通常のキューは入れた順番に取り出しますが、std::priority_queue は優先度に基づいて取り出します。
デフォルトでは、大きい値が優先されます。
std::priority_queueが向いている場面
std::priority_queue は、優先度付きの処理に向いています。
たとえば、重要度の高いタスクから処理する場合、上位N件を抽出する場合、スケジューリング、ダイクストラ法などのアルゴリズムで使われます。
イテレータとは
イテレータの概要
イテレータは、コンテナ内の要素を指し示すための仕組みです。
ポインタに似た感覚で使われ、コンテナの先頭から末尾まで要素を順番にたどるために利用されます。
begin()とend()の意味
多くのコンテナには、先頭を表す begin() と、末尾の次を表す end() があります。
ここで重要なのは、end() は最後の要素そのものではないという点です。
end() は、最後の要素の次を示す特別な位置です。
この考え方は、C++の標準アルゴリズムや範囲処理で非常に重要です。
イテレータの無効化
コンテナに要素を追加・削除すると、既存のイテレータや参照が無効になることがあります。
特に std::vector は、再確保が発生すると、既存のイテレータや参照が無効になる可能性があります。
一方、std::list はノードベースの構造なので、特定の操作ではイテレータが比較的安定しやすいという特徴があります。
ただし、コンテナごとに無効化のルールは異なるため、要素を操作しながら走査する場合は注意が必要です。
コンテナを選ぶときの考え方
まずstd::vectorを検討する
C++では、特別な理由がなければ、まず std::vector を検討するのが実用的です。
std::vector はメモリ効率が良く、アクセスが速く、標準アルゴリズムとも相性が良いためです。
ただし、先頭への頻繁な追加・削除や、キーによる高速検索が必要な場合は、別のコンテナを選ぶべきです。
キーで値を引きたい場合
キーから値を取得したい場合は、std::map または std::unordered_map を使います。
キー順に並べたいなら std::map、順序が不要で検索速度を重視したいなら std::unordered_map が向いています。
重複を排除したい場合
重複しない値の集合を作りたい場合は、std::set または std::unordered_set を使います。
ソートされた状態が必要なら std::set、順序が不要なら std::unordered_set が向いています。
先頭と末尾の操作が多い場合
先頭と末尾の両方で追加・削除を行いたい場合は、std::deque が向いています。
std::vector は末尾操作には強いですが、先頭操作には向いていません。
位置が分かっている場所で挿入・削除したい場合
イテレータで位置を保持しておき、その位置に対して頻繁に挿入・削除を行う場合は、std::list が候補になります。
ただし、単に「途中の値を探して削除する」場合は、検索自体に時間がかかります。
順番待ちを表したい場合
先に入れたものを先に処理したい場合は、std::queue が向いています。
タスク処理や幅優先探索のような処理に適しています。
後戻り処理をしたい場合
最後に入れたものを先に取り出したい場合は、std::stack が向いています。
undo処理や括弧の対応チェックなどで使われます。
優先度順に処理したい場合
優先度が高いものから順に取り出したい場合は、std::priority_queue が向いています。
スケジューリングや最短経路探索などでよく使われます。
コンテナごとの計算量の目安
std::vector
添字アクセスは定数時間です。
末尾追加は償却定数時間です。
先頭や途中への挿入・削除は線形時間になります。
検索は、特別な工夫をしなければ線形時間です。
std::deque
添字アクセスは定数時間です。
先頭と末尾への追加・削除は定数時間です。
途中への挿入・削除や検索は、基本的に線形時間になります。
std::list
先頭や末尾への追加・削除は定数時間です。
位置が分かっている場合の挿入・削除も定数時間です。
ただし、任意の値を探す処理は線形時間です。
添字アクセスはできません。
std::setとstd::map
検索、挿入、削除は通常、対数時間です。
要素はキー順に管理されます。
先頭や末尾に追加するという考え方ではなく、キーの順序に従って適切な位置に挿入されます。
std::unordered_setとstd::unordered_map
検索、挿入、削除は平均的には定数時間です。
ただし、ハッシュ衝突が多い場合などには、最悪で線形時間になることがあります。
順序は保証されません。
自作クラスをコンテナで扱う場合
std::vectorに自作クラスを入れる場合
std::vector には、自作クラスのオブジェクトをそのまま入れることができます。
ユーザー情報、商品情報、座標、設定値などをまとめて管理する場合に便利です。
std::setに自作クラスを入れる場合
std::set に自作クラスを入れる場合は、要素同士の順序を決める必要があります。
たとえば、年齢順に並べる、名前順に並べる、ID順に並べるなど、比較の基準を明確にする必要があります。
注意点として、比較に使わない項目は、集合上では区別されない場合があります。
たとえば、年齢だけで比較すると、名前が違っても同じ年齢のユーザーは同じ要素のように扱われる可能性があります。
そのため、どの項目で同一性や順序を判断するのかを慎重に設計する必要があります。
std::unordered_mapに自作クラスをキーとして使う場合
std::unordered_map のキーに自作クラスを使う場合は、ハッシュ関数と等値比較が必要です。
どのような条件で同じキーとみなすのか、そのキーをどのようにハッシュ化するのかを定義する必要があります。
この点は、std::map よりも少し難易度が高くなります。
push_backとemplace_backの違い
push_backの考え方
push_back は、すでに作られたオブジェクトをコンテナへ追加する操作です。
単純な値を追加する場合や、すでにオブジェクトが存在している場合に自然に使えます。
emplace_backの考え方
emplace_back は、コンテナの中で直接オブジェクトを構築する操作です。
一時オブジェクトの生成やコピー・ムーブを減らせる場合があります。
どちらを使うべきか
emplace_back は便利ですが、常に明確に速いとは限りません。
現代のC++では、ムーブやコピー省略などの最適化も強力です。
そのため、単純な値を追加するだけなら push_back でも十分です。
オブジェクトをその場で構築したい場合は emplace_back が便利です。
可読性も考えて使い分けることが大切です。
コンテナ使用時の注意点
イテレータや参照の無効化に注意する
コンテナに要素を追加・削除すると、既存のイテレータ、参照、ポインタが無効になる場合があります。
特に std::vector は、内部再確保が起きると要素の配置場所が変わるため注意が必要です。
要素追加後も以前のイテレータを使い続けると、未定義動作につながる可能性があります。
削除しながら走査する場合は注意する
コンテナを走査しながら要素を削除する場合は、イテレータの扱いに注意が必要です。
削除によって現在のイテレータが無効になることがあるため、削除後に次の有効な位置を正しく扱う必要があります。
C++20以降では、条件に一致する要素を削除する便利な仕組みも用意されています。
mapの添字アクセスに注意する
std::map や std::unordered_map の添字アクセスは便利ですが、存在しないキーにアクセスすると新しい要素が作られます。
値を追加したい場合やカウント処理では便利ですが、単に存在確認をしたいだけなら適切な検索方法を使う方が安全です。
unordered系の順序に依存しない
std::unordered_map や std::unordered_set は、要素の順序を保証しません。
実行環境や挿入順、ハッシュの状態によって、走査順が変わる可能性があります。
順序が必要な処理では、std::map や std::set を使うべきです。
実務でよく使うコンテナ
特によく使うコンテナ
実務で特によく使われるのは、std::vector、std::unordered_map、std::map、std::set、std::unordered_set です。
多くの場面では、これらを理解していればかなり対応できます。
場面によってよく使うコンテナ
std::deque、std::queue、std::stack、std::priority_queue、std::array もよく使われます。
ただし、用途が比較的はっきりしています。
やや特殊なコンテナ
std::list、std::forward_list、std::multimap、std::unordered_multimap は、使う場面がやや限定されます。
便利な場面はありますが、初心者が最初に多用するコンテナではありません。
コンテナ選びのまとめ
普通に複数データを持つならstd::vector
順番にデータを並べて保持したいなら、まず std::vector を検討します。
高速な添字アクセス、良いメモリ効率、標準アルゴリズムとの相性の良さが大きな強みです。
固定長ならstd::array
要素数がコンパイル時に決まっていて、後から増減しないなら std::array が向いています。
通常の配列よりも扱いやすく、安全性も高いです。
先頭と末尾を操作するならstd::deque
先頭にも末尾にも頻繁に追加・削除するなら std::deque が向いています。
キュー的な使い方にも適しています。
キーで値を管理するならstd::mapまたはstd::unordered_map
キー順に並べたいなら std::map、順序が不要で高速検索を重視するなら std::unordered_map が向いています。
重複を排除するならstd::setまたはstd::unordered_set
ソートされた集合が必要なら std::set、順序が不要なら std::unordered_set を選びます。
順番待ちならstd::queue
先に入れたものから順に処理したい場合は std::queue を使います。
後入れ先出しならstd::stack
最後に入れたものを最初に取り出したい場合は std::stack を使います。
優先度順ならstd::priority_queue
優先度の高いものから処理したい場合は std::priority_queue を使います。
最終的な考え方
C++のコンテナは、単にデータを入れる箱ではありません。
どのコンテナを選ぶかによって、処理速度、メモリ使用量、コードの分かりやすさ、保守性が大きく変わります。
重要なのは、「どんなデータを入れるか」だけではなく、「どの操作が多いか」を考えることです。
添字アクセスが多いのか、末尾追加が多いのか、検索が多いのか、重複を防ぎたいのか、順序が必要なのか。
それによって選ぶべきコンテナは変わります。
基本的には、まず std::vector を検討します。
キー検索が必要なら std::map や std::unordered_map、重複排除が必要なら std::set や std::unordered_set を選びます。
この判断基準を押さえておけば、C++の標準コンテナをかなり実用的に使い分けられるようになります。
以上、C++のコンテナクラスについてでした。
最後までお読みいただき、ありがとうございました。
