从零开始，打造自己的STL(四、list)

简述

在前面我们看了vector的实现之后相信对容器有了一定的认识。容器即为存放物件之所，它代表着一块空间。想要直观的了解一个容器，那么看懂他的空间分配策略是一个非常有效的入手方式。接下来我们就来看看STL中的list又是如何实现的吧。

list的结构

list就是我们常说的链表，说到链表相信大家就很熟悉了。非连续空间、通过指针来连接每一个小空间、插入和删除都是O(1)操作，元素访问效率较低等等。。。
list采用的结构是双端环形链表，用下面一幅图来形象的表达

咳咳，虽然图是丑了点，确也是可以直观的看出它的结构的。图中红色的方框就代表着一块空间，在这块空间中存放了三个东西，第一个东西是下一块空间所在的位置，也就是next指针所指向的位置。第二个是上一块空间所在的位置。第三个就是存放的数据呐。其中有一个特殊的是有一块 head 的区域，有人会想这块区域显然就是标识我大链表的头部了。其实它既是链表头，也是链表尾。看一下下面对链表的遍历操作你很块就能理解了

for (auto i = head->next; i != head; ++it)
{
    //...
}

list的空间配置

list的空间配置呢相对vector就要复杂一点点，vector的空间是一整块一整块分配的，当这一块空间不足够存放我的数据的时候，就重新分配一块*2大小的空间，再将原来的数据搬过来。说了这么多就是想找个对比，没有对比就没有伤害嘛

list是一小块一小块的节点空间，那么每次新增一个节点的时候就要分配一块空间供我们使用。分配多大呢？看一下list的节点的结构就知道那

struct _List_node_base
{
	_List_node_base *_m_next;
	_List_node_base *_m_prev;
};

template<typename _Tp>
struct _List_node : public _List_node_base
{
	_Tp _m_data;
};

大家看到这个节点的结构的时候有没有感觉到有一点点奇怪，为什么有两个结构体？

在SGI的STL实现中呢，将list的节点分为了指针域和数据域。为什么要这么划分，当然是有它的好处的。

我们对list的操作中更多的是对节点进行遍历，而访问数据成员总是在我们找到了某个节点的时候。那我们在遍历操作中只存放节点的指针域，而不存放数据是不是很大的节省了空间呢，特别是对于c++来说，这个数据域大多都是我们自定义的类，而一个类所占用的空间可能会很大，不像指针，在32位下一个指针才4bytes

看懂了节点的结构之后，那么它的空间分配也就显而易见了，即每次分配sizeof(_List_node<_Tp>) 大小的空间即可

template<typename _Tp, typename _Alloc>
class _List_base
{
public:
	typedef _Alloc allocator_type;

	_List_base()
	{
		_m_head = _M_get_node();
		_m_head->_m_next = _m_head;
		_m_head->_m_prev = _m_head;
	}

	~_List_base()
	{
		clear();
		_M_put_node(_m_head);
	}

	void clear();
protected:
	typedef simple_alloc<_List_node<_Tp>, _Alloc> _Alloc_type;

	_List_node<_Tp> * _M_get_node() // 分配节点空间
	{
		return _Alloc_type::allocate(1);
	}
	void _M_put_node(_List_node<_Tp> *_p) // 释放节点空间
	{
		_Alloc_type::deallocate(_p);
	}

	_List_node<_Tp>* _m_head;
};

代码还是比较简单的，_List_base类主要就负责head节点的初始化工作。需要注意的就是传递给分配器的模板参数是 **_List_node<_Tp>，该类型作为simple_alloc的_Tp参数

list的元素访问

明白了list的内存布局之后，我们在看看list的迭代器，看看迭代器是如何实现对其进行元素访问的。

话不多说，先上代码，从源码中见分晓

struct _List_iterator_base
{
	_List_node_base* _m_node;

	_List_iterator_base(_List_node_base *_x) :_m_node(_x){}
	_List_iterator_base():_m_node(nullptr){}

	void _M_incr() 
	{
		_m_node = _m_node->_m_next;
	}

	void _M_decr() 
	{
		_m_node = _m_node->_m_prev;
	}

	bool operator==(const _List_iterator_base &_x)const
	{
		return _m_node == _x._m_node;
	}

	bool operator!=(const _List_iterator_base &_x)const
	{
		return _m_node != _x._m_node;
	}
};

看到第一行的_m_node相信大家应该明白了之前所说的为什么将节点的指针域和数据域分开的原因了吧，在迭代器中只需要指针域，因为迭代器的工作就是访问节点，而不是数据

iteartor的基类做的工作很简单

1. 初始化当前节点
2. 提供访问当前节点的相邻节点的接口
3. 提供节点比较的方法

有了基类提供的接口之后，迭代器的实现也就很简单了

template<typename _Tp, typename _Ref, typename _Ptr>
struct _List_iterator : public _List_iterator_base
{
public:
	typedef _List_iterator<_Tp, _Tp&, _Tp*>	iterator;
	typedef _List_iterator<_Tp, const _Tp&, const _Tp*>	const_iterator;
	typedef _List_iterator<_Tp, _Ref, _Ptr>	_Self;

	typedef _Tp value_type;
	typedef _Ptr pointer;
	typedef _Ref reference;
	typedef _List_node<_Tp> _Node;
	

	_List_iterator(_Node *_x): _List_iterator_base(_x){}
	_List_iterator(){}
	_List_iterator(const iterator& _x):_List_iterator_base(_x._m_node){}

	reference operator*()const 
	{
		return ((_Node*)_m_node)->_m_data;
	}

	pointer operator->()const
	{
		return &(operator*());
	}

	_Self& operator++()
	{
		this->_M_incr();
		return *this;
	}

	_Self operator++(int)
	{
		_Self _tmp = *this;
		this->_M_incr();
		return _tmp;
	}

	_Self &operator--()
	{
		this->_M_decr();
		return *this;
	}
	_Self operator--(int)
	{
		_Self _tmp = *this;
		this->_M_decr();
		return _tmp;
	}
};

在前面定义了一些类型的别名，iterator真正提供的接口就是访问下一个节点(operator++), 访问前一个节点(operator–)以及访问当前节点的数据(operator*)

前期的准备工作都做好了，可以开始看list的具体实现了

list的具体实现

template<typename _Tp, typename _Alloc = alloc >
class list : protected _List_base<_Tp, _Alloc>
{
	typedef _List_base<_Tp, _Alloc> _Base;
public:
	typedef _Tp	value_type;
	typedef _Tp* pointer;
	typedef const _Tp*	const_point;
	typedef _Tp&	reference;
	typedef const _Tp&	const_reference;
	typedef  _List_node<_Tp> _Node;
	typedef size_t	size_type;
	typedef ptrdiff_t	difference_type;
	
	typedef _List_iterator<_Tp, _Tp&, _Tp*>	iterator;
	typedef _List_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;

	typedef reverse_iterator<const_iterator> const_reverse_iterator;
	typedef reverse_iterator<iterator>     reverse_iterator;

protected:
	using _Base::_M_put_node;
	using _Base::_M_get_node;
	using _Base::_m_head
};

这些都是一些别名的定义以及对基类成员和函数的引用，基类的代码在上面有贴出，忘记了的同学可以翻上去看一下

构造函数

list() : _Base(){}

list(size_type _n, const_reference _value):_Base()
{
	insert(begin(), _n, _value);
}

list(size_type _n):_Base()
{
	insert(begin(), _n, _Tp());
}

list(const_point _first, const_point _last)):_Base()
{
	insert(begin(), _first, _last);
}

list(const_iterator _first, const_iterator _last):_Base()
{
	insert(begin(), _first, _last);
}

list(const list<_Tp, _Alloc> &_x):_Base())
{
	insert(begin(), _x.begin(), _x.end());
}

别看构造函数好像都与insert函数有关，然后跑去看insert，结果被其吓倒了，其实构造函数无非就做了两件事

1. 通过基类初始化head节点
2. 将传递进来的数据插入到list中

只是我们提供的构造数据的方式多种多样，就显得比较负责而已，等到后面我们在来了解它到底是如何进行花式插入的

成员访问函数

iterator begin()
{
	return (_Node*)_m_head->_m_next;
}
const_iterator begin()const
{
	return (_Node*)_m_head->_m_next;
}
iterator end()
{
	return (_Node*)_m_head;
}
const_iterator end()const
{
	return (_Node*)_m_head;
}

reverse_iterator rbegin()
{
	return reverse_iterator(end());
}
const_reverse_iterator rbegin() const
{
	return const_reverse_iterator(end());
}

reverse_iterator rend()
{
	return reverse_iterator(begin());
}
const_reverse_iterator rend() const
{
	return const_reverse_iterator(begin());
}

bool empty()const
{
	return _m_head == _m_head->_m_next;
}

size_type size()
{
	size_type _result = 0;
	distance(begin(), end(), _result);
	return _result;
}
size_type max_size()const
{
	return (size_type)(-1);
}

reference front()
{
	return *begin();
}
const_reference front()const
{
	return *begin();
}
reference back()
{
	return *(--end());
}
const_reference back()const
{
	return *(--end());
}

这些统一的接口相信大家一看就懂了。我还是在这里多说几句。reverse_iterator是反向迭代器，意思就是将迭代器的访问顺序反着来，本来我们是从头访问到尾，而它正好相反，这个将在后面来实现，在size()中的distance()函数大家可以这样理解

for(auto it = begin(); it != end(); ++it)
	++result;

它只是为了提供一个统一的接口供不同的迭代器调用。对于list这样的不能随机访问的迭代器来说就要通过遍历来知道它的size有多大，而对于像vector这样的随机访问迭代器来说，直接end()-begin()就知道了它的size，它的作用就是统一接口，针对不同的迭代器采取不同的策略

insert

insert是list中比较重要的一部分了，list就是为了插入删除操作而生的。我们来好好了解一下到底是如何进行花式insert的吧

// 在pos处插入值x
iterator insert(iterator _pos, const_reference _x)
{
	_Node *_tmp = _M_create_node(_x);
	_tmp->_m_next = _pos._m_node;
	_tmp->_m_prev = _pos._m_node->_m_prev;
	_pos._m_node->_m_prev->_m_next = _tmp;
	_pos._m_node->_m_prev = _tmp;
	return _tmp;
}

这个很关键，还是画一幅图好好理解一下，因为后面的插入操作无非也就是在pos出插入多个值而已，咳，又到了展现画工的时候了，还真是激动。

好了，这就是初始状态，为了方便，就不画成环形了，大家知道就好
接下来分两步走
1.改变tmp指针域的指向

2.改变pos指针域的指向

红色代表被删除了，蓝色代表新加入的。这样新节点就成功加入到了pos前

iterator insert(iterator _pos)
{
	return insert(_pos, _Tp());
}

void insert(iterator _pos, const_point _first, const_point _last)
{
	for (; _first != _last; ++_first)
		insert(_pos, *_first);
}
void insert(iterator _pos, const_iterator _first, const_iterator _last)
{
	for (; _first != _last; ++_first)
		insert(_pos, *_first);
}

void insert(iterator _pos, size_type _n, const_reference _x)
{
	for (; _n > 0; --_n)
		insert(_pos, _x);
}

可以看到，剩下的插入操作都是调用的第一个接口。

erase

iterator erase(iterator _pos)
{
	_List_node_base *_next_node = _pos._m_node->_m_next;
	_List_node_base *_prev_node = _pos._m_node->_m_prev;
	_Node *_tmp = (_Node*)_pos._m_node;
	_prev_node->_m_next = _next_node;
	_next_node->_m_next = _prev_node;
	destroy(&_tmp->_m_data);
	_M_put_node(_tmp);
	return iterator((_Node*)_next_node);
}

删除操作看代码应该很好理解，将pos的前一个节点的next指针指向pos的下一个节点，pos的后一个节点的prev指针指向pos的前一个节点

push && pop

void push_front(const_reference _x)
{
	insert(begin(), _x);
}
void push_front()
{
	insert(begin());
}
void push_back(const_reference _x)
{
	insert(end(), _x);
}
void push_back()
{
	insert(end());
}
void pop_front()
{
	erase(begin());
}
void pop_back()
{
	erase(--end());
}

有了insert和erase做接口，push和pop直接调用即可