【STL】list的实现原理（包括slist）

原理（包括slist）"/>

【STL】list的实现原理（包括slist）

今日记

在我的博客，看到前两日的文章，现在的我，慵懒，堕落。大抵是要放弃了吧。回想曾经的”假装“，侯捷老师下课时的”假笑“，不禁起笔。

一、概述

与vector的连续空间相比，list就显得尤为复杂。正如上帝给他关上一道门就会开一扇窗。复杂的结构也给它带来一线生机，便是每次插入或删除一个元素时，就会配置或者释放一个元素空间。因此，list对于空间的使用是比较吝啬的，不会产生过多的残渣。同时，又能在常数时间内，完成插入、删除。

本章所采用list版本为 SGI STL 2.91版本。

二、list的节点（node）

list的本身和其节点是不同的结构，需要分开设计。

以下是STL list 的节点结构：

template <class T>
struct __list_node{typedef void* void_pointer;void_pointer prev;  //类型为 void* ，其实可以设计为 __list_node<T>* ，在新版好像已经改正 __list_node<T>*void_pointer next;T data;
}

如图所示：

三、list的迭代器

由于复杂的空间结构，普通指针已经不能满足它的迭代器了。身为复杂结构list的迭代器，自然需要身兼数职：递增，递减，取值，存取，样样不可或缺。如图所示：

同时，由于list是双向链表，所以提供的是 Bidirectional Iterators。下面我们一起欣赏一下美妙的设计吧：

template<class T,class Ref,class Ptr>
struct __list_iterator{typedef __list_iterator<T,T&,T*> 	iterator;typedef __list_iterator<T,Ref,Ptr> 	self;typedef bidirectional_iterator_tag 	iterator_category;typedef T							value_type;typedef Ptr							pointer;typedef Ref							reference;typedef __list_node<T>*				link_type;typedef size_t						size_type;typedef  ptrdiff_t					difference_type;link_type							node; //迭代器内部的普通指针，指向ist的结点// 构造函数__list_iterator(link_type x) : node(x) {}__list_iterator() {}__list_iterator(const iterator&x):node(x.node){}//操作运算符重载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;   //唤起copy ctor 用以创建tmp 并以 *this 为初值。++*this;			//不会唤起operator* 因为*this 已经被解释为operator++ 的参数return tmp;			//唤起 copy ctor }//--操作相同，不再赘述
}

list有一个重要设计，insert和splice都不会造成原有的迭代器失效。而且，list的erase操作，也只有”指向被删除元素“那个迭代器失效，其他迭代器并不受影响。

四、list的数据结构

SGI list是双向链表，并且还是环状的，所以只需要一个指针，便可完整表现整个链表。

template <class T,class Alloc = alloc>
class list{protected:typedef __list_node<T> list_node;public:typedef list_node* link_type;protected:link_type node;....
}

如果指针node 指向尾部空白点，node便符合了”前闭后开“区间的要求，成为迭代器。那么：

	iterator begin() { return (link_type)((*node).next);}  //环状链表，node下一个即为第一个iterator end() {return node;}	//返回最后一个空结点bool empty() const {return node->next==node}  //检查node节点是不是自己指向自己size_type size() const{size_type result=0;distance(begin(),end(),result);   //计算两个迭代器的距离return result;}reference front() { return *begin(); }    //取头结点reference back() { return *(--end()); }	  //取尾结点

如图所示：

五、list的构造和内存管理

list 缺省使用alloc作为空间配置器。

template <class T,class Alloc=alloc>
class list{
protected:typedef __list_node<T> 					list_node;typedef simple_alloc<list_node,Alloc> 	list_node_allocator;...	
}

list_node_allocator表示配置n个节点空间。下面四个函数，分别用来配置、释放、构造、销毁一个节点。

protected://配置一个结点link_type get_node() { return list_node_allocator::allocate(); }//释放一个节点void put_node(link_type p){ list_node_allocator::deallocate(p); }//构造link_type create_node(const T& x){link_type p=get_node();construct(&p->data,x);return p;}//析构void destroy_node(link_type p){destroy(&p->data);put_node(p);}

list 具有很多构造函数，其中有一个是默认构造，生成一个空list。

public:list(){ empty_initialize(); }
protected:void empty_initialize(){node=get_node();	//生成一个节点，头尾指向自己，不设原始值node->next=node;node->prev=node;}

如图所示：

当使用push_back() 的时候，内部是调用 insert() 。而insert() 是一个重载函数，有多种形式，下面是最简单的一种。

//在迭代器position所指的位置插入一个节点，值为x
iterator insert(iterator position, const T&x){link_type tmp=create_node(x);  //产生一个新结点，内容是x//将前后接入链表中tmp->next=position.node;tmp->prev=position.node->prev;(link_type(position.node->prev))->next=tmp;position.node->prev=tmp;return tmp;	
}

六、slist

概述

slit并不在标准规格内，但它与list有很多相似地方。其中，不同处在于迭代器由双向变成单向。损失一定操作性，但节省了空间。

注意：根据STL的习惯，插入操作会将元素插入到迭代器所指位置之前而不是之后，但slist没办法快速找到其前一个节点，只能从头遍历，这便是slist最大的缺点，因此slist不提供push_back操作，只提供insert_after、erase_after、push_front操作

slist的节点

slist的节点显得尤为复杂，主要是由于它是继承来的。关系，如图所示：

节点基本代码：

slist的迭代器

slist的迭代器如图所示：

slist的数据结构

template <class _Tp, class _Alloc = alloc >
class slist 
{__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;typedef typename _Base::allocator_type allocator_type;allocator_type get_allocator() const { return _Base::get_allocator(); }private:typedef _Slist_node<_Tp>      _Node;typedef _Slist_node_base      _Node_base;typedef _Slist_iterator_base  _Iterator_base;_Node* _M_create_node(const value_type& __x) {_Node* __node = this->_M_get_node();__STL_TRY {construct(&__node->_M_data, __x);__node->_M_next = 0;}__STL_UNWIND(this->_M_put_node(__node));return __node;}public:explicit slist(const allocator_type& __a = allocator_type()) : _Base(__a) {}....slist& operator= (const slist& __x);~slist() {}
public:iterator begin() { return iterator((_Node*)this->_M_head._M_next); }  iterator end() { return iterator(0); }iterator before_begin() { return iterator((_Node*) &this->_M_head); }size_type size() const { return __slist_size(this->_M_head._M_next); }size_type max_size() const { return size_type(-1); }bool empty() const { return this->_M_head._M_next == 0; }void swap(slist& __x) { __STD::swap(this->_M_head._M_next, __x._M_head._M_next); }
public:reference front() { return ((_Node*) this->_M_head._M_next)->_M_data; }void push_front(const value_type& __x)   {__slist_make_link(&this->_M_head, _M_create_node(__x));}void pop_front() {_Node* __node = (_Node*) this->_M_head._M_next;this->_M_head._M_next = __node->_M_next;destroy(&__node->_M_data);this->_M_put_node(__node);}
......

总结

1、STL list实现的三个模块节点__list_node，迭代器__list_iterator以及list本身(使用一个__list_node*代表整个链表)的介绍。
2、迭代器的移动就是通过操作节点的指针实现的，而不能随机访问。
3、STL中使用了大量地操作符重载来实现相应的功能。

参考资料：
《STL源码剖析》 侯捷