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

柔情只为你懂 2023-06-03 02:55 25阅读 0赞

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

### 文章目录 ###

*  STL源码剖析（十二）序列式容器之slist
 *   *  一、slist的数据结构
     *  二、slist的迭代器
     *  三、slist的操作
     *   *  3.1 构造函数
         *  3.2 析构函数
         *  3.3 添加元素
         *  3.4 删除元素
         *  3.5 其他操作

`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内部数据结构如下

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70]

## 二、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`的定义如下

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70]: /images/20230601/4382c29ec84a4858bee6522c08dc994a.png