1.一個萬用的hash function
在之前的課程中，我們知道以Hash Table為底層的容器過程（如unordered_map）翔忽，在使用過程中辆脸，必須要有一個hash function來為每一個元素生成一個hash code作為元素在哈希表中的key臂聋，也就是元素在哈希表中的具體位置告材。對于一些build-in類型（比如字符串），標準庫自帶hash function步鉴，但是對于自定義類型來說揪胃，這個函數(shù)該如何定義璃哟？我們能否找到一個通用的方法，實現(xiàn)hash code的計算呢喊递？
自定義類型沮稚，都是由基本類型組成，我們可以將它其中的各個基本數(shù)據(jù)類型分開計算出册舞，然后將其相加（當(dāng)然這是比較天真的方法）。先看看這種方法的實現(xiàn)代碼：
class CustomerHash
{
public:
std::size_t operator()(const Customer& c) const{
return std::hash<std::string>()(c.fname)
+ std::hash<std::string>()(c.Iname)
+ std::hash<long><c.no);
}
}
這個方法可以實現(xiàn)出計算Hash code障般，但是因為這個方法只是簡單的相加hash code调鲸，因此hash code的重復(fù)概率比較高進而會導(dǎo)致籃子中的元素過多，影響查詢的效率挽荡。
在了解其他方法之前藐石，先介紹一下hash function的三種定義型式：
型式1：
#include<functional>
class Customer{
//........
};
class CustomerHash
{
public:
std::size_t operator()(const Customer& c) const{
return /*........*/;
}
};
unordered_set<Customer, CustomerHash> customers;
型式2：
size_t customer_hash_func(const Customer& c)
{
return /*......*/;
}
unorder_set<Customer, size(*) (const Cunstomer&)> customers(20， customer_hash_func);
型式3：
通過偏特化來實現(xiàn)
class MyString
{
private:
char* _data;
size_t _len;
};
namespace std;
{
template<>
struct hash<MyStrinng>
{
size_t operatoe()(const MyString& s) const noexcept{
return hash<string>()(string(s.get()));
}
}
}
通過以上三種型式可以指定我們需要的hash function定拟，但是能否能有一個萬用的hash function來實現(xiàn)自定義類型的hash code的計算于微？
在C++ TR1版本及以后，STL為我們提供了一個萬用的hash function青自，它是如何實現(xiàn)的呢株依？
具體調(diào)用代碼如下：
class CustomerHash
{
public:
std::size_t operator()(const Cunstomer& c) const {
return hash_val(c.fname, c,Iname, c.no);
}
}
接下來看看它的實現(xiàn)代碼，具體如下：
//auxiliary generic funtions
template<typename... Types>
inline size_t hash_val(const Types&... args){
size_t seed = 0;
hash_val(seed, args...);
return seed;
}
template<typename T, typename... Types>
inline void hash_val(size_t& seed, const T& val, const Type&... args){
hash_combine(seed, val);
hash_val(seed, args...);
}
#include<functional>
template<typename T>
inline void hash_combine(size_t& seed, const T& val){
seed = std::hash<T>(val) + 0x9e3779b9
+ (seed << 6) + (seed >> 2);
}
//auxiliary generic funtions
template<typename T>
inline void hash_val(size_t& seed, const T& val){
hash_combine(seed, val);
}
這種方法和之前提到的簡單相加的方法相比延窜，更加的巧妙恋腕，它使用了C++11中的variadic templates，可以傳入多個模板逆瑞，傳入函數(shù)中的每個參數(shù)都有一個模板荠藤，對不同類型的參數(shù)會有不同的解決方案，也就是會傳入不同的函數(shù)获高。
由上圖可知哈肖，在①中加入了seed（最終被視為hash code），從而使得模板變成1+n的形式念秧，通過遞歸調(diào)用②中的hash_val函數(shù)淤井，不斷調(diào)用④中的hash_combine函數(shù)來改變seed，同時減少接收的參數(shù)出爹，最終遞歸結(jié)束時變成1+1的形式庄吼，調(diào)用③中的hash_val函數(shù)，也會調(diào)用④中的hash_combine函數(shù)严就，最終確認seed值总寻，也就是算出最后的hash code。
其中④中的hash_combine函數(shù)中的0x9e3779b9屬于黃金比例中的一部分：
2.tuple
tuple是元之組合梢为，數(shù)之組合的意思渐行，它是C++2.0之后引進的一種存放各種不同類型元素的集合轰坊。
tuple的使用方法如下：
tuple實現(xiàn)的原理，以Gnu4.8為例：
它是通過繼承的方法來不斷地剔除第一個參數(shù)祟印，最終來實現(xiàn)對每一個元素的操作肴沫。
3.type traits
type traits（類型萃取機）能有效地分辨類是否具有某種類型，通過調(diào)用它我們可以實現(xiàn)對不同的類型指定不同的操作蕴忆。
在Gnu2.9中的實現(xiàn)代碼如下：
struct __true_type{};
struct __false_type{};
//泛化
template<class type>
struct __type_traits{
typedef __true_type this_dummy_member_must_be_first;
typedef __false_type has_trivial_default_constructor;
typedef __false_type has_trivial_copy_constructor;
typedef __false_type has_trivial_assignment_operator;
typedef __false_type has_trivial_destructor;
typedef __false_type is_POD_type; //POD = Plain Old Data颤芬，代表舊式的class 也就是struct
}；
//int的特化
template<>
struct __type_traits<int>{
typedef __true_type has_trivial_default_constructor;
typedef __true_type has_trivial_copy_constructor;
typedef __true_type has_trivial_assignment_operator;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
}
//double的特化
template<>
struct __type_traits<double>{
typedef __true_type has_trivial_default_constructor;
typedef __true_type has_trivial_copy_constructor;
typedef __true_type has_trivial_assignment_operator;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
}
上面的type traits是依靠模板的泛化和特化的版本來實現(xiàn)套鹅。
從C++11開始站蝠，type traits的特性變得更為強大和復(fù)雜。
type traits的實現(xiàn)
萬變不離其宗卓鹿，通過模板的泛化和特化菱魔，我們可以實現(xiàn)各種操作。
（1）is_void
（2）is_integral
（3）is_class吟孙，is_union澜倦，is_enum，is_pod
（4）is_move_assignable
4.cout
Gnu2.9：
Gnu4.9：
5.moveable元素對容器的影響
5.1對vctor影響
5.2對list影響
5.3對deque影響
5.4對multiset影響
5.5對unordered_multiset影響
5.6寫一個moveable class
