[c++11]hash<T>哈希結構模板

2019-11-08 02:38:48

字體：大中小

來源：轉載

供稿：網友

一、哈希結構模板hash簡介

c++11新增的哈希結構模板定義于頭文件 <functional>：

template<class _Kty>struct _Bitwise_hash : public unary_function<_Kty, size_t>{...};

哈希結構模板定義一個函數對象（重載了Operator()），實現了散列函數: 1.接受一個參數的類型Key 2.返回一個類型為size_t的值，表示該參數的哈希值 3.調用時不會拋出異常 4.若兩個參數k1k2相等，則hash<Key>()(k1) == hash<Key>()(k2) 5.若兩個不同的參數k1k2不相等，則hash<Key>()(k1) == hash<Key>()(k2)成立的概率應非常小，接近1.0/std::numeric_limits<size_t>::max()

無序關聯容器unordered_set，unordered_multiset，unordered_map和unordered_multimap默認使用哈希結構模板來為鍵計算散列值。

二、成員

成員類型

`argument_type`	模板第一個類型參數
`result_type`	`size_t`

公有成員方法

默認構造函數	構造一個哈希函數對象
`size_t operator()(T &t)`	計算t的散列值

三、擴展和應用

在頭文件里，實例化了內置類型的哈希結構模板：

template<> struct hash<bool>;template<> struct hash<char>;template<> struct hash<signed char>;template<> struct hash<unsigned char>;template<> struct hash<char16_t>;template<> struct hash<char32_t>;template<> struct hash<wchar_t>;template<> struct hash<short>;template<> struct hash<unsigned short>;template<> struct hash<int>;template<> struct hash<unsigned int>;template<> struct hash<long>;template<> struct hash<long long>;template<> struct hash<unsigned long>;template<> struct hash<unsigned long long>;template<> struct hash<float>;template<> struct hash<double>;template<> struct hash<long double>;template< class T > struct hash<T*>;

C++11實例化了字符串的哈希結構模板

std::hash<std::string>std::hash<std::u16string>std::hash<std::u32string>std::hash<std::wstring>

C++11，std::error_code的哈希支持

std::hash<std::error_code>

C++11實例化的其他哈希結構模板

std::hash<std::bitset>std::hash<std::unique_ptr>std::hash<std::shared_ptr>std::hash<std::type_index>std::hash<std::vector<bool>>std::hash<std::thread::id>

四、代碼示例

IDE：vs2013

#include <iostream>#include <functional>//#include <string>#include <stdlib.h>using std::hash;//using std::string;using std::cout;//自定義類型class S {public: string first_name; string last_name;};//自己封裝一個哈希函數對象的類型，內部使用了hash結構模板class MyHash {public: size_t operator()(const S &s) const { size_t h1 = hash<string>()(s.first_name); size_t h2 = hash<string>()(s.last_name); return h1 ^ (h2 << 1); }};//也可以用自定義類實例化一個hash結構模板template<>class hash < S > {public: size_t operator()(const S &s) const { size_t h1 = hash<string>()(s.first_name); size_t h2 = hash<string>()(s.last_name); return h1 ^ (h2 << 1); }};int main(){ cout << "計算string的散列值的示例：/n"; string str = "Meet the new boss..."; hash<string> hash_fn; size_t str_hash = hash_fn(str); cout << str_hash << '/n'; cout << "/n計算自定義類型S的散列值的示例：/n"; string s1 = "Hubert"; string s2 = "Farnsworth"; hash<string> h1; S obj_S; obj_S.first_name = s1; obj_S.last_name = s2; cout << "hash(s1) = /t" << h1(s1) << "/n" << "hash(s2) = /t" << hash<string>()(s2) << "/n" << "MyHash(obj_S) = " << MyHash()(obj_S) << "/n" << "hash(obj_S) = /t" << hash<S>()(obj_S) << "/n"; ::system("pause"); return 0;}

輸出：運行結果輸出