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

概述

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

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

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

---

源码实现">slist源码实现

在sgi stl源码中，slist的实现位于stl_slist.h中

节点设计

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

代码实现如下：

 

//stl_slist.h
//单向链表的节点结构
struct _slist_node_base
{
  _slist_node_base* _m_next;
};
//使用继承来实现单链表的节点结构：指针+数据 
template 
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 
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  
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  
_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 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);
  }