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

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

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::operator==(const 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` に変更します。その結果、コレクション内のオブジェクトのすべてが再ハッシュされます。