目錄

1. 源代碼之分布（VC括蝠， GCC）

2. 面向?qū)ο缶幊蹋∣bject-Oriented Programming称近，OOP） vs. 泛型編程 （Generic Programming淋昭，GP）

3. 閱讀C++標(biāo)準(zhǔn)庫(kù)源碼（Source Code）之必要基礎(chǔ)：操作符重載（Operator Overloading）and 模板(Templates)

4. 分配器（allocators）

5. 迭代器（Iterator）的設(shè)計(jì)原則和 Iterator Traits 的作用與設(shè)計(jì)

6. 容器之間的實(shí)現(xiàn)關(guān)系與分類

7. 深度探索 vector

8. 深度探索 list

9. 淺談 array & forward_list

1. 源代碼之分布（VC虫几， GCC）

• VC：...\include
• GCC：...\4.9.2\include\C++
  • 原生標(biāo)準(zhǔn)庫(kù)：...\include\C++\bits
  • 擴(kuò)充標(biāo)準(zhǔn)庫(kù)：...\include\C++\ext

2. 面向?qū)ο缶幊蹋∣bject-Oriented Programming豹爹，OOP） vs. 泛型編程 （Generic Programming滑蚯，GP）

問(wèn)：為什么 list 不能使用 ::sort() 排序俺附？

答：只有隨機(jī)訪問(wèn)迭代器才能進(jìn)行上述加減乘除肥卡，而 list 在內(nèi)存里面是一個(gè)一個(gè)結(jié)點(diǎn)用指針串起來(lái)的，并不是一個(gè)連續(xù)空間事镣，所以它所具備的迭代器是不能夠跳來(lái)跳去的步鉴，它只能一個(gè)一個(gè)前進(jìn)或后退。
因此標(biāo)準(zhǔn)庫(kù)中的 ::sort() 所需要的迭代器是 list 中提供的迭代器所不能滿足的蛮浑。

操作符重載扮演了非常重要的角色唠叛。

如果需要定制特殊的算法琐驴，對(duì)特定“比大小”功能的設(shè)計(jì)就顯得尤為重要矗积。

3. 閱讀C++標(biāo)準(zhǔn)庫(kù)源碼（Source Code）之必要基礎(chǔ)：操作符重載（Operator Overloading）and 模板(Templates)

3.1 操作符重載（Operator Overloading）

因?yàn)橹暗墓P記中對(duì)操作符重載已經(jīng)有比較詳細(xì)的介紹，這里就不贅述了骚露，只簡(jiǎn)單的羅列一些要注意的點(diǎn)：

當(dāng)一個(gè)重載的運(yùn)算符是成員函數(shù)時(shí)蕴掏， this 綁定到左側(cè)運(yùn)算對(duì)象障般。成員運(yùn)算符函數(shù)的（顯式）參數(shù)數(shù)量比運(yùn)算對(duì)象的數(shù)量要少一個(gè)调鲸。

可以（不能）被重載的運(yùn)算符：

通常情況下，不應(yīng)該重載逗號(hào)挽荡、取地址藐石、邏輯與和邏輯或運(yùn)算符。

3.2 模板(Templates)

模板是 C++ 中泛型編程的基礎(chǔ)定拟。一個(gè)模板就是一個(gè)創(chuàng)建類或函數(shù)的藍(lán)圖或者說(shuō)公式于微。

模板定義以關(guān)鍵字 template 開(kāi)始，后跟一個(gè)模板參數(shù)列表（template parameter list）青自，其不能為空株依。

當(dāng)使用模板時(shí)，我們（隱式地或顯式地）指定模板實(shí)參（template argument）延窜，將其綁定到模板參數(shù)上恋腕。

模板類型參數(shù)前必須使用關(guān)鍵字 class 或 typename。
在模板參數(shù)列表中逆瑞，這兩個(gè)關(guān)鍵字的含義相同荠藤，可以互換使用。

3.2.1 模板類型

主要有類模板获高，函數(shù)模板和成員模板三種類型：

3.2.1.1 類模板（Class Templates）

編譯器不能為類模板推斷模板參數(shù)類型哈肖，因此必須顯式使用。

3.2.1.2 函數(shù)模板（Function Templates）

編譯器自動(dòng)為函數(shù)模板推斷模板參數(shù)類型念秧。

3.2.1.3 成員模板（Member Templates）

成員模板不能是虛函數(shù)牡彻。

3.2.2 模板特化（Specialization）

模板的特化就是一個(gè)獨(dú)立的定義，在其中一個(gè)或多個(gè)模板參數(shù)被指定為特定的類型出爹。
注意：特化的本質(zhì)是實(shí)例化一個(gè)模板，而非重載它缎除。因此严就，特化不影響函數(shù)匹配。

特化：

偏特化（個(gè)數(shù)的偏特化和范圍的偏特化）：

4. 分配器（allocators）

標(biāo)準(zhǔn)庫(kù) allocator 類定義在頭文件 memory 中器罐，它幫助我們將內(nèi)存分配和對(duì)象構(gòu)造分離開(kāi)來(lái)梢为。它提供一種類型感知的內(nèi)存分配方法，它分配的內(nèi)存是原始的轰坊、未構(gòu)造的铸董。

藍(lán)色部分：切實(shí)需要的空間大小
灰色部分：debug mode 模式的空間需求
紅色部分：cookie，幫助編譯器識(shí)別此段空間的內(nèi)容
綠色部分：用來(lái)調(diào)整邊界肴沫，使空間分配統(tǒng)一化

4.1 VC6 STL 中的分配器設(shè)計(jì)

• (int*)0：只為了告訴函數(shù)是 int 型
• typename 后面加（）構(gòu)成一個(gè)臨時(shí)對(duì)象
• VC 中的分配器最終就是調(diào)用 C 中的 malloc 和 free粟害， 沒(méi)有任何特殊的設(shè)計(jì)

4.2 BC5 STL 中的分配器設(shè)計(jì)

4.3 G2.9 STL 中的分配器設(shè)計(jì)（侯大師推薦！可讀性非常高２摇）

此處的設(shè)計(jì)并未被使用悲幅。

設(shè)計(jì)目的：減少額外開(kāi)銷（避免之前那種用cookie包起來(lái)的大量額外開(kāi)銷）

4.4 G4.9 STL 中的分配器設(shè)計(jì)

又用回傳統(tǒng)方式了-套鹅。-

若要使用 G2.9 中設(shè)計(jì)的 alloc，就要像用例中那樣汰具。

5. 迭代器（Iterator）的設(shè)計(jì)原則和 Iterator Traits 的作用與設(shè)計(jì)

5.1 迭代器的設(shè)計(jì)原則

不論是泛型思維或 STL 的實(shí)際運(yùn)用卓鹿，迭代器都扮演者重要的角色。 STL 的中心思想在于：將數(shù)據(jù)容器（containers）和算法（algorithms）分開(kāi)留荔，彼此獨(dú)立設(shè)計(jì)吟孙，最后再通過(guò)“粘合劑”將它們撮合在一起。容器和算法的泛型化聚蝶，從技術(shù)角度來(lái)看并不困難杰妓，C++ 的 class templates 和 function templates 可分別達(dá)成目標(biāo)。如何設(shè)計(jì)出兩者之間的良好膠粘劑既荚，才是大難題稚失。

迭代器是一種行為類似指針的對(duì)象，而指針的各種行為中最常見(jiàn)也最重要的便是內(nèi)容提領(lǐng)（dereference）和成員訪問(wèn)（member access）恰聘，因此句各，迭代器最重要的編程工作就是對(duì) operator* 和 operator-> 進(jìn)行重載（overloading）工作。關(guān)于這一點(diǎn)晴叨，C++ 標(biāo)準(zhǔn)程序庫(kù)有一個(gè) auto_ptr 可供我們參考凿宾。這是一個(gè)用來(lái)包裝原生指針（native pointer）的對(duì)象，聲名狼藉的內(nèi)存泄漏（memory leak）問(wèn)題可藉此獲得解決兼蕊。簡(jiǎn)化版的 auto_ptr（源代碼在頭文件<memory>中） 如下初厚，可具體說(shuō)明 auto_ptr 的行為與能力：

template<typename T>
class auto_ptr {
public:
  explicit auto_ptr(T *p = 0):pointee(p) {}
  template<typename U>
  auto_ptr(auto_ptr<U>& rhs):pointee(rhs.release()) {}
  ~auto_ptr() { delete pointee; }

  template<typename U>
  auto_ptr<T>& operator = (auto_ptr<U>& rhs) {
    if (this != &rhs) reset(rhs.release());
    return *this;
  }
  T& operator*() const { return *pointee; }
  T* operator->() const { return pointee; }
  T* get() const { return pointee; }
  // ...
private:
    T *pointee;
};

5.2 迭代器相應(yīng)型別（associated types）

在算法中運(yùn)用迭代器時(shí)，很可能會(huì)用到其相應(yīng)型別（associated type）孙技。什么是相應(yīng)型別呢产禾？迭代器所指之物的型別便是其一。假設(shè)算法中有必要聲明一個(gè)變量牵啦，以“迭代器所指對(duì)象的型別”為型別亚情，如何是好？畢竟 C++ 只支持 sizeof()哈雏，并未支持 typeof()楞件！即便動(dòng)用 RTTI 性質(zhì)中的 typeid()，獲得的也只是型別名稱裳瘪，不能拿來(lái)做變量聲明之用土浸。

那么解決辦法是：利用 function template 的參數(shù)推導(dǎo)（argument deduction）機(jī)制。例如：

template <class I, class T>
void func_impl(I iter, T t)
{
  T tmp; // 這里解決了問(wèn)題彭羹。T 就是 迭代器所指之物的型別黄伊，本例為 int

   //  ...  這里做原本 func() 應(yīng)該做的全部工作
};

tempalte <class I>
inline
void func(I iter)
{
  func_impl(iter, *iter);  //  func 的工作全部移往 func_impl
}

int main()
{
  int i;
  func(&i);
}

我們以 func() 為對(duì)外接口，卻把實(shí)際操作全部置于 func_impl() 之中派殷。由于 func_impl() 是一個(gè)function template毅舆，一旦被調(diào)用西篓，編譯器會(huì)自動(dòng)進(jìn)行 template 參數(shù)推導(dǎo)。于是導(dǎo)出型別 T憋活，順利解決了問(wèn)題岂津。

迭代器相應(yīng)型別（associated types）不只是“迭代器所指對(duì)象的型別”一種而已。最常用的型別有五種悦即，然而并非任何情況下任何一種都可利用上述的 template 參數(shù)推導(dǎo)機(jī)制來(lái)取得吮成。于是 traits 應(yīng)運(yùn)而生。

5.3 Traits 編程技法——STL 源代碼門(mén)鑰

下面這個(gè) class template 專門(mén)用來(lái)“萃取”迭代器的特性辜梳，而 value type 正是迭代器的特性之一：

template <class I>
struct iterator_traits {   // traits 意為“特性”
  typedef typename I::value_type value_type;
};

這個(gè)所謂的 traits粱甫，其意義是，如果 I 定義有自己的 value type作瞄，那么通過(guò)這個(gè) traits 的作用茶宵，萃取出來(lái)的 value_type 就是 I::value_type。

根據(jù)經(jīng)驗(yàn)宗挥，最常用到的迭代器相應(yīng)型別有五種： value type（迭代器所指對(duì)象的類型）乌庶，difference type（兩個(gè)迭代器之間的距離），pointer契耿，reference瞒大，iterator category（迭代器的分類）。

C++ 標(biāo)準(zhǔn)庫(kù)中只出現(xiàn)過(guò)以下三種相應(yīng)型別：

聲明一個(gè)無(wú)法賦值（因 const 之故）的暫時(shí)變量搪桂，沒(méi)什么用透敌！因此，如果迭代器是個(gè) pointer-to-const踢械，我們應(yīng)該設(shè)法令其 value type 為一個(gè) non-const 型別酗电。利用偏特化，我們就可進(jìn)行如下設(shè)計(jì)：

完整的 iterator_traits 如下：

除了 iterator traits 以外内列，標(biāo)準(zhǔn)庫(kù)里還設(shè)計(jì)了各式各樣的 traits 滿足不同的需求顾瞻，如：

6. 容器之間的實(shí)現(xiàn)關(guān)系與分類

本圖以內(nèi)縮方式來(lái)表達(dá)基層與衍生層的關(guān)系。這里所謂的衍生德绿，并非派生（inheritance）關(guān)系，而是內(nèi)含（containment）關(guān)系退渗。例如 heap 內(nèi)含一個(gè) vector移稳。

此處 sizeof() 為控制數(shù)據(jù)結(jié)構(gòu)本身所需要的空間大小，而不是放入其中的數(shù)據(jù)的占用空間会油。

接下來(lái)我們分門(mén)別類講講幾種典型的序列式容器（sequential containers）个粱。

7. 深度探索 vector

vector 的數(shù)據(jù)安排以及操作方式，與 array 非常相似翻翩。兩者的唯一差別在于空間的運(yùn)用的靈活性：

• array 是靜態(tài)空間都许，一旦配置了就不能改變稻薇；要換個(gè)大（或小）一點(diǎn)的空間胶征，就非常麻煩：首先配置一塊新空間塞椎，然后將元素從舊址一一搬往新址，再把原來(lái)的空間釋還給系統(tǒng)睛低。

• vector 是動(dòng)態(tài)空間案狠，隨著元素的加入，它的內(nèi)部機(jī)制會(huì)自行擴(kuò)充空間以容納新元素钱雷。因此骂铁，vector 的運(yùn)用對(duì)于內(nèi)存的合理利用與運(yùn)用的靈活性有很大的幫助，我們?cè)僖膊槐睾ε驴臻g不足而一開(kāi)始就要求一個(gè)大塊頭 array 了罩抗，我們可以安心使用 vector拉庵，吃多少用多少。

vector 的實(shí)現(xiàn)技術(shù)套蒂，關(guān)鍵在于其對(duì)大小的控制以及重新配置時(shí)的數(shù)據(jù)移動(dòng)效率钞支。一旦 vector 舊空間滿載，如果客戶端每新增一個(gè)元素泣懊，vector 內(nèi)部只是擴(kuò)充一個(gè)元素的空間伸辟，實(shí)為不智，因?yàn)樗^擴(kuò)充空間（不論多大）馍刮，一如稍早所說(shuō)信夫，是“配置新空間——數(shù)據(jù)移動(dòng)——釋還舊空間”的大工程，時(shí)間成本很高卡啰，應(yīng)該加入某種未雨綢繆的考慮静稻，因此標(biāo)準(zhǔn)庫(kù)中的 vector 使用了“二倍成長(zhǎng)”的空間配置策略：

當(dāng)我們以 push_back() 將新元素插入于 vector 尾端時(shí)，該函數(shù)首先檢查是否還有備用空間匈辱，如果有就直接在備用空間上構(gòu)造元素振湾，并調(diào)整迭代器 finish，使 vector 變大亡脸。如果沒(méi)有備用空間了押搪，就擴(kuò)充空間（重新配置、移動(dòng)數(shù)據(jù)浅碾、釋放原空間）：

這段代碼不僅被 push_back 用大州，也被 insert 用，所以還要拷貝安插點(diǎn)后的原內(nèi)容

注意：所謂動(dòng)態(tài)增加大小垂谢，并不是在原空間之后接續(xù)新空間（因?yàn)闊o(wú)法保證原空間之后尚有可供配置的空間）厦画，而是以原大小的兩倍另外配置一塊較大空間，然后將原內(nèi)容拷貝過(guò)來(lái)，最后才開(kāi)始在原內(nèi)容之后構(gòu)造新元素根暑，并釋放原空間力试。因此，對(duì) vector 的任何操作排嫌，一旦引起空間重新配置畸裳，指向原 vector 的所以迭代器就都失效了。這是程序員容易犯的一個(gè)錯(cuò)誤躏率，務(wù)必小心躯畴！

8. 深度探索 list

8.1 list 概述

相較于 vector 的連續(xù)線性空間，list 就顯得復(fù)雜許多薇芝，它的好處是每次插入或刪除一個(gè)元素蓬抄，就配置或釋放一個(gè)元素空間。因此夯到，list 對(duì)于空間的運(yùn)用有著絕對(duì)的精準(zhǔn)嚷缭，一點(diǎn)也不浪費(fèi)。而且耍贾，對(duì)于任何位置的元素插入或元素移除阅爽，list 永遠(yuǎn)是常數(shù)時(shí)間。

list 和 vector 是兩個(gè)最常被使用的容器荐开。什么時(shí)機(jī)下最適合使用哪一種容器付翁，必須視元素的多寡、元素的構(gòu)造復(fù)雜度（有無(wú) non-trivial copy constructor晃听，非默認(rèn)拷貝構(gòu)造函數(shù)百侧，non-trival copy assignment operator，非默認(rèn)拷貝賦值運(yùn)算符）能扒、元素存取行為的特性而定佣渴。

• __list_node 中 prev 和 next 的型別都為 void*，使用時(shí)還要類型轉(zhuǎn)換初斑，不太理想辛润，其實(shí)可設(shè)為 __list_node<T>*
• list 是一個(gè)環(huán)狀雙向鏈表，所以它只需要一個(gè)指針见秤，便可以完整表現(xiàn)整個(gè)鏈表砂竖。
• 如果讓指針 node 指向刻意置于尾端的一個(gè)空白節(jié)點(diǎn)，node 便能符合 STL 對(duì)于“前閉后開(kāi)”區(qū)間的要求鹃答，成為 last 迭代器乎澄。這么一來(lái)，begin() 挣跋、end()、empty()狞换、size() 避咆、front()舟肉、back() 等函數(shù)便可以輕易完成。

8.2 list 的迭代器

list 不再能夠像 vector 一樣以普通指針作為迭代器查库，因?yàn)槠涔?jié)點(diǎn)不保證在存儲(chǔ)空間中連續(xù)存在路媚。list 迭代器必須有能力指向 list 的節(jié)點(diǎn)，并有能力進(jìn)行正確的遞增樊销、遞減整慎、取值、成員存取等操作（遞增時(shí)指向下一個(gè)節(jié)點(diǎn)围苫，遞減時(shí)指向上一個(gè)節(jié)點(diǎn)裤园，取值時(shí)取的是節(jié)點(diǎn)的數(shù)據(jù)值，成員取用時(shí)取用的是節(jié)點(diǎn)的成員）剂府，如下圖：

由于 STL list 是一個(gè)雙向鏈表（double linked-list）拧揽，迭代器必須具備前移、后移的能力腺占，所以 list 提供的是 Bidirectional Iterators淤袜。

list 有一個(gè)重要性質(zhì)：插入操作（insert）和接合操作（splice）都不會(huì)造成原有的 list 迭代器失效。這在 vector 是不成立的衰伯，因?yàn)?vector 的插入操作可能造成記憶體重新配置，導(dǎo)致原有的迭代器全部失效烦周。甚至 list 的元素刪除操作（erase），也只有“指向被刪除元素”的那個(gè)迭代器失效论矾，其它迭代器不受任何影響杆勇。

• self operator++(int) 中的 int 無(wú)意義，用來(lái)表示后置++闰靴，函數(shù)體{ }內(nèi)編譯器先遇到重載的“=”，調(diào)用拷貝構(gòu)造 copy ctor
• 前++的返回值帶引用蚂且，后++不帶引用幅恋，是向 int 型的設(shè)計(jì)看齊，保持一致性。（不允許后++兩次淑翼，而前++可以）

G4.9 中 list iterator 的實(shí)現(xiàn)：

與G2.9 相比復(fù)雜太多

9. 淺談 array & forward_list

array 就是固定內(nèi)存空間的 vector腐巢，而 forward_list 是“閹割版”的 list，相關(guān)知識(shí)這里就不再贅述了玄括。

部分內(nèi)容參考自《C++ Primer 中文版（第5版）》以及《STL 源碼剖析》