A.1 Tools.h++ コレクションクラスの選択
選択チャートには、コレクションに格納するデータについての質問が含まれています。選択チャートにざっと目を通すことにより、作成するプログラムとそのデータにどの Tools.h++ コレクションが最適であるかが分かります。
A.1.1 選択チャートの使い方
選択チャートを見やすくするために、各選択肢の質問は簡潔になっています。次に、選択肢の質問について解説します。
コレクション内のデータの順序には意味がありますか?
コレクションの中には、コレクション内のデータの位置を制御できるものがあります。例えば、配列やベクトル、およびリンクリストはデータを「順序付きで」提示します。特定の順序で、または数値インデックスに基づいてデータにアクセスする必要がある場合、順序には意味があります。
重複項目を許可しますか?
コレクションの中には、コレクション内にすでに存在している項目と等しい項目を挿入できないものがあります (通常、この種のコレクションはセットと呼ばれます)。別の種類のコレクションには、複数の同一項目を保持する様々な方法があり、重複項目の挿入を許可します。Tools.h++ コレクションには、重複を調べる機構と重複項目を保持する機構の両方が備えられています。
順序付けは本質的なものですか、それとも外部的なものですか?
コレクション内のデータがそれを挿入する方法によって制御される場合は、「順序が外部的に決定される」と言います。例えば、ベクトルやリンクリストは、外部的に順序付けられています。データがコレクションによって使用されるアルゴリズムによって決定された位置に格納される場合は、順序付けは「本質的」です。例えば、格納されたベクトルやバランスツリーは本質的な順序を持ちます。
外部キーによってデータにアクセスしますか?
値とは異なるキーを基準にして値にアクセスする場合、「外部キーによってデータにアクセスする」と言います。例えば、「電話番号リスト」は、電話番号というデータを、名前の形式をとったキーに関連付けます。逆に、「委員会メンバのリスト」は、名前の形をとったデータだけになります。情報を取得するためには、キーを必要としません。
数値インデックスでデータにアクセスしますか?
配列またはベクトルに格納されているオブジェクトには、数値インデックスでアクセスします。例えば、数値インデックス「12」を用いてオブジェクトを見つけ、12
という位置にあるオブジェクトにアクセスします。
自身との比較によってデータにアクセスしますか?
明示的なインデックスやキーのいずれとも一緒に格納されていないデータは、検索データとコレクション内のデータの一致を探すことによって見つけることができます。前述した委員会メンバのリストは、この種類のデータの例です。Set や Bag は自身との比較によってアクセスするコレクションの例です。
自身との比較によってデータにアクセスする場合は、どの種類の一致基準を使用するかを知る必要があります。一致には、あるオブジェクトを別のオブジェクトと直接比較する「等値性」を基準にすることも、オブジェクトのアドレスを比較し、オブジェクトが同一であるかどうかを調べる「アイデンティティ」を基準にすることもできます。
最適のアクセス方式は、リンクノードによるものですか?
リンクノードを利用するコレクションは、通常リストと呼ばれます。リストでは、コレクションの両端にあるデータに素早くアクセスでき、コレクションの真ん中にデータを効率よく挿入することができます。ただし、コレクションの真ん中にあるデータに頻繁にアクセスする必要がある場合、リストは他のコレクションに比べてそれほど効率的ではありません。
頻繁にアクセスするデータがコレクションの両端にありますか?
処理しなければならないデータの量が分からない場合は頻繁にありますが、処理するほとんどのデータは、コレクションの最も新しいデータか、最も古いデータです。最後に追加されたデータを処理するのに最も効率的なのは、「後入れ先出し」方式を持つコレクションです。後入れ先出し (LIFO) のコンテナは「スタック」です。先入れ先出し (FIFO) 方式でデータを処理するコレクションは、「待ち行列」と呼ばれます。最新データと最古データの両方に効率的にアクセスできるコレクションは、「両頭列」あるいは Deque (Double Ended Queue) と呼ばれます。
リンクリストの場合－データにリストの一方からだけ、または両方からアクセスする必要がありますか?
一重リンクリストはサイズが小さいのですが、リストの「正面」からだけアクセスできます。二重リンクリストは、より柔軟性のあるアクセス方式を持ちますが、格納されている各オブジェクトごとに追加のポインタを必要とします。
数値インデックスでアクセスするコレクションの場合－コレクションを自動的にサイズ変更する必要がありますか?
コレクションに格納する項目の最大数があらかじめ分かっている場合は、固定サイズのコレクションを選択する方がより効率的に挿入と削除を行うことができます。反対に、ほとんど無制限に拡張する必要がある場合は、現在格納しているデータ量に合わせて自動的にサイズを調整するコレクションを選択するべきです。
A.1.2 その他の選択基準
どのコレクションを選択するかは、これまでの経験や直観を含め、数多くの要素に依存します。選択チャートの質問の他に、どのコレクションを選択するかを決める上で次の質問も考慮してください。
複数コレクションで単一オブジェクトを保持する必要がありますか?
「はい」の場合は、ポインタベースのコレクションを使用します。
コピーするのに時間のかかるオブジェクトを収集しますか?
「はい」の場合は、ポインタベースのコレクションを使用します。
ポインタベースのコレクションを使用しなければならない理由がありますか?
「いいえ」の場合は、値ベースのコレクションを使用します。
コレクション内のオブジェクトの順序を外部的に制御しますか?
「はい」の場合は、ベクトルやリストなどのシーケンスコレクションを使用します。
挿入後、コレクション内の項目が変更可能である必要がありますか?
「はい」の場合は、シーケンスコレクションまたはマッピング (辞書) コレクションを使用します。マップと辞書は、不変のキーを持ちますが、値は変更可能です。
コレクションがオブジェクトの比較を基準に独自の順序を保持するようにしますか?
「はい」の場合は、セット、マップ、あるいはソート済みコレクションを使用します。
数値インデックスによってコレクション内のオブジェクトにアクセスしますか?
「はい」の場合は、シーケンスコレクションまたはソート済みコレクションを使用します。
非数値キーによって値を検索する必要がありますか?
「はい」の場合は、マップまたは辞書を使用します。
比較するオブジェクトを指定して、コレクション内のオブジェクトにアクセスしますか?
「はい」の場合は、セット、マップ、あるいはハッシュベースのコレクションを使用します。
意味のある順序付けをなしで済まし、その代わりメモリをキーによる定時間のルックアップに使いますか?
「はい」の場合は、ハッシュベースのコレクションを使用します。
必要に応じて拡張または縮小するコレクションで高速のルックアップと挿入が必要ですか?
「はい」の場合は、B-ツリー、あるいは新しい標準 C++ ライブラリを基にした連想コンテナを使用します。
メモリにデータすべてを読み込まずに、アクセスする必要がありますか?
RWBTreeOnDisk または RWTValVirtualArray を使用します。
