STL剖析

STL.jpeg

1, allocator

两级配置方法，128bytes为边界，第一级：malloc/free or new/delete; 第二级：memory pool(free lists)
简单的memory pool 实现：

1.JPG

STL 中分为16个freelists, 每个管理8，16，24 ... 128大小的块

2 iterator

利用iterator_trait获得associated type

template <class Ite>
struct iterator_trait
{
  typename Ite::value_type value_type;
}

//partial specification for pointer
template<class T>
struct iterator_trait<T*>
{
  typedef T value_type;
}

3 container Container.jpeg

• 红黑树
  • 黑色节点个数一致
  • 红色节点的子节点为黑色

  • root = 黑色
    

    基本的旋转维护其平衡 270025006402285.gif

4, functor

class Fun
{
    bool operator() (){}
};