1

私は持っています：

const unsigned int hash_1 = 0xaf019b0c;
const unsigned int hash_2 = 0xf864e55c;  
const unsigned int hash_3 = 0xfaea8ed5;

ハッシュは、自動生成されたヘッダーから取得されます。これらのハッシュは、タグ1、2、3に間接的に関連付けられています。タグは、コンパイル時に生成された単純なIDを介してクラスに関連付けられます。そうGetTag<Class1>()すれば、Class1のintタグを取得できます。

私の目標は、ハッシュ->タグの関連付けを単純化することです。できれば、これはコンパイル時とO（1）アクセス時に生成される必要があります。この場合のメモリは問題ではありません。サードパーティのソフトウェアを使用できません。

私は以下を試しました： 

template<uint32 t>  size_t GetTagByHash() { return 0; }

次のような特定の実装で： 

template<> size_t GetTagByHash<hash_1>() { return GetTag<Class1>(); }

しかし、この種の実装を使用するのは困難です。なぜならuint32 my_hash;、コンパイラがコンパイル時にどの値を持っているかをコンパイラが判別できないローカル変数がある場合、コンパイラはGetTagByHash()呼び出しの正しい実装を解決できないからです。

4

1 に答える 1

2

私が理解しているように、あなたの問題は、コンパイル時の値だけでなく、実行時の値を使用してこのルックアップを実行する方法です。

本当に2つの質問があります。まず、ルックアップを実行するためにどのアルゴリズムを使用しますか。次に、C ++にそれを実装するようにどのように指示しますか？

使用するアルゴリズムは、やや自明ではない質問です。事実上乱数のリストがあり、そのリストで何かを検索して、関連付けられたタグを返したいとします。おそらく、ある種のハッシュテーブルが必要ですが、最初に、より単純な例をいくつか示します。ハッシュの数が少ない場合は、次のようになります。擬似コードでの単純なO（N）ルックアップ：

if i = N return tag_N
else if i = N-1 ...
...
else if i = 1 return tag_1
else return tag_0

では、C ++にこれを行うようにどのように指示しますか？すべてのハッシュタグのリストとその手順を作成する必要があります。簡単な方法は次のとおりです。

template<int i> struct lookup
{
  int result(int j) { return 0; }
};

const unsigned int hash_1 = 0xaf019b0c;
template<> struct lookup<1>
{
  int result(int j)
  {
    if (j == hash_1)
      return GetTag<Class1>();
    return lookup<0>::result(j);
  }
};

const unsigned int hash_2 = 0xf864e55c;
template<> struct lookup<2>
{
  int result(int j)
  {
    if (j == hash_2)
      return GetTag<Class2>();
    return lookup<1>::result(j);
  }
};

などなど。そして、最後に、あなたは持つことができます

int hash_lookup(int j)
{
  return lookup<last_hash_number>::result(j);
}

ただし、これらの同一の定義をすべて書き出すのは面倒なので、C ++にそれを行わせるのが最善です。そのためには、ハッシュを繰り返し実行できるように定義する必要があります。そうしよう：

template<int> struct hash_tag {
  static const int value = 0;
  typedef type void;
};

#define SET_HASH(I, VALUE, CLASS)   \
template<> struct hash_tag<(I)>     \
{                                   \
  static const int value = (VALUE); \
  typedef type (CLASS);             \
}

SET_HASH(1, 0xaf019b0c, Class1);
SET_HASH(2, 0xf864e55c, Class2);
SET_HASH(3, 0xfaea8ed5, Class3);

// Define a general recursive lookup struct.
template<int i> struct lookup
{
  int result(int j)
  {
    if (j == hash_tag<i>::value)
      return GetTag<hash_tag<i>::type>;
    return lookup<i-1>::result(j);
  }
};

// Make sure the recursion terminates.
template<> struct lookup<0>
{
  int result(int) { return 0; }
};

次に、これを前と同じように使用します。

それでは、最初の質問に戻りましょう。ルックアップを実行するために実際にどのアルゴリズムを使用しますか？この反復O（N）ルックアップの利点は、プログラミングが簡単で、実行時にデータ構造を初期化する必要がないことです。これを呼び出すだけです。ただし、前述のように、O（N）です。別の選択肢は、std::mapオブジェクトを使用することです。同様の再帰的定義を使用して、実行時に初期化し、使用することができます。これは次のようになります。

// Make a typedef to save some typing.
typedef std::map<unsigned int, size_t> Map_type;
typedef std::pair<unsigned int, size_t> Map_value;

// Define a recursion to add hashes to the map.
template<int i> struct add_hash
{
  void add(Map_type& hashmap)
  {
    hashmap.insert(
      Map_value(hash_tag<i>::value, 
                GetTag<hash_tag<i>::type>));
    add_hash<i-1>::add(hashmap);
  }
};

// Make sure the recursion terminates.
template<> struct lookup<0>
{
  void add(Map_type&) {}
};

// Now, create a class to initialize the std::map and do lookup.
class Hash_lookup
{
  Hash_lookup() { add_hash<last_hash_number>(map_); }
  int result(unsigned int j) { return map_[j]; }
private:
  Map_type map_;
}

個人的には、これをあなたのGetTagByHash<>アイデアと組み合わせて、Hash_loopに、説明した「ランタイム計算結果」関数と、関数引数ではなくテンプレート引数を取る「コンパイル時計算結果」関数を与えると思います。 。ただし、一般的には、これがランタイムルックアップを実行するための基本的な考え方です。ルックアップする値を、コンパイル時に再帰的に反復できる一連のテンプレート化されたクラスに入れ、その再帰的な反復を使用して次のいずれかを定義します。ルックアップ関数を実行するか、ルックアップの実行に使用できるランタイム構造を初期化します。

于 2010-07-23T19:33:33.577 に答える