在完成了STL與泛型編程第一周的學(xué)習(xí)之后骂因，有一些總結(jié)和心得在這里通過(guò)學(xué)習(xí)筆記的方式分享出來(lái)炎咖，筆記我是跟著老師在視頻中所講的內(nèi)容按照順序記錄的，也不能說(shuō)是流水賬寒波，對(duì)課程中的一些問(wèn)題還是添加了自己的理解和分析乘盼，供也在學(xué)習(xí)C++的小伙伴用作學(xué)習(xí)交流，如有理解不到位的地方俄烁，歡迎批評(píng)指正绸栅。
上周對(duì)于STL，老師做了一個(gè)大概的介紹页屠，本周接著上周的內(nèi)容繼續(xù)學(xué)習(xí)了分配器以及各類容器的結(jié)構(gòu)與分類粹胯。
一．OOP與GP的區(qū)別
OOP（Object-Oriented programming）企圖將datas和methods關(guān)聯(lián)在一起
GP（Generic Programming）卻是將datas和methods分開來(lái)，如下圖所示：
采用GP卷中，Containerns和Algorithms兩個(gè)團(tuán)隊(duì)可以閉門造車矛双，其間以Iterator溝通即可。Algorithms通過(guò)Iterators確定操作范圍蟆豫，并通過(guò)Iterators取用Container中的元素议忽。
二．特化（Specialization）和偏特化（Partial Specialization）
C++源碼中運(yùn)用了大量的操作符重載（Operator Overloading）以及模板（Templates），操作符重載的相關(guān)規(guī)則這里就不再贅述十减，模板的運(yùn)用分為類模板（Class Templates）栈幸、函數(shù)模板（Function Templates）和成員模板（Member Templates）愤估，之前的課程有詳細(xì)講過(guò)，老師也進(jìn)行了復(fù)習(xí)速址，這里也不再贅述玩焰。
我的理解是，特化就是泛化的反面芍锚，常規(guī)的模板都是泛化的昔园，所謂特化，就是當(dāng)模板替代類型中的一個(gè)類型有它特有的處理方法時(shí)并炮，我們可以將template< >中的內(nèi)容抽離出來(lái)默刚，即為這個(gè)類型定義它特有的方法，如下代碼所示：
偏特化分為個(gè)數(shù)上的偏和范圍上的偏逃魄。
個(gè)數(shù)上的偏很好理解荤西，就是具有多個(gè)模板參數(shù)時(shí)，將一部分模板參數(shù)特化伍俘，其他模板參數(shù)保持泛化邪锌，如下代碼所示：
這里值得注意的是，特化部分參數(shù)只能從左至右特化癌瘾，也就是說(shuō)觅丰，不能第一個(gè)模板參數(shù)泛化，而將第二個(gè)模板參數(shù)特化妨退。
我理解的范圍上的偏就是模板參數(shù)的類型是一個(gè)指針舶胀，那么模板參數(shù)所代表的類型就是這個(gè)指針?biāo)赶虻念愋汀Ｈ缦麓a所示：
這里值得注意的是碧注，該指針指向什么由程序員自己定義嚣伐。
三．分配器（allocators）
分配器最重要的兩個(gè)函數(shù)：allocate（）和deallocate（）
VC6所附的標(biāo)準(zhǔn)庫(kù)，其分配器的實(shí)現(xiàn)只是以：：operator new（）和：：operator delete（）來(lái)完成allocate（）和deallocate（）萍丐，并沒(méi)有任何特殊的設(shè)計(jì)轩端。
而operator new（）和operator delete（）本質(zhì)上還是調(diào)用基本的內(nèi)存分配函數(shù)malloc（）和內(nèi)存釋放函數(shù)free（）：
BC++與VC6一樣，最終還是調(diào)用malloc（）和free（）逝变，并且也是分配512ints基茵，但是分配多少內(nèi)存就要還多少內(nèi)存，因此其接口設(shè)計(jì)非常不利于直接使用壳影。
G2.9并沒(méi)用使用分配器allocator拱层，而創(chuàng)造了另一個(gè)分配器alloc，
alloc的實(shí)現(xiàn)如下圖所示：
用鏈表的方式來(lái)分配內(nèi)存宴咧，盡量減少調(diào)用malloc的次數(shù)根灯，這樣程序運(yùn)行效率更高，節(jié)省了額外的開銷。
但是之后的G4.9并沒(méi)有使用這種高效率的alloc分配器（原因不得而知）烙肺，而是改用了new_allocator分配器纳猪，這又與之前提到的VC/BC一致了，本質(zhì)上還是調(diào)用malloc和free桃笙。但是G4.9所附的標(biāo)準(zhǔn)庫(kù)中氏堤，有許多extention allocators，其中_pool_alloc就是G2.9中的alloc
四．容器——結(jié)構(gòu)與分類
先來(lái)一張老師整理出的各種容器類型和所占字節(jié)數(shù)的圖：
1.容器list
List其實(shí)是一個(gè)環(huán)狀雙向鏈表搏明，用雙向指針串起來(lái)鼠锈，如下圖所示：
List的iterator是一個(gè)類，G2.9中星著，這個(gè)類與list是包含關(guān)系脚祟。
這里值得注意的是，除了array和vector之外强饮，所有容器的iterator都必須是class
之前說(shuō)到過(guò)GP的好處就是將data和algorithm分開，那么iterator就是它們之間的橋梁为黎，算法提出的問(wèn)題邮丰，iterator要必須都能回答，這是iterator必須遵循的原則铭乾。
Iterators的五個(gè)associated types：
①Iterator_category（）分類
②Difference_type（）距離
③Value_type（）指向值的類型
④Reference
⑤Pointer
后面兩個(gè)目前還未使用剪廉。
萃取機(jī)（Iterator Traits）用以分離class iterators（直接問(wèn)）和non-class iterators（間接問(wèn)）
加入中間層traits，利用偏特化回答non-class類型
2.容器vector
Vector是一種單向開口先進(jìn)后出的容器炕檩，它所占用的是連續(xù)內(nèi)存空間斗蒋，因此它不能原地?cái)U(kuò)充，一旦空間不夠笛质，它必須尋找新的空間擴(kuò)充泉沾，并且二倍增長(zhǎng)，整個(gè)搬離到新開辟的兩倍空間妇押。
Vector靠3根指針控制整個(gè)容器：
因其是占用連續(xù)內(nèi)存空間跷究，所以它的iterator不必設(shè)計(jì)成class
3.容器array
Arry跟vector一樣，也是占用連續(xù)的內(nèi)存空間敲霍，其iterator是native pointer
4.容器forward_list
Forward_list是一種線狀單向串列俊马，與雙向鏈表list差不多
