前言

相较于 vector 的连续线性空间，list 就显得复杂许多、它的好处是每次插人或删除一个元素，就配置或释放一个元素空间。因此，1ist 对于空间的运用有绝对的精准，一点也不浪费。而且，对于任何位置的元素插入或元素移除，list 永远是常数时间。
———— 《STL源码剖析》侯捷

本篇博客将会分析 STL 中 list 的结构定义部分。值得注意的是，在原始的 MyTinySTL 仓库中，作者 list 部分的实现方式是有些怪异的，包括但不限于：使用了本该出现在 SGI-STL 的 slist 中的 base_ptr 与 node_ptr 来代表 list 的指针、没有实现 transfer 函数、sort 的实现也很繁杂；保险起见，下面的解析均以 SGI-STL 中的实现为准。

list

SGI-STL 中的 list 是一个 双向环状链表。对删除、插入的时间复杂度为O(1)O(1)，效率相当高；但是随机访问的时间复杂度为O(n)O(n)。另外，list在插入和删除操作后迭代器并不会失效。

__list_node

以下是 list 的节点结构。

1
2
3
4
5
6
7
8
9
template <class T> struct __list_node 
{
    // 前后指针
  	typedef void* void_pointer;
  	void_pointer next;  // 性别为 void*，其实可设为 __list_node<T>*
  	void_pointer prev;
    // 属性
  	T data;
};

__list_iterator

list 不再能够像 vector 一样以普通指针作为迭代器，因为其节点不保证在储存空间中连续存在。list 迭代器必须有能力指向 list 的节点，并有能力进行正确的递增、递减、取值、成员存取等操作。所谓 “1ist 迭代器正确的递增、递减、取值、成员取用” 操作是指，递增时指向下一个节点，递减时指向上一个节点，取值时取的是节点的数据值，成员取用时取用的是节点的成员。

由于 list 是一个双向链表 ( double linked-list )，迭代器必须具备前移、后移的能力，所以 list 提供的是 Bidirectional Iterators。

型别定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template<class T, class Ref, class Ptr> struct __list_iterator 
{
  	typedef __list_iterator<T, T&, T*>             iterator;	// 迭代器
  	typedef __list_iterator<T, const T&, const T*> const_iterator;
  	typedef __list_iterator<T, Ref, Ptr>           self;		
	
    // 迭代器是bidirectional_iterator_tag类型
  	typedef bidirectional_iterator_tag iterator_category;
  	typedef T value_type;
  	typedef Ptr pointer;
  	typedef Ref reference;
  	typedef size_t size_type;
  	typedef ptrdiff_t difference_type;
    ... 
};

构造函数

1
2
3
4
5
6
7
8
9
10
11
12
13
template<class T, class Ref, class Ptr> struct __list_iterator 
{
    ...
    // 定义节点指针
  	typedef __list_node<T>* link_type;
  	link_type node;  // 指向 list 节点的指针

	// 构造函数
  	__list_iterator(link_type x) : node(x) {}
  	__list_iterator() {}
  	__list_iterator(const iterator& x) : node(x.node) {}
   ... 
};

操作符重载

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
template<class T, class Ref, class Ptr> struct __list_iterator 
{
    ...
	// 重载
  	bool operator==(const self& x) const { return node == x.node; }
  	bool operator!=(const self& x) const { return node != x.node; }
    // 对*和->操作符进行重载
  	reference operator*() const { return (*node).data; }
  	pointer operator->() const { return &(operator*()); }

  	self& operator++() 
    { 
	    node = (link_type)((*node).next);
	    return *this;
  	}
  	self operator++(int) 
    { 
	    self tmp = *this;
	    ++*this;
	    return tmp;
  	}
  	self& operator--() 
    { 
	    node = (link_type)((*node).prev);
	    return *this;
  	}
  	self operator--(int) 
    { 
    	self tmp = *this;
    	--*this;
    	return tmp;
  	}
};

可以看到，由于 list 为双向链表，需要其迭代器重载 operator--() 并且也很好实现，直接利用 node->prev 就行。但 SGI-STL 中的另一种链表 slist ( single list )，就不支持 operator--()，因为内部仅有 next 指针。

list 的结构

实现过 list 的人都知道，list 的节点与 list 本身是不同的结构，需要分开设计。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
template <class T, class Alloc = alloc>
class list 
{
protected:
    typedef void* void_pointer;
    typedef __list_node<T> list_node;	// 节点
    typedef simple_alloc<list_node, Alloc> list_node_allocator;	// 空间配置器

public:  // 定义嵌套类型     
    typedef T                 value_type;
    typedef value_type*       pointer;
    typedef const value_type* const_pointer;
    typedef value_type&       reference;
    typedef const value_type& const_reference;
    typedef list_node*        link_type;
    typedef size_t            size_type;
    typedef ptrdiff_t         difference_type;
    
protected:
    link_type node;  // 只需要一个指针，便可以表示整个环状双向链表
    
public:  // 定义迭代器
    typedef __list_iterator<T, T&, T*>             iterator;
    typedef __list_iterator<T, const T&, const T*> const_iterator;
	...
};

这里的 node 节点指针是 list 结构的核心，可以代表整个 list。如果让指针 node 指向刻意置于尾端的一个空白节点，node 便能符合STL 对于 “前闭后开” 区间的要求，成为 last 迭代器。这么一来，以下几个函数便都可以轻易完成：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 由于 list 为环状链表，因此可以这样得到第一个元素
iterator begin() { return (link_type)((*node).next); }
// 这里的 node 为一个空节点，作为 last 迭代器恰好满足了前闭后开，十分巧妙。
iterator end()   { return node; }
// 初始状态下 node->prev == node->next == node，表示链表为空
bool empty() const { return node->next == node; }
// 取得链表大小
size_type size() const {
    size_type res = 0;
    distance(begin(), end(), res);
    return res;
}
// 取头节点的内容（元素值）
reference front()  { return *begin(); }
// 取尾节点的内容（元素值）
reference back()   { return *(--end()); }