STL源码剖析（十二）序列式容器之slist

slist是这个版本的STL中的单向链表，它是非标准的，也就是STL的标准中并没有要求实现它。在C++11中，有一个标准的单向链表，称为forward_list，下面来看一看slist是如何实现的

一、slist的数据结构

template <class T, class Alloc = alloc>
class slist
{
public:
  typedef __slist_iterator<T, T&, T*>             iterator;
  ...
    
private:
  typedef __slist_node<T> list_node;
  typedef __slist_node_base list_node_base;
  ...
private:
  list_node_base head;
  ...
};

slist中只有一个成员head，它是单向链表的链表头，其定义如下

struct __slist_node_base
{
  __slist_node_base* next;
};

仅仅包含一个指针

下面看看slist中的链表节点的定义

template <class T>
struct __slist_node : public __slist_node_base
{
  T data;
};

__slist_node继承于__slist_node_base，因此每个__slist_node中都有两个变量，一个维护链表的指针，一个数据

__slist_node_base* next;
T data;

所以__slist_node可以设计成下面的模样

template <class T>
struct __slist_node
{
  __slist_node_base* next;
  T data;
};

但为什么需要使用继承呢？

那是因为可以使用基类指针指向派生类，编译器不会产生警告

slist内部数据结构如下

二、slist的迭代器

slist的迭代器也是采用继承的方式实现的，如下__slist_iterator继承于__slist_iterator_base

struct __slist_iterator : public __slist_iterator_base

我们先看__slist_iterator_base的定义

struct __slist_iterator_base
{
  /* STL迭代器的设计规范 */
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;
  typedef forward_iterator_tag iterator_category;

  __slist_node_base* node;

  void incr() { node = node->next; }

  ...
};

__slist_iterator_base的定义较为简单，它包含成员__slist_node_base* node，用于指向链表中的某个节点

然后还有自增操作incr，就是将当前的node指向下一个node

下面再来看看__slist_iterator的定义

template <class T, class Ref, class Ptr>
struct __slist_iterator : public __slist_iterator_base
{
  /* STL迭代器的设计规范 */
  typedef T value_type;
  typedef Ptr pointer;
  typedef Ref reference;
  
  reference operator*() const { return ((list_node*) node)->data; }
  
  self& operator++()
  {
    incr();
    return *this;
  }
};

__slist_iterator继承于__slist_iterator_base

它重载自增运算符，调用基类的incr函数，然后返回

它还重载的取值操作operator*，它先将node强制转换为派生类，然后再取出其中的data

三、slist的操作

3.1 构造函数

默认构造函数

slist() { head.next = 0; }

将链表设置为空

拷贝构造函数

slist(const slist& L) { range_initialize(L.begin(), L.end()); }

调用range_initialize，并传递首尾迭代器，下面看看range_initialize的定义

template <class InputIterator>
void range_initialize(InputIterator first, InputIterator last) {
  head.next = 0; //初始化链表头
  _insert_after_range(&head, first, last); //插入所有元素
}

首先初始化链表头，然后调用_insert_after_range插入所有的元素，其定义如下

template <class InIter>
void _insert_after_range(list_node_base* pos, InIter first, InIter last) {
    while (first != last) {
        pos = __slist_make_link(pos, create_node(*first));
        ++first;
    }
}

首先通过create_node创建一个节点，然后通过__slist_make_link将其插入链表中

__slist_make_link的定义如下

inline __slist_node_base* __slist_make_link(__slist_node_base* prev_node,
                                            __slist_node_base* new_node)
{
  new_node->next = prev_node->next;
  prev_node->next = new_node;
  return new_node;
}

下面再看create_node的定义

static list_node* create_node(const value_type& x) {
  list_node* node = list_node_allocator::allocate(); //分配内存
  construct(&node->data, x); //构造对象
  node->next = 0; //初始化节点
   
  return node;
}

3.2 析构函数

~slist() { clear(); }

slist的析构函数调用clear函数，其定义如下

void clear() { erase_after(&head, 0); }

clear调用erase_after，传递链表的头部和尾部，其定义如下

list_node_base* erase_after(list_node_base* before_first,
                            list_node_base* last_node) {
  list_node* cur = (list_node*) (before_first->next);
  while (cur != last_node) {
    list_node* tmp = cur;
    cur = (list_node*) cur->next;
    destroy_node(tmp);
  }
  before_first->next = last_node;
  return last_node;
}

该函数会遍历链表指定的范围，然后通过destroy_node销毁每个节点

destrot_node的定义如下

static void destroy_node(list_node* node) {
  destroy(&node->data); //析构对象
  list_node_allocator::deallocate(node); //释放内存
}

3.3 添加元素

slist添加元素的方法有两种，一种是push，一种是insert。其中push只支持push_front，只支持在链表首部插入。insert有insert和insert_after两种，insert是在某个位置插入，insert_after是在某个位置之后插入，下面来看一看它们的定义

push_front

在链表首部插入

void push_front(const value_type& x) {
  __slist_make_link(&head, create_node(x));
}

首先会使用create_node创建一个节点，然后通过__slist_make_link插入到链表中

__slist_make_link的定义如下

inline __slist_node_base* __slist_make_link(__slist_node_base* prev_node,
                                            __slist_node_base* new_node)
{
  new_node->next = prev_node->next;
  prev_node->next = new_node;
  return new_node;
}

insert_after

在指定位置后面插入

iterator insert_after(iterator pos, const value_type& x) {
  return iterator(_insert_after(pos.node, x));
}

insert_after会调用另外一个insert_after，其定义如下

list_node* _insert_after(list_node_base* pos, const value_type& x) {
  return (list_node*) (__slist_make_link(pos, create_node(x)));
}

还是调用create_node创建一个节点，然后调用 __slist_make_link将其插入链表中

insert

在指定位置插入节点

iterator insert(iterator pos, const value_type& x) {
    return iterator(_insert_after(__slist_previous(&head, pos.node), x));
}

首先通过__slist_previous找到指定位置的前一个节点，然后继续调用_insert_after

__slist_previous的定义如下

inline const __slist_node_base* __slist_previous(const __slist_node_base* head,
                                                 const __slist_node_base* node)
{
  while (head && head->next != node)
    head = head->next;
  return head;
}

从链表头开始寻找，知道下一个节点为指定节点，就退出

3.4 删除元素

删除操作有pop和erase，pop中有pop_front，erase操作有erase和erase_after

pop_front

删除首部节点

void pop_front() {
  list_node* node = (list_node*) head.next; //取出第一个节点
  head.next = node->next; //改变链表头指向
  destroy_node(node); //销毁节点
}

首先通过链表头取出第一个节点，然后改变链表头指向的下一个节点，然后再销毁节点

erase_after

删除指定位置后的节点

iterator erase_after(iterator pos) {
    return iterator((list_node*)erase_after(pos.node));
}

首先从迭代器取出node，然后再调用别的erase_after，其定义如下

list_node_base* erase_after(list_node_base* pos) {
  list_node* next = (list_node*) (pos->next); //取出下一个节点
  list_node_base* next_next = next->next; //取出下下个节点
  pos->next = next_next; //从链表中删除指定节点的下一个节点
  destroy_node(next); //销毁节点
  return next_next;
}

首先取出指定节点的下一个节点和下下个节点，然后从链表中删除指定节点的下一个节点，再销毁此节点

erase

删除指定位置的节点

iterator erase(iterator pos) {
  return (list_node*) erase_after(__slist_previous(&head, pos.node));
}

通过__slist_previous找到指定节点的上一个节点，然后再调用erase_after删除指定节点

3.5 其他操作

begin

头部迭代器

iterator begin() { return iterator((list_node*)head.next); }

end

尾部迭代器

iterator end() { return iterator(0); }

size

元素个数

size_type size() const { return __slist_size(head.next); }

遍历链表获取元素个数

inline size_t __slist_size(__slist_node_base* node)
{
  size_t result = 0;
  for ( ; node != 0; node = node->next)
    ++result;
  return result;
}