C++的书也看了几本了，除了最开始的《C++ Primer》让自己初步了解了C++的基本语法，《Effective C++》和《深度探索C++对象模型》基本都没记住太多东西，感觉还不是很适合我这种入门的门槛还没跨过去的人，这些书应该适合有一定代码量之后再去学习。所以，自己有了非常强烈的意愿想去写点C++的代码，或者看看别人的C++代码到底是怎么写的。知乎上看到有人推荐自己实现一遍STL的源码，正好之前也想看《STL源码剖析》这本书，所以就从图书馆借来看了一些，发现SGI STL的源代码没有想象的那么晦涩，结构还是很清晰的，感觉可以写起来哇！那就开篇博文专门来记录一下看书和源码过程中的收获，顺便也自己实现一个STL 的子集吧，开搞开搞！
空间配置器
STL的空间配置器用来进行内存的申请与释放，SGI采用的是一个特殊的两级空间配置器，第一级直接采用malloc和free来申请和释放内存空间，第二级则采用了内存池技术。具体来说，如果申请的区块大于128 bytes，那么就直接交由第一级配置器来配置，否则，第二级配置器维护了一个内存空间的链表free list，分别用来管理大小为8、16、24、32、40……128的内存区块。每次申请会把申请空间对齐为8个倍数，然后从对应的链表下取出相应大小的空间，释放时再将空间还回，这样就节省了大量的malloc操作。
当对应的链表下没有可用的空间时，会从内存池内取出若干个对应大小的空间来填充链表，当然这里就比较复杂了：
-
如果内存池里的空间足够，那么直接取出；
-
如果内存池内的空间不足，那么检查是否能先返回至少1个空间块（例如申请了20个32 bytes的空间，但内存池只能提供10个，那么就先返回10个），
-
如果连一个都提供不了，那么就只能调用malloc来申请新的空间
-
如果malloc失败，那就调用第一级的配置器，那里有申请失败的一些处理函数
Traits编程技法
traits这个东西在《Effective C++》里就看到了，当时没有理解，感觉也没什么作用，而在STL这里发现被大量使用，甚至被作者称为STL源代码门钥。traits编程最主要的作用是在迭代器上，用来“榨取”迭代器的类型信息。
考虑如下代码：
template<typename T>class Myiter{
typedef T value_type;
...
};
template<typename I> typename I::value_type func(I ite){
return *ite;
}
通过在Myiter中内嵌一个类别信息，就可以在模板函数func中使用类型T的信息了，但是在STL中，如果func是一个以迭代器为输入参数的函数的话，它也因该支持内置的指针类型，而内置指针并不是一个类，无法定义内嵌类型，这个时候怎么办呢？
我们可以利用偏特化来解决这个问题，专门来设计一个类来“萃取”迭代器的类型信息
template<class I> class iterator_traits{
typedef typename I::value_type value_type;
}
这样func可以写成：
template<typename I>
typename iterator_traits<I>::value_type func(I ite){
return *ite;
}
而对于内置的指针类型，我们可以定义interator_traits的一个偏特化版本
template<class I> class iterator_traits<T*>{
typedef T value_type;
}
template<class I> class iterator_traits<const T*>{
typedef T value_type;
}
这样函数在迭代器和内置指针类型上就都可以正常运行了！
所以，为了符合STL的标准，每个迭代器都要定义一些相应类型，才能兼容哦，这些类型包括value_type, difference_type, pointer, reference, iterator_category, 而inerator_traits就会“萃取”出这些类型。
template<class I> class iterator_traits{
typedef typename I::value_type value_type;
typedef typename I::difference_type difference_type;
typedef typename I::pointer pointer;
typedef typename I::reference reference;
typedef typename I::iterator_category iterator_category;
}
为了以防万一你忘记定义这些东西，STL提供了一个iterator class，每一个新的迭代器都继承于它，
template <class Category,
class T,
class Distance = ptrdiff_t,
class Pointer = T*,
class Reference = T&>
struct interator{
typedef Category iterator_category;
typedef T value_type;
typedef Distance defference_type;
typedef Pointer pointer;
typedef Reference reference;
};
由于后三个都有默认值，所以在定义新的迭代器时，只需要继承该类并提供category和T的信息就好。
序列式容器
vector
对于每个容器来说，个人感觉内存管理总是最重要的。vector的元素在内存中全部都是连续存放的，所以vector在中间插入元素效率可能会很慢，因为可能会涉及到整块内存的移动。当空间不够的时候，就会重新申请原空间两倍大小的新内存区域，然后把数据整体迁移过去。所以插入元素后，vector的迭代器可能会失效哦。
说到vector的迭代器，其实没有单独的vector_iterator的struct，直接采用的就是内置类型的指针，所以它的类型是random access itrator。
vector的其他方面应该都还好，仔细地写好就好了。但是目前只实现了一小部分功能，还有其他的一些例如：const interator，reverse interator这些，都还没有加入，可以之后继续完善。
list
list的内存结构和vector有所不同，它不是连续存储的，而是一个类似双向链表的结构。所以，有一个单独的list_node的struct，里边存储了数据，前向指针prev和后向指针next。
list的内部其实是一个循环双向链表，其中存储了一个空的list_node作为哨兵节点（或者说头节点应该也可以吧）。当list是空的时候，这个node的prev和next都指向自身。
list的迭代器是一个bidirectional iterator，里边封装了一个指向list_node的指针。需要注意的是在重载迭代器的 “->”操作符时，具体的写法哦。
reference operator*() { return node->data; }
pointer operator->() { return &(operator*()); }
list有一个比较反常理的地方是它的size函数，是O(n)复杂度的，而不是O(1)的，作者的解释说是，为了在执行splice操作的时候，不用去遍历一遍需要接合部分的长度。所以，当list长度过大的时候，size()的性能可能会有些差，也许是个隐藏的坑！
list中有一个sort函数，《STL源码剖析》里边说是quick_sort，看了半天没看懂，最后查了一些资料，其实是一个merge sort。
template<class T, class alloc>
void list<T, alloc>::sort() {
list<T, alloc> carry;
list<T, alloc> counter[64];
int fill = 0;
while (!empty()) {
carry.splice(carry.begin(), *this, begin());
int i = 0;
while (i < fill && !counter[i].empty()) {
counter[i].merge(carry);
carry.swap(counter[i++]);
}
carry.swap(counter[i]);
if (i == fill) ++fill;
}
for (int i = 1; i < fill; ++i)
counter[i].merge(counter[i-1]);
swap(counter[fill-1]);
}
函数中用counter数组记录2^n个元素merge排序后的结果，所以其实是一个非递归版本的merge sort。
deque
deque也是一个连续空间的容器，但是他与vector不一样的是，它是双向开口的，即在两端都可以在常数时间内进行元素插入和删除操作。而且，deque没有所谓容量的概念，它的连续空间实际上是由多段连续空间组合而成的，可以随时增加一段新的空间连接起来，因此，deque不会像vector那样，在空间不足时，申请更大的空间，然后复制元素，再释放旧空间。另外，deque有自己的迭代器，虽然是Random Access Iterator，但是比起vector的普通指针效率还是差了很多。
deque的内存管理
deque中存在一个“中控器”，来管理deque的内存。这个中控器其实是个数组，类似于整个STL的内存池的数组，数组的每个元素也是一个指针，指向deque存储的数据类型的数据。deque的数据会尽量放置在中控器的中间部位，这样给deque的两端都留下一些空闲位置，可以用来插入新的数据。当空间不够的时候，将会申请更大的一个中控器。
