C++のコンテナ一覧

はじめに

C++には標準ライブラリ(STL)には様々なコンテナが用意されている．種類が多いため，どういう時にどのコンテナを扱うのが疑問に持った．それでcpprefjpや過去の誰かが書いていた記事,生成系AIからそれぞれのコンテナの特徴と使用用途を書いた．

コンテナの情報がほしいときにつかってほしい

コンテナ一覧

シーケンスコンテナ

• std::vector - 動的配列
• std::deque - 両端キュー
• std::list - 双方向リンクリスト
• std::forward_list - 単方向リンクリスト
• std::array - 固定長配列(C++11以降)

コンテナアダプタ

• std::stack - LIFO(後入れ先出し)データ構造
• std::queue - FIFO(先入れ先出し)データ構造
• std::priority_queue - 優先度付きキュー

関連コンテナ

• std::set - 集合(ユニークな要素の集まり)
• std::multiset - 重複を許可する集合
• std::map - 連想配列(キーと値のペア)
• std::multimap - 重複キーを許可する連想配列

未順序化コンテナ

• std::unordered_set - ハッシュ集合(C++11以降)
• std::unordered_multiset - 重複を許可するハッシュ集合(C++11以降)
• std::unordered_map - ハッシュマップ(C++11以降)
• std::unordered_multimap - 重複キーを許可するハッシュマップ(C++11以降)

シーケンスコンテナ

std::vector

• 特徴: 動的配列。要素はメモリ上で連続して配置されます。
• 使用時のシナリオ: 空間的局所性が重要な場合や、ランダムアクセスが頻繁に必要な場合に適しています。大きさが動的に変更可能で、末尾への追加・削除が効率的ですが、先頭や中間への挿入・削除はコストが高くなります。

std::deque

• 特徴: 両端キュー。メモリ上では非連続のブロックで管理されることが多く、先頭と末尾の両方への追加・削除が効率的です。
• 使用時のシナリオ: 頻繁に先頭または末尾に要素を追加・削除する場合に適しています。キューの実装やスクロールバッファなどに使用されます。

std::list

• 特徴: 双方向リンクリスト。各要素が個別にメモリ割り当てされ、前後の要素へのポインタを持ちます。
• 使用時のシナリオ: リスト内の任意の位置での挿入と削除が頻繁に行われる場合に適しています。ランダムアクセスはサポートされていませんが、イテレータを使った要素へのアクセスが可能です。

std::forward_list

• 特徴: 単方向リンクリスト。std::listよりもメモリ使用量が少ないですが、前方向へのみアクセス可能です。
• 使用時のシナリオ: メモリ消費を抑えつつ、リスト内での要素の挿入や削除を行いたい場面に適しています。データの一時的な保管、スペースが重要な組み込みシステムに利用されることがあります。

std::array

• 特徴: 固定長配列。std::vectorと同様に要素はメモリ上で連続して配置されますが、サイズはコンパイル時に固定され、変更不可能です。
• 使用時のシナリオ: 配列のサイズが変更されることがなく、コンパイル時にサイズが既知の場合に適しています。スタック上に配置されるため、ヒープ割り当てを避けたい場合やリアルタイムシステムでの使用に適しています。

まとめ

これらのシーケンスコンテナは、様々なデータ管理ニーズに応じて選択することができます。std::vectorは最も一般的に使われるコンテナで、高速なランダムアクセスと効率的なメモリ使用が求められる場合に適しています。一方、std::listやstd::forward_listは挿入と削除が頻繁に行われるシナリオで有効ですが、ランダムアクセスのパフォーマンスは低下します。std::dequeは先頭や末尾への操作が多い場合に、std::arrayは固定サイズのデータを効率的に扱う場合に最適です。

コンテナアダプタ

std::stack

• 特徴: Last-In, First-Out (LIFO) データ構造。最後に追加された要素が最初に取り出される。
• 使用時のシナリオ: 履歴の追跡、後戻り機能、再帰アルゴリズムの実装、文法解析などで使用されます。関数コールのスタックや逆ポーランド記法の計算などに利用されることが多いです。

std::queue

• 特徴: First-In, First-Out (FIFO) データ構造。最初に追加された要素が最初に取り出される。
• 使用時のシナリオ: タスクキュー、イベント管理、データのバッファリング（例：プリンタのジョブキュー）、幅優先探索アルゴリズムなどに適しています。ジョブの公正な処理や、順番を保持する必要がある場合に使用されます。

std::priority_queue

• 特徴: 要素が優先度順にソートされており、最も優先度の高い要素が常に先に取り出される。
• 使用時のシナリオ: スケジューリングシステム（例：オペレーティングシステムのタスクスケジューラー）、Dijkstraの最短経路アルゴリズム、ヒューリスティック探索アルゴリズム（例：A*アルゴリズム）、リアルタイムのデータ処理など、優先度が重要な場面で使用されます。

まとめ

これらのコンテナアダプタは、特定のデータ処理やアルゴリズムの要件に応じて選択されます。std::stackは後入れ先出しの操作が必要な場合、std::queueは先入れ先出しの操作が必要な場合、そしてstd::priority_queueは優先度に基づいて項目を処理する必要がある場合に適しています。

関連コンテナ

std::set

• 特徴: キーのみからなる集合で、全ての要素がユニーク（重複なし）です。要素はキーによって自動的にソートされます。
• 使用時のシナリオ: ユニークな要素のコレクションを管理し、高速な検索、挿入、削除が必要な場合に適しています。例えば、アイテムの一意性を保証するためや、ソートされたデータの集合を維持する場合などに使用されます。

std::multiset

• 特徴: std::setと似ていますが、重複する要素の挿入を許可します。こちらも要素はキーによってソートされます。
• 使用時のシナリオ: 要素の順序を保ちつつ、同じ値の要素を複数保持したい場合に適しています。統計計算やデータの分類、グルーピングが求められる場面で有効です。

std::map

• 特徴: キーと値のペアで構成される連想配列（または辞書）。各キーはユニークであり、キーに基づいて要素がソートされます。
• 使用時のシナリオ: キーを基に値を効率的に検索、更新したい場合に使用します。データベースのような構造で、キーによるアクセスが頻繁に行われる場合に最適です。例えば、ユーザIDに基づいてユーザ情報を保存・検索する場合などに利用されます。

std::multimap

• 特徴: std::mapと似ていますが、重複するキーを許可します。同じキーに対して複数の値を関連付けることが可能です。
• 使用時のシナリオ: 一つのキーに対して複数の値を持つことが必要な場合に使用します。例えば、一つの会社名に対して複数の従業員を関連付ける、または一つの出発地に対する複数の到着地を管理する場合などに適しています。

まとめ

これらの関連コンテナは、データの整理と検索を効率化するために非常に有用です。std::setやstd::mapはユニークなキーを持つデータの管理に、std::multisetやstd::multimapは同じキーを持つデータの管理に適しています。これらのコンテナは内部的にソートされているため、要素の順序に依存する操作が容易になります。

未順序化コンテナ

std::unordered_set

• 特徴: 一意の要素の集合を保持するコンテナで、内部ではハッシュテーブルを使用しています。要素間には順序関係が定義されていません。
• 使用時のシナリオ: 要素の順序が重要でない場合や、挿入、削除、検索において非常に高速な操作が求められる場合に適しています。例えば、アイテムの存在を迅速にチェックする必要がある場合などに使用されます。

std::unordered_multiset

• 特徴: 重複を許可するハッシュ集合です。std::unordered_setと同様に、要素間に順序はありません。
• 使用時のシナリオ: 要素の順序を気にせず、同じ値の要素を複数回挿入する必要がある場合に適しています。データの集計や分析などに利用されることがあります。

std::unordered_map

• 特徴: キーと値のペアを格納するハッシュマップで、各キーは一意です。要素間に順序はありません。
• 使用時のシナリオ: 頻繁に要素の挿入や削除、アクセスを行うアプリケーションで効率的なパフォーマンスを実現したい場合に適しています。例えば、インメモリのキャッシュや高速アクセスが要求されるデータ構造に利用されます。

std::unordered_multimap

• 特徴: キーの重複を許可するハッシュマップです。複数の値を同一のキーに紐づけることができます。
• 使用時のシナリオ: 一つのキーに対して複数の値を関連付ける必要がある場合に適しています。例えば、一つのトランザクションIDに対して複数の詳細な記録を保持するなどの用途で使用されます。

まとめ

未順序化コンテナは、操作の速度を最優先する場合に特に有効です。これらは要素の順序を保持しないため、順序付けが必要ないシナリオでの使用が推奨されます。また、ハッシュ関数の質に依存するため、適切なハッシュ関数の選定がパフォーマンスに大きく影響します。