コンテナ（抽象データ型）

コンピュータサイエンスにおいて、コンテナとはクラスまたはデータ構造^{[ 1 ]}^{[ 2 ]}であり、そのインスタンスは他のオブジェクトの集合です。言い換えれば、コンテナは特定のアクセスルールに従ってオブジェクトを整理された方法で格納します。

コンテナのサイズは、コンテナに含まれるオブジェクト（要素）の数によって決まります。様々なコンテナ型の基盤となる（継承された）実装は、サイズ、複雑さ、言語の種類が異なる場合がありますが、多くの場合、特定のシナリオに適した実装を柔軟に選択できます。

コンテナデータ構造は、多くの種類のプログラミング言語で一般的に使用されます。

機能と特性

コンテナは次の 3 つのプロパティによって特徴付けられます。

アクセスとは、コンテナ内のオブジェクトにアクセスする方法です。配列の場合、アクセスは配列のインデックスで行われます。スタックの場合、アクセスはLIFO（後入れ先出し）順序で行われ、キューの場合、アクセスはFIFO（先入れ先出し）順序で行われます。
ストレージ、つまりコンテナのオブジェクトを保存する方法です。
トラバーサル、つまりコンテナのオブジェクトをトラバースする方法です。

コンテナクラスは、次の操作を実行するために CRUDのようなメソッドを実装することが期待されています。

空のコンテナ（コンストラクター）を作成します。
コンテナにオブジェクトを挿入します。
コンテナからオブジェクトを削除します。
コンテナ内のすべてのオブジェクトを削除します（クリア）。
コンテナ内のオブジェクトにアクセスします。
コンテナ内のオブジェクトの数 (カウント) にアクセスします。

コンテナは、イテレータと組み合わせて実装されることもあります。

種類

コンテナーは、単一値コンテナーまたは連想コンテナーのいずれかに分類できます。

単一値コンテナは各オブジェクトを独立して格納します。オブジェクトには直接アクセスすることも、言語のループ構造（例：for ループ）やイテレータを使ってアクセスすることもできます。

連想コンテナは、キーと値のペアで構成される連想配列、マップ、または辞書を使用します。各キーはコンテナ内で最大1回出現します。キーは、コンテナ内に値（オブジェクト）が格納されている場合、その値を見つけるために使用されます。連想コンテナは、プログラミング言語でクラステンプレートとして使用されます。

コンテナ抽象データ型には次のものがあります。

FIFOキュー
LIFOスタック
優先キュー
ルックアップテーブル（LUT）
キー関連データ構造
- 値または特定のプロパティによってオブジェクトを含み、インデックスを付けるセット。
- マップは、各キーに検索用の「値」を関連付けます

これらの抽象型を実装するために使用される一般的なデータ構造は次のとおりです。

グラフィックコンテナ

ウィジェットツールキットは、ウィンドウやパネルなどの他のウィジェットをグループ化するための特別なウィジェットであるコンテナも使用します。コンテナはグラフィカルなプロパティ以外にも、コンテナクラスと同様の動作を持ちます。つまり、子ウィジェットのリストを保持し、子ウィジェット間でウィジェットを追加、削除、または取得することができます。

静的型付け言語では

コンテナ抽象化は、その型システムに関係なく、事実上あらゆるプログラミング言語で記述できます。^{[ 3 ]}^：273ただし、厳密に型付けされたオブジェクト指向プログラミング言語では、開発者が再利用可能な同種のコンテナを記述するのはやや複雑になる可能性があります。

要素の種類によって異なるため、すべての要素の種類ごとにコンテナのコレクションを作成して保持するという面倒な作業が発生します。^{[ 3 ]}^：274–276

多くの要素型（例えば整数や浮動小数点数）は、占有するメモリサイズや意味的な意味の都合上、本質的に互いに互換性がなく、そのため異なるコンテナが必要となる（もちろん、相互に互換性があったり変換可能な場合は除く）。^{[ 3 ]}^：274–276現代のプログラミング言語は、この問題を解決するための様々なアプローチを提供している。^{[ 3 ]}^：274–281

ユニバーサルベーシックタイプ: 他の任意のクラスによって普遍的に割り当て可能な型 (例: ルートオブジェクトクラス)。
ダウンキャスティング;
クラス置換: 上記の 3 つのアプローチは、弱く型付けされた言語に使用されます。これらは通常、型によって共有される継承とポリモーフィズムを意味します。
ユニオン型（C/C++言語）: 異なるデータサイズの型を格納できます。ただし、取得時にユニオンにどの型が格納されているかを保証することは難しいため、慎重に従う必要があります。
型変換
テンプレートまたはジェネリック: 再利用性と型安全性を確保します。逆継承と考えることもできます。ただし、このアプローチではテンプレートの特殊化を実装する必要がある可能性があり、型によってメソッドが異なるため、時間のかかるプロセスになると言われています。^{[ 3 ]}^{: 281}

参照

参考文献

^ Paul E. Black (編)、「アルゴリズムとデータ構造辞書」のデータ構造の項目。米国国立標準技術研究所、2004年12月15日。2011年10月4日にアクセス。
^ブリタニカ百科事典（2009年）のオンラインエントリのエントリデータ構造。2011年10月4日にアクセス。
^ ^a ^b ^c ^d ^eティモシー・バッド (1997).オブジェクト指向プログラミング入門（第2版）. マサチューセッツ州レディング: アディソン・ウェスレー. ISBN 0-201-82419-1. OCLC 34788238 .

外部リンク

コンテナデータ構造の宣言と初期化

[1] Paul E. Black (編)、「アルゴリズムとデータ構造辞書」のデータ構造の項目。米国国立標準技術研究所、2004年12月15日。2011年10月4日にアクセス。

[2] ブリタニカ百科事典（2009年）のオンラインエントリのエントリデータ構造。2011年10月4日にアクセス。

[Budd1997-3] ティモシー・バッド (1997).オブジェクト指向プログラミング入門（第2版）. マサチューセッツ州レディング: アディソン・ウェスレー. ISBN 0-201-82419-1. OCLC 34788238 .

[ 1 ]

[ 2 ]

[ 3 ]