STL源码剖析（四）：容器（2）list

list是一个双向链表，为了满足半开半闭区间性质，还添加了一个用来标志的尾节点。

list插入和接合 *** 作不会造成原迭代器失效，而在vector中是行不通的；而不能向vector用原生指针做为迭代器，因为不能直接用++ *** 作。

看下list迭代器的结构设计，成员函数都挺简单的（++ ，--，==，->啥的），就不贴上来了

struct _List_iterator_base {
  typedef size_t                     size_type;  // list迭代器类型所占字节数
  typedef ptrdiff_t                  difference_type; // 1.区间
  typedef bidirectional_iterator_tag iterator_category; // 2.迭代器类型

  _List_node_base* _M_node;  // 普通指针，指向list的节点
};  

template
struct _List_iterator : public _List_iterator_base {
  // 用来初始化迭代器，主要用在construct里
  typedef _List_iterator<_Tp,_Tp&,_Tp*>             iterator;
  typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
  typedef _List_iterator<_Tp,_Ref,_Ptr>             _Self;

  typedef _Tp value_type;  // 3....
  typedef _Ptr pointer;   // 4....
  typedef _Ref reference;  // 5.....
  typedef _List_node<_Tp> _Node;
};

list缺省使用alloc做为空间配置器，并据此定义了一个list_node_allocator,更方便地以节点大小为配置单位。

template 
class list : protected _List_base<_Tp, _Alloc> {
  // requirements:

  __STL_CLASS_REQUIRES(_Tp, _Assignable);

  typedef _List_base<_Tp, _Alloc> _Base;
protected:
  typedef void* _Void_pointer;    

public:      
  typedef _Tp value_type;
  typedef value_type* pointer;
  typedef const value_type* const_pointer;
  typedef value_type& reference;
  typedef const value_type& const_reference;
  typedef _List_node<_Tp> _Node;
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;  // 为什么容器也要有 区间类型 呢？

  typedef simple_alloc<_List_node<_Tp>, _Alloc> _Alloc_type; // 定义于_List_base
  typedef typename _Base::allocator_type allocator_type;
  allocator_type get_allocator() const { return _Base::get_allocator(); }

public:
  typedef _List_iterator<_Tp,_Tp&,_Tp*>             iterator;
  typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
};

list的Sort()：STL算法sort()，只接收RAI，因此list需定义自己的sort()方法，sort函数用到了splice,merge，它们又都是基于transefer函数的。

template 
void list<_Tp, _Alloc>::sort()
{
  // Do nothing if the list has length 0 or 1.
  if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) {
    list<_Tp, _Alloc> __carry;
    list<_Tp, _Alloc> __counter[64];
    int __fill = 0;
    while (!empty()) {
      // 把当前链表的第一个元素放到carry的头部
      __carry.splice(__carry.begin(), *this, begin());
      int __i = 0;
      // 这个wihle循环是精华，crray不断和counter[0]、counter[1]...去合并
      // 假设和counter[0]成功合并，由于i