【STL 源码剖析】系列九：序列式容器 --slist

前言

本篇主要是介绍 SGI STL 中提供的单链表容器 ——slist，主要内容如下：

1. 分析 slist（单链表）与 list（双向循环链表）的不同，引入 slist 的主要原因是占用空间更小，虽然操作上受限；

2.slist 的迭代器和节点设计架构采用了继承的方式，这种设计与后面关联式容器中的 RB-Tree（红黑树）类似；

3.slist 常见的对外接口。

slist

概述

slist 是 SGI STL 提供的一种单向链表（single linked list）。

slist 与 list 的主要差别是，前者的迭代器是单向迭代器，后者的迭代器属于双向迭代器。

slist 与 list 共同特点是，由于每个元素都被装在一个节点中，因此插入（insert）、移除（erase）、接合（splice）等操作不会使得原有的迭代器失效。

STL 的习惯是插入操作将新元素插入指定位置之前，但是作为一个单向链表，slist 没有方便的方法可以向前空出一个位置，因此它必须从头开始查找。所以对于 slist 而言，除了起点附近的区域，在其它位置采用插入或者删除操作都是不合适的。（对于 list 而言在任何位置插入都是可以的）基于同样的效率考虑，slist 不提供 push_back，只提供 push_front。

slist 的节点

slist 的节点与迭代器的设计比 list 复杂很多，使用了继承关系，所以在类型转换上有复杂的表现。下图是 slist 节点和迭代器的设计架构：

下面是 slist 的节点结构：

slist 的迭代器

slist 的迭代器为单向迭代器，因此只能递增：

base 迭代器结构：

派生的迭代器结构：

判断两个 slist 的迭代器是否相等，最终会调用 base 迭代器的 operator==，即最终是判断两个迭代器拥有的成员指针是否指向同一个元素。

slist 的数据结构

slist 的元素操作

实际上 slist 也提供了 insert 等操作，上面源代码介绍中并没有包含，这是因为其它操作效率比较低，不是 slist 常用的操作。

这里另外需要注意的是，slist 的 end () 函数是构造了一个临时迭代器对象，这个临时迭代器对象成员指针是一个空指针，与正常的迭代器不同：