1、list的概述

相比较于 vector 的连续线型空间，list 就显得复杂的多，它的好处是每次插入或删除一个元素，就配置或释放一个元素空间。因此，list对于空间的运用有绝对的精准，一点也不浪费。而且，对于任何位置的元素插入或元素移除，list永远是常数时间。

list 和 vector 是两个最常用被使用的容器 。什么时机下最适合使用哪一种容器，我们最后进行整理。

list 本身和 list 的节点是不同的结构

，需要分开设计。以下是 STL list 的节点结构：

template <class T>
struct __list_node
{
	typedef void* void_pointer;	//类型为void* 其实可以设计成 T*
	void_pointer prev;
	void_pointer next;
	T data;
};

2、list 的迭代器

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

由于 STL list 是一个双向链表，迭代器必须具备前移、后移的能力，所以 list 提供的是 bidirectional iterators（双向迭代器）类型

。

list 有一个重要性质：

插入操作和 接合操作 都不会造成原有的 list 迭代器失效

。这在 vector 是不成立的，因为 vector 的插入操作可能造内存的重新配置，导致原有迭代器全部失效。甚至 list 的元素删除操作也只有“指向被删除元素” 的那个迭代器失效，其它迭代器不受任何影响。

list 迭代器的设计如下：

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 size_t		size_type;
	
	typedef ptrdiff_t		difference_type;
	typedef __list_node<T>*	link_type;    	

	link_type	node;	//迭代器内部当然要有一个普通指针，指向list的节点
	
	bool 	operator==(const self& x) const;
	bool 	operator!=(const self& x) const;
	reference 	operator*() const;
	pointer 	operator->() const;
	self& 		operator++();
	self		operator++( int );
	self& 		operator--();
	self		operator--( int );
};

3、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便能符合STL 对于“前闭后开”区间的要求，称为 last 迭代器。这么一来，以下几个函数变都可以轻易完成：

iterator begin() { return (link_type)((*node).next); }	//返回头部迭代器
iterator end() { return node;}							//返回尾部迭代器
bool empty() const { return node->next == node; }		//判空
reference front() { return *begin(); }					//返回第一个元素数据
reference back() { return *(--end()); }					//返回最后一个元素数据

4、list的其它操作

因为 list 要分配和释放单独的一个节点，所以 list 提供了以下四个函数分别用来配置、释放、构造、销毁一个节点，当然这是底层的操作，我们是看不见的：

link_type 	get_node();					//配置一个节点并传回
void 		put_node();					//释放一个节点
link_type 	create_node(const T& x);	//产生一个节点，并构造对象
void 		destroy_node(link_type p);	//销毁一个几点，并析构对象

我们能看见的是，对于元素 和 迭代器 操作的接口，如下：

void	pop_front();				//移除头节点
void	pop_back();					//移除尾节点
void	push_back( const T& x)； 	//将新元素插入到 list 尾端，作为尾节点
void	push_front( const T& x);	//将新元素插入到list，作为头节点
iterator	insert(...);			//多种形式，将元素插入到列表中
iterator	earse( iterator position);	//移除迭代器position所指节点

void	clear(); 					//清除所有节点
void	remove( const T& value);	//将数值为value之所有元素移除
void	unique();					//移除数值相同的连续元素

由于list 是一个双向环状链表，只要我们把边际条件处理好，那么，在头部或尾部插入元素，操作几乎是一样的，在头部或尾部移除元素，操作也几乎是一样的。

list内部提供一个所谓的迁移操作（transfer）：将某连续范围的元素迁移到某个特定位置之前

。技术上很简单，节点间的指针移动而已。这个操作位其它的复杂操作如 splice，sort，merge 等奠定良好的基础。

//将[first，last)内的所有元素移动到position之前
void	transfer( iterator position, iterator first, iterator last);	
void	splice(...);	//多种形式，接合操作
void	merge(...);		//合并操作，两个list都必须先经过递增排序
void	reverse();		//将链表逆向重置
void	sort();			// 排序操作，使用了 quick sort

因为STL 算法 sort() 只接受 RamdonAccessIterator（随机访问迭代器），所以list 只能使用自己的。

感谢大家，我是假装很努力的YoungYangD（小羊）

。

参考资料：

《STL源码剖析》