STL漫谈

Traits
Iterator是STL的核心思想。Iterator是把针对容器的算法与容器的具体实现分离、解耦的设计模式。以C++的泛型为例，Iterator允许我们这样写代码：

template <typename Iter>
void f(Iter begin, Iter end)
{
    //do something
}

但是，我们都知道Iterator是一种“类指针”，对Iterator解引用会得到容器中的对象。但是，这个对象的类型是什么呢？我们不得而知。如果我们需要一个临时变量的话，那么这就是一个问题。例如：

template <typename Iter>
void f(Iter begin, Iter end)
{
    WHAT temp = *begin;
}

这里的WHAT是什么类型呢？
为了解决这个问题，我们在设计Iterator的时候，可以在Iterator中定义一个类型ValueType，然后通过typename Iterator::ValueType获取。例如：

template <typename Iter>
void f(Iter begin, Iter end)
{
    typename Iter::ValueType temp = *begin;
}

我们看似解决这个问题了。然而当一个容器他的Iterator并不是一个我们实现的类型，而是指针类型，即T*，那么我们显然不可能期待typename (T*)::ValueType返回什么。所以，我们需要再一层抽象，可以利用模板的偏特化：

template <typename Iter>
struct IteratorTraits
{
    using ValueType = typename Iter::ValueType;
};

template <typename T>
struct IteratorTraits<T*>
{
    using ValueType = T;
};

这样，我们想要获得Iterator里面的类型的时候，只需要调用typename IteratorTraits<Iter>::ValueType;即可。至此，我们已经完美解决问题。

---

Allocator
C++对于堆上空间的分配有自己的封装——new操作符。即，如果你编写这样的代码T* ptr = new T(args...);实际上就相当于：

T* ptr = (T*)malloc(sizeof(T));
ptr->T(args...);

用C++的描述方法，也相当于：

T* ptr = ::operator new(sizeof(T));
new (ptr) T(args...);

可以发现，C++的new操作符认为“分配堆空间”和“构造对象”是紧密联系、不可分割的。然而，频繁的分配和释放空间会浪费很多时间，所以可以在编程阶段就采用一定的内存管理手段，当然操作系统也会有自己的管理方式。我们可以采用最常规的内存管理手段，即空闲链表（类似Linux的slab）。我们可以用“容器<-空闲链表<-内存池<-堆”的架构来管理我们的内存。空闲链表可以管理[8, 16.., 128]的小字节分配，而超过128的字节可以直接用堆。