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

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

RWTPtrHashTable<T>

形式 

#include <rw/tphasht.h>
unsigned hashFun(const T&);
RWTPtrHashTable<T> table(hashFun);
注 - 標準 C++ ライブラリがない場合は、ここで説明しているインタフェースを使用してください。標準 C++ ライブラリがある場合は、クラスリファレンスの説明にあるインタフェースを使用してください。

説明

このクラスは、型 T のパラメータ化されたハッシュテーブルを実装します。チェーンを使用してハッシュの衝突を避けています。項目の重複は許可されています。

このクラスはポインタにもとづくコレクションです。ハッシュバケット・オブジェクトへのポインタをコピーしたり取り出します。

パラメータ T は、テーブルに挿入されるオブジェクトの型を表すもので、クラスまたは組み込み型です。クラス T には次のものが必要です。

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

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

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

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

以上の処理を自動的に行いたい場合は、このクラスからサブクラスを作成し、必要に応じて resize() を実行するユーザー専用の insert() および remove 関数を実装することができます。

持続性

なし

例 

#include <rw/tphasht.h>
#include <rw/cstring.h>
#include <rw/rstream.h>

main()  {
  RWTPtrHashTable<RWCString> table(RWCString::hash);
  RWCString *states[4] = { new RWCString("Alabama"),
                           new RWCString("Pennsylvania"),
                           new RWCString("Oregon"),
                           new RWCString("Montana") };

  table.insert(states[0]);
  table.insert(states[1]);
  table.insert(states[2]);
  table.insert(states[3]);

  RWCString key("Oregon");
  cout << "The table " <<
    (table.contains(&key) ? "does " : "does not ") <<
    "contain Oregon\n";

  table.removeAll(&key);
  cout << "Now the table " <<
    (table.contains(&key) ? "does " : "does not ") <<
    "contain Oregon";

  delete states[0];
  delete states[1];
  delete states[2];
  delete states[3];
  return 0;
}

プログラム出力: 

The table does contain Oregon
Now the table does not contain Oregon

公開コンストラクタ 

RWTPtrHashTable<T>(unsigned (*hashFun)(const T&),
                       size_t buckets = RWDEFAULT_CAPACITY);

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

RWTPtrHashTable<T>(const RWTPtrHashTable<T>& c);

新しいハッシュテーブルを、c のシャローコピーとして作成します。作成後、ポインタは 2 つのコレクション間で共有されます。新しいオブジェクトは c と同じ数のバケットを持ちます。したがって、キーを再ハッシュしません。

公開演算子 

RWTPtrHashTable&
operator=(const RWTPtrHashTable<T>& c);

自分自身に c のシャローコピーを設定します。設定後、ポインタは 2 つのコレクション間で共有されます。自分自身は c と同じ数のバケットを持ちます。したがって、キーは再ハッシュしません。

公開メンバー関数 

void
apply(void (*applyFun)(T*, void*), void* d);

テーブル内のすべての項目に対してユーザー定義関数 applyFun を適用します。この関数には次のプロトタイプが必要です。 

    void yourFun(T* a, void* d);

クライアントデータをパラメータ d として引き渡すことができます。項目に対し、ハッシュ値を変えるような変更を行わないでください。 

void
clear();

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

void
clearAndDestroy();

コレクション内のすべての項目を取り除き、それぞれのデストラクタを呼び出します。 

RWBoolean
contains(const T* p) const;

項目 p と等しい項目がコレクション内にあれば TRUE を、なければ FALSE を返します。等しいかどうかは、型 T に対するクラス定義の等価演算子で判定します。 

size_t
entries() const;

現在、コレクション内にある項目の数を返します。 

T*
find(const T* target) const;

オブジェクト target と等しいオブジェクトへのポインタを返します。等しいオブジェクトがなければ NULL を返します。等しいかどうかは、型 T に対するクラス定義の等価演算子で判定します。 

void
insert(T* a);

オブジェクト a をコレクションに追加します。 

RWBoolean
isEmpty() const;

コレクションに項目がなければ TRUE を、あれば FALSE を返します。 

size_t
occurrencesOf(const T* a) const;

コレクション内のオブジェクト a と等しいオブジェクトの数を返します。等しいかどうかは、型 T のクラス定義の等価演算子で判定します。 

T*
remove(const T* a);

オブジェクト a と等しいオブジェクトを取り除き、そのオブジェクトへのポインタを返します。等しいオブジェクトがない場合は NULL を返します。等しいかどうかは、型 T に対するクラス定義の等価演算子で判定します。 

size_t
removeAll(const T* a);

オブジェクト a と等しいオブジェクトをすべて取り除き、そのオブジェクトの数を返します。等しいかどうかは、型 T に対するクラス定義の等価演算子で判定します。 

void
resize(size_t N);

バケット数を N に変更します。その結果、コレクション内のオブジェクトのすべてが再ハッシュされます。