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

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

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

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

機能と特性

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

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

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

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

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

種類

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

単一値コンテナは各オブジェクトを個別に保存します。オブジェクトには、言語のループ構造 (例: for ループ) またはイテレータを使用して直接アクセスできます。

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

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

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

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

グラフィックコンテナ

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

静的型付け言語では

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

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

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

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

参照

参考文献

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

外部リンク

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

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

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

[Budd1997-3] Budd, Timothy (1997). オブジェクト指向プログラミング入門 (第 2 版). マサチューセッツ州レディング: Addison-Wesley. ISBN 0-201-82419-1. OCLC 34788238.