4.9.1 slist概述

    在STL标准中提供了双向链表list，本文介绍的是SGISTL中<stl_slist.h>定义的单向链表slist。单向链表的迭代器是属于正向迭代器，所以在单链表进行插入元素时，在指定节点之后插入时时间是常数O(1)，在指定节点之前插入时需要线性时间O(n)。相比于双向链表list，它所耗用的空间更小，某些操作更快。slist和list有一个共同的特殊是：它们的插入，移除，拼接等操作不会造成原有的迭代器失效。

    根据STL的习惯，插入操作会将新元素插入于指定位置之前，作为单向链表，slist不能回头定出前一个位置，因此它必须从头找起。为此，slist特别提供了insert_after() 和erase_after()供灵活使用。同理，slist只提供push_front()。

4.9.2 slist的节点

        slist的节点结构只有存储节点数据和指向下一个节点的指针。

//单向链表的节点基本结构  
struct _Slist_node_base  
{  
  _Slist_node_base* _M_next;  
};  
//单向链表节点结构  
template <class _Tp>  
struct _Slist_node : public _Slist_node_base  
{  
  _Tp _M_data;  
};  

4.9.3 slist的迭代器

    由于slist是单向链表，所以只提供正向迭代器，若要查找指定节点的前一个节点时，operator--不能使用，只能从头遍历，但是可以operator++和operator*操作；

//单向链表的迭代器的基本结构  
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 */  
  
  //前缀operator++  
  _Self& operator++()  
  {  
    _M_incr();  
    return *this;  
  }  
  //后缀operator++  
  _Self operator++(int)  
  {  
    _Self __tmp = *this;  
    _M_incr();  
    return __tmp;  
  }  
  //单向链表不能operator--操作  
};  

4.9.4 slist的数据结构

      slist单向链表只需要给出该链表的头部head，便可以通过head->next遍历该链表；

 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;  
};    
  
  
//单向链表slist定义  
template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >  
class slist : private _Slist_base<_Tp,_Alloc>  
{  
  // requirements:  
  
  __STL_CLASS_REQUIRES(_Tp, _Assignable);  
  
private:  
  typedef _Slist_base<_Tp,_Alloc> _Base;  
public:  
  typedef _Tp                value_type;  
  typedef value_type*       pointer;  
  typedef const value_type* const_pointer;  
  typedef value_type&       reference;  
  typedef const value_type& const_reference;  
  typedef size_t            size_type;  
  typedef ptrdiff_t         difference_type;  
  
  typedef _Slist_iterator<_Tp, _Tp&, _Tp*>             iterator;  
  typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;  
  
  
private:  
  typedef _Slist_node<_Tp>      _Node;  
  typedef _Slist_node_base      _Node_base;  
  typedef _Slist_iterator_base  _Iterator_base;  
  ...  
};