C++中簡單的hashmap實現

Question

我對C++比較陌生。在Java中，我很容易實例化並使用hashmap。我想知道如何在C++中以簡單的方式來完成它，因爲我看到了很多不同的實現，而且它們都不那麼簡單。

Answer 1

大多數編譯器應該爲你定義std::hash_map;在即將到來的C++0x標準中，它將作爲std::unordered_map的標準庫的一部分。其上的STL Page是相當標準的。如果您使用Visual Studio，Microsoft上有一個頁面。

如果你想使用你的類作爲值，而不是作爲鍵，那麼你不需要做任何特殊的事情。所有原始類型（例如int,char,bool乃至char *）應該「只是作爲」hash_map中的鍵。但是，對於其他任何事情，您將不得不定義自己的哈希和平等函數，然後編寫將它們包裝到類中的「函子」。

假設你的類被稱爲MyClass，並且您已經定義爲：

size_t MyClass::HashValue() const { /* something */ } 
bool MyClass::Equals(const MyClass& other) const { /* something */ } 

您需要定義兩個函子來包裝對象的方法。

struct MyClassHash { 
    size_t operator()(const MyClass& p) const { 
    return p.HashValue(); 
    } 
}; 

struct MyClassEqual { 
    bool operator()(const MyClass& c1, const MyClass& c2) const { 
    return c1.Equals(c2); 
    } 
}; 

和實例您hash_map/hash_set爲：

hash_map<MyClass, DataType, MyClassHash, MyClassEqual> my_hash_map; 
hash_set<MyClass, MyClassHash, MyClassEqual> my_hash_set; 

一切都應該工作之後，隨着預期。

Answer 2

嘗試助推的unordered類。

Answer 3

看看boost.unordered及其data structure。

Answer 4

在C++中使用hashmaps很簡單！這就像使用標準的C++地圖。您可以使用您的編譯器/庫實現unordered_map或使用boost或某個其他供應商提供的編譯器/庫實現。這是一個快速示例。你會發現更多，如果你按照你給的鏈接。

#include <unordered_map> 
#include <string> 
#include <iostream> 

int main() 
{ 
    typedef std::tr1::unordered_map< std::string, int > hashmap; 
    hashmap numbers; 

    numbers["one"] = 1; 
    numbers["two"] = 2; 
    numbers["three"] = 3; 

    std::tr1::hash<std::string> hashfunc = numbers.hash_function(); 
    for(hashmap::const_iterator i = numbers.begin(), e = numbers.end() ; i != e ; ++i) { 
     std::cout << i->first << " -> " << i->second << " (hash = " << hashfunc(i->first) << ")" << std::endl; 
    } 
    return 0; 
} 

Answer 5

退房Simple Hash Map (Hash Table) Implementation in C++與泛型類型鍵值對和分離鏈戰略的一個基本的哈希表。