主要內(nèi)容：
本節(jié)主要講解了面向?qū)ο蠛头盒途幊痰膮^(qū)別，以及source code所涉及到的基礎(chǔ)知識（包括運算符重載旺芽、各種模板等）沪猴，還有利用源碼深入剖析了分配器、容器（list, vector, array, forward_list等）甥绿、迭代器字币。
源碼之前则披，了無密碼共缕。
1.源碼所在目錄
- visual c++源代碼文件：..\include 下面有這個c++標準庫的頭文件（自己的環(huán)境vs 2017，C:\Program Files (x86)\Microsoft Visual Studio\2017\Community\VC\Tools\MSVC\14.10.25017\include在這個目錄下）
- gnc c++4.9.2 頭文件的位置：..\4.9.2\include\c++
stl開頭的頭文件：\include\c++\bits
擴充的（分配器）頭文件：\include\c++\ext
2. oop（面向?qū)ο螅┡cgp（泛型編程）
- oop企圖數(shù)據(jù)和操作放在一起士复。而gp是將數(shù)據(jù)和操作分開图谷，容器存放數(shù)據(jù)，算法實現(xiàn)各種操作阱洪，它們之間通過迭代器聯(lián)系起來便贵。gp的好處在于容器和算法相互獨立，他們之間只要具有可以相互使用的接口即可冗荸。eg. ::min() 對于兩個類對象比較大小承璃，調(diào)用這個算法，就要重載小于號或是自定義比較大小的函數(shù)蚌本。
- list不能調(diào)用::sort()盔粹，因為只有隨機訪問的迭代器才能調(diào)用::sort()，list不支持隨機訪問程癌。所以list只能用自己的sort.
- 算法對于元素本身的操作舷嗡，最終都是比較大小嵌莉？进萄。
3. 技術(shù)基礎(chǔ)--運算符重載、模板
四個運算符不能重載： :: , . , .*， :?
類模板中鼠、函數(shù)模板可婶、成員模板
類模板中又分為泛化、特化兜蠕、偏特化（局部特化扰肌，個數(shù)和范圍上）
template <typename T> struct __type_traits {...} // 泛化
template<> struct __type_traits<int> {...} // 特化
template <class Iterator> struct iterator_traits {...} // 泛化
template <class T> struct struct iterator_traits<T *> {} //偏特化，傳入指針
template <class T> struct struct iterator_traits<const T *> {} //偏特化熊杨，傳入常量指針
4. 分配器allocators
- malloc會在申請分配的內(nèi)存大小的基礎(chǔ)上附加額外的空間曙旭，如果申請分配的內(nèi)存小，那么額外的空間所占的比例就大晶府。
- 分配器是用來分配內(nèi)存的桂躏，對于VC下的allocator類中有兩個重要的函數(shù)allocate和deallocate. allocate函數(shù)內(nèi)部會調(diào)用::operator new，operator new內(nèi)部會調(diào)用malloc. deallocate內(nèi)部會調(diào)用::operator delete川陆，都沒有任何特殊設計剂习。
使用方法：
eg. int *p = allocator<int>().allocate(512, (int *)0); //首先是創(chuàng)建一個臨時allocator對象，之后調(diào)用allocate函數(shù)分配512字節(jié)较沪，且全部初始化為0鳞绕。
allocator<int>().deallocate(p, 512); //釋放空間，這里要求告知分配的空間大小尸曼。
- 對于BC5下的allocator類们何，頭文件<memory.stl>. 且也是利用::operator new和::operator delete實現(xiàn)allocate和deallocate的，都沒有任何特殊設計控轿。
使用方法：
eg. int *p = allocator<int>().allocate(512); //allocate函數(shù)第二個參數(shù)用默認值是0.
allocator<int>().deallocate(p, 512);
- 對于GCC2.9下也是利用::operator new和::operator delete實現(xiàn)allocate和deallocate的冤竹，都沒有任何特殊設計。GCC2.9在容器中采用的不是allocator茬射，而是alloc, 頭文件<stl_alloc.h>. 在擴展空間時鹦蠕，盡量減少malloc次數(shù)，做法是創(chuàng)建16條鏈表在抛，每條鏈表存放的字節(jié)是以8的倍數(shù)增長钟病，第0條鏈表存放8字節(jié)，第1條鏈表存放16字節(jié)...刚梭。容器會和分配器要內(nèi)存肠阱，容器中元素的大小會被調(diào)整為8的倍數(shù)，分配器會找到相應的鏈表上望浩，再調(diào)用malloc分配內(nèi)存辖所，一個鏈上的每個內(nèi)存塊不帶有上下cookie（8字節(jié)），只在鏈的頭尾帶有cookie磨德，從而大幅節(jié)省額外空間開銷缘回。
- GCC4.9則沒有在沿用GCC2.9這種好的方式吆视，而是使用的是std::allocator, 繼承于new_allocator, 且又是采用和vc和bc一樣的分配和回收方法。GCC4.9中alloc還存在酥宴，只是名字改為了__pool_alloc. eg.vector<string, __gnu_cxx::__pool_alloc<string>>vec;
5. 容器之間實現(xiàn)關(guān)系
對于GCC2.9啦吧，屬于早期的標準庫版本，容器之間是復合的關(guān)系拙寡，而不是繼承的關(guān)系套菜。heap中擁有vector执隧，priority-queue中擁有heap, stack和queue都擁有deque. 關(guān)聯(lián)容器set琳轿、map篙议、multiset、multimap都擁有rb_tree(高度平衡的二叉樹).
6. 深度探索list
- 容器中要提供迭代器诚啃，和一系列操作符重載淮摔。迭代器內(nèi)部要定義迭代器相關(guān)的5種typedef。
- ++運算符的重載：前++沒有參數(shù)始赎，后++是有一個函數(shù)參數(shù)的和橙，為了與前++進行區(qū)分。后++首先會用tmp記錄原有的指針造垛，再對原有的指針自加魔招，最后返回tmp。
self operator++(int)
{
self tmp = *this; //會調(diào)用iterator的拷貝構(gòu)造函數(shù)是對list中的node進行拷貝五辽，并不是調(diào)用operator*办斑。
++*this;
return tmp; //這里返回的是對象。而前++返回的是reference奔脐。
}
對于整數(shù)變量俄周，前++可以加兩次吁讨，后++則不行髓迎。迭代器的自加也是按照這個原則設計的。
- GCC4.9相對于GCC2.9在list容器上的改進：1. 其中的_list_iterator類模板的typename進行了精簡建丧，由3個typename改為1個typename. 2. _list_node在2.9中是由data和兩個void_pointer類型指針組成排龄，而在4.9中則是先構(gòu)造_list_node_base這個結(jié)構(gòu)存放兩個指向自己這種類型的指針，之后_list_node繼承于它翎朱，并存放data橄维，這樣指針指向的類型就確定了。3. 在32位cpu下拴曲，4.9中sizeof(list<int>) = 8争舞，有兩個指針，分別指向prev和next節(jié)點澈灼； 2.9中是4竞川，只有一個指向node的指針店溢。
- list最后一個有數(shù)據(jù)的節(jié)點的下一個節(jié)點是空的，end()指向的就是這個節(jié)點委乌。這樣是為了前閉后開遍歷設計床牧。
7. iterator需要遵循的原則
- 迭代器內(nèi)部定義的5種迭代器相關(guān)的typedef是為了給算法調(diào)用的。
eg. rotate()算法的內(nèi)部調(diào)用iterator_traits<_Iter>::iterator_category (); 萃取出iterator_category（迭代器的分類遭贸，如前向迭代器戈咳，只能++，或是雙向迭代器等）壕吹，還萃取出difference_type（兩個iterator之間的距離）和value_type（容器中元素類型）著蛙。和迭代器相關(guān)的還有兩種typedef，分別是reference和pointer從沒有在標準庫中使用過耳贬。 - iterator_traits（迭代器的萃取機）有一個泛化的類模板册踩，如果iterator是class，那么會使用這個泛化的類模板效拭，還有兩個偏特化類模板暂吉，一個模板參數(shù)特化為T ，另一個特化為const T缎患。所以無論iterator是類還是指針慕的，都可以萃取其中的5種類型，具體使用eg. iterator_traits<T>::value_type挤渔。value_type主要是用于聲明變量的肮街，所以即使是const T*類型，value_type也是T判导。
- 標準庫中還有其他的萃取機嫉父。
8. 深入探索vector
- 各個編譯器下，容量都會2倍增長眼刃。vector中有三個iterator(start指向第一個元素的位置绕辖，finish指向當前存放的最后一個元素的下一個位置，end_of_storage指向可以容納最后一個元素的位置)擂红，vector的函數(shù)begin(),end(),size(),capactity(),empty(),front(),back(),operator[]等都是利用這三個iterator計算的仪际。
- push_back()首先會利用finish和end_of_storage指針判斷是否還有空閑位置，如果有昵骤，則插入元素树碱，finish自加；如果沒有变秦，那么會調(diào)用輔助函數(shù)insert_aux(end(), x),這是一個函數(shù)模板成榜，其內(nèi)部會再次判斷是否還有剩余空間，因為其他函數(shù)也可以調(diào)用這個函數(shù)蹦玫，如果沒有剩余空間赎婚，那么會分配原有空間大小的二倍雨饺，（如果原有空間是0，那么新的空間大小會是1）惑淳，之后將原有的元素拷貝到新的空間额港，再將新的元素放進去，finish自加歧焦，之后會在新元素后面（安插點后）將剩余的原有元素拷貝過來（這里也是因為這個函數(shù)會被其他函數(shù)調(diào)用）移斩。
- 32位下sizeof(vector<T>) = 12（有3個指針）。
9. array和forward_list 單向鏈表
- TR1版（是1998-2011中間的過度版本绢馍，大概是2003左右）
array內(nèi)部是用數(shù)組實現(xiàn)的向瓷，大小不能擴充，所以定義時要聲明大小舰涌，eg. array<int, 10> arr; 如果給定的array的大小是0猖任，那么在array內(nèi)部會變?yōu)?. 這里的iterator是指針。 - G4.9 array內(nèi)部聲明數(shù)組變得更加復雜了瓷耙。
typedef int T[100]; T c; 這樣寫是對的朱躺。
10.forward_list
- 與list類似，只是是單向的搁痛。
