STL源码笔记（16）—单链表slist

女爷i 2022-07-24 05:12 159阅读 0赞

# STL单链表slist简介 #

## 概述 ##

slist（Single linked list）顾名思义，是一个单向链表，这个容器并不在标准规格之内，在我几年的代码学习生涯中也是第一次听说，既然侯老师的书中提到了，那也还是学习一蛤。

slist与list的主要差别是，前者的迭代器属于单向的Forward Iterator（可读写），后者的迭代器属于双向的Bidirectional Iterator（可以双向读写）。看起来slist的功能应该会不如list，但由于其单向链表的实现，其消耗的空间更小，某些操作更快。

回忆数据结构中在单链表的某个位置插入元素的过程，slist的底层实现就是单链表，因此会遇到我们曾经遇到过的麻烦：**在某个位置插入时，必须要用一个指针从头到尾找到待插入位置的前一个位置。**这便是在slist的一个大的缺点之一，因此，书中提到，**在非起点位置使用insert或erase的算法是不智之举。**

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

## slist源码实现 ##

在SGI STL源码中，slist的实现位于**`stl_slist.h`**中

### 节点设计 ###

容器的核心就是其底层存储于迭代器设计了，对于节点设计，使用了继承的关系，实际上简单的来说就是单链表的节点：**指向下一个节点的指针和数据**

![这里写图片描述][20160514084339727]  
代码实现如下：

//stl_slist.h
    //单向链表的节点结构
    struct _Slist_node_base
    {
      _Slist_node_base* _M_next;
    };
    //使用继承来实现单链表的节点结构：指针+数据 
    template <class _Tp>
    struct _Slist_node : public _Slist_node_base
    {
      _Tp _M_data;
    };

基于单链表的特性和节点的结构，源码中提供了不少内部全局函数，这些函数不对外开放的，仅仅在某些对外使用的接口实现中直接调用，例如：

//全局函数：单链表节点数，其实就是简单的遍历计数
    inline size_t __slist_size(_Slist_node_base* __node)
    {
      size_t __result = 0;
      for ( ; __node != 0; __node = __node->_M_next)
        ++__result;
      return __result;
    }
    //全局函数：已知某一节点，插入新节点于其后
    //返回插入节点之后的指针。
    inline _Slist_node_base*
    __slist_make_link(_Slist_node_base* __prev_node,
                      _Slist_node_base* __new_node)
    {
      __new_node->_M_next = __prev_node->_M_next;
      __prev_node->_M_next = __new_node;
      return __new_node;
    }

### 迭代器设计 ###

如上图所示，迭代器同样是使用了继承的方式：

//单向链表的迭代器基本结构
    struct _Slist_iterator_base
    {
      typedef size_t               size_type;
      typedef ptrdiff_t            difference_type;
      typedef forward_iterator_tag iterator_category;//单向的可读写迭代器
    
      _Slist_node_base* _M_node;//数据类型，这里父类只包含指针结构
    
      //构造函数：父类只包含了带参数的构造函数
      _Slist_iterator_base(_Slist_node_base* __x) : _M_node(__x) {}
      void _M_incr() { _M_node = _M_node->_M_next; }//指针向后移动一位
    
      bool operator==(const _Slist_iterator_base& __x) const {
        return _M_node == __x._M_node;//重载==指针是否相等
      }
      bool operator!=(const _Slist_iterator_base& __x) const {
        return _M_node != __x._M_node;//重载!=指针是否相等
      }
    };
    
    //继承关系
    //单向链表的迭代器结构
    template <class _Tp, class _Ref, class _Ptr>
    struct _Slist_iterator : public _Slist_iterator_base
    {
      typedef _Slist_iterator<_Tp, _Tp&, _Tp*>             iterator;//定义迭代器类型
      typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
      typedef _Slist_iterator<_Tp, _Ref, _Ptr>             _Self;
    
      typedef _Tp              value_type;
      typedef _Ptr             pointer;
      typedef _Ref             reference;
      typedef _Slist_node<_Tp> _Node;//节点类型
    
      //构造函数
      //这里由于父类只包含了带参数的构造函数，因此子类只能显示的初始化父类的构造函数
      _Slist_iterator(_Node* __x) : _Slist_iterator_base(__x) {}
      _Slist_iterator() : _Slist_iterator_base(0) {}
      //拷贝构造函数
      _Slist_iterator(const iterator& __x) : _Slist_iterator_base(__x._M_node) {}
    
      //*访问符重载，返回元素的引用
      reference operator*() const { return ((_Node*) _M_node)->_M_data; }
    #ifndef __SGI_STL_NO_ARROW_OPERATOR
    //->访问符重载，返回元素的地址的引用
      pointer operator->() const { return &(operator*()); }
    #endif /* __SGI_STL_NO_ARROW_OPERATOR */
    
    //前置++重载
      _Self& operator++()
      {
        _M_incr();//直接调用父类函数指针向后移动一位
        return *this;
      }
      //后置++重载
      _Self operator++(int)
      {
        _Self __tmp = *this;
        _M_incr();//直接调用父类函数指针向后移动一位
        return __tmp;
      }
      //这里没有--的重载，因为Forward Iterator的特性不支持双向操作
    };

### slist的数据结构 ###

有了迭代器设计和节点设计的基础，单链表的实现就非常之简单了。虽然算法实现很简单，但是由于用到了继承关系，设计上看起来就有些复杂了：

//stl_slist.h
    //父类定义了空间构造器等
    template <class _Tp, class _Alloc> 
    struct _Slist_base {
      typedef _Alloc allocator_type;
      allocator_type get_allocator() const { return allocator_type(); }
    
      //构造函数，初始化指针
      _Slist_base(const allocator_type&) { _M_head._M_next = 0; }
      ~_Slist_base() { _M_erase_after(&_M_head, 0); }
    
    protected:
      typedef simple_alloc<_Slist_node<_Tp>, _Alloc> _Alloc_type;//空间构造器类型
      _Slist_node<_Tp>* _M_get_node() { return _Alloc_type::allocate(1); }//分配一个节点
      void _M_put_node(_Slist_node<_Tp>* __p) { _Alloc_type::deallocate(__p, 1); }//释放一个节点空间
    
      //删去指定元素的后一个位置的元素
      _Slist_node_base* _M_erase_after(_Slist_node_base* __pos)
      {
        _Slist_node<_Tp>* __next = (_Slist_node<_Tp>*) (__pos->_M_next);
        _Slist_node_base* __next_next = __next->_M_next;
        __pos->_M_next = __next_next;
        destroy(&__next->_M_data);//释放节点
        _M_put_node(__next);//释放空间
        return __next_next;
      }
      //删去区间内的所有元素
      _Slist_node_base* _M_erase_after(_Slist_node_base*, _Slist_node_base*);
    
    protected:
      _Slist_node_base _M_head;//“头指针”，但事实上并不是指针
    };  
    
    #endif /* __STL_USE_STD_ALLOCATORS */
    
    //根据代码来看，删除应该是前闭后开
    template <class _Tp, class _Alloc> 
    _Slist_node_base*
    _Slist_base<_Tp,_Alloc>::_M_erase_after(_Slist_node_base* __before_first,
                                            _Slist_node_base* __last_node) {
      _Slist_node<_Tp>* __cur = (_Slist_node<_Tp>*) (__before_first->_M_next);//记录区间的前一个位置
      while (__cur != __last_node) {
        _Slist_node<_Tp>* __tmp = __cur;
        __cur = (_Slist_node<_Tp>*) __cur->_M_next;
        destroy(&__tmp->_M_data);
        _M_put_node(__tmp);
      }
      __before_first->_M_next = __last_node;
      return __last_node;
    }

//stl_slist.h
    template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
    class slist : private _Slist_base<_Tp,_Alloc>
    {
    private:
      typedef _Slist_base<_Tp,_Alloc> _Base;//父类类型定义
    //...
    //创建特定元素值构造节点(内部函数)
      _Node* _M_create_node(const value_type& __x) {
        _Node* __node = this->_M_get_node();
        __STL_TRY {
          construct(&__node->_M_data, __x);//直接构造
          __node->_M_next = 0;
        }
        __STL_UNWIND(this->_M_put_node(__node));
        return __node;//返回指针
      }
      //创建元素值为0的节点(内部函数)
      _Node* _M_create_node() {
        _Node* __node = this->_M_get_node();
        __STL_TRY {
          construct(&__node->_M_data);
          __node->_M_next = 0;
        }
        __STL_UNWIND(this->_M_put_node(__node));
        return __node;
      }
    explicit slist(const allocator_type& __a = allocator_type()) : _Base(__a) {}//构造函数，指定空间配置器类型
    //此外，还有许多用到其内部函数的构造函数，例如_M_insert_after_range等，这里就不一一列出。
    };

除了上述简单介绍的构造和析构操作外，slist作为容器，它应该有一些容器统一的接口实现吧，根据STL的习惯，插入操作会将新元素插入于指定位置的前面，而非之后，作为一个单项链表，slist没有任何方便的办法可以回头定出前一个位置（没有prev指针），基于效率考虑，slist不提供push\_back()只提供push\_front()函数，这样插入顺序和元素次序就会相反。

//stl_slist.h
    //首尾迭代器，包含头结点
      iterator begin() { return iterator((_Node*)this->_M_head._M_next); }
      const_iterator begin() const 
        { return const_iterator((_Node*)this->_M_head._M_next);}
    
      iterator end() { return iterator(0); }
      const_iterator end() const { return const_iterator(0); }
    
      //调用内部函数求size大小
      size_type size() const { return __slist_size(this->_M_head._M_next); }
    
      //判断是否为空
      bool empty() const { return this->_M_head._M_next == 0; }
    
      //在头部插入元素
      void push_front(const value_type& __x)   {
        __slist_make_link(&this->_M_head, _M_create_node(__x));
      } 
       //在头部删除元素 
      void pop_front() {
        _Node* __node = (_Node*) this->_M_head._M_next;
        this->_M_head._M_next = __node->_M_next;
        destroy(&__node->_M_data);
        this->_M_put_node(__node);
      }

[20160514084339727]: /images/20220722/6ff5d75497d3480ca06a3a3016627e64.png