體系結(jié)構(gòu)與內(nèi)核分析第四講
萬(wàn)用的hash function
hash function就是把任意長(zhǎng)的輸入字符串變化成固定長(zhǎng)的輸出字符串的一種函數(shù)风皿。輸出字符串的長(zhǎng)度稱(chēng)為hash函數(shù)的位數(shù)。
使用以hash table為底層的容器時(shí)铛绰，必須要為放的元素寫(xiě)一個(gè)hash function。在計(jì)算機(jī)編程里面瓦宜，所有的data也是由原始的整數(shù)峡眶、浮點(diǎn)數(shù)覆山、字符串組成的，基本的數(shù)值型這些本身都有hash function端幼，他們的hash function傳回來(lái)的就是自己礼烈。有沒(méi)有可能把一個(gè)設(shè)計(jì)出來(lái)的數(shù)據(jù)結(jié)構(gòu)，一個(gè)元素婆跑，把它拆分開(kāi)來(lái)此熬，然后把它各自的hash code（hash function產(chǎn)生hash code）加起來(lái)，就變成這個(gè)元素的hash code滑进。hash function是將產(chǎn)生的hash code做到越亂越好犀忱，不要重復(fù)。將每個(gè)hash code相加太過(guò)天真：元素容易碰撞扶关，每個(gè)籃子掛的元素多阴汇，查找慢。從TR1開(kāi)始有了下面1234幫你寫(xiě)hash function节槐。typename...表示可以接受任意多的模板參數(shù)搀庶。
hash function設(shè)計(jì)原則：產(chǎn)生的hash code盡可能減少?zèng)_突， 使元素能夠盡可能多的落在不同的籃子里铜异。
計(jì)算hash code時(shí)哥倔，0x9e3779b9是借用的黃金比例。
hash function的寫(xiě)法形式有三種：
1.形式1模板參數(shù)只需要填元素類(lèi)型和函數(shù)類(lèi)型就可以揍庄，自動(dòng)產(chǎn)生函數(shù)對(duì)象被調(diào)用咆蒿。
2.形式2模板參數(shù)需要填元素類(lèi)型和函數(shù)類(lèi)型，創(chuàng)建容器時(shí)候還要把真正的函數(shù)地址放進(jìn)來(lái)。
3.第三種實(shí)現(xiàn)形式是通過(guò)對(duì)自己的元素作一個(gè)偏特化版本實(shí)現(xiàn)hash function沃测。G4.9以后有了string的偏特化版本缭黔。
代碼：
#include
class Customer {
...
};
//-------------------------形式1成員函數(shù)---------------------
class CustomerHash
{
public:
std::size_t operator()(const Customer& c) const {
return...
};
//-----------------------------------------------------------
unordered_set custset;
//-------------------------形式2一般函數(shù)---------------------
size_t customer_hash_func(const Customer& c){
return...
};
//-----------------------------------------------------------
unordered_set
custset(20,customer_hash_func);
unordered_set兩種使用方法：一種是針對(duì)需要存放的元素類(lèi)型，定義泛函數(shù)蒂破。另一種是定義一個(gè)hash_function试浙。
tuple
C++11中的tuple（元組）是一個(gè)固定大小的不同類(lèi)型值的集合，是泛化的std::pair寞蚌。我們可以把他當(dāng)做一個(gè)通用的結(jié)構(gòu)體來(lái)用田巴，不需要?jiǎng)?chuàng)建結(jié)構(gòu)體又獲取結(jié)構(gòu)體的特征，在某些情況下可以取代結(jié)構(gòu)體使程序更簡(jiǎn)潔挟秤，直觀壹哺。tuple可以指定任意類(lèi)型元素。
eg. tuple> t; //sizeof(t) = 32.艘刚？
tuple t1(41, 6.3, "nice");
get<0>(t1)取t1的第0個(gè)元素管宵。get<1>(t1)取t1的第1個(gè)元素...
auto t2 = make_tuple(22, 44, "stacy"); //創(chuàng)建一個(gè)tuple,并寫(xiě)入元素。
get<1>(t1) = get<1>(t2); //assign value
tuple之間可以比較大小攀甚。
tie綁定箩朴，將tuple中對(duì)應(yīng)的各個(gè)元素綁定到tie中。
tuple_size獲取tuple中value個(gè)數(shù)秋度。
tuple_element獲取tuple中第幾個(gè)元素的類(lèi)型炸庞。
tuple會(huì)自動(dòng)遞歸，把元素分隔為head和tail, tail會(huì)再分隔為head和tail, 直到tail只有一個(gè)元素為止荚斯。層層繼承埠居， tail作為基類(lèi)，head作為數(shù)據(jù)成員事期。
type traits 類(lèi)型萃取器
type_traits：回答class中的默認(rèn)構(gòu)造滥壕、拷貝構(gòu)造、拷貝賦值兽泣、析構(gòu)函數(shù)重要不重要绎橘、是否是POD(plain old data, c風(fēng)格的結(jié)構(gòu)，沒(méi)有成員函數(shù))等唠倦，默認(rèn)是false称鳞。對(duì)于自己定義的類(lèi)型，可以自己定義__type_traits的特化版本牵敷。泛化版本（默認(rèn)）六個(gè)typedef胡岔。
設(shè)計(jì)一個(gè)復(fù)數(shù)法希，有實(shí)部和虛部枷餐，不必為他寫(xiě)析構(gòu)函數(shù)、拷貝構(gòu)造函數(shù)苫亦、拷貝賦值函數(shù)毛肋，因?yàn)椴粚?xiě)的話編譯器有一個(gè)默認(rèn)版本怨咪。
使用：string的析構(gòu)函數(shù)不是虛函數(shù)，string的設(shè)計(jì)上是不打算讓用戶(hù)繼承的润匙。has_virtual_destructor是0.诗眨，is_polymorphic（是否有多態(tài)）是0。
Zoo(const Zoo&) = delete; 不要編譯器默認(rèn)的孕讳。
Zoo(Zoo&&) = default; 要編譯器默認(rèn)的搬移構(gòu)造函數(shù)匠楚， 和用戶(hù)不寫(xiě)意義相同。
Zoo& operator=(const Zoo&) = default;
Zoo& operator=(const Zoo&&) = delete; //不要編譯器默認(rèn)的搬移賦值函數(shù)厂财。
萃取器可以得知以上這四個(gè)函數(shù)是否需要編譯器給的芋簿。
traits實(shí)現(xiàn)原理
is_void的實(shí)現(xiàn)：is_void類(lèi)模板繼承自__is_void_helper類(lèi)模板，首先對(duì)類(lèi)型去除const璃饱、volatile（多線程用到与斤，易揮發(fā)）屬性，用remove_cv函數(shù)實(shí)現(xiàn)荚恶，remove_const和remove_volatile各用一個(gè)泛化和偏特化版本的函數(shù)來(lái)使得傳入的是否有const（volatile）都會(huì)去掉這兩個(gè)撩穿。再傳給__is_void_helper，利用它的泛化和特化void谒撼，判斷是否是void食寡。
is_integral的實(shí)現(xiàn)：也是先除去const和volatile屬性，再利用__is_integral_helper的泛化和偏特化判斷廓潜，如果不是和某種特化版本匹配的類(lèi)型冻河，那么就會(huì)使用泛化版本，泛化版本的回答是false茉帅。
有些type_traits的實(shí)現(xiàn)找不到源代碼叨叙，是由編譯器實(shí)現(xiàn)的。
cout是一個(gè)類(lèi)的對(duì)象堪澎，extern表示cout可以被外界看到擂错，它能接受這么多類(lèi)型是因?yàn)樗髁舜罅康?lt;<重載。如果你想寫(xiě)自己的類(lèi)型樱蛤，那么就要仿照寫(xiě)出<<的重載钮呀。sub_match對(duì)正則表達(dá)式的輸出。
moveable元素
moveable元素對(duì)于容器速度效能的影響：
分別用moveable和non-moveable以insert的方式放進(jìn)來(lái)昨凡，紅黑樹(shù)和哈希表的容器爽醋，你只要insert，那么它就會(huì)落在該落的地方便脊，但是vector蚂四、list、deque你要insert必須要告訴它哪里insert。stl里的insert提供插入位置選擇遂赠，但對(duì)于關(guān)聯(lián)式容器久妆，就算指定插入位置，如果不合理跷睦，他還是落在它應(yīng)該落在的地方筷弦。
兩種拷貝方式：
eg. M c11(c1);
M c12(std::move(c1));
vector放三百萬(wàn)個(gè)元素，而拷貝構(gòu)造函數(shù)卻調(diào)用了七百多萬(wàn)次抑诸，是因?yàn)関ector的成長(zhǎng)是兩倍兩倍的烂琴，在成長(zhǎng)的過(guò)程中引發(fā)拷貝構(gòu)造。如果一開(kāi)始指定有足夠大的vector蜕乡，就不會(huì)有這么大的拷貝構(gòu)造监右。
1.moveable和non-moveable的效率差別很大，2.move copy和copy效率差別很大异希。
list健盒、deque、關(guān)聯(lián)式容器放三百萬(wàn)個(gè)元素称簿，拷貝構(gòu)造也調(diào)用三百萬(wàn)次扣癣，這是因?yàn)樗麄儾幌駐ector是連續(xù)的內(nèi)存空間。
雖然list憨降、deque父虑、關(guān)聯(lián)式容器一開(kāi)始放元素moveable和non-moveable的效率差別不大，但是后來(lái)的操作也會(huì)影響授药。
string是具有moveable的功能士嚎。
