Tools.h++ 7.0 ユーザーズガイド: 9 - コレクションクラス

Copyright 1999 Rogue Wave Software
Copyright 1999 Sun Microsystems, Inc.

# コレクションクラス | # 9 |

Tools.h++ クラスライブラリには、3 種類のコレクションクラスが含まれます。

- テンプレートベースのコレクションクラス。コレクションクラステンプレート、あるいは、短縮してテンプレートと呼びます。
- 総称コレクションクラス。『プログラミング言語 C++』(1986) の 7.3.5 節にならってモデル化されたもの。
- Smalltalk 式コレクションクラス。

これらは、実装方法がまるで違ってはいるものの、実質的な機能やユーザーインタフェース (メンバー関数名など) はよく似ています。

次の節では、各コレクションクラスについて順番に説明します。この章では、コレクションクラスの基本的な概念を解説し、本書や C++ の資料で使用される用語のいくつかについて説明します。

## コレクションクラスの格納方法

コレクションクラス (短縮してコレクションとも呼ぶ) の一般的な目的は、オブジェクトを格納したり、取り出したりすることです。実際、コレクションクラスは、オブジェクトの格納方法によって分類することができます。値にもとづくコレクションでは、オブジェクトそのものを確認します。参照にもとづくコレクションでは、オブジェクトへのポインタか参照を格納します。これらの 2 つの方法の違いは、コレクションクラスの機能のいくつかを Tools.h++ でどのように使用するかに影響を与えます。

値にもとづくコレクションクラスは理解しやすく、操作も簡単です。たとえば、整数や `double` 型のリンクリスト、あるいは `short` 型のハッシュテーブルを作成することができます。格納される型は、RWCStrings のように、もっと複雑になるかもしれません。重要な点は、それらが他のオブジェクトへのポインタを含むことがあっても、値と同様に働くということです。オブジェクトが値にもとづくコレクションクラスに挿入されると、コピーが作成されます。この手続きは、C 言語の関数呼び出しにおける値渡しの方法に似ています。

参照にもとづくコレクションクラスでは、他のオブジェクトへのポインタを格納したり、取り出したりします。たとえば、整数や `double` 型へのポインタのリンクリスト、あるいは RWCStrings へのポインタのハッシュテーブルを作成することができます。

次に、値にもとづく手続きと参照にもとづく手続きの違いを示す 2 つのコードを示します。

値にもとづく手続きの例 | 参照にもとづく手続きの例
--- | ---
    /* RWCStringsのベクトル */
    RWTValOrderedVector<RWCString> v;
    RWCString s("A string");
    v.insert(s);
    /* RWCStrings へのポインタのベクトル */
    RWTPtrOrderedVector<RWCString> v;
    RWCString* p = new RWCString("A string");
    v.insert(p);

どちらのコードでも、RWCString を ベクトル `v` に挿入しています。最初の例では、`s` が「A string」を含む RWCString オブジェクトです。文 `v.insert(s)` は、`s` の値をベクトルにコピーします。ベクトル内のオブジェクトは、明確であり、元のオブジェクト `s` から分離されています。2 番目の例では、`p` が RWCString オブジェクトへのポインタです。手続き `v.insert(p)` が完了すると、`v` の新しい要素は同じ RWCString オブジェクトを `p` として参照します。

### メモリー管理に関する注意

参照にもとづくコレクションは、ポインタが小さく処理にコストがかからないため、非常に効率的です。ただし、参照にもとづくコレクションを使用する場合は、メモリー管理に常に注意する必要があります。つまり、実際のオブジェクトそのものの作成、保守、破棄に気を付けなければなりません。同じオブジェクトに対して 2 つのポインタを作成して、そのオブジェクトを早々に削除した場合、2 番目のポインタは何も指さないことになります。同様に、参照にもとづくコレクションに `NULL` ポインタを挿入してはなりません。これは、コレクションが、含まれる値を間接参照する方式を持つためです。

注意すべき事項が増えたからといって、必要なときに、参照にもとづくコレクションの使用を避けることはしないでください。Tools.h++ クラスには便利なメンバー関数があります。またほとんどの場合、含まれるオブジェクトの所有権は明白です。パフォーマンスとサイズを改善する必要がある場合は、参照にもとづくコレクションを選択してください。ポインタのサイズはすべて同じであるため、ほとんどのコードを再使用することができます。また、オブジェクトを含めるのではなく (たとえば、ダイアログリスト内の指定のオブジェクトセット)、単にポイントしたい場合にも、参照にもとづくコレクションを選択してください。最後に、ある種の異種オブジェクト混在コレクションの場合は、参照にもとづくコレクションがおそらく唯一の有効な方法でしょう。

## コレクションクラスのコピー

クラスのコピーは、ソフトウェアの一般的な手順です。この手順は、コピーコンストラクタが適用されるか、あるいはプログラムの中でコピーが必要な場合には必ず行われます。値にもとづくコレクションクラスのコピーは簡単です。しかし、参照にもとづくクラスをコピーする場合は、特殊な考慮事項があります。次のこの問題について説明します。

### 参照にもとづくコレクションクラスのコピー

参照にもとづくコレクションクラス (つまり、他のオブジェクトを参照するクラス) のコピーを作成する場合に起こることは、シャローコピーとディープコピーのどちらの方法を選択かによって異なります。

1. オブジェクトのシャローコピーとは、元のオブジェクトと同じインスタンス変数を持つ新しいオブジェクトのことです。たとえば Set のシャローコピーは、元の Set と同じメンバーを持ちます。新しい Set は元の Set と (ポインタを通じて) オブジェクトを共有します。シャローコピーのことを、参照の意味を使用する方法ということがあります。

> 注 - Rogue Wave の参照にもとづく全コレクションクラスのコピーコンストラクタは、シャローコピーを作成します。

2. オブジェクトのディープコピーは、まったく新しいインスタンス変数を持つコピーを作ります。この新しいオブジェクトは、元のオブジェクトとオブジェクトを共有しません。たとえば Set のディープコピーは、新しいセットを作るだけでなく、そこに挿入される項目も元の項目のコピーとなります。真のディープコピーでは、このコピー操作が再帰的に行われます。ディープコピーのことを、値の意味を使用する方法ということがあります。

参照にもとづくコレクションクラスのいくつかは、完全に新しいインスタンス変数を持つ新しいオブジェクトを返す `copy()` メンバー関数を持つことに注意してください。このコピーは、再帰的には実行されません。また、新しいインスタンス変数は、古いインスタンス変数のシャローコピーです。

次に、シャローコピーとディープコピーの違いを図で表した例を示します。Bag という、複写が許可され、順序付けされていない、オブジェクトのコレクションクラスを想像してください。コピー前は次のように見えます。

Bag のシャローコピーとディープコピーを作成すると、次の結果が得られます。

ディープコピーでは、Bag そのものだけでなく、その内部にあるオブジェクトすべてが再帰的にコピーされることがわかります。

どのコピー方式を選択するかが重要です。たとえば、シャローコピーではコピー内容が少ないため便利で迅速に処理を行うことができますが、2 つのコレクションが同時に同じオブジェクトを参照することになるため、注意が必要です。一方のコレクションの全項目を削除した場合、他方のコレクションが無意味なものを指すことになります。

オブジェクトをディスクに書き込むときの方式についても考慮する必要があります。あるオブジェクトに、同じオブジェクトに対するポインタや参照が複数含まれている場合、復元時にこの持続性が保存されている必要があります。RWCollectable から継承するクラスは、オブジェクトの持続性を確実に維持するアルゴリズムを継承します。詳細については、第 13 章「持続性」を参照してください。

### 値にもとづくコレクションクラスのコピー

参照にもとづくコレクションをコピーした結果を、値にもとづくコレクションと対比してみます。次のクラスを想定してください。

RWTValOrderedVector<RWCString>

つまり、RWCString についてインスタンス化された順序付きベクトルテンプレートです。この場合、各文字列はコレクション内に組み込まれます。コレクションクラスのコピーが作成されると、コレクションクラスそのものだけでなく、その中のオブジェクトもコピーされます。この結果、収集されたオブジェクトのまったく新しいコピーができ上がります。

## コレクション内のオブジェクトの検索

コレクションクラスの主な目的は、オブジェクトの格納と検索 (取り出し) であると説明しました。オブジェクトをどのように検索するかは、その特性によって決まります。ユーザーが作成するすべてのオブジェクトは、次の 3 つの特性を持ちます。

1. 型：たとえば、RWCString クラスや `double` 型。C++ では、オブジェクトの型は作成時に設定されます。これは、変更することはできません。

2. 状態：例えば、文字列の値。オブジェクトの状態は、そのオブジェクトのすべてのインスタンス変数または属性の値によって決まります。これは、変更することができます。

3. 同一性：オブジェクトを常に一意的に定義するもの。言語によって、オブジェクトの同一性を設定する方法は異なります。C++ では、常にオブジェクトのアドレスを使用します。各オブジェクトには、アドレスが 1 つだけ関連付けられます。継承があるため、この逆は必ずしも真ではありません。一般に、ある継承階層内で指定するオブジェクトを明確に特定するには、アドレスと型1 の両方が必要です。

### 検索方法

オブジェクトの特性によって、オブジェクトを検索する方法には 2 つの一般的な方法があります。コレクションクラスの中には、この両方ともサポートできるもの、どちらか一方しかサポートできないものがあります。どちらの方法を指定したかを、必ず覚えておいてください。次の 2 つの方法があります。

1. 特定の状態を持つオブジェクトを見つけます。たとえば、2 つの文字列が同じ値を持つかどうかを調べます。これは、文献の中で 2 つのオブジェクトが "`isEqual`" であるか調べる、"等値" である、"等しいか比較する"、同じ "値" を持つ、"= =" 演算子が真か調べる、などと表現されます。ここでは、2 つのオブジェクトが等しい ("`isEqual`") か調べる、という表現を使用することにします。一般に、等値を調べるための適切なインスタンス変数を見つけるには、2 つのオブジェクトの型 (継承の場合はサブタイプ) について一定の知識が必要です 2 。

2. 特定のオブジェクト (つまり、同一性を持つもの) を見つけます。これは、文献の中では、2 つのオブジェクトが "`isSame`" か調べる、同一性を持つ、"= =" 演算子が真かテストする、などと表現されます。ここでは、2 つのオブジェクトが同一性を持つ、と表現することにします。なお、値にもとづくコレクションクラスは挿入されたオブジェクトのコピーを作るので、値にもとづくコレクションクラスの中で、同一性を持つオブジェクトを見つけることは意味がありません。

C++ で、同一性を (つまり、2 つのオブジェクトが実際に同じオブジェクトかどうか) 調べるためには、同じアドレスを持っているかどうかを調べます。C++ では、多重継承があるため、基底クラスとそれに関連する派生クラスのアドレスが同じでないこともあります。このため、同一性を調べるのに 2 つのポインタ (つまり 2 つのアドレス) を比較する場合、2 つのポインタの型が同じでなければなりません。

Smalltalk は、演算子 = を使用して等値性をテストし、演算子 `==` を使用して同一性をテストします。ただし C++ では、演算子 = は代入に、`==` はいくつかの種類の値の等値性に固く結びついています。ここでは、C++ の方式をとりました。Rogue Wave では、演算子 `==` は一般に、2 つのクラスに適用された場合の値の等値性 (`isEqual`) のテストと、2 つのポインタに適用された場合の同一性のテストを示します。

等値性か同一性のどちらをテストするかは、各自の問題によって決まります。次に、どちらを選択するかが明らかにわかる例をいくつか示します。

等値性のテストが必要な例では、メーリングリストを保守する場合を想定してください。ある人の名前から、その人のアドレスを探したいとします。この場合は、手元にある名前に等しい名前を検索します。RWHashDictionary が適切です。つまり、名前がこの辞書へのキーであり、アドレスがその値になります。

次の例では、同一性をテストします。ハイパーテキストアプリケーションを作成していて、特定のグラフィックがどの文書にあるかを知る必要があると想定します。これは、グラフィックとそれに対応する文書の RWHashDictionary を保持すればわかります。ただし、この場合は、特定のグラフィックがどの文書で使われているかを知りたいため、RWIdentityDistionary が必要です。ここでは、グラフィックがキーとして、文書が値として働きます。

ディスクキャッシュを維持する場合は、特定のオブジェクトがメモリーに存在するかどうかを知る必要があると想定します。この場合は、RWIdentitySet が適切です。オブジェクトを与えられれば、それがメモリーに存在するかどうかを確認することができます。これも同一性テストの一種です。

## コレクションクラスの反復子

コレクションクラスの多くは、関連する反復子を持っています。反復子の利点は、それが内部状態を維持するということです。これによって、次の 2 つの重要な利点が生まれます。

- 同じコレクションクラスから複数の反復子を作成できる
- 単一のスイープですべての項目を調査する必要がなくなる

反復子は、次の例に示すように、常にそのコレクションクラス自体から作成されます。

      RWBinaryTree bt;
      .
      .
      .
      RWBinaryTreeIterator bti(bt);

生成直後 (あるいは `reset()` の呼び出し直後)、反復子の状態は未定義です。現在の状態 (すなわち、位置) を使用する前に、それを進めるか位置付ける必要があります。

従来の Tools.h++ 反復子、つまりコレクションクラスに関連する明確なクラスとして宣言された反復子では、規則は「進んでから戻す」です3。ただし、標準 C++ ライブラリによって実装されたクラスから直接獲得された反復子は異なります。コンテナクラスの標準を守って、これらは原則に従います。`begin()` や `end()` メソッドを使用する反復子、あるいは反復子を返すアルゴリズムを獲得すると、「標準ライブラリ」反復子4が得られます。標準ライブラリ反復子は、そのコレクションの `end()` 反復子と必ず比較して、それがコンテナ内の項目を参照するかどうかを確かめる必要があります。

### 従来の Tools.h++ 反復子

従来の Tools.h++ 反復子には、多数の固有な機能があります。

作成直後 (あるいは `reset()` の呼び出し直後)、反復子の状態が未定義であることは、すでに説明したとおりです。また、反復子が有効である間に、オブジェクトを追加または削除することによってコレクションクラス5を直接変更しても、反復子の状態は未定義になります。この時点で反復子を使用すると、予期せぬ結果を生むことがあります。この場合は、メンバー関数 `reset()` を使用して、反復子を作成直後のように再起動する必要があります。

反復子は、どの時点においても、コレクションクラスの中にあるオブジェクトをマークします。これを現在のオブジェクトと考えます。このマークを移動するための方法は何通りもあります。たとえば、ほとんどの場合は、メンバー関数 `operator()` を使用します。Tools.h++ では、これは常に次のオブジェクトに進んでから、関連するコレクションクラスが値にもとづくか参照にもとづくかによって、`TRUE` か次のオブジェクトへのポインタのどちらかを返すように設計されています。また、コレクションクラスの最後に達したときには、必ず `FALSE` (つまりゼロ) を返します。したがって、反復子を使用するための、簡単で標準的な形式は次のようになります。

      RWSlistCollectable list;
      .
      .
      .
      RWSlistCollectableIterator iterator(list);
      RWCollectable* next;
      while (next = iterator()) {
        .
        .                                               // (next を使う)
        .
      }

代わりに、接頭インクリメント演算子 (`++X`) を使用することもできます。反復子によっては、マークを操作するための他のメンバー関数 (`findNext()`、`removeNext()` など) を備えているものもあります。

メンバー関数 `key()` は常に現在のオブジェクトもしくは現在のオブジェクトへのポインタを返します。どちらが返される、または戻されるかは、対応するコレクションが値にもとづくものか、参照にもとづくものかによって決まります。

ほとんどのコレクションでは、すべてのメンバーにアクセスする場合、メンバー関数 `apply()` を使用すると、反復子を使用するよりも処理がはるかに速くなります。ソートされたコレクションの場合は通常、ツリーを調査する必要があります。これは、ノードの親がスタック上に格納されていなければならないからです。関数 `apply()` はプログラムのスタックを使用しますが、ソートされたコレクションの反復子はそれ自身のスタックを保守しなければなりません。そのため、関数 `apply()` を使用した方が処理ははるかに速くなります。

1 多重継承のため、ユーザーがどのオブジェクトを指しているのかを明らかにするには、オブジェクトの型だけでなく継承ツリーの中でのオブジェクトの位置も知る必要があります。

2 Rogue Wave のコレクションクラスでは、一般的な等価テストを行うことができます。2 つのオブジェクトが "等しい" ということの意味を定義するのはユーザー自身です。つまり、2 つのオブジェクトのビット単位の比較は行われません。どちらも哺乳動物であるという理由でパンダがシカと同じだというように、"等価" を定義することもできるわけです。

3 これは『プログラミング言語 C++』(1986) の 7.3.2 節にもとづいてパターン化されています。

4 ANSI 標準草案では、コンテナ反復子を詳細にわたって説明しています。簡単に説明すると、このような反復子は、「最初の要素」から「最後の要素の 1 つ後」までの範囲内で有効です。これらは、メソッド `begin()` と `end()` によってそれぞれ返されます。ただし、「end」反復子はコンテナ内の項目を参照せず、標識として働きます。

5 反復子そのものを介してコレクションを変更することは可能です。