1

私の目標は、C++ テンプレート クラスで作成しているハッシュ テーブルの rehash() メソッドを実装することです。ただし、このメソッドは型をジェネリックとしてしか認識していないため、正確に何をハッシュできるか混乱しています。私の知る限り、これはJavaジェネリックとは異なります

Java についての私の理解... Java では、すべてのオブジェクトが hashCode() メソッドを継承するため、このメソッドをオーバーライドできます。Java で一般的なハッシュ テーブルを作成する場合、rehash() 中に hashCode() メソッドを呼び出すだけで値を返すことができます。これは tableSize で変更できます。無痛

C++ に戻ります... C++ ジェネリックで hashCode() メソッドを単純に呼び出すことも、ジェネリック型のデータ メンバーにアクセスすることもできないと思うので、何を再ハッシュできるかわかりません。

仮想 hashcode()=0 メソッドを強制できるように、C++ のジェネリック型が何らかの方法で抽象クラスを継承することは可能ですか? それとも、テンプレート クラスのハッシュ関数は、他の種類の非データメンバー ハッシュに依存していますか?

できるだけ明確にしようとしました。私を正しい方向に向けたり、ガイダンスを提供したりできる人に感謝します。

4

1 に答える 1

1

注:もちろん、ハッシュテーブルを実装するという目標は学習目的のためだと思います。そうでない場合は、 を使用しますstd::unordered_map。

ここで最も重要な点は、既に気づいたことです:テンプレートとジェネリックは同じものではありません。(まあ、Java ジェネリックは、型消去のおかげで、派手な構文シュガー ツールにすぎませんが、それは別の話です)。

C++ テンプレートは、テンプレートのさまざまなインスタンスごとにクラスのバージョンを記述して機能します。つまり、プログラムで と を使用する場合std::vector<int>、std::vector<bool>コンパイラは int 型のクラス vector と bool 型のクラス vector のコードを生成します。

テンプレートの最も強力な側面の 1 つは、すべての型関連の操作がコンパイル時に評価されることです。つまり、すべてのテンプレートのインスタンス化、エイリアス、typedef などはコンパイル時に行われます。実行時に取得するコードは、さまざまなテンプレート インスタンスに対して最終的に生成されたクラスを組み合わせたものです。したがって、Java や C# などの OO 言語のように、実行時に型について考えるのではなく、コンパイル時に考えます。コンパイルが終了したら、すべてを解決する必要があります。

ここで問題を見てみましょ
う。ハッシュテーブル内のハッシュ関数を呼び出すために、型に「ハッシュ可能な」「インターフェース」が必要です。これには、次の 2 つの方法があります。

メンバー関数ベースの方法:

hash()問題を解決する 1 つの方法は、型にpublic メンバー関数があると仮定することです( getHashCode()Java のように、Object から継承されます)。したがって、ハッシュテーブルの実装では、このハッシュ関数を要素にあるかのように使用します。渡された型について心配する必要はありません。実際、これを行う場合、パブリック ハッシュ メンバー関数を持たない型をテンプレート引数として渡すと、テンプレートをインスタンス化できません。ビオラ！テンプレートをコントラクトと
考えてください: テンプレートには完全に汎用的なコードを記述します。テンプレートに渡される型は、契約を満たす必要があります。つまり、あなたが彼らが持っていると思っていたものをすべて持っている必要があります。

このアプローチの問題は、ハッシュマップで使用されるすべての型がハッシュ パブリック メンバー関数を持たなければならないことです。この方法では、ハッシュマップで基本型を使用できないことに注意してください。

ファンクターベースの方法:

ファンクターは、関数として機能するクラスです。つまり、そのクラスのインスタンスを関数として使用できます。例えば：

template<typename T>
struct add
{
    T operator()(const T& a , const T& b)
    {
        return a + b;
    }
};

このファンクターは次のように使用できます。

int main()
{
   add<int> adder;

   int a = 1 , b = 2;
   int c = adder(a,b);
}

しかし、ファンクターの最も重要な使用法は、ファンクターがクラスのインスタンスであるため、引数として他のサイトに渡すことができることに基づいています。つまり、ファンクターは高レベルの関数ポインターとして機能します。

これは、次のような一般的な STL アルゴリズムでstd::find_if使用されます。Find if は、検索条件に基づいて、指定された間隔の要素を検索するために使用されます。その基準は、ブール述語として機能するファンクターで渡されます。例えば：

class my_search_criteria
{
   bool operator()(int element)
   {
      return element == 0;
   }
};  

int main()
{
    std::vector<int> integers = { 5 , 4 , 3 , 2 , 1 , 0 };

    int search_result = std::find_if( std::begin( integers ) , std::end( integers ) , my_search_criteria() );
}

しかし、ファンクターはどのように問題を解決できるのでしょうか?
ハッシュ関数として機能する汎用ファンクターを実装できます。

template<typename T>
struct hash
{
   unsigned int operator()(const T& element) 
   {
      return /* hash implementation */
   }
};

ハッシュテーブルクラスで使用します：

template<typename T>
class hachtable
{
private:
   hash<T> hash_function;
   std::vector<T> _container;

   void add(const T& element)
   {
      _container.insert(std::begin( _container ) + hash_function( element ) , element);
   }
};

要素の型に対してハッシュが実装されている必要があることに注意してください。C++ テンプレートを使用すると、テンプレートの特別な明示的なケースを作成できます。たとえば、ジェネリック配列クラスを作成し、要素の型がブール値である場合、ブール値を数値のビットとして格納すると、メモリ消費を削減できるため、より効率的であることに気付きました。C++ テンプレートを使用すると、その特殊なケースを作成できます。テンプレート引数として明示的な型を使用して、テンプレート クラスを明示的に記述します。これは「テンプレートの特殊化」として知られています。std::vector実際、その「ブールケースにビットを使用する」例は、まさに.

この場合、ハッシュ ファンクターの宣言があるとします。

template<typename T>
struct hash;

ハッシュマップで使用するすべてのタイプの特殊化が必要です。たとえば、unsigned int の特殊化は次のとおりです。

template<>
struct hash<unsigned int>
{
   unsigned int operator()(unsigned int element)
   {
       return element;
   }
};

ファンクタベースの方法は、C++ 標準ライブラリが行うこととまったく同じです。ハッシュ ファンクタ の定義があり、などのstd::hashハッシュ テーブルの実装で使用されますstd::unordered_map。ライブラリには、基本型の一連の組み込みハッシュ特殊化があることに注意してください。

于 2013-07-30T11:47:27.913 に答える