更多精彩内容，请关注微信公众号：后端技术小屋

1 相关文件

list
list.h
stl_list.h

2 链表节点结构

基类_List_node_base只有_M_prev, _M_prev，分别指向前置节点和后继节点，由此看出STL list是双向链表（首节点为空）

struct _List_node_base {
  _List_node_base* _M_next;
  _List_node_base* _M_prev;
}

派生类_List_node还有_M_data，用于存放数据项

template <class _Tp>
struct _List_node : public _List_node_base {
  _Tp _M_data;
}

3 链表的内存分配

同vector, 申请内存的调用链如下。allocator见STL源码分析–内存分配器

_Alloc_type::allocate
  -> simple_alloc<_List_node<_Tp>, _Alloc>::allocate
    -> _Alloc::allocate (list中_Alloc缺省为__STL_DEFAULT_ALLOCATOR(_Tp))
      -> allocator<_Tp>

4 list接口

4.1 默认构造

注意用户可为list实例自定义内存分配器，内存分配器类型通过模板参数传入，内存分配器实例通过函数参数传入。_M_get_node从内存分配器中申请一个链表节点_List_node<_Tp>大小的内存。使用默认构造函数时，list中并没有任何元素，因此_M_get_node中只申请内存，但并不在其上构造_Tp对象，即该节点是空的哨兵节点。

  explicit list(const allocator_type& __a = allocator_type()) : _Base(__a) {}

  _List_base(const allocator_type&) {
    _M_node = _M_get_node();
    _M_node->_M_next = _M_node;
    _M_node->_M_prev = _M_node;
  }

4.2 从元素个数与值构造

实现：连续向list中插入__n个值为__value的元素
调用链如下。

list::list
  -> list::insert(批量版本，一次插入n条数据)
    -> list::_M_fill_insert
      -> list::insert(非批量，一次插入1条数据)

相关代码片段如下：

``` c++
// list::list
  list(size_type __n, const _Tp& __value,
       const allocator_type& __a = allocator_type())
    : _Base(__a)
    { insert(begin(), __n, __value); }
   

// list::insert(批量版本，一次插入n条数据)
 void insert(iterator __pos, size_type __n, const _Tp& __x)
    { _M_fill_insert(__pos, __n, __x); }
   
   
   
// list::_M_fill_insert
template <class _Tp, class _Alloc>
void 
list<_Tp, _Alloc>::_M_fill_insert(iterator __position,
                                  size_type __n, const _Tp& __x)
{
  for ( ; __n > 0; --__n)
    insert(__position, __x);
}

// list::insert(非批量，一次插入1条数据)  
  iterator insert(iterator __position, const _Tp& __x) {
    _Node* __tmp = _M_create_node(__x);
    __tmp->_M_next = __position._M_node;
    __tmp->_M_prev = __position._M_node->_M_prev;
    __position._M_node->_M_prev->_M_next = __tmp;
    __position._M_node->_M_prev = __tmp;
    return __tmp;
  }

_M_create_node也会新建链表节点，其与_M_get_node的不同在于会在内存上构造值为__x的_Tp对象。

  _Node* _M_create_node(const _Tp& __x)
  {
    _Node* __p = _M_get_node();
    __STL_TRY {
      _Construct(&__p->_M_data, __x);
    }
    __STL_UNWIND(_M_put_node(__p));
    return __p;
  }

4.3 从容器区间构造

遍历容器区间[__first, __last), 依次将元素插入list中

  // We don't need any dispatching tricks here, because insert does all of
  // that anyway.  
  template <class _InputIterator>
  list(_InputIterator __first, _InputIterator __last,
       const allocator_type& __a = allocator_type())
    : _Base(__a)
    { insert(begin(), __first, __last); }

template <class _Tp, class _Alloc>
void 
list<_Tp, _Alloc>::insert(iterator __position,
                         const_iterator __first, const_iterator __last)
{
  for ( ; __first != __last; ++__first)
    insert(__position, *__first);
}

4.4 复制构造

实现上同从容器区间构造类似，在此略过。

  list(const list<_Tp, _Alloc>& __x) : _Base(__x.get_allocator())
    { insert(begin(), __x.begin(), __x.end()); }

4.5 析构函数

实现上分两步：

  • 对于每个除_M_node的节点，依次遍历并对其中的_Tp执行析构，并释放节点内存。
  • 对于头节点，直接释放节点内存。

_M_put_node调用_Alloc_type::deallocate释放内存。

  ~list() { }

  ~_List_base() {
    clear();
    _M_put_node(_M_node);

template <class _Tp, class _Alloc>
void 
_List_base<_Tp,_Alloc>::clear() 
{
  _List_node<_Tp>* __cur = (_List_node<_Tp>*) _M_node->_M_next;
  while (__cur != _M_node) {
    _List_node<_Tp>* __tmp = __cur;
    __cur = (_List_node<_Tp>*) __cur->_M_next;
    _Destroy(&__tmp->_M_data);
    _M_put_node(__tmp);
  }
  _M_node->_M_next = _M_node;
  _M_node->_M_prev = _M_node;
}

  void _M_put_node(_List_node<_Tp>* __p) { _Alloc_type::deallocate(__p, 1); }

4.6 resize

遍历一遍list, 得到链表长度，然后根据长度判断是否对链表进行增长或减短

  • 如果是前者，调用insert在链表尾部插入new_size - __len个值为__x的节点
  • 如果是后者，调用erase在链表尾部删除__len - new_size个节点 因为会遍历全部节点，最好不要执行list::resize, list.size同理

template <class _Tp, class _Alloc>
void list<_Tp, _Alloc>::resize(size_type __new_size, const _Tp& __x)
{
  iterator __i = begin();
  size_type __len = 0;
  for ( ; __i != end() && __len < __new_size; ++__i, ++__len)
    ;
  if (__len == __new_size)
    erase(__i, end());
  else                          // __i == end()
    insert(end(), __new_size - __len, __x);
}

4.7 reverse

从头节点_M_node开始逆序遍历链表，交换所有节点的prev和next指针

inline void __List_base_reverse(_List_node_base* __p)
{
  _List_node_base* __tmp = __p;
  do {
    __STD::swap(__tmp->_M_next, __tmp->_M_prev);
    __tmp = __tmp->_M_prev;     // Old next node is now prev.
  } while (__tmp != __p);
}

4.8 sort

sort代码如下所示。list排序时，链表中维护临时链表__carry和链表数组__counter[64], 和__fill状态。其中__counter用于暂存当前的排序结果，__fill表示当前已被使用的__counter数组中的链表数量。

注意：代码中调用merge方法时，会将两个list按照顺序合并成一个。假设有两个list a与b, 调用a.merge(b)之后，b中所有节点都被转移到a中，b为空链表，a中包含了所有的节点，并按照顺序排列。


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]);
    swap(__counter[__fill-1]);
  }
}

举个例子可能更好理解一些：假设链表中有4个值，从前到后分别为v0, v1, v2, v3。__counter数组长度为4, 即__counter[0], __counter[1], __counter[2], __counter[3]

  • 初始状态：__fill = 0, __counter中所有链表为空
  • 第一轮循环：加入v0, 状态变成__counter[0] = {v0}, __fill = 1
  • 第二轮循环： 加入v1, 变成__counter[0] = {}, __counter[1] = {v0, v1}, __fill = 2
  • 第三轮： 加入v2, 变成__counter[0] = {v2}, __counter[1] = {v0, v1}, __fill = 2
  • 第四轮： 加入v3, 变成__counter[0] = {}, __counter[1] = {}, __counter[2] = {v0, v1, v2, v3}, __fill = 3
  • 最终得到一组__counter[4]，从左到右merge所有__counter中的链表，最终得到排过序的{v0, v1, v2, v3}结果, 并通过swap将结果转移给list对象本身。

其实list中sort算法就是非递归版本的归并排序，时间复杂度为O(n logn)

推荐阅读

更多精彩内容，请扫码关注微信公众号：后端技术小屋。如果觉得文章对你有帮助的话，请多多分享、转发、在看。
二维码