在根据《STL源码剖析》实现STL的过程中，有了一点感想，这里进行记录，给感兴趣的朋友做个参考。代码参见githubbridgeqiao
前期准备
不管对STL的熟悉程度如何，有几点是要知道的。
- 至少是知道大概是怎么用的，用过push_back、pop_back之类的函数；
- 熟悉C++的struct和class定义，常用的语法，知道template的特化和偏特化，阅读过《c++ primer》最好；
- 读过《effective c++》更好，知道c++默认构造的四个函数和大概的对象内存模型（没有虚函数的对象和有虚函数的），面向对象编程基本概念；
- 代码实现时，最好用c++11的新特性，nullptr、using之类的，头文件使用c++的版本，就是普通的c头文件前加个
c去掉.h，比如limits.h改为climits。
STL背景
在书中的第一章有介绍，六大组件、GNU、不同的版本，1.9.1感觉没必要细看，定义的一些宏，自己实现代码的话没必要搞这么复杂，用c++11就行了，后几个小节倒是可以细看，特别是关于临时对象的，可以参考c++的move语义和RVO，减少一次拷贝析构。
空间配置器
最开始的简单allocator可以参考我写的一篇博客，书上的存在一点问题，当然直接忽略了也行，反正和后面的没联系。2.2.1可以忽略，从2.2.2开始看。需要知道new operator、operator new和placement new。里面的异常处理和宏定义都可以忽略。
一级空间配置器只有在分配大于128字节时起作用，使用malloc()分配内存，然后用placement new进行构造。销毁空间时，先析构，再free。扩展阅读c++内存管理，malloc在分配大于128KB时的实现。
二级空间配置器是为了减少内存碎片而使用的，使用free_list管理空闲内存，以每8个字节递增，从8字节到128字节，union obj可以简单理解为void*。大于128B，交给malloc分配，小于的话，使用free_list里找个空闲的块分配，如果free_list里面没有空闲的块，使用refill重新填充。
refill很有意思，它不直接参与分配内存，而是通过chunk_alloc在内存池分配，然后根据分到的内存，将第一小块返回给对象，后面剩余的给串起来，放到free_list中，这里要注意，每一个小块大小是按照8的倍数来的，不是对象要求的大小。这个refill函数里面将obj*强转成char*，其实可以直接用next_obj->data的，除了这里可能会用到union obj的特性，其它地方是真没发现有用到的。
uninitialized_**几个函数可以先实现，不用管type traits，按照书上的顺序看就行。
迭代器和traits
那个auto_ptr可以换成shared_ptr，更有意义一点，auto_ptr过时了。重点看3.3节后面，参考SFINAE(Substitution Is Not A Error)，在进行模板匹配时，用最近的那个。迭代器类型定义的时候，用最强化（精细化？）的那个，定义函数模板，用最低阶的那个。这个没什么好说的，最好都实现一遍，加强理解。
vector
从这章到hashtable都是容器的定义及实现，书上是按照概述、定义摘要、实际使用例子、迭代器、容器构造插入删除的顺序来的，感觉定义摘要没有把重点写出来，有点杂，应该主要关注容器的成员变量，以及它在插入删除时是大概怎样操作的，给读者一个感性的认识。
通过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]倍增长为宜，我觉得这个没有定数，只要不太大就行。
vector的迭代器是原始指针，所以当发生插入删除、内存变了的话，指针会失效。其它的照着实现就行，可能要细看的是插入多个元素的函数，注意const函数的实现。
list
成员变量只有一个node，为双向环状链表，node包括值data，两个指针prev、next。初始时，只有一个node，插入一个元素，往front插入，用next指针指向新的节点，往back插入，用prev指向新的节点。迭代器存放指向节点的指针，然后实现operator++之类的方法，目标是达到和原生裸指针的外在功能。结构比较简单，难点在算法的实现上，特别是sort函数，需要先实现swap、merge函数。
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个元素，继续第三轮。
deque
deque这章还不错，讲解的很细，实现起来比较麻烦，特别是迭代器，为了达到RandomAccess的效果，operator+=(int n)和operator-=(int n)，还有reallcate_map函数。
stack、queue和heap
stack和queue是容器适配器，外面套了个壳，看下接口就行，可以实现下。heap可以细看，结合网上的博客之类的，注意堆需要的迭代器为RandomAccessIterator。
rb_tree
个人觉得这章写的不错，树的概念，二叉搜索树、平衡二叉树，红黑树。在5.2.2节，代码是从下到上的，不是从上到下。实现红黑树的删除时，rebanlance参考了这篇博客，注意leftmost、rightmost和root的变化。注意全黑的情况，待删除节点为黑色，没有孩子，兄弟节点为黑色，也没有孩子，父节点为黑色，这种情况需要迭代调整颜色。
hashtable
这个实现比较容易，如果是从前面实现到这个的话，书本只是一个参考的作用了。
算法
6.1和6.2可以看下， 然后找几个实现一遍，推荐find、lower_bound，其它的感兴趣可以看下。
仿函数
知道unary_function和binary_function的定义，以及是如何与算法结合使用的，可以实现下identity和select1st，set和map可以用到。
配接器
知道三种不同的配接器，由于容器配接器前面实现过，这里可以实现下insert和stream迭代器，代码量不大。仿函数适配器也可以实现下，ptr_fun。
总结
全部写一遍的话，基本上对STL是很熟悉了，使用起来更加得心应手，对STL的模板编程(GP?)也是有了更深的了解，当然精通是肯定谈不上的-。对内存分配、type_traits更熟悉。貌似除了这些就没了。。。打基础用的项目吧，后面可以做些面向对象方面的东西，偏网络、多线程方面更好吧应该。
