STL標(biāo)準(zhǔn)庫與泛型編程（侯捷）
本文是學(xué)習(xí)筆記，僅供個(gè)人學(xué)習(xí)使用。如有侵權(quán)，請聯(lián)系刪除。
參考鏈接
Youbute: 侯捷-STL標(biāo)準(zhǔn)庫與泛型編程
B站: 侯捷 - STL
Github:STL源碼剖析中源碼 https://github.com/SilverMaple/STLSourceCodeNote/tree/master
Github:課程ppt和源碼 https://github.com/ZachL1/Bilibili-plus
下面是第二講的部分筆記：C++標(biāo)準(zhǔn)庫體系結(jié)構(gòu)與內(nèi)核分析（第二講）
主要介紹分配器allocator，還有容器list的底層實(shí)現(xiàn)，討論iterator traits的設(shè)計(jì)
8 源代碼之分布 VCGcc
學(xué)這門課應(yīng)該有的基礎(chǔ)：
C++基本語法
模板基礎(chǔ)
數(shù)據(jù)結(jié)構(gòu)和算法的基礎(chǔ)
9 OOP 面向?qū)ο缶幊?vs GP 泛型編程
面向?qū)ο笙胍裠ata和method關(guān)聯(lián)在一起，比如list類內(nèi)部實(shí)現(xiàn)sort函數(shù)。
泛型編程想要把data和method分開來，比如vector和deque類沒有實(shí)現(xiàn)sort函數(shù)，而是調(diào)用algorithm里面的sort函數(shù)，兩者分開來。
10 技術(shù)基礎(chǔ)：操作符重載and模板泛化, 全特化, 偏特化
這部分在侯捷老師的面向?qū)ο笳n程里有詳細(xì)的介紹，請參考筆者的筆記，里面含有課程的視頻鏈接。
C++面向?qū)ο蟾呒?jí)編程（侯捷）筆記1
C++面向?qū)ο蟾呒?jí)編程（侯捷）筆記2
C++程序設(shè)計(jì)兼談對(duì)象模型（侯捷）筆記
這里補(bǔ)充type_traits里面用到的特化（specialization）的知識(shí)
泛化指的是用模板，特化指的是指定模板到具體的類型。下面的代碼中__STL_TEMPLATE_NULL指的是 template<> 這種類型，表示空模板。
//type_traits.h文件
// 泛化
template <class _Tp>
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;
};
// 特化
__STL_TEMPLATE_NULL 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;
};
__STL_TEMPLATE_NULL struct __type_traits<unsigned 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;
};
下圖中的allocator這個(gè)類也是用到了泛化和特化，比如當(dāng)allocator指定的是void類型的時(shí)候，會(huì)調(diào)用特化版本的代碼。
偏特化：有多個(gè)模板參數(shù)，只指定部分個(gè)參數(shù)為特定類型。比如下圖中的vector的類型T指定為bool，而后面的Alloc分配器沒有指定類型，這就是一種偏特化。是一種個(gè)數(shù)的偏特化。
另外下圖中iterator_traits中也用到了偏特化，只不過這里是對(duì)指針類型的一個(gè)偏特化，如果傳入的是T*，會(huì)有一種處理方式。這種偏特化是范圍的偏特化，指的是從T類型，范圍縮到T *指針類型。
11 分配器
分配器 allocators
先談operator new() 和malloc()
malloc的內(nèi)存實(shí)際分配情況：
下圖中的內(nèi)存分配，藍(lán)色是塊是實(shí)際我們需要malloc給我們分配的空間，灰色的塊是debug mode需要添加的內(nèi)存空間，上下兩個(gè)紅色的塊是cookie，它記錄分配內(nèi)存的大?。ā渡疃忍剿鱟++對(duì)象模型》書上稱為記錄元素的大小，這個(gè)指的是delete時(shí)，該delete多大的內(nèi)存空間，即delete掉的數(shù)組維度大?。G色的部分指的是為了內(nèi)存大小的對(duì)齊。
STL對(duì)allocator的使用
VC++6編譯器所附的標(biāo)準(zhǔn)庫
allocator分配內(nèi)存的時(shí)候，調(diào)用operator new，而operator new調(diào)用c語言的malloc。
而釋放內(nèi)存的時(shí)候，調(diào)用operator delete，而operator delete調(diào)用c語言的free。
測試，分配512個(gè)int型數(shù)據(jù)：需要指定分配的大小，釋放時(shí)也要指定大小
// VC的allocate第二個(gè)參數(shù)沒有默認(rèn)值，需要自己給定，任意值都行
int* p = allocator<int>().allocate(512, (int *)0); // allocator<int>()是一個(gè)臨時(shí)對(duì)象
allocator<int>().deallocate(p, 512);
BC5編譯器所附的標(biāo)準(zhǔn)庫對(duì)allocator的使用
_RWSTD_COMPLEX_DEFAULT(a)就是a
所以可以看到下面的分配器用的就是allocator
那么BC5編譯器對(duì)于allocator的內(nèi)部設(shè)計(jì)呢？分配內(nèi)存和回收內(nèi)存用的還是operator new和operator delete，底部還是用c語言的malloc和free完成，和VC6的實(shí)現(xiàn)別無二致。
接著示范BC5分配器的使用
測試，分配512個(gè)int型數(shù)據(jù)：需要指定分配的大小，釋放時(shí)也要指定大小
// BC的allocate第二個(gè)參數(shù)有默認(rèn)值為0
int* p = allocator<int>().allocate(512); // allocator<int>()是一個(gè)臨時(shí)對(duì)象
allocator<int>().deallocate(p, 512);
GNU C++（G++） 2.9版本所附的標(biāo)準(zhǔn)庫
分配內(nèi)存和回收內(nèi)存用的還是operator new和operator delete，底部還是用c語言的malloc和free實(shí)現(xiàn)，和上面相同。
參見右下角的說明，這個(gè)分配器并沒有被SGI STL header引入，即沒有被使用。
那GNU C++2.9對(duì)allocator的使用是怎么樣的呢？
它用的是一個(gè)名字叫做alloc的分配器，如下圖所示。
G++2.9 alloc的實(shí)現(xiàn)如下圖所示，共有16條鏈表，每一條鏈表負(fù)責(zé)特定大小的區(qū)塊，編號(hào)為#0的鏈表負(fù)責(zé)大小為8B的內(nèi)存塊，編號(hào)為#1的鏈表負(fù)責(zé)大小為8 x 2 = 16B的內(nèi)存塊，編號(hào)為#3的鏈表負(fù)責(zé)大小為8 x 3 = 24B的內(nèi)存塊，…，以此類推，每次增加8B。每一條鏈表都是一次用malloc分配的一大塊內(nèi)存（帶cookie），然后切分成小的標(biāo)準(zhǔn)塊（不帶cookie），當(dāng)容器需要內(nèi)存的時(shí)候，alloc就會(huì)按照需要的大?。ㄗ兂?B的倍數(shù)）在鏈表中查找進(jìn)行分配，這樣實(shí)現(xiàn)在分配小塊的時(shí)候就不需要存儲(chǔ)cookie的開銷了。
G++4.9所附的標(biāo)準(zhǔn)庫，它的分配器實(shí)現(xiàn)
名字叫做new_allocator, 這個(gè)4.9版本默認(rèn)又不再使用alloc分配器，而是繼續(xù)調(diào)用operator new 和operator delete。
G++4.9所附的標(biāo)準(zhǔn)庫中的__pool_alloc就是G++2.9版本的alloc分配器
如果想要使用這個(gè)分配器，語法是什么呢？
vector<string, __gnu_cxx::__pool_alloc<string>> vec;// __gnu_cxx是一個(gè)命名空間
12 容器之間的實(shí)現(xiàn)關(guān)系與分類
容器，結(jié)構(gòu)與分類
下圖中縮進(jìn)的函數(shù)：下圖中的rb_tree（紅黑樹）下面有4個(gè)set,map,multiset,multimap縮進(jìn)，這表示下面四個(gè)和rb_tree是衍生關(guān)系（復(fù)合composition關(guān)系，has-a），拿set舉例，表示set里面有（has a）1個(gè)rb_tree做底部，拿heap舉例，表示heap里面有一個(gè)vector做底部，拿priority_queue舉例，它是heap的縮進(jìn)，表示priority_queue里面有一個(gè)heap作為底部，等等。
13 深度探索list（上）
容器list
容器list是雙向鏈表：底部實(shí)現(xiàn)是環(huán)狀雙向鏈表
下面是以GNU C++2.9版本進(jìn)行介紹
list內(nèi)部除了存data之外，還要存一個(gè)前向指針prev和一個(gè)后向指針next。
list的iterator，當(dāng)?shù)?+的時(shí)候，是從一個(gè)節(jié)點(diǎn)走到下一個(gè)節(jié)點(diǎn)，是通過訪問next指針實(shí)現(xiàn)的。
template<class T>
struct __list_node {
// 設(shè)計(jì)不理想，后面需要類型轉(zhuǎn)型
typedef void* pointer; // 這里__list_node中竟然有一種指向void的指針，而不是指向自己類型的指針
void_pointer prev;
void_pointer next;
T data;
};
template<class T, class Alloc = alloc>
class list {
protected:
typedef __list_node<T> list_node;
public:
typdef list_node* link_node;
typedef __list_iterator<T, T&, T*> iterator;
protected:
link_type node;
...
};
template<class T, class Ref, class Ptr>
struct __list_iterator {
typedef T value_type;
typedef Ptr pointer;
typedef Ref reference;
...
};
list’s iterator
下面看list的迭代器
__list_iterator 這個(gè)類中主要有兩部分：一部分是一堆typedef，另一部分是操作符的重載，如下圖所示。
看迭代器iterator，迭代器的++操作
++操作有兩種，一種是++ite，另一種是ite++，分別是前置(prefix)和后置(postfix)
先看prefix form：通過取出next指針，指向鏈表的下一個(gè)節(jié)點(diǎn)，實(shí)現(xiàn)迭代器++的操作。
self&
operator++() // ++操作符重載
{
// node是一個(gè)指向結(jié)構(gòu)體__list_node的指針
// 取出結(jié)構(gòu)體里面的成員next指針
node = (link_type)((*node).next); // link_type是指針類型
return *this;
}
// 結(jié)構(gòu)體如下所示
template<class T>
struct __list_node {
typedef void* pointer;
void_pointer prev;
void_pointer next;
T data;
};
再看postfix form：用一個(gè)int參數(shù)operator++(int) 表示后++,當(dāng)使用后置遞增符號(hào)（如ite++）時(shí)，意味你想要遞增迭代器，但在遞增之前返回其先前的值。
self
operator++(int) //++操作符重載
{
self tmp = *this; // 1.記錄原值
++*this; // 2.前進(jìn)一個(gè)位置
//整個(gè)操作 ++*this 的結(jié)果是遞增迭代器并返回遞增后的迭代器的引用
return tmp; // 3.返回原來的值
}
這里的 self tmp = *this;沒有調(diào)用operator*這個(gè)操作，而是調(diào)用拷貝構(gòu)造的函數(shù)，把后面*this解釋為拷貝構(gòu)造的參數(shù)
__list_iterator(const iterator& x): node(x.node) {}
再看這里的第2步++*this;，它也沒有調(diào)用operator* 這個(gè)操作，而是因?yàn)?+在前，調(diào)用前置++操作（進(jìn)行node指向next指針，實(shí)現(xiàn)真正的迭代器前進(jìn)），這里的*this被解釋為operator++的參數(shù)。
*this 指向的是鏈表節(jié)點(diǎn)，通過 ++*this 可以使得鏈表迭代器前進(jìn)到下一個(gè)節(jié)點(diǎn)。
template<class T,class Ref,class Ptr>
struct __list_iterator {
typedef __list_iterator<T,T&,T*> iterator;
typedef __list_iterator<T,Ref,Ptr> self;
typedef bidirectional_iterator_tag iterator_category;
typedef T value_type;
typedef Ptr pointer;
typedef Ref reference;
typedef __list_node<T>* link_type;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
link_type node; //迭代器內(nèi)部需要一個(gè)普通指針，指向list的節(jié)點(diǎn)
//構(gòu)造函數(shù)
__list_iterator(link_type x):node(x) {}
__list_iterator() {}
__list_iterator(const iterator& x):node(x.node) {}
reference operator*() const { return (*node).data;}
pointer operator->() const {return &(operator*());}
//前向迭代器
self& operator++(){ // 前置++ite
node = (link_type)((*node).next);
return *this;
}
self operator++(int){ // 后置ite++
self tmp = *this;
++*this;
return tmp;
}
//后向迭代器
self& operator--(){ // 前置--ite
node=(link_type)((*node).prev);
return *this;
}
self operator--(int){ // 后置ite--
self tmp = *this;
--*this;
return tmp;
}
};
這里的代碼參考：https://www.cnblogs.com/ybf-yyj/p/9843391.html
14 深度探索list（下）
GNU C++2.9版本和GNU C++ 4.9版本關(guān)于list中iterator的設(shè)計(jì)差別
G2.9中iterator需要傳三個(gè)模板參數(shù)<T, T&, T*>，而G4.9中僅需要傳一個(gè)模板參數(shù)
G2.9中l(wèi)ist的結(jié)構(gòu)
G4.9中l(wèi)ist的結(jié)構(gòu)：繼承關(guān)系更加復(fù)雜
15 迭代器的設(shè)計(jì)原則和Iterator Traits的作用與設(shè)計(jì)
Iterator需要遵循的原則
看一下rotate函數(shù)，它的參數(shù)里調(diào)用std::__iterator_category，里面返回iterator_category，這是iterator的一個(gè)屬性，下面圖還有另外兩個(gè)屬性，difference_type和value_type,這里共涉及三個(gè)associated types（相關(guān)的類型），另外還有兩種，分別是reference和pointer。也就是說共有5種associated types。
算法algorithm模塊和容器container彼此獨(dú)立，中間需要迭代器iterator進(jìn)行交流
iterator必須提供的5種associated types，剛才上面介紹過，如下圖所示：iterator_category, value_type, pointer, reference, difference_type。
difference指的是距離， 一個(gè)容器中兩個(gè)iterator的距離
為什么需要traits？指針也被看作是一種退化的iterator，但指針并不是一個(gè)類，自然無法在類中定義上述的5種associated types。
traits機(jī)制必須有能力分辨它所獲得的iterator是class iterator T還是native pointer to T（native pointer，原生指針，指的是non class(template) iterators，它無法定義associated type）
iterator traits用來分離class iterator和non-class iterator
當(dāng)想知道一個(gè)迭代器的value type是什么的時(shí)候，不能直接I::value_type，而是
iterator_traits<I>::value_type
這就涉及到iterator_traits的偏特化（指針是范圍上的偏特化，前文講過），如果傳入的是指針T*，它就是調(diào)用上圖中的2或者3，直接定義T為value_type類型，如果傳入的是class iterator，那就直接定義I::value_type為value_type。
完整的iterator_traits，這里就全部列出了5個(gè)asscicated types，以及偏特化處理傳入的是指針的情況
后面還有各種類型的traits，比如type traits, char traits, allocator traits, pointer traits, array traits等等文章來源：http://www.zghlxwxcb.cn/news/detail-810581.html
后記
這是系列筆記連載，會(huì)繼續(xù)更新。文章來源地址http://www.zghlxwxcb.cn/news/detail-810581.html
到了這里，關(guān)于STL標(biāo)準(zhǔn)庫與泛型編程（侯捷）筆記2的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
