在根據《STL源碼剖析》實現(xiàn)STL的過程中匙瘪，有了一點感想铆铆，這里進行記錄，給感興趣的朋友做個參考丹喻。代碼參見githubbridgeqiao
前期準備
不管對STL的熟悉程度如何薄货，有幾點是要知道的。
- 至少是知道大概是怎么用的碍论，用過push_back谅猾、pop_back之類的函數(shù)；
- 熟悉C++的struct和class定義鳍悠，常用的語法赊瞬，知道template的特化和偏特化先煎，閱讀過《c++ primer》最好贼涩；
- 讀過《effective c++》更好巧涧，知道c++默認構造的四個函數(shù)和大概的對象內存模型（沒有虛函數(shù)的對象和有虛函數(shù)的），面向對象編程基本概念遥倦；
- 代碼實現(xiàn)時谤绳，最好用c++11的新特性，nullptr袒哥、using之類的缩筛，頭文件使用c++的版本，就是普通的c頭文件前加個
c去掉.h堡称，比如limits.h改為climits瞎抛。
STL背景
在書中的第一章有介紹，六大組件却紧、GNU桐臊、不同的版本，1.9.1感覺沒必要細看晓殊，定義的一些宏断凶，自己實現(xiàn)代碼的話沒必要搞這么復雜，用c++11就行了巫俺，后幾個小節(jié)倒是可以細看认烁，特別是關于臨時對象的，可以參考c++的move語義和RVO介汹，減少一次拷貝析構却嗡。
空間配置器
最開始的簡單allocator可以參考我寫的一篇博客，書上的存在一點問題嘹承，當然直接忽略了也行窗价，反正和后面的沒聯(lián)系。2.2.1可以忽略赶撰，從2.2.2開始看舌镶。需要知道new operator、operator new和placement new豪娜。里面的異常處理和宏定義都可以忽略餐胀。
一級空間配置器只有在分配大于128字節(jié)時起作用，使用malloc()分配內存瘤载，然后用placement new進行構造否灾。銷毀空間時，先析構鸣奔，再free墨技。擴展閱讀c++內存管理惩阶，malloc在分配大于128KB時的實現(xiàn)。
二級空間配置器是為了減少內存碎片而使用的扣汪，使用free_list管理空閑內存断楷，以每8個字節(jié)遞增，從8字節(jié)到128字節(jié)崭别，union obj可以簡單理解為void*冬筒。大于128B，交給malloc分配茅主，小于的話舞痰，使用free_list里找個空閑的塊分配，如果free_list里面沒有空閑的塊诀姚，使用refill重新填充响牛。
refill很有意思，它不直接參與分配內存赫段，而是通過chunk_alloc在內存池分配呀打，然后根據分到的內存，將第一小塊返回給對象瑞佩，后面剩余的給串起來聚磺，放到free_list中，這里要注意炬丸，每一個小塊大小是按照8的倍數(shù)來的瘫寝，不是對象要求的大小。這個refill函數(shù)里面將obj*強轉成char*稠炬，其實可以直接用next_obj->data的焕阿，除了這里可能會用到union obj的特性，其它地方是真沒發(fā)現(xiàn)有用到的首启。
uninitialized_**幾個函數(shù)可以先實現(xiàn)暮屡，不用管type traits，按照書上的順序看就行毅桃。
迭代器和traits
那個auto_ptr可以換成shared_ptr褒纲，更有意義一點，auto_ptr過時了钥飞。重點看3.3節(jié)后面莺掠，參考SFINAE(Substitution Is Not A Error)，在進行模板匹配時读宙，用最近的那個彻秆。迭代器類型定義的時候，用最強化（精細化？）的那個唇兑，定義函數(shù)模板酒朵，用最低階的那個。這個沒什么好說的扎附，最好都實現(xiàn)一遍蔫耽，加強理解。
vector
從這章到hashtable都是容器的定義及實現(xiàn)帕棉，書上是按照概述针肥、定義摘要、實際使用例子香伴、迭代器、容器構造插入刪除的順序來的具则，感覺定義摘要沒有把重點寫出來即纲，有點雜，應該主要關注容器的成員變量博肋，以及它在插入刪除時是大概怎樣操作的低斋，給讀者一個感性的認識。
通過allocator配置空間后匪凡，返回的頭指針賦值給start(類型為T*)膊畴，空間大小為n*sizeof(T)，這n個元素未初始化病游，end_of_storage指向start+n的位置唇跨，也就是空間的尾部，finish指向已初始化元素的尾部衬衬。首先买猖，start和end_of_storage不變，每次插入元素滋尉，finish往后移一個元素玉控，直到finish==end_of_storage，此時狮惜，再插入元素的話高诺，會分配新的內存，然后將原來的元素進行拷貝碾篡，刪除原來的空間虱而。這里有個問題，就是內存為什么以2倍增長耽梅？博客里說linux是2倍薛窥，windows是1.5倍，以(1,2]倍增長為宜，我覺得這個沒有定數(shù)诅迷，只要不太大就行佩番。
vector的迭代器是原始指針，所以當發(fā)生插入刪除罢杉、內存變了的話趟畏，指針會失效。其它的照著實現(xiàn)就行滩租，可能要細看的是插入多個元素的函數(shù)赋秀，注意const函數(shù)的實現(xiàn)。
list
成員變量只有一個node律想，為雙向環(huán)狀鏈表猎莲，node包括值data，兩個指針prev技即、next著洼。初始時，只有一個node而叼，插入一個元素身笤，往front插入，用next指針指向新的節(jié)點葵陵，往back插入液荸，用prev指向新的節(jié)點。迭代器存放指向節(jié)點的指針脱篙，然后實現(xiàn)operator++之類的方法娇钱，目標是達到和原生裸指針的外在功能。結構比較簡單涡尘，難點在算法的實現(xiàn)上忍弛，特別是sort函數(shù)，需要先實現(xiàn)swap考抄、merge函數(shù)细疚。
sort的原理如下：歸并排序，定義了carry和counter[64]對象川梅，每次carry從原來的list中取一個元素疯兼，放到count[0]中，從count[0]開始贫途，如果滿2個元素吧彪，將這兩個給count[1]，然后如果count[1]滿4個元素丢早，給count[2]姨裸，依次類推秧倾。
| count列表 | 初始化 | 第1輪 | 第2輪 | 第3輪 |
|---|---|---|---|---|
| count[0] | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
| count[1] | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| count[2] | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
0表示count[i]未滿2^i個元素，1表示滿傀缩。例如第二輪那先，往count[0]里面放一個元素，滿了赡艰，然后將這兩個元素給count[1]售淡，count[1]沒滿4個元素，繼續(xù)第三輪慷垮。
deque
deque這章還不錯揖闸，講解的很細，實現(xiàn)起來比較麻煩料身，特別是迭代器汤纸，為了達到RandomAccess的效果，operator+=(int n)和operator-=(int n)惯驼，還有reallcate_map函數(shù)蹲嚣。
stack、queue和heap
stack和queue是容器適配器祟牲，外面套了個殼，看下接口就行抖部，可以實現(xiàn)下说贝。heap可以細看，結合網上的博客之類的慎颗，注意堆需要的迭代器為RandomAccessIterator乡恕。
rb_tree
個人覺得這章寫的不錯，樹的概念俯萎，二叉搜索樹傲宜、平衡二叉樹，紅黑樹夫啊。在5.2.2節(jié)函卒，代碼是從下到上的，不是從上到下撇眯。實現(xiàn)紅黑樹的刪除時报嵌，rebanlance參考了這篇博客，注意leftmost熊榛、rightmost和root的變化锚国。注意全黑的情況，待刪除節(jié)點為黑色玄坦，沒有孩子血筑，兄弟節(jié)點為黑色，也沒有孩子，父節(jié)點為黑色豺总，這種情況需要迭代調整顏色车伞。
hashtable
這個實現(xiàn)比較容易，如果是從前面實現(xiàn)到這個的話园欣，書本只是一個參考的作用了帖世。
算法
6.1和6.2可以看下， 然后找?guī)讉€實現(xiàn)一遍沸枯，推薦find日矫、lower_bound，其它的感興趣可以看下绑榴。
仿函數(shù)
知道unary_function和binary_function的定義哪轿，以及是如何與算法結合使用的，可以實現(xiàn)下identity和select1st翔怎，set和map可以用到窃诉。
配接器
知道三種不同的配接器，由于容器配接器前面實現(xiàn)過赤套，這里可以實現(xiàn)下insert和stream迭代器飘痛，代碼量不大。仿函數(shù)適配器也可以實現(xiàn)下容握，ptr_fun宣脉。
總結
全部寫一遍的話，基本上對STL是很熟悉了剔氏，使用起來更加得心應手塑猖，對STL的模板編程(GP?)也是有了更深的了解，當然精通是肯定談不上的-谈跛。對內存分配羊苟、type_traits更熟悉。貌似除了這些就沒了感憾。蜡励。。打基礎用的項目吧吹菱，后面可以做些面向對象方面的東西巍虫，偏網絡、多線程方面更好吧應該鳍刷。
