动态散列>类标签

Question

我有：

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标记。

我的目标是简化hash->标签关联。最好这应该是编译时生成和O（1）访问时间。这种情况下的内存不是问题。我无法使用任何第三方软件。

我曾尝试以下：

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

与像具体实现：

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

但那种落实很难使用，因为如果我有一个局部变量uint32 my_hash;编译器可以不确定它在编译时具有什么价值，那么编译器无法解析调用GetTagByHash()的正确实现。

Answer 1

据我所知，你的问题是如何使用运行时间值和编译时间值进行查找。

你真的有两个问题。首先，你想用什么算法来进行查找，其次，你如何告诉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一个“运行时计算的结果”功能，因为我所描述的，还有一个“编译时计算结果“函数，它采用模板参数而不是函数参数。但是，一般来说，这是执行运行时查找的基本思路 - 将希望查看的值放入一组可在编译时递归迭代的模板化类中，然后使用该递归迭代来定义查找函数或初始化可用于执行查找的运行时结构。