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-tag。

我的目标是简化 hash->tag 关联。最好这应该是编译时生成和 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

据我了解，您的问题是如何使用运行时值和编译时值进行此查找。

你真的有两个问题。首先，您想使用什么算法来进行查找，其次，您如何告诉 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 回答