コレクションの型
Core Foundation の主要なコレクション型：配列、辞書、セット、バッグ、及びツリーは共通の特徴を持っていますが、それぞれに含まれるデータ要素を編成する明確な方法があり、場合によっては含まれる要素を制限します。
配列
不透明型 CFArray のオブジェクトである Core Foundation の配列は、順序付けられたコンパクトな値のコンテナです。値は連続した順序であり、これらの値にアクセスするためのキーはそれらの インデックス で、シーケンス内の値の位置を指定する整数です。インデックスの範囲は 0 から n-1 までです。ここで、n は配列内の値の数です。インデックス 0 は配列の最初の値を示します。配列は番号付きスロットと考えることができます。
配列は、項目がいくつかのスキーム (たとえば優先順位) にしたがってランク付けされたリスト、または配列内の値とメニューなどのリスト型コントロールの項目間のマッピングがある場合など、シーケンシャルな位置が重要なプログラムの状況に最適です。ただし、配列を汎用コンテナとして使用して、収集された値を保持および反復することができます。
可変配列では、値を削除しても配列にギャップが残らないため、配列はコンパクトと言われています。数値が大きいほど、インデックスは 1 ずつ減少します。値を挿入すると、後続のすべての要素のキーが 1 ずつ増加します。この動作により、特定のオブジェクトにアクセスするためのキーは、値を配列に挿入してから、配列から削除する度に変わります。しかし、有効なインデックスのセットは常に 0 と n-1 の間です。
配列内の値に対するアクセス時間は、全ての実装、現在および将来の最悪の O(log N) になることが保証されていますが、多くの場合、O(1) (つまり一定の時間) になります。線形検索演算も同様に O(N*log N) の最悪の複雑さを有するが、通常は境界がより堅くなる。挿入操作または削除操作は、典型的には配列内のオブジェクトの数において線形であるが、最悪の場合には明らかに O(N*log N) であることがある。パフォーマンスのために配列内に好ましい位置はありません。たとえば、インデックスが小さい値にアクセスしたり、インデックスが高い値を挿入または削除したりする時に速くなる必要はありません。
辞書
辞書 (CFDictionary 型のオブジェクト) は、その値にアクセスするためのキーがプログラムで定義された一切れの任意のデータ (またはデータへのポインタ) であるハッシュベースのコレクションです。キーは通常は文字列 (または、Core Foundation の CFString オブジェクト) ですが、ポインタのサイズに合うものであれば何でもかまいません。整数、Core Foundation オブジェクトへの参照、データ構造体へのポインタ (おそらくそうではないかもしれない) でもかまわない。辞書のキーは、他のコレクションオブジェクトのキーとは異なり、概念上、値とともにコレクションにも含まれます。辞書は、ユーザーインターフェイスのテキストフィールドから抽出された値など、ラベル付け可能なデータの保持および整理に主に役立ちます。
Core Foundation では、辞書の特定の値にアクセスするために使用されるキーは、値が辞書に追加されたり辞書から削除されるものと同じままであるという点で、特定のキーに関連付けられた値が置き換えられるか 除去されると言う点で配列と異なります。配列では、特定の値を取得するために使用されるキー (つまり、インデックス) は、値が配列に追加され、または配列から削除されるごとに変化する可能性があります。また、配列とは異なり、辞書はその値を任意の順序で入れません。後で値を取得できるようにするには、キーと値のペアのキーを一定にする (または定数として扱う) 必要があります。値を辞書に入れるのに使用された後にキーが変更された場合、その値は回収できない可能性があります。辞書のキーはセットを形成します。換言すれば、キーは辞書内で一意であることが保証されます。
CFDictionary 型のカスタマイズでは、値の格納にハッシュとハッシュテーブルを使用しない場合がありますが、キーにはハッシュコードを生成する関数と、それらのハッシュコードに基づいて 2 つのキーが等しいかどうかをテストする関数の両方必要です。これら 2 つの関数は共に変態ではないままでなければなりません：
if equal(X,Y) then
hash(X) == hash(Y)
この論理の逆は一般的に真ではありませんが、待遇はブール論理によって必要とされます。
if hash(X) != hash(Y),
then !equal(X,Y)
hash と equal キーの呼び出し関数が NULL の場合、キーはポインタサイズの整数として使用され、ポインタの等価性が使用されます。最高のパフォーマンスを得るには、キーセットの十分に分散されたハッシュコードを計算する hash 呼び出し関数を提供するようにしてください。
CFDictionary オブジェクト内の値へのアクセス時間は、すべての実装で最悪の O(log N) になることが保証されていますが、しばしば O(1) (一定時間) です。挿入操作または削除操作は、通常は一定時間内に行われますが、最悪の場合は O(N*log N) になります。直接キーにアクセスするよりも、キーを通して値にアクセスする方が高速です。辞書は、同じ数の値を持つ配列よりも大幅に多くのメモリを使用する傾向があります。
セットとバッグ
セットとバッグはコレクションの関連型です。それらが共通しているのは、コレクション内の値にアクセスするための鍵は値そのものであるということです。セットとバッグの違いは、値のメンバーシップの "ルール" です。セットでは、コレクション内に値がすでに存在する場合、同一の値をセットに追加することはできません。逆に、バッグが既にその値を保持していても、バッグに任意の値を追加できます。
この "ユニークな" 機能 (またはその欠如) には、多くの用途があります。たとえば、プログラムがインターネットを検索していて、すべての適格な URL を保持したいが、重複しないようにしたいとします。セットはこの目的のためにうまく動作します。バッグは、統計的サンプリングに有用かも知れません。すべての収集された値をその中に入れることができ、データの収集が終了した後で、各値の頻度について照会することができます。
キー値と含まれる値の等価性は、定義できる呼び出し関数によって決まります。この関数は、等しいかどうかの基準を設定できます。たとえば、セットまたはバッグの値は、顧客レコードを表すカスタム構造体とすることができます。両方の構造体のアカウントー数フィールドの値が同じであれば、外部 (キー) 値と含まれている値が同じであると判断することができます。(コレクションと同じように、Core Foundation オブジェクトがセットまたはバッグの値である場合は、デフォルトの呼び出し関数を指定することもできます)。セットの場合 (辞書と同じように)、equal 呼び出し関数はコレクションに合法的にどの値が追加できるかを決定します。
樹 (Trees)
樹 (CFTree 型のオブジェクト) を使用すると、階層構造のノード (ファイルとディレクトリを持つファイルシステムなど) を表すことができます。この樹構造の各ノードは樹オブジェクトであり、そのオブジェクトは他の樹オブジェクトとの関係を持っています。概念的には、CFTree 型のオブジェクトは、他の Core Foundation のコレクションオブジェクトと大きく異なります。配列、辞書、セット、及びバッグは (通常) 複数の値のコンテナですが、樹オブジェクトはデータと 1 対 1 の関係にあります。つまり、樹オブジェクトは 1 つのポインタサイズ値に関連付けられます (しかし、その値は、例えば、複数のメンバーを持つ構造体へのポインタやコレクションオブジェクトへの参照などでも構いません)。しかし、樹オブジェクトの本質的な特徴は、それぞれが独自のデータチャンクを持つ複数のサブツリーへの参照を保持し、その意味では樹オブジェクトの相互リンクされたグループ (樹構造) はコレクションと見なされるということです。
親子の枠組みは、樹オブジェクトを理解するのに便利です。上記のように、これらのオブジェクトはお互いに階層関係にあり、階層の最上部には "ルート" の樹があります。この樹は他の樹のサブツリーでは決してありません。つまり、親の樹はありませんが、1 つ以上のサブツリーまたは子の樹があります。これらの子の樹は、他の樹の親になることができます。
樹オブジェクトには、その関係を管理するはっきりとした規則があります。樹に子供たちを追加すると、親はそれらを保持しますが、子供たちは親を保持しません。さらに、樹にはその子の樹の 1 つとして、それ自身が子である子の樹を持たないこともあります。樹とそのサブツリーの横断には循環参照は許されません。同じ親の樹を持つ 2 つの樹は、お互いの "兄弟 (sibling)" と呼ばれます。概念的には、兄弟はリンクされたリストのように順番に並んでいます。樹の子に対して実行される操作は、直接の子孫にのみ適用されます。言い換えれば、それらの子どものサブツリーには再帰的に影響を与えません。
他のコレクションオブジェクトとは異なり、構造的には、これらの値は CFTree 型のみであるため、樹は含まれた値で動作する呼び出し関数を必要としません。しかし、有用であるためには、樹オブジェクトはそれに関連する何らかのデータを持たなければならず、このデータは他の樹との関係を決定することができます。Core Foundation の樹オブジェクトを作成するときは、樹の "コンテキスト" を定義しなければなりません。コンテキストは、関連したデータを識別し、データの保持、解放、比較、および記述など、データに必要な操作を実行するために呼び出される呼び出し関数を定義します。
前の章 次の章