STL源码笔记（10）—序列式容器之list

STL中的list容器本质上来说就是一个双向链表，可以高效的完成插入删除等，所以它的源码中与数据结构中的双向链表差不多，在STL源码中list是一个模板类，以封装一些操作。

list数据结构

我们知道链表的节点分为数据域和指针域，对于双向链表来说，其指针域包含额外的指向上一个节点的指针，在STL源码stl_list.h中，用了继承的方法来表示：

struct _List_node_base {
  _List_node_base* _M_next;
  _List_node_base* _M_prev;
};
template <class _Tp>
struct _List_node : public _List_node_base {
  _Tp _M_data;
};
template <class _Tp, class _Alloc>
class _List_base 
{
//...
protected:
  _List_node<_Tp>* _M_node;//双向链表维护的指针
//...
};
//在class list中，用typedef做了进一步修饰
template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class list : protected _List_base<_Tp, _Alloc> {
//...
    typedef _List_node<_Tp> _Node;
//...
};

书中提到SGI list不仅是一个双向链表，还是一个环状的双向链表，为了保证STL容器前闭后开的一致性，这里可以在尾部插入一个空白节点，而list（事实上是在其父类定义的_List_node<_Tp>* _M_node;）维护的双向链表的“头指针”，就指向这个空白节点，由于在该双向链表是一个环，于是就有了：

template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class list : protected _List_base<_Tp, _Alloc> {
public:
    iterator begin()             { return (_Node*)(_M_node->_M_next); }
    const_iterator begin() const { return (_Node*)(_M_node->_M_next); }

    //这里end()实际上返回的是空白节点，也就是最后一个节点的后一个位置，
    //就满足了前闭后开的原则
    iterator end()             { return _M_node; }
    const_iterator end() const { return _M_node; }
};

根据此可以容易获取链表的某些属性：

//当只剩下一个“刻意的”空节点时list为空
bool empty() const { return _M_node->_M_next == _M_node; }
//distance返回迭代器之间的距离
size_type size() const 
{
    size_type __result = 0;
    distance(begin(), end(), __result);
    return __result;
}

关于上述distance函数，书中仅仅简单一个全局函数，在第3章迭代器萃取的时候，以advance为示例，而distance函数与advance在同一个文件中stl_iterator_base.h，都是根据不同的iterator_category(迭代器类型)，来选择不同的重载版本：这里根据链表的特性（不支持随机元素访问），应该选择：

template <class _InputIterator, class _Distance>
inline void __distance(_InputIterator __first, _InputIterator __last,
                       _Distance& __n, input_iterator_tag)
{
  while (__first != __last) { ++__first; ++__n; }
}

list的构造与内存管理

书中给出4list-test.cpp从中可以大概看到list的某些机制，比如查找，插入，删除等，这些机制都是基于链表的一些操作，而对于链表这种数据结构来说，其内存管理（以插入为例），每次创建的节点都是一次内存分配的过程，这里就与空间配置器相关了:

typedef simple_alloc<_List_node<_Tp>, _Alloc> _Alloc_type;
_List_node<_Tp>* _M_get_node() { return _Alloc_type::allocate(1); }//申请
void _M_put_node(_List_node<_Tp>* __p) { _Alloc_type::deallocate(__p, 1); }//释放 

初始化时，会生成一个节点其next和prev指针都指向自己，在书中对其进行了简化（仅仅是链表操作），在源码中实际用到了继承的内容：

template <class _Tp, class _Alloc>
class _List_base //基类
{
public:
  typedef _Alloc allocator_type;
  _List_base(const allocator_type&) {//链表操作
    _M_node = _M_get_node();
    _M_node->_M_next = _M_node;
    _M_node->_M_prev = _M_node;
  }
};

template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class list : protected _List_base<_Tp, _Alloc> {//子类
  typedef _List_base<_Tp, _Alloc> _Base;
  typedef typename _Base::allocator_type allocator_type;
  allocator_type get_allocator() const { return _Base::get_allocator(); }

public:
//allocator_type()只是一个临时对象
//使用基类的构造函数
  explicit list(const allocator_type& __a = allocator_type()) : _Base(__a) {}
};

list元素操作

即链表操作，插入，删除等。

void push_front(const _Tp& __x) { insert(begin(), __x); }//向前插入
void push_back(const _Tp& __x) { insert(end(), __x); }//向后插入
iterator erase(iterator __position) {//删除指定元素
    _List_node_base* __next_node = __position._M_node->_M_next;
    _List_node_base* __prev_node = __position._M_node->_M_prev;
    _Node* __n = (_Node*) __position._M_node;
    __prev_node->_M_next = __next_node;
    __next_node->_M_prev = __prev_node;
    _Destroy(&__n->_M_data);
    _M_put_node(__n);
    return iterator((_Node*) __next_node);
 }
//erase删除范围元素
template <class _Tp, class _Alloc>
typename list<_Tp,_Alloc>::iterator list<_Tp, _Alloc>::erase(iterator __first, 
                                                             iterator __last)
{
  while (__first != __last)
    erase(__first++);
  return __last;
}

类似的还有很多比如pop_front()、pop_back()等等，都是简单的链表操作，不过书中提到一个很重要的操作叫transfer()，作用就是将特定范围的元素移动到position之前，说白了也是链表操作，只是看起来比较吃力。这个transfer作为内部的函数，为splice、sort、merge等奠定了良好的基础。

//将特定范围的元素移动到__position之前
void transfer(iterator __position, iterator __first, iterator __last) {
    if (__position != __last) {
      // Remove [first, last) from its old position.
      __last._M_node->_M_prev->_M_next     = __position._M_node;
      __first._M_node->_M_prev->_M_next    = __last._M_node;
      __position._M_node->_M_prev->_M_next = __first._M_node; 

      // Splice（接合） [first, last) into its new position.
      _List_node_base* __tmp      = __position._M_node->_M_prev;
      __position._M_node->_M_prev = __last._M_node->_M_prev;
      __last._M_node->_M_prev     = __first._M_node->_M_prev; 
      __first._M_node->_M_prev    = __tmp;
    }
  }

图示：

在看刚刚提到的splice、sort、merge等操作就简洁不少：

splice

//版本1：将整个链表接在__position之前
 void splice(iterator __position, list& __x) {
    if (!__x.empty()) 
      this->transfer(__position, __x.begin(), __x.end());
  }
 //版本2：将__i指向的元素接合到__position之前
  void splice(iterator __position, list&, iterator __i) {
    iterator __j = __i;
    ++__j;
    if (__position == __i || __position == __j) return;
    this->transfer(__position, __i, __j);
  }
 //版本3：将first last范围的元素接合到position之前
 //position不能位于[fisrt，last)内
  void splice(iterator __position, list&, iterator __first, iterator __last) {
    if (__first != __last) 
      this->transfer(__position, __first, __last);
  }

merge

//将两个有序序列合并到*this上
template <class _Tp, class _Alloc>
void list<_Tp, _Alloc>::merge(list<_Tp, _Alloc>& __x)
{
  iterator __first1 = begin();
  iterator __last1 = end();
  iterator __first2 = __x.begin();
  iterator __last2 = __x.end();
  while (__first1 != __last1 && __first2 != __last2)
    if (*__first2 <*__first1) {
      iterator __next = __first2;
      transfer(__first1, __first2, ++__next);
      __first2 = __next;
    }
    else
      ++__first1;
  if (__first2 != __last2) transfer(__last1, __first2, __last2);
}

sort

//list容器不能使用泛型算法sort()，因为list作为链表不支持随机存取，
//因此，list只能使用自己的sort，这里书中说的是quick sort，开始以为是非递归的快排，
//在VS下面单步了一下，更觉得像两两归并，大致的过程就是每次从原list里面取出一个元素，
//放到carry里面，这个counter数组用来保存有序lists（这些list的size可能不同也可能相同），
//并且counter数组中包含元素多的有序list总是往数组后面移动，来给原list中后取出的元素腾出合并的位置。
//而carry更像是一个用来交换的临时list，先是存放新取出来的元素，
//然后跟counter中的list换进换出进行两两合并。
//最后当原list中所有的元素都被取出来以后(跳出while循环)，
//要将counter中临时的有序序列merge成一个有序序列，
//最后再将有序序列swap返回给当前list（即调用sort()函数的list本身也就是*this）
template <class _Tp, class _Alloc>
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.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]);//将__counter中的有序序列归并成一个有序序列
    swap(__counter[__fill-1]);//将有序序列换出去
  }
}