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

妖狐艹你老母 2022-07-30 14:55 202阅读 0赞

# 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;
        }
      }

图示：

![这里写图片描述][20160419113721784]

在看刚刚提到的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]);//将有序序列换出去
      }
    }

--------------------

[20160419113721784]: /images/20220724/cbcc957a55144c259e10a1eca3f0ad3b.png