動態散列>類標籤

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一個「運行時計算的結果」功能，因爲我所描述的，還有一個「編譯時計算結果「函數，它採用模板參數而不是函數參數。但是，一般來說，這是執行運行時查找的基本思路 - 將希望查看的值放入一組可在編譯時遞歸迭代的模板化類中，然後使用該遞歸迭代來定義查找函數或初始化可用於執行查找的運行時結構。