Copyright 1999 Rogue Wave Software
Copyright 1999 Sun Microsystems, Inc.
コレクションクラステンプレート |
10 |
![]() |
Smalltalk 式コレクションクラス (詳細は後で説明) は、多相性と継承によって、オブジェクトコードの再使用を可能にします。この章では、Tools.h++ コレクションクラステンプレート (このマニュアルではテンプレートと呼ぶ) での再使用について説明します。
テンプレートとは、型に関してパラメータ化されたクラス宣言のことです。テンプレートは、特定の型のコレクションクラスの動作を規定します。たとえば、Vector テンプレートは、要素のインデックス付けの方法、要素の長さ、要素のサイズ変更の方法などを記述します。要素の実際の型は、このような一般的で重要な問題とは無関係です。
テンプレートを使用すると、収集される要素の特定の型 (1 つあるいは複数) に関係なくコレクション用のコードを作成することによって、ソースコードの再使用を大幅に実現することができます。テンプレート機構によって、可変部分として機能する形式的なテンプレートパラメータを使用して、これらの型を表わすことができます。その後、コレクションクラステンプレートを利用したい場合は、実際の型によってテンプレートをインスタンス化します。この時点でコンパイラはクラステンプレートに戻り、最初からそう作成されていたかのように、その型によってそのテンプレートを埋めます。
テンプレートを使用しないと、クラス VectorOfInt、VectorOfDouble、VectorOfFoo などを作成しなければなりません。テンプレートを使用すると、Vector<T> という 1 つのクラスをコーディングするだけですみます。ここで T は任意の型を示すことができます。ここから、Vector<int>、Vector<double>、Vector<Foo>、あるいはクラステンプレートを最初に作成した時点には想像もできなかった型まで、あらゆるベクトルを作成する手間から解放されます。
テンプレートの概要
テンプレートの動作を説明するために、まず一般的な例を示すことにします。この節では、次の例を使用して概念を説明します。したがって、問題なく理解できると思います。
#include <iostream.h> #include <rw/cstring.h> #include <rw/regexp.h> #include <rw/tvdlist.h> int main() { // 文字列のリンクリストを宣言する RWTValDlist<RWCString> stringList; RWTValDlist<RWCString>::iterator iter; RWCString sentence; // リストに単語を追加する stringList.insert("Templates"); stringList.insert("are"); stringList.insert("fun"); // 標準反復子を使用して文を作成する iter = stringList.begin(); while (iter != stringList.end()) { sentence += (*iter++ + " "); } // 後続ブランクを ! に置換する sentence(RWCRegexp(" $")) = "!" // 結果を表示する cout << sentence << endl; return 0; } |
Templates are fun! |
テンプレートの命名規則
例に示されたコレクションクラステンプレートの RWTValDlist が固有の形式に従っていることに注意してください。Tools.h++ では、すべてのテンプレートの名前は RWT (Rogue Wave Template を表わす) で始まり、その後ろに次のような 3 文字のコードが付きます。
Isv | Intrusive lists (侵入的リスト、『プログラミング言語 C++』の 8.3.1 節を参照) |
Val | Value-based (値にもとづく) |
Ptr | Pointer-based (ポインタにもとづく) |
したがって、RWTValOrderedVector<T> は、型名 T の順序付きベクトル用の値にもとづくテンプレートを示します。RSTPtrMultiMap<Key,T,C> は、標準 C++ ライブラリの multimap クラスにもとづく、ポインタにもとづくテンプレートを示します。RWTValSortedDlist<T,C> のように、特殊な特性によって名前が変更されることもあります。これは、自動的に要素をソートされた順序で維持する、値にもとづく、二重リンクのテンプレートリストを示します。
テンプレートにおける値と参照の意味論
Tools.h++ コレクションクラステンプレートは、値にもとづくか、またはポインタにもとづくかのどちらかです。値にもとづくコレクションは、値意味論を使用して、挿入されたオブジェクトのコピーを維持し、検索されたオブジェクトのコピーを返します。これに対して、ポインタにもとづくコレクションは参照意味論を使用して、オブジェクトそのものではなく、オブジェクトへのポインタを扱います。値と参照の意味論に関する他の例については、110 ページの「コレクションクラスの格納方法」を参照してください。
テンプレートでは、値と参照のどちらかの意味論を選択することができます。実際にはほとんどの場合、値にもとづくクラスかポインタにもとづくクラスのどちらか (たとえば、RWOrderedVectorVal か RWOrderedVectorPtr) を選択しなければなりません。
アプリケーションの要件によって、どちらを選択するかが決まります。値にもとづくテンプレートは、大きいオブジェクトの効率を最大化したい場合、つまり、いくつかの方法で参照される同じグループのオブジェクトが必要であり、各コレクションクラスがそれらの目標オブジェクトを完全に含むのではなく指す必要がある場合に適しています。
// RWDate ポインタの値にもとづくリスト RWTValDlist<RWDate*> myBirthdayV;
RWDate* d1 = new RWDate(29,12,55); // 1955 年 12 月 29 日 myBirthdayV.insert(d1); RWDate* d2 = new RWDate(29,12,55); // 異なるオブジェクト、同じ日付 cout << myBirthdayV.occurrencesOf(d2); // ゼロが出力される
このコードを次のコードと比較してください。
RWTPtrDlist<RWDate> myBirthdayP; // RWDates のポインタにもとづくリスト RWDate* d1 = new RWDate(29,12,55); // 1955 年 12 月 29 日 myBirthdayP.insert(d1); RWDate* d2 = new RWDate(29,12,55); // 異なるオブジェクト、同じ日付 cout << myBirthdayP.occurrencesOf(d2); // 1 が出力される
テンプレートの侵入的リスト
型名 T のコレクションクラスの場合、侵入的リストとは、型 T がリンク型そのものから直接継承するリストのことです1。この結果、空間的にも時間的にも最適になりますが、継承階層を遵守する必要があります。このため、継承階層の柔軟性が失われて、既存のクラスとの使用が若干困難になります。各侵入的リストクラスに対して、Tools.h++ は、テンプレート化された値リストを代替の非侵入的リンクリストとして提供します。
侵入的リストに項目を挿入する場合、コピーではなく実際の項目が挿入されることに注意してください。各項目はリンクフィールドを 1 つしか持たないため、同じ項目を複数のリストに挿入することも、同じリストのに 2 回以上挿入することもできません。
Tools.h++ テンプレートと標準 C++ ライブラリ
ほとんどの Tools.h++ コレクションクラステンプレートは、標準 C++ ライブラリを基本となる実装に使用します。標準 C++ ライブラリのコレクションクラスはコンテナと呼ばれ、Tools.h++ テンプレートを実現するためのエンジンとして機能します。
たとえば、値にもとづく Tools.h++ 二重終端キュー RWTValDeque<T> には、標準 C++ ライブラリからの型 deque<T> のメンバーがあります。このメンバーは、コレクションの実装として機能します。エンジンと同様、これは要素の追加と削除などの大量の作業を実行します。RWTValDeque<T> は、エンジンを保護するフードに似たラッパークラスです。これは、装飾としてだけでなく、deque クラスへのより単純なオブジェクト指向インタフェースとしても機能し、簡単で処理しやすくします。
インライン化と余分なレベルの間接演算がないことのおかげで、このラップによってパフォーマンスが低下することは (あったとしても) ほとんどありません。実装への直接アクセスが必要な場合、ラッパークラスは、実装への参照を返すメンバー関数 std() を提供します。また、Rogue Wave テンプレートコレクションは標準反復子を提供するため、これらを標準 C++ ライブラリコレクションそのものように、標準 C++ ライブラリのアルゴリズムで使用することができます。
標準 C++ ライブラリが必要ない場合
Tools.h++ のこのバージョンに固有の特徴として、そのテンプレートコレクションの多くが、実際には標準 C++ ライブラリを必要としないということがあります。RWTValDlist<T> について考えてみます。標準 C++ ライブラリをサポートするプラットフォームで Tools.h++ を使用している場合、RWTValDlist<T> は、標準 C++ ライブラリの list コンテナを囲んで作成されます。しかし、プラットフォームで標準 C++ ライブラリをサポートしていない場合は、やはりクラスを使用する必要があります。Tools.h++ は、この処理を標準 C++ ライブラリに頼らず、代替実装によって透過的に行います。適切な実装は、コンパイル時に、設定ヘッダファイル rw/compiler.h の設定に従って選択されます。実際には、代替実装は、前のバージョンの Tools.h++ で採用されたものとまったく同じものです。
標準 C++ ライブラリなしでこれらのテンプレートのひとつを使用する場合は、完全なインタフェースのサブセットに制限されます。たとえば、前に説明した std() メンバー関数は使用できません。さらに、標準 C++ ライブラリの反復子を返す begin() 関数や end() 関数も使用できません。Tools.h++ の『Tools.h++ 7.0 クラスライブラリ・リファレンスマニュアル』には、標準 C++ ライブラリを使用しても、あるいは使用しなくても、使用できるテンプレートすべてへの完全なインタフェースとインタフェースのサブセットの両方についての項目が含まれます。
コレクションクラステンプレートへのインタフェースの限定されたサブセットを使用する理由には、次の 2 つがあります。
Tools.h++ 標準ライブラリにもとづくテンプレート | |||
分類//注記 | 値にもとづく | ポインタにもとづく | 標準ライブラリの必要性 |
シーケンスにもとづく | RWTValDlist | RWTPtrDlist | 不要 |
RWTValDeque | RWTPtrDeque | 必要 | |
RWTValOrderedVector | RWTPtrOrderedVector | 不要 | |
//外部順序付け、インデックスによるアクセス | RWTValSlist | RWTPtrSlist | 不要 |
ソートされたシーケンスにもとづく | RWTValSortedDlist | RWTPtrSortedDlist | 必要 |
//内部順序付け、インデックスによるアクセス | RWTValSortedVector | RWTPtrSortedVector | 不要 |
連想コンテナにもとづく | RWTValSet | RWTPtrSet | 必要 |
(セットにもとづく) | RWTValMutliSet | RWTPtrMultiSet | 必要 |
(マップにもとづく) | RWTValMap | RWTPtrMap | 必要 |
//内部順序付け、キーによるアクセス | RWTValMultiMap | RWTPtrMultiMap | 必要 |
連想ハッシュにもとづく | RWTValHashSet | RWTPtrHashSet | 不要 |
(セットにもとづく) | RWTValHashMutliSet | RWTPtrHashMultiSet | 不要 |
(マップにもとづく) | RWTValHashMap | RWTPtrHashMap | 不要 |
//順序付けなし、キーによるアクセス | RWTValHashMultiMap | RWTPtrHashMultiMap | 必要 |
インタフェースの共通性
処理を単純にして、プログラムをより自由に作成できるようにするために、標準ライブラリにもとづく各種のコレクションクラステンプレート内に、共通のインタフェースを実装しています。たとえば、RWTPtrSet と RWTPtrMultiSet の各テンプレートには、それらに対応する値にもとづくテンプレートと同じインタフェースがあります。マップにもとづくコレクションクラスの場合も同様です。シーケンスにもとづくコレクションはすべて、値とポインタにもとづくサブグループ内で、ほとんど同じインタフェースを持っています (例外としては、deque にもとづくクラスがあります。これには、キューデータ構造の抽象化を強化するように設計された push と pop の各メンバー関数が含まれます)。
共通インタフェースには、長所と短所があります。短所としては、適切なコレクションクラスの選択において開発者の負担が多少増えるという点があります。たとえば、もしクラス RWOrderedVectorVal<Type> に insertAt(size_type index) メンバー関数を与えないように選択されていれば、コレクションクラスの途中への挿入にとって、ベクトルにもとづくテンプレートが適切な選択ではないという考えが強く主張されていることになります。そのかわり、このようなメンバー関数を慎重に選択して使用することが、ユーザー (開発者) の責任となります。
長所としては、共通インタフェースを使用すると、コレクションの習得に要する時間が短くなって、異なるコレクションを自由に試すことができるようになるという点があります。さらに、Rogue Wave テンプレートを汎用性を通じて多相的に処理することができます 2。
実際のプログラミングが、データ構造の教科書での実習のようにスムーズにいくことはほとんどありません。かね合いのバランスをとって、どのコレクションクラスを使用するかを判断するのが難しい状況にぶつかる可能性があります。共通インタフェースを使用すると、RWTValDeque を使用するコードをベンチマークテストして、後で RWTValOrderedVector や RWTValDlist に置き換えてから、もう一度そのコードをベンチマークテストすることができます。コレクションクラス型でパラメータ化されるクラスと関数テンプレートを作成することもできます。次に例を示します。
template <class RWSeqBased> void tossHiLo(RWSeqBased& coll) { // 高い値と低い値を捨てる assert(coll.entries() >= 2); // 前提条件 coll.sort(); coll.removeFirst(); coll.removeLast(); }
パラメータの要件
Tools.h++ テンプレートコレクションクラスを使用して、型 T のオブジェクトを収集するためには、この型は、特定の最小要件を満たしていなければなりません。残念ながら、コンパイラの中には、必要以上に強力な型のインスタンス化を必要とするものがあります。
C++ 標準草案によれば、コンパイラは、実際に使用されるテンプレート関数だけをインスタンス化してコンパイルする必要があります。したがって、有効な less-than 意味論を必要とする sort() などのメンバー関数の呼び出しを避ける場合は、インスタンス u1 と u2 について、式 (u1 < u2) が不正な形式になるような、型 U のコレクションクラスをやはり作成できなければなりません。使用しているコンパイラでこのようにインスタンス化を選択できない場合は、operator<(const U&, const U&) を型 U に実装することなく、この型のオブジェクトを収集することはできません。
比較子
連想するコンテナにもとづくコレクションクラスとソートされたシーケンスにもとづくコレクションクラスは、順序を内部的に維持します。この順序付けは、比較オブジェクトにもとづいています。これは、テンプレートをインスタンス化するときに提供しなければならない比較子クラスのインスタンスです。比較子には、関数呼び出し演算子である const メンバー operator() が含まれなければなりません。この演算子は、コレクションクラスの 2 つの潜在的な要素を引数としてとり、ブール値を返します。返された値は、最初の引数がコレクションクラス内の 2 番目の引数の前になければならない場合は true になります。そうでない場合は false になります。通常、ヘッダファイル <functional> で、標準 C++ ライブラリによって提供される関数オブジェクトクラスのどれかひとつを使用すると最も簡単です。特に、要素を昇順で維持する場合は less<T> を、降順で維持する場合は greater<T> を使用します。
#include <functional> #include <rw/tvset.h> #include <rw/rwdate.h> RWTValSet<int, less<int> > mySet1; RWTValSet<RWDate, greater<RWDate> > mySet2;
ここで、mySet1 は昇順で維持される整数の集合を示すのに対し、mySet2 は降順、つまり最新のものから古いものへという順序で維持される日付の集合を示します。標準 C++ ライブラリのこれらの比較子は、less<T> の場合は (x<y)、または greater<T> の場合は (x>y) という式が、型 T のオブジェクトに対して全体的な順序付けを行う有効な式であるかぎり、使用することができます。
全順序の詳細
前述したように、比較子は、コレクションクラス内の項目の型に対して全体的な順序付けを行わなければなりません。つまり、comp が比較オブジェクトであり、x、y、z がコレクションクラス3の潜在的な (必ずしも明白ではない) 要素であると想定した場合に、比較子の関数呼び出し演算子は、次の 2 つの条件を満たさなければならないということです。
(または、comp(x,y) と comp(y,x) 両方が同時に true ではない。)
I.a は、コレクションクラス内で x が y の前になければならないことを示します。これに対して I.b は、y が x の前になければならないことを示します。さらに興味深いのは I.c です。この文が true の場合、x と y は等価であり、コレクションクラス内でそれらが現れる順序は問題になりません。これは、パラメータとして比較子をとるテンプレートにおいて一般的な等値性の考え方です。たとえば、関連コンテナにもとづくテンプレートのメンバー関数 contains(T item) は、コレクションクラスに item と等しい要素があるかどうかを調べる場合、実際には、comp(x,item) と comp(item,x) の両方が false であるような要素 x をコレクションクラス内で検索します。== 演算子は使用されていないことを理解することが重要です。最初は、否定によって等値性を求めることが直感的でないように思えるかもしれませんが、心配しないでください。この方法によって、すべての項目をコレクションクラスで正しく位置付けられることがすぐにわかるはずです。
比較子は通常、その実装においては非常に単純なものです。次に例を示します。
class IncreasingLength { public: bool operator()(const RWCString& x, const RWCString& y) { return x.length() < y.length(); } }; RWTValSet<RWCString,IncreasingLength> mySet;
class DecreasingInt { public: bool operator()(int x, int y) { return x > y; } }; RWTValSet<int, DecreasingInt> mySet2;
// このようなことはしてはならない class BadCompare { public: bool operator()(int x, int y) { return x <= y; } // 全順序の関係ではない }; RWSetVal<int, BadCompare> mySet3; // 無効な比較子
ハッシュ関数子と等値子
連想ハッシュにもとづくテンプレートは、ハッシュ関数オブジェクトを使用して、コレクションクラス内でのオブジェクトの設定と検索方法を決めます。ハッシュ関数オブジェクトを使用すると、オブジェクトを効率的に一定の時間で検索することができます。しかし、ハッシュ関数の結果をコレクションクラス自体の物理レイアウトにマッピングすることによって決まる順序で、オブジェクトが維持されるという短所もあります。ハッシュにもとづくコンテナという内部機構よりもこの順序付けが有効である場合はほとんどありません。
混乱を避けるために、連想ハッシュにもとづくコンテナは、等値オブジェクトを使用します。相互に等しい複数のキーを認めるコレクションは、コンテナを介した反復が起こったときには常に、等値オブジェクトを使用して、等しいオブジェクトをグループ化します。複数キーを認めないハッシュコレクションは、等値オブジェクトを使用して、固有の項目だけが認められるようにします。これらの手順を有効にするには、収集される要素の型 (1 つあるいは複数) だけでなく、ハッシュ関数子と等値子という 2 つのテンプレート引数が必要です。
「ハッシュ関数子」とは、コレクションクラスの潜在的な要素への const 参照をとり、unsigned long 型のハッシュ値を返す関数呼び出し演算子を含む、クラスか struct のことです。等値子とは、コレクションクラスの 2 つの潜在的な要素をとり、オブジェクトをグループ化するか、あるいはコレクションクラス内での一意性を確保するためにそれらの要素を等しいと見なす必要がある場合は true を返す関数呼び出し演算子を含む、クラスか struct のことです。
#include <rw/tvhset.h> // RWTValHashSet を含む #include <rw/cstring.h> // RWCString を含む struct StringHash { unsigned long operator()(const RWCString& s) { return s.hash(); } }; struct StringEqual { unsigned long operator()(const RWCString& s, const RWCString& t) { return s == t; } }; RWTValHashSet<RWCString, StringHash, StringEqual> rwhset;
反復子
Tools.h++ には、コレクションクラスを反復するための方法がいくつかあります。ほとんどのコレクションは、apply メンバー関数を提供しています。これは、提供された関数をコレクションクラスのすべての要素に適用してから返るものです。反復のもうひとつの形式は、多数のコレクションに関連する、別の共同反復子クラスによって提供されます。たとえば、RWTPtrDlistIterator<T> は、RWTPtrDlist<T> の各要素を順番に訪ねるために使用することができます。反復子については、「Collection Classes」の 123 ページの「コレクションクラスの反復子」を参照してください。
標準 C++ ライブラリの反復子
Tools.h++ 標準ライブラリにもとづくコレクションクラステンプレートにはすべて、標準反復子があります。これらの反復子は、反復子についての標準 C++ ライブラリの要件に完全に準拠しているため、標準 C++ ライブラリ、特にアルゴリズムと組み合わせてクラスを使用するときの強力なツールとなっています。反復子の完全な説明は、このマニュアルの範囲を越えるものですが、標準 C++ ライブラリのリファレンスとチュートリアルには詳しい情報が示されています。
標準ライブラリにもとづくコレクションクラステンプレートには、順方向、双方向、ランダムアクセスという 3 種類の反復子があります。順方向反復子を使用すると、最初から最後への単一方向へたどることが可能になります。名前からわかるように、双方向反復子では、前から後ろと、後ろから前の両方向へたどることが可能です。ランダムアクセス反復子も両方向ですが、一定の時間に任意の数の要素だけ進むことができる機能によって区別されます。これらの反復子のどれを使用しても、間接参照演算子 * によって、現在の位置にある項目にアクセスすることができます。
反復子 iter と整数値 n を指定した場合、次ページの表の基本的な演算は、サポートされているものの一部分になります。
式 | 意味 | サポートするもの |
---|---|---|
++iter; | 次の項目に進んで返す | Forw, Bidir, Random |
iter++; | 次の項目に進んで、元の値を返す | Forw, Bidir, Random |
*iter; | 現在の位置の項目に対する参照を返す | Forw, Bidir, Random |
--iter; | 前の項目に後退して返す | Bidir, Random |
iter--; | 前の項目を後退して、元の値を返す | Bidir, Random |
iter+=n; | n 項目進んで返す | Random |
iter-=n; | n 項目後退して返す | Random |
標準ライブラリのマニュアルでも、各種類の反復子で使用できる演算子と関数すべてについて説明しています。
説明した反復子だけでなく、標準ライブラリにもとづくコレクションクラステンプレートには、コレクションクラス内の項目を繰り返すために使用される、iterator と const_iterator という 2 つの typedef があります。iterator という typedef を使用すると、コレクションクラスをくまなくたどって、その中の要素を変更することができます。const_iterator のインスタンスを使用すると、コレクションクラスをくまなくたどって要素にアクセスすることができますが、変更できません。関連するコンテナにもとづくコレクションとソートされた順序にもとづくコレクションの場合は、コレクションクラス内にある要素を修正することができないため、iterator と const_iterator の各型は同じになります。
テンプレートには、それぞれのコレクションクラスをくまなくたどるために使用できる実際の反復子を返す 2 つのメンバー関数もあります。これらのメンバー関数は、begin() と end() です。これらの各メンバー関数は、const 指定できるように多重定義されて、非 const バージョンが型 iterator のインスタンスを返し、const バージョンが型 const_iterator のインスタンスを返すようになっています。
メンバー関数 begin() は、コレクションクラスの最初の項目にすでに設定されている反復子を返します。メンバー関数 end() は、最後の次 (past-the-end) の値を持つ反復子を返します。これは、ヌル終了文字列のヌル文字へのポインタが、最後の次を指す値を持つ方法と同様です。最後の次の値の反復子は、他の反復子と比較して、コレクションクラス内のすべての要素を訪ねたかどうかを確認するために使用することができます。これは、双方向かランダムアクセスかどちらかの反復子を提供するコレクションクラスを逆方向に移動するときの開始点として使用することもできます。end() 反復子で不可能なことはそれを間接参照することです。次に、反復子を使用してリスト内を移動して、一致を検索する例を示します。
RWTValDlist<int> intCollection; // 整数のリスト // ... < リストに項目を挿入する > // 開始点に iter を設定する RWTValDlist<int>::iterator iter = intCollection.begin(); // 別の反復子を最後の次に設定する RWTValDlist<int>::iterator theEnd = intCollection.end(); // 7 を検索して反復する while (iter != theEnd) { // コレクションの最後をテストする if (*iter == 7) // 「*」を使用して現在の要素にアクセスする return true; // 7 を見つける ++iter; // 7 ではない場合は、次の要素を試す } return false; // 7 を見つけられない |
マップにもとづく反復とペア
RWMapVal<K,T,Compare> のようなマップにもとづくコレクションクラスの場合、反復子は、標準 C++ ライブラリの構造体 pair<const K,T> のインスタンスを参照します。マップにもとづくコレクションを反復するとき、トラバーサルの各ステップで、キーとそれに関連するデータの両方にアクセスすることができます。pair 構造体は、メンバー first と second を提供します。これらのメンバーを使用すると、それぞれ、キーとそのデータに個々にアクセスすることができます。次に例を示します。
typedef RWTValMap<RWCString, RWDate, less<RWCString> > Datebook; Datebook birthdays; // ... < 誕生日コレクションを集める > Datebook::iterator iter = birthdays.begin(); while (iter != birthdays.end()) { cout << (*iter).first // キー << " was born on " << (*iter).second // そのキーのデータ << endl; ++iter; }; |
このような pair に非 const 参照が存在するならば、2 番目の要素だけを変更することができます。つまり、キーに関連するデータです。これは、最初の要素の型が const K と宣言されているためです。コレクションクラス内でのオブジェクトの配置は、キーの値によって内部的に維持されるため、それを const として宣言すると、コレクションクラスの保全性が保護されます。マップ内のキーを変更するには、キーとそのデータを完全に削除してから、新しいエントリによってそれらを置換する必要があります。
汎用ポインタとしての反復子
反復子は汎用ポインタと考えることができます。int の配列へのポインタについて考えてください。配列自体はコレクションクラスであり、この配列の要素へのポインタはランダムアクセス反復子です。次の要素に進むには、単に単項演算子 ++ を使用します。前の要素に戻るには、-- を使用します。反復子の現在位置にある要素にアクセスするには、単項演算子 * を使用します。最後に、要素すべてをいつ訪ねたかを知る必要があります。C++ は、割り当てられた配列の最後を過ぎた最初のアドレスを常に指すことができるように保証します。次に例を示します。
int intCollection[10]; // 整数の配列 // ... < 配列に項目を挿入する > // 開始点に反復子を設定する int* iter = intCollection; // 別の反復子を最後の次に設定する int* theEnd = intCollection + 10; // 7 を検索して反復する while (iter != theEnd) { // 配列の最後をテストする if (*iter == 7) // 「*」を使用して現在の要素にアクセスする return true; // 7 を見つける ++iter; // 7 ではない場合は、次の要素を試す } return false; // 7 を見つけられない |
このコードを 156 ページの「標準 C++ ライブラリの反復子」の標準反復子を使用するコードと比較すると、類似点がわかります。標準反復子の動作を想像するために助けが必要な場合は、それらを汎用ポインタとして考えることができます。
反復子と std() ゲートウェイ
Tools.h++ テンプレートは、標準 C++ ライブラリの障壁となるのではなく、これを強化することを目的としています。前の項で説明した反復子は標準反復子であり、標準反復子にもとづくインタフェースを提供する任意の構成要素と組み合わせて使用することができます。特に、Rogue Wave 標準ライブラリにもとづくコレクションでは、標準アルゴリズムのすべてを使用することができます。次に例を示します。
// ... < ベクトルに項目を挿入する > // 最初の 5 つの要素を 0 に設定する fill(vec.begin(), vec.begin() + 5, 0);
両方の利点の活用例
次の例は、1 組のトランプカードを作成してそれをかき混ぜるための完全なプログラムです。この例の目的は、Tools.h++ のテンプレートコレクションを標準 C++ ライブラリとどのように組み合わせて使用できるかを示すことにあります。この例で使用される機能の詳細については、各自の標準 C++ ライブラリの資料を参照してください。
/* 注:この例には C++ 標準ライブラリが必要 */ #include <iostream.h> #include <algorithm> #include <rw/tvordvec.h> struct Card { char rank; char suit; bool operator==(const Card& c) const { return rank == c.rank && suit == c.suit; } Card() { } Card(char r, char s) : rank(r), suit(s) { } // カードの出力:3-C はクラブの 3、A-S はスペードのエース friend ostream& operator<<(ostream& ostr, const Card& c) { return (ostr << c.rank << "-" << c.suit << " "); } }; /* * 生成クラス − カードを順番に返す */ class DeckGen { int rankIdx; // 下記の静的配列へのインデックス int suitIdx; static const char Ranks[13]; static const char Suits[4]; public: DeckGen() : rankIdx(-1), suitIdx(-1) { } // 次のカードを生成する Card operator()() { rankIdx = (rankIdx + 1) % 13; if (rankIdx == 0) // ある組を作り終えれば、次の組に移動する suitIdx = (suitIdx + 1) % 4; return Card(Ranks[rankIdx], Suits[suitIdx]); } }; const char DeckGen::Suits[4] = {'S', 'H', 'D', 'C' }; const char DeckGen::Ranks[13] = {'A', '2', '3', '4', '5', '6', '7', '8', '9', 'T', 'J', 'Q', 'K' }; int main(){ // Tools.h++ コレクション RWTValOrderedVector<Card> deck; RWTValOrderedVector<Card>::size_type pos; Card aceOfSpades('A','S'); Card firstCard; // 標準ライブラリアルゴリズムを使用して組を生成する generate_n(back_inserter(deck.std()), 52, DeckGen()); cout << endl << "The deck has been created" << endl; // Tools.h++ メンバー関数を使用してカードを検索する pos = deck.index(aceOfSpades); cout << "The Ace of Spades is at position " << pos+1 << endl; // 標準ライブラリアルゴリズムを使用してカードをかき混ぜる random_shuffle(deck.begin(), deck.end()); cout << endl << "The deck has been shuffled" << endl; // Tools.h++ メンバー関数を使用する pos = deck.index(aceOfSpades); firstCard = deck.first(); cout << "Now the Ace of Spades is at position " << pos+1 << endl << "and the first card is " << firstCard << endl; } /* 出力 (かき混ぜによって異なる) The deck has been created The Ace of Spades is at position 1 The deck has been shuffled Now the Ace of Spades is at position 37 and the first card is Q-D */ |
標準ライブラリなしでテンプレートを使用する
RWTValVector<T>、RWTPtrVector<T>、RWTIsvSlist<T>、RWTIsvDlist<T> などの Tools.h++ テンプレートのいくつかは、標準 C++ ライブラリにもとづいていません。これらのテンプレートは、検証された任意のプラットフォームで使用することができます。また、概要でも述べたように、完全なインタフェースのサブセットを維持していれば、いわゆる標準ライブラリにもとづくテンプレートの多くを標準 C++ ライブラリなしで使用することもできます。
標準 C++ ライブラリの移植可能性の考慮
制限されたサブセットのインタフェースは、それに対応する標準ライブラリにもとづくインタフェースとほぼ完全に上方互換性を持ちます。主な違いは、コレクションのいくつかが、使用している基本実装によって、異なる数のテンプレートパラメータをとるという点です。たとえば、RWTPtrHashSet は、標準 C++ ライブラリで使用すると、153 ページの「ハッシュ関数子と等値子」で説明したように、3 つのテンプレート引数をとります。ただし、同じクラスが標準 C++ ライブラリなしで使用された場合、制限されたインタフェースは、1 つのテンプレートパラメータしか呼び出しません。つまり、含まれる項目の型だけです。標準 C++ ライブラリがあってもなくても動作する移植可能なコードを作成するために、Tools.h++ には次の 2 つのマクロが用意されています。
RWTPtrHashSet<int RWDefHArgs(int)> hset;
標準 C++ ライブラリがあるかどうかに関係なく、同じ意味解釈を持つハッシュにもとづくセットを宣言します。要素の型とマクロの間にはコンマを使用してはいけないことに注意してください。標準 C++ ライブラリがない場合、マクロは何も展開せず、次のように宣言した場合と同様になります。
RWTPtrHashSet<int> hset;
ただし、標準 C++ ライブラリが使用できる場合、マクロは次のように展開されます。
RWTPtrHashSet<int ,RWTHasher<int>, equal_to<int> > hset;
この宣言は、3 つのパラメータすべてで標準ライブラリにもとづくインタフェースの完全な要件を満たし、代替の非標準ライブラリにもとづく実装と整合性のある意味解釈を維持します。
RWTValSortedVector<int RWDefCArgs(int)> srtvec;
これは、標準 C++ ライブラリがあってもなくても動作する移植可能な宣言です。ここでも、マクロと要素の型を区切るために、コンマは使用しないでください。
#include <rw/tvvector.h> // 1 main() { RWTValVector<double> vec(20, 0.0); // 2 int i; for (i=0; i<10; i++) vec[i] = 1.0; // 3 for (i=11; i<20; i++) vec(i) = 2.0; // 4 vec.reshape(30); // 5 for (i=21; i<30; i++) vec[i] = 3.0; // 6 return 0; } |
次に、このプログラムを 1 行ずつ説明します。
//1 | RWTValVector<T> のテンプレートが定義されます。 |
//2 | 20 要素の長さで 0.0 に初期化される倍精度浮動小数点のベクトルが宣言されて定義されます。 |
//3 | このベクトルの最初の 10 要素が 1.0 に設定されます。ここでは、RWValVector<double>::operator[](int) が使用されています。この演算子は引数に対して常に境界検査を行います。 |
//4 | このベクトルの次の 10 要素が 2.0 に設定されます。この場合、RWValVector<double>::operator()(int) が使用されています。この演算子は一般に境界検査を行いません。 |
//5 | メンバー関数 reshape(int) がベクトルの長さを変更します。 |
//6 | 最後の 10 要素が 3.0 に初期化されます。 |
例 2
2 番目の例は、ハッシュ付き辞書に関係します。ハッシュ付き辞書を宣言するときにマクロ RWDefHArgs(T) を使用すると、標準 C++ ライブラリにアクセスしてもしなくても、コードを移植可能にすることができます。
#include <rw/tvhdict.h> #include <rw/cstring.h> #include <rw/rstream.h> #include <iomanip.h> class Count { // 1 int N; public: Count() : N(0) { } // 2 int operator++() { return ++N; } // 3 operatorint() { return N; } // 4 }; unsigned hashString ( const RWCString& str ) // 5 { return str.hash(); } main() { RWTValHashDictionary<RWCString, Count /* ここにはコンマを入れません */ RWDefHArgs(RWCString)> hmap(hashString); //6 RWCString token; while ( cin >> token ) // 7 ++hmap[token]; // 8 RWTValHashDictionaryIterator<RWCString,Count> next(hmap); // 9 cout.setf(ios::left, ios::adjustfield); // 10 while ( ++next ) // 11 cout << setw(20) << next.key() << " " << setw(10) << next.value() << endl; // 12 return 0; } |
How much wood could a woodchuck chuck if a woodchuck could chuck wood ? |
much 1 wood 2 a 2 if 1 woodchuck 2 could 2 chuck 2 How 1 ? 1 |
//1 | 辞書の値部分として使用されるクラスです。 |
//2 | 出現回数をゼロにするデフォルトコンストラクタが与えられます。 |
//3 | 接頭インクリメント演算子を与えます。これは出現回数を増分する方法として使いやすく便利なものです。 |
//4 | Count を int 型に変換するための変換演算子が与えられます。これは、結果の出力に使用されます。別の方法として、多重定義した operator<<() を与えて、Count 自体を出力するようにすることもできますが、こちらの方が簡単です。 |
//5 | これは、辞書コンストラクタに与えなければならない関数です。その役割は、キーの型の引数が与えられたとき、ハッシュ値を返すことです。Tools.h++ は、ユーザー定義関数のかわりに使用できるクラス RWCString、RWDate、RWTime、RWWString に静的ハッシュメンバー関数を与えることに注意してください。この例を一般的にするために、Tools.h++ によって定義された静的ハッシュメンバー関数のひとつではなく、ユーザー定義の関数を選択しました。 |
//6 | ここで辞書が構築されます。キーが与えられたとき、値を検索するためにこの辞書が使用されます。この場合、キーは RWCString 型で、値の型は Count です。コンストラクタには単一の引数が必要です。これは、キーを与えられたときにハッシュ値を返す関数のポインタです。この関数は行 5 で定義されています。標準 C++ ライブラリを使用するプラットフォームと使用しないプラットフォームの間でプログラムを移植可能にするために、RWDefHArgs(T) マクロを使用したことに注意してください。 |
//7 | トークンが入力ストリームから RWCString へ読み込まれます。これは EOF に達するまで続けられます。式「cin >> token」が単一のトークンを読み取り、ostream& を返します。クラス ostream には、while ループの実際の調査対象である void* への型変換演算子があります。Operator void* は、ストリームの状態が「good」であれば「this」を返し、そうでなければゼロを返します。EOF はストリームの状態を「not good」にするので、while ループは EOF に達したところで終了します。詳細は『Tools.h++ 7.0 クラスライブラリ・リファレンスマニュアル』の「RWCString」と、コンパイラに付属のクラスに関する文書から、「ios」の項を参照してください。 |
//8 |
すべての仕掛けはここにあります。オブジェクト map は辞書です。これは多重定義された operator[] を持っており、この関数はキーの型の引数をとり、対応する値への参照を返します。値の型は Count です。したがって、map[token] は Count 型になります。行 3 で見たように、Count には多重定義された接頭インクリメント演算子があります。これは Count に関して呼び出され、その値を増分します。 キーがディクショナリに存在しない場合は、多重定義された operator[] がそのキーを新しい値 (その値のクラスのデフォルトコンストラクタを使用して作成されたもの) とともに挿入します。これは行 2 で、出現回数をゼロに初期化するように定義されています。 |
//9 | これから結果を出力していきます。まず、辞書を走査する反復子を定義し、各キーと値を返します。 |
//10 | 出力の外観をよくするために、出力ストリームのフィールド幅を調整します。 |
//11 | コレクションの終りに達するまで反復子が進められます。接頭インクリメント演算子は反復を進め、それがコレクションの終わりを過ぎたかどうかを調べます。これはテンプレートのすべての反復子に対して実行されます。 |
//12 | 反復子の位置にあるキーと値が出力されます。 |
移行の手引き:旧バージョンの Tools.h++ を使用している場合
本書の概要で説明したように、このバージョンの Tools.h++ の主な目的の 1 つは、前のバージョンのライブラリにもとづく既存コードに対する投資を保護することにあります。この章で説明したように、コレクションクラステンプレートには、標準 C++ ライブラリに合わせるために大幅な変更が加えられています。次のクラスが変更されました。
RWTPtrDlist | RWTValDlist |
RWTPtrHashDictionary | RWTValHashDictionary |
RWTPtrHashSet | RWTValHashSet |
RWTPtrHashTable | RWTValHashTable |
RWTPtrOrderedVector | RWTValOrderedVector |
RWTPtrSlist | RWTValSlist |
RWTPtrSortedVector | RWTValSortedVector |
これらのクラスはすべて、標準 C++ ライブラリがあってもなくても使用することができます。標準 C++ ライブラリなしで使用した場合、これらのクラスは、前のバージョンの Tools.h++ と同じインタフェースと実装を持ちます。若干のバグ修正は行われていますが、このようなわずかな拡張によって、既存コードとの互換性がなくなることはありません。
標準 C++ ライブラリとともに上記のクラスを使用する場合は、既存のソースコードに多少の変更を加えなければならない場合があります。特定のクラスに必要な調整については、次に説明します。
RWTPtrHashDictionary | RWTValHashDictionary |
RWTPtrHashSet | RWTValHashSet |
RWTPtrHashTable | RWTValHashTable |
RWTPtrSortedVector | RWTValSortedVector |
RWTPtrHashSet | RWTValHashSet |
RWTPtrHashTable | RWTValHashTable |
RWTPtrOrderedVector | RWTValOrderedVector |
RWTPtrSortedVector | RWTValSortedVector |
RWTValHashSet から RWTValHashTableIterator、あるいは RWTPtrHashSet から RWTPtrHashTableIterator を作成する場合、既存コードでこの問題が発生することがよくあります。RWTValHashTableIterator のコンストラクタは、RWTValHashTable への参照を期待するため、かわりの RWTValHashSet の受け渡しは継承関係に依存します。
この問題を解決する方法は、新しいクラス RWTPtrHashSetIterator にあります。RWTValHashSet から RWTValHashTableIterator を作成するコードを見つけたら、RWTValHashSetIterator に置き換えます。RWTValHashSetIterator は、標準 C++ ライブラリが使用できるかどうかに関係なく用意されているため、コードを標準ライブラリにもとづく実装に移行することが期待されている場合は、ここでコードを修正できることに注意してください。
RWTPtrDlist | RWTValDlist |
RWTPtrOrderedVector | RWTValOrderedVector |
RWTPtrSlist | RWTValSlist |
RWTPtrSortedVector | RWTValSortedVector |
operator<() の定義が実際に必要なメンバー関数を使用している場合は、実際に使用できる方法で定義するのが一番です。コンパイラを満たす目的だけのダミー operator<() を大域的に定義する方法は簡単で便利ですが、このような「コンパイラを満たすためだけ」に作成されたコードは、保守が非常に困難です。このようなコードはできるだけ作成しないでください。
2 汎用性と継承については、『Object-oriented Software Construction』Meyer, Bertrand, 1988 を参照してください。
3 Knuth (1973) から採用
4 残念ながら、全順序の要求は論理的であり、意味上のものではありません。したがって、コンパイラは、間違って選択された比較子を拒否することによってサポートすることができません。一般に、このようなコードはコンパイルされますが、その動作は予測不可能になります。