list的实现，还是比较简单的，大家只要想着土家楼的形状，画出图来就好了，不需要过多担心。本次的博客会发出一个完整的实现List的List.hpp，以后也会这样，主要是分段发被说孩子分段生。

二、模拟List

        由于list中的结构需要特定的类型和特定的指定地址的，所以我们先要实现list中的结点和迭代器。正所谓"工欲善其事，必先利其器"。

        2.1        List内的结点制造

                 可以理解为一个包裹，用箱子包裹着的网购物品，list相当于分配的快递线。list结点要有前后指针，肯定也要有存储数据的类型。所以list_node中设计三个数据。

代码语言：javascript

AI代码解释

// 模版的使用。
// 可以套用任何类型，让编译器自己去推。
template< class T >
// 用struct是因为struct默认public访问(也就是允许访问任何资源)。
struct List_Node
{
    // 缺省参数，未传参时，可以默认初始化_val。
    // _next和_prev都是nullptr，初始化好，方便list类盖。
	List_Node(T val = T())
		:_val(val)
		, _next(nullptr)
		, _prev(nullptr)
	{
		;
	}

    // C++11的万能引用，等些到万能引用会粘贴好的。
	template < class X >
	List_Node(X&& val)
		:_val(val)
		, _next(nullptr)
		, _prev(nullptr)
	{
		;
	}
    
	T _val;
	List_Node* _next;
	List_Node* _prev;
};

        2.2      Iterator的模拟实现

                iterator迭代器是用来代替指针指向list中的地址的，所以肯定要有list结点的指针。在iterator迭代器中我们需要重载他们的运算符，重载运算符是C++的特性(operator 要重载的运算符，值得一提的是，重载的运算符不能违背运算符本身之外的操作，不然很容易报错)。我们根据迭代器类比指针就可以知道要重载什么运算符，由于list迭代器是双向迭代器，不支持+、-某一位置的单位距离，所以我们不能支持Self operator + ()和Self operator - ()，不仅如此还要删除掉他们。使用delete关键字，令这两个函数赋值delete，两个函数就会停止生成。

代码语言：javascript

AI代码解释

template< class T , class Ptr , class Ref >
struct Iterator
{
    // 设置list中的List_Node，一个具有标识性的名字。
    // 封装好一点。
	typedef List_Node < T > Node;
    // 可变性
    // 为了实现在list中的普通类型和const类型的迭代器。
    // 不用实现两份代码。
    // 在接下来的list中会讲。
    // 最主要的原因是list的迭代器不能像vector中的迭代器直接加const。
    // 如果只加const，说明迭代器指向了另一个结点类型，根本无法适用。
	typedef Iterator < T , Ptr , Ref > Self;
    // 而且这样不用写一大串类型名。
    
    // 初始化对象。
	Iterator(Node* node)
		:_node(node)
	{
		;
	}
    
	Ref operator * ()
	{
		return _node->_val;
	}

	Ptr operator -> ()
	{
		return &(_node->_val);
	}

	Self& operator ++ ()
	{
		_node = _node->_next;

		return (*this);
	}

	Self& operator -- ()
	{
		_node = _node->_prev;

		return _node;
	}

	Self operator ++ (int)
	{
		Self tmp(_node);
		_node = _node->_next;

		return tmp;
	}

	Self operator -- (int)
	{
		Self tmp(_node);
		_node = _node->_next;

		return tmp;
	}

    Self& operator = (const Self& s)
    {
        _node = s._node;

        return (*this);
    }

	// 减少拷贝，怕临时值捣乱，无法左值引用。
	bool operator == (const Self& node)
	{
		return _node == node._node;
	}

	bool operator != (const Self& node)
	{
		return _node != node._node;
	}
    
		// 删除这两个函数，不让这两个函数被错误调用。
		Self& operator + (size_t i) = delete;
		Self& operator - (size_t i) = delete;

	Node* _node;
};

        2.3        List中的基本结构和初始化函数

                List中一定包含着List_Node类型结点，就像快递线上有着的包裹，回转寿司有着寿司，土家族楼有着房间一样。上一章我们说过如果设计一个环形的结构，不知道以哪个结点为开头，所以我们新增一个带头链接点为开头，避免群龙无首的事情发生。另外插入过程中，我们无法通过结点直接的运算得到插入结点总数量为多少，所以我们添加一个变量，记录插入结点的总数量。

代码语言：javascript

AI代码解释

// 无参构造
List()
{
	_lt = new Node();

	_lt->_next = _lt;
	_lt->_prev = _lt;
}

// 初始化列表构造，就把它当做数组就行了。
// 另外initializer_list是C++11的内容，使用时记得调好编译器选项。
List(initializer_list<T> lt)
{
	_lt = new Node();

	for (auto& e : lt)
	{
		Emplace_back(e);
	}
}

Node* _lt;
size_t _n;

        2.4        size()函数和empty()函数

                List不像Vector和String一样有capacity(）有着空间大小，只要有_n就行了。根据_n我们可以判断List中是否存在数据以及插入数据有多少个。

代码语言：javascript

AI代码解释

size_t size()
{
	return _n;
}

bool empty()
{
    return _n == 0;
}

        2.5        Insert()和Erase()函数

                Insert()函数和Erase()函数都是在指定位置插入删除。

                我们先从插入开始讲起。插入只需要将pos位置上的结点(我们将这个结点设为结点A)和要pos位置之前(_prev)的结点(我们将这个结点设为结点B)和该位置的结点的_prev、_next指针做修改就可以了。由图可知让结点A(pos)的_prev指针指向新结点的地址，结点B(--pos上的结点)的_next指针指向新结点的地址，再让新结点的_prev指向结点B，_next指针指向结点A。