Tools.h++ 7.0 クラスライブラリ・リファレンスマニュアル: RWTValHashDictionary

バナーをクリックすれば目次に戻ります

RWTValHashDictionary<K,V>

形式

#include <rw/tvhdict.h>
unsigned hashFun(const K&);
RWTValHashDictionary<K,V> dictionary(hashFun);

注 - 標準 C++ ライブラリがない場合は、ここで説明しているインタフェースを使用してください。標準 C++ ライブラリがある場合は、クラスリファレンスの説明にあるインタフェースを使用してください。

説明

このクラスは型 K のキーと型 V の値から成るディクショナリを表すもので、ハッシュテーブルを使用して実装されます。値の重複は可能ですが、キーの重複は許可されていません。

これは値にもとづくコレクションです。キーと値をハッシュバケットにコピーしたり取り出します。

パラメータ K と V は、それぞれテーブルに挿入されるキーの型と値の型とを表すもので、クラスまたは基本型です。クラス K と V には次のものが必要です。

コピーの意味の定義 (T::T(const T&) または同等のもの)
代入の意味の定義 (T::operator=(const T&) または同等のもの)

さらに、クラス K には次のものも必要です。

等価の意味の定義 (K::operator==(const K&))

新しいテーブルを作成するときは、型 K のユーザー提供のハッシュ関数をコンストラクタに用意する必要があります。K が Rogue Wave クラスの場合は、Rogue Wave オブジェクトのすべてがハッシュ値を返す方法を知っているので、この条件を満たすのは簡単です。実際には、クラス RWCString、RWDate、RWTime、および RWWString には、コンストラクタにそのまま提供できる hash と呼ばれる静的メンバー関数が含まれます。この関数には次のプロトタイプがあります。

 unsigned hFun(const K& a);

また、この関数はオブジェクト a の適切なハッシュ値を返さなければなりません。

値を見つけるには、まずキーをハッシュしてキーと値が存在するバケットを判定します。次にバケットを検索して、キーと等しい (等価演算子で判定) オブジェクトを見つけます。

テーブル内のバケットの初期数はコンストラクタで設定します。これにはデフォルト値があります。コレクション内のキーと値の対の数がバケット数よりずっと大きい場合は、バケットの検索が線形であるため効率が悪くなります。バケット数は、メンバー関数 resize() を呼び出して変更できます。しかしこの方法は、すべての項目を新しいバケットにコピーしなければならない上、すべてのキーを再ハッシュするので時間がかかります。

バケット数の変更を自動的に行いたいときは、このクラスのサブクラスを作成し、ユーザー専用の insert() および remove() 関数を実装して、必要に応じて resize() を実行させることができます。

持続性

なし

例

#include <rw/tvhdict.h>
#include <rw/cstring.h>
#include <rw/rwdate.h>
#include <rw/rstream.h>

main()  {
  RWTValHashDictionary<RWCString, RWDate>
birthdays(RWCString::hash);

  birthdays.insertKeyAndValue(
    "John",
    RWDate(12, "April", 1975)
  );
  birthdays.insertKeyAndValue("Ivan", RWDate(2, "Nov", 1980));

  // 別の構文
  birthdays["Susan"] = RWDate(30, "June", 1955);
  birthdays["Gene"] = RWDate(5, "Jan", 1981);

  // 誕生日を出力する
  cout << birthdays["John"] << endl;
  return 0;
}

プログラム出力:

April 12, 1975

公開コンストラクタ

RWTValHashDictionary<K,V>(unsigned (*hashKey)(const K&),
                       size_t buckets = RWDEFAULT_CAPACITY);

新しいハッシュディクショナリを作成します。第 1 引数は、型 K の項目 (キー) に対するユーザー定義ハッシュ関数へのポインタです。テーブルは最初 buckets 個のバケットから構成されますが、メンバー関数 resize() で変更できます。

RWTValHashDictionary<K,V>(const RWTValHashDictionary<K,V>&
                          dict);

コピーコンストラクタ。新しいハッシュディクショナリを dict のコピーとして構築します。新しいディクショナリは、前のテーブルと同じ数のバケットを持ちます。したがって、キーと値は新しいテーブルにコピーする必要がありますが、キーを再ハッシュしなくても構いません。

公開演算子

RWTValHashDictionary<K,V>&
operator=(const RWTValHashDictionary<K,V>& dict);

自分自身に dict のコピーを設定します。設定後、新しいテーブルは前のテーブルと同じ数のバケットを持ちます。したがって、キーと値は新しいテーブルにコピーする必要がありますが、キーを再ハッシュしなくても構いません。

V&
operator[](const K& key);

キー key を検索し、左辺値参照としてその値を返します。key がディクショナリ内にない場合はディクショナリに追加されます。この場合、対応する値は型 V のオブジェクトのデフォルトコンストラクタが提供します。

公開メンバー関数

void
applyToKeyAndValue(void (*applyFun)(const K&, V&,void*),
                   void* d);

ディクショナリ内のすべてのキーと値の対に対してユーザー定義関数 applyFun を適用します。この関数には次のプロトタイプが必要です。

   void yourFun(const K& key, V& value, void* d);

キーは定数参照渡しされるので変更できません。値は参照渡しされるので変更できます。クライアントデータをパラメータ d として引き渡すことができます。

void
clear();

コレクション内のすべての項目を取り除きます。

RWBoolean
contains(const K& key) const;

キー key と等しいキーがディクショナリ内にあれば TRUE を、なければ FALSE を返します。等しいかどうかは、クラス K のクラス定義の等価演算子で判定します。

size_t
entries() const;

現在、ディクショナリにあるキーと値の対の数を返します。

RWBoolean
find(const K& target, K& retKey) const;

キー target と等しいキーがディクショナリにあれば TRUE を返し、一致したキーを retKey にセットします。等しいキーがなければ FALSE を返し、retKey は変わりません。等しいかどうかは、クラス K のクラス定義の等価演算子で判定します。

RWBoolean
findValue(const K& key, V& retVal) const;

キー key と等しいキーがディクショナリにあれば TRUE を返し、対応する値を retVal にセットします。等しいキーがなければ FALSE を返し、retVal は変わりません。等しいかどうかは、クラス K のクラス定義の等価演算子で判定します。

RWBoolean
findKeyAndValue(const K& key, K& retKey,V& retVal) const;

キー key と等しいキーがディクショナリにあれば TRUE を返し、そのキーを retKey に、対応する値を retVal にそれぞれセットします。等しいキーがなければ FALSE を返し、retKey と retVal は変わりません。等しいかどうかは、クラス K のクラス定義の等価演算子で判定します。

void
insertKeyAndValue(const K& key, const V& value);

キー key と値 value をディクショナリに挿入します。

RWBoolean
isEmpty() const;

ディクショナリに項目がなければ TRUE を、あれば FALSE を返します。

RWBoolean
remove(const K& key);

key と等しいキーの (キーと値の) 対を取り除いて TRUE を返します。等しいキーがない場合は FALSE を返します。等しいかどうかは、クラス K のクラス定義の等価演算子で判定します。

void
resize(size_t N);

バケット数を N に変更します。コレクション内の項目が多いとかなり時間がかかります。