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

Smalltalk 式コレクションクラス

12

これらのコレクションクラスには、2、3 の短所があります。つまり、動作がやや遅くなり、型保証が完全ではなく、オブジェクトが多少大きくなります。しかし、これらのクラスの能力とその明確なプログラミングインタフェースは、このような短所を補ってあまりあるものです。中でも、Smalltalk 式コレクションクラスは、異種コレクションと多相持続性に適しています。

Tools.h++ の Smalltalk 式クラスの多くには、対応する Smalltalk 名か総称名のどれかに対する typedef があります。この typedef は、プリプロセッサマクロ RW_STD_TYPEDEFS を定義することによって有効になります。typedef は自由に使用できますが、コードを保守しやすくするためには、実際のクラス名を使用するようお勧めします。

RWCollectable
    RWCollection (抽象基底クラス)
        RWBinaryTree
        RWBTree
            RWBTreeDictionary
        RWBag
        RWSequenceable (抽象基底クラス)
            RWDlistCollectables (二重リンクリスト)
            RWOrdered
                RWSortedVector
            RWSlistCollectables (一重リンクリスト)
                RWSlistCollectablesQueue
                RWSlistCollectablesStack
        RWHashTable
            RWSet
                RWIdentitySet
                RWHashDictionary
                    RWIdentityDictionary

そこに挿入されるオブジェクトは、仮想関数 compareto() によって返される相対値にもとづいた順序で格納されます (337 ページの「仮想関数の定義を追加する」を参照してください)。次にコードを示します。

#define RW_STD_TYPEDEFS 1 //1 #include <rw/bintree.h> #include <rw/collstr.h> //2 #include <rw/rstream.h> main(){ // 空の SortedCollection を作成する SortedCollection sc; //3 // RWCollectableString をいくつか挿入する sc.insert(new RWCollectableString("George")); // 4 sc.insert(new RWCollectableString("Mary")); // 5 sc.insert(new RWCollectableString("Bill")); // 6 sc.insert(new RWCollectableString("Throkmorton")); // 7 // コレクションの中を反復する すべてのメンバーを出力する RWCollectableString* str; // 8 SortedCollectionIterator sci(sc); // 9 while( str = (RWCollectableString*)sci() ) // 10 cout << *str << endl; // 11 sc.clearAndDestroy(); return 0; }

プログラム出力

Bill George Mary Throkmorton

このプログラムは実行時に 4 つの収集済み文字列を "順序正しく" 出力します。クラス RWCollectableString の場合、これは辞書式順序を意味します。

バッグ、セット、ハッシュテーブル

クラス RWBag は RWHashTable に似ていますが、同じ値を持つ複数のオブジェクトの出現回数を数えるという点が異なります。つまり、最初の出現のみが保持され、2 番目以降は単に "出現" 回数を増加させるだけです。このクラスは、挿入されるオブジェクトをキーとし、出現回数を値とするような辞書として実装されます。これは Smalltalk における "Bag" オブジェクトの実装方法です。なお、この実装は C++ の他の数多くの "Bag" クラスとかなり違っています。他の "Bag" クラスは、さらに RWHashTable クラスに近く、真の Bag ではありません。

クラス RWSet は 基底クラス RWHashTable と似ていますが、重複が許されないという点が異なります。つまり、ある値を持つオブジェクトを複数挿入しようとすると、重複するものの挿入が拒否されます。

クラス RWIdentitySet は RWSet からの継承です。このクラスは、値の代わりに同一性にもとづいてオブジェクトを取り出します。これは RWIdentitySet がセットの一種であるため、各オブジェクトについて、インスタンスを 1 つしか挿入できません。

ハッシュテーブルにもとづくこれらのクラスのいずれにおいても、オブジェクトの順序は意味を持たないことに注意してください。順序が重要である場合は、順序付きクラスを選択してください。

順序付きクラス

これらのクラスは一般に、ベクトルとして、あるいは一重リンクリストまたは二重リンクリストとして実装されます。ベクトルにもとづくクラスは、スタックおよびキューの操作には向いていますが、途中への挿入には適していません。ベクトルにもとづくコレクションクラスの容量を超えて挿入を行うと、自動的にサイズ変更が行われますが、そのためにパフォーマンスの大幅な低下をもたらすこともあります。

バイナリクラスおよび B ツリークラスはソートされているので、固有の順序を持つ、という意味で、"順序付きクラス" とみなすことができるでしょう。しかしその順序は挿入の順序ではなく、収集されたオブジェクトの相対的な値によって内部的に決定されます。つまりオブジェクトを、ソートされたコレクションの中の希望する位置に任意に挿入することはできないのです (ソートされた状態が失われてしまうという問題があるからです)。したがって、これらのクラスは別にサブクラス化されます。

辞書

Tools.h++ には、RWHashDictionary (ハッシュテーブルとして実装) と、RWBTreeDictionary (B ツリーとして実装) という 2 つの辞書クラスがあります。キーと値は両方とも抽象基底クラス RWCollectable から継承しなければなりません。

抽象基底クラスとは、それ自体が使用されるのではなく、他のクラスによって継承されることを目的としたクラスのことです。このクラスを一種の仮想クラスと考えると、仮想関数の意味を簡単に投影することができます。抽象規定クラスの仮想関数は、派生クラスの機能の青写真を提供します。RWCollection は、抽象基底クラスとして、insert()、remove()、entries() などの各種の仮想関数を宣言することにより、コレクションクラスに対して青写真を提供します。

この節では、Smalltalk 式コレクションのすべてに継承される仮想関数を説明します。これらの仮想関数はどのコレクションでも理解されるものと考えられます。

insert()

virtual RWCollectable* insert(RWCollectable*);

この関数は、コレクションにとって最も自然な方法で挿入を行います。スタックの場合は、項目をスタックにプッシュします。キューの場合は、項目をキューに追加します。ソートされたコレクションの場合は、新しい項目の前にある項目が新しい項目よりも小さくなり、後ろにある項目が新しい項目よりも大きくなり、重複が可能な場合は、等しい項目は等しくなるように挿入されます。insert() を使用する例については、207 ページの「例」を参照してください。

必ず、実在するオブジェクトへのポインタを挿入してください。すべての RWCollection クラスは、find() などいくつかのメソッドで、その内容を間接参照する必要があるため、ゼロを挿入すると、このようなメソッドはクラッシュします。空のオブジェクトを格納しなければならない場合は、RWCollectable* などの適切な型のデフォルト作成オブジェクトを作成して挿入するようにしてください。RWCollection 中のすべてのオブジェクトを削除する予定がない場合は、大域 RWnilCollectable を選択することもできます。これは、キャッシュされた RWCollectable オブジェクトへのポインタです。ただし、RWnilCollectable は 1 つしかないため、もし削除すると、このクラスに対する他の参照すべてが無効なメモリーを参照することになるので注意してください。

find() とフレンド

virtual RWBoolean       contains(const RWCollectable*) const;
virtual unsigned        entries() const;
virtual RWCollectable*  find(const RWCollectable*) const;
virtual RWBoolean       isEmpty() const;
virtual unsigned        occurrencesOf(const RWCollectable*) const;

関数 contains() は、引数がコレクション内のある項目に等しい場合に TRUE を返します。「等しい」という意味は、テストの対象となるコレクションとオブジェクトの型によって異なります。コレクションのハッシュでは、まず引数をハッシュして、1 つのハッシュバケットの中にある候補者の数を減らしてから、仮想関数 isEqual() を使用して等値性をテストします (ここでは、相互に「isEqual (等しい)」である項目はすべて、同じ値にハッシュすることが重要です)。ソートされたコレクションは、引数に等しい項目、つまり compareTo() がゼロを返す項目を検索します。

仮想関数 occurrencesOf() は contains() と似ていますが、引数と等しい項目の数を返します。

仮想関数 find() は引数と等しい項目へのポインタを返します。

次の例は、207 ページの「例」にもとづくものですが、find() を使用してコレクション内の Mary の発生を検索し、occurencesOf を使用して Mary の発生回数を検索しています。

#define RW_STD_TYPEDEFS 1 #include <rw/bintree.h> //1 #include <rw/collstr.h> //2 #include <rw/rstream.h> main(){ // 空の SortedCollection を作成する SortedCollection sc; //3 // RWCollectableString をいくつか挿入する sc.insert(new RWCollectableString("George")); //4 sc.insert(new RWCollectableString("Mary")); //5 sc.insert(new RWCollectableString("Bill")); //6 sc.insert(new RWCollectableString("Throkmorton")); //7 sc.insert(new RWCollectableString("Mary")); //8 cout << sc.entries() << "\n"; //9 RWCollectableString dummy("Mary"); //10 RWCollectable* t = sc.find( &dummy ); //11 if(t){ //12 if(t->isA() == dummy.isA()) //13 cout << *(RWCollectableString*)t << "\n"; //14 } else cout << "Object not found.\n"; //15 cout << sc.occurrencesOf(&dummy) << "\n"; //16 sc.clearAndDestroy(); return 0; }

プログラム出力

5 Mary 2

remove() 関数

virtual RWCollectable*  remove(const RWCollectable*);
virtual void            removeAndDestroy(const RWCollectable*);

関数 removeAndDestroy() は remove() と似ていますが、違うところは項目を返さずにすべての RWCollectable 項目に継承される仮想デストラクタを使用してそれを削除することです。この関数を使用するときは、項目は実際にヒープ (スタックではなく) から割り当てられており、他のコレクションと共有されていないということに注意しなければなりません。また、RWnilCollectable は キャッシュおいて RWCollectable を参照するので、削除しないように注意してください。

次の例は、前の例を拡張したものですが、仮想関数 removeAndDestroy() の使用を説明しています。

RWCollectable* oust = sc.remove(&dummy);                     //17
delete oust;                                                 //18
sc.removeAndDestroy(&dummy);                                 //19

apply() 関数

virtual void apply(RWapplyCollectable ap, void* x);

typedef void  (*RWapplyCollectable)(RWCollectable*, void*);

void yourApplyFunction(RWCollectable* item, void* x)

Smalltalk 式コレクションの apply() 関数が総称コレクションの apply() 関数と似ていることに注意してください (200 ページの「適用関数」と比較してください)。相違点は、ユーザー定義関数の最初の引数の型にあります。Smalltalk 式コレクションは RWCollectable* を使用するのに対して、総称コレクションは type* を使用します。いずれのコレクションでも、ポインタ item を正しい派生クラスにキャストするように注意する必要があります。

適用関数は一般に、コレクションの全メンバーを調べるために "最も効率の良い方法" を採用します。これは適用関数の最大の長所です。その短所は、若干使いにくいところがあり、ユーザーが別の関数を用意しなければならないということです ¹ 。

関数 clear() および clearAndDestroy()

virtual voidclear();
virtual voidclearAndDestroy();

クラス変換

RWBag         asBag() const;
RWSet         asSet() const;
RWOrdered     asOrderedCollection() const;
RWBinaryTree  asSortedCollection() const

他のコレクションの挿入と除去

void  operator+=(const RWCollection&);
void  operator-=(const RWCollection&);

typedef RWBoolean (*RWtestCollectable)(const RWCollectable*,
                   const void*);
RWCollection*     select(RWtestCollectable tst, void*);

virtual RWCollectable*&       at(size_t i);
virtual const RWCollectable*  at(size_t i) const;

RWOrdered od;
od.insert(new RWCollectableInt(0));                          // 0
od.insert(new RWCollectableInt(1));                        // 0 1
od.insert(new RWCollectableInt(2));                      // 0 1 2

delete od(1);              // RWOrdered に有効な可変要素を使用する
od.at(1) = new RWCollectableInt(3);                      // 0 3 2

次の仮想関数はそれぞれ、コレクション内の最初の項目か最後の項目を返します。ただし、コレクションが空であれば NULL を返します。

virtual RWCollectable*  first() const;
virtual RWCollectable*  last() const;

virtual size_t  index(const RWCollectable*) const;

RWOrdered od;
od.insert(new RWCollectableInt(6));                          // 6
od.insert(new RWCollectableInt(2));                        // 6 2
od.insert(new RWCollectableInt(4));                      // 6 2 4

RWCollectableInt dummy(2);
size_t inx = od.index(&dummy);
if (inx == RW_NPOS)
  cout << "Not found.\n";
else
  cout << "Found at index " << inx << endl;

プログラム出力

Found at index 1

virtual RWCollectable* insertAt(size_t i, RWCollectable* c);

RWOrdered od;
od.insert(new RWCollectableInt(6));                          // 6
od.insert(new RWCollectableInt(2));                        // 6 2
od.insertAt(1, new RWCollectableInt(4));                 // 6 4 2

次のコードはこのことを説明しています。

SortedCollection sc;
RWCollectableString member;

sc.insert(&member);

RWCollectableString target;
RWCollectableString* p = (RWCollectableString*)sc.find(&target);

member.compareTo(&target);               // これが呼び出させる
target.compareTo(&member);               // こちらではない

一般に、ハッシュと線形探索のこの組み合わせと、ほとんどのハッシュアルゴリズムの複雑さにより、ハッシュコレクション内でのオブジェクトの順序はあまり意味を持ちません。したがって、apply() 関数または反復子がハッシュテーブルを走査するとき、オブジェクトが何か特定の順序で調べられるということはありません。