在定義hash_map容器的時候,不僅需要指定鍵和值的類型,還需要指定hash函數和相等函數
(一)hash_map 的hash函數
hash< int>到底是什麼樣子?看看源碼:
struct hash{ size_t operator()(int __x) const { return __x; } };
原來是個函數對象。在SGI STL中,提供了以下hash函數:
struct hashstruct hash struct hash struct hash struct hash struct hash struct hash struct hash struct hash struct hash struct hash
也就是說,如果你的key使用的是以上類型中的一種,你都可以使用缺省的hash函數。當然你自己也可以定義自己的hash函數。對於自定義變量,你只能如此,例如對於string,就必須自定義hash函數。例如:
struct str_hash{ size_t operator()(const string& str) const { unsigned long __h = 0; for (size_t i = 0 ; i < str.size() ; i ++) __h = 5*__h + str[i]; return size_t(__h); } }; //如果你希望利用系統定義的字符串hash函數,你可以這樣寫: struct str_hash{ size_t operator()(const string& str) const { return __stl_hash_string(str.c_str()); } };
在聲明自己的哈希函數時要注意以下幾點:
(二)hash_map 的比較函數
在map中的比較函數,需要提供less函數。如果沒有提供,缺省的也是less< Key> 。在hash_map中,要比較桶內的數據和key是否相等,因此需要的是是否等於的函數:equal_to< Key> 。先看看equal_to的源碼:
//本代碼可以從SGI STL //先看看binary_function 函數聲明,其實只是定義一些類型而已。 templatestruct binary_function { typedef _Arg1 first_argument_type; typedef _Arg2 second_argument_type; typedef _Result result_type; }; //看看equal_to的定義: template struct equal_to : public binary_function<_Tp,_Tp,bool> { bool operator()(const _Tp& __x, const _Tp& __y) const { return __x == __y; } };
如果你使用一個自定義的數據類型,如struct mystruct, 或者const char* 的字符串,如何使用比較函數?使用比較函數,有兩種方法. 第一種是:重載==操作符,利用equal_to;看看下面的例子:
struct mystruct{ int iID; int len; bool operator==(const mystruct & my) const{ return (iID==my.iID) && (len==my.len) ; } };
這樣,就可以使用equal_to< mystruct>作為比較函數了。另一種方法就是使用函數對象。自定義一個比較函數體:
struct compare_str{ bool operator()(const char* p1, const char*p2) const{ return strcmp(p1,p2)==0; } };
有了compare_str,就可以使用hash_map了。
typedef hash_map, compare_str> StrIntMap; StrIntMap namemap; namemap["岳不群"]="華山派掌門人,人稱君子劍"; namemap["張三豐"]="武當掌門人,太極拳創始人"; namemap["東方不敗"]="第一高手,葵花寶典";
(三)如何在hash_map中加入自己定義的類型?
#include#include #include using namespace std; //define the class class ClassA{ public: ClassA(int a):c_a(a){} int getvalue()const { return c_a;} void setvalue(int a){c_a;} private: int c_a; }; //1 define the hash function struct hash_A{ size_t operator()(const class ClassA & A)const{ // return hash (classA.getvalue()); return A.getvalue(); } };
//2 define the equal function struct equal_A{ bool operator()(const class ClassA & a1, const class ClassA & a2)const{ return a1.getvalue() == a2.getvalue(); } }; int main() { hash_maphmap; ClassA a1(12); hmap[a1]="I am 12"; ClassA a2(198877); hmap[a2]="I am 198877"; cout<