本篇主要为了再次复习和梳理自己在进行list的模拟实现中遇到的问题和解决方式。

首先，知道list就是双向循环链表，那就开始实现。链表是由结点构成的，所以先写出结点的模板。

template<class T>
   struct list_node
	{
		T _data;
		list_node<T>* _next;
		list_node<T>* _prev;

		list_node(const T& x = T())
			:_data(x)
			,_next(nullptr)
			,_prev(nullptr)
		{}

有了结点的模板，那么下面可以写链表的类域，类里面有一系列的函数对链表进行操作。但是，链表的操作似乎没有vector方便，因为vector的地址空间是连续的，而list的地址空间可能不连续，下一个结点只能通过上一个结点来进行访问，所以链表的++似乎不好操作，那么怎么办呢？

迭代器！通过迭代器对结点的访问，来进行操作，使用迭代器还可以保护链表中的结点不被显现（后面说），但是我们需要通过对迭代器进行封装，因为list的迭代器不像vector的迭代器那么拥有先天的优势，所以我们需要后天勤奋的努力来实现成功（封装）。

接下来我们对迭代器进行封装（接下来我就直接引用list的源代码进行讲解）：

template<class T, class Ref, class Ptr>
	struct __list_iterator
	{
		typedef list_node<T> Node;
		typedef __list_iterator<T, Ref, Ptr> Self;
		Node* _node;

		__list_iterator(Node* node)
			:_node(node)
		{}

		Ref operator*()
		{
			return _node->_data;
		}

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

		Self& operator++()
		{
			_node = _node->_next;
			return *this;
		}

		Self operator++(int)
		{
			Self tmp(*this);
			_node = _node->_next;
			return tmp;
		}

		Self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

		Self operator--(int)
		{
			Self tmp(*this);
			_node = _node->_prev;
			return tmp;
		}

		bool operator!=(const Self& it) const
		{
			return _node != it._node;
		}

		bool operator==(const Self& it) const
		{
			return _node == it._node;
		}
	};

我们发现类模板里面有三个参数，它们分别有什么用：T就是结点里的值的类型，Ref就是解引用操作返回的值，其实是引用（这个有很大用途，可以解决const修饰方面的问题，一会儿讲），Ptr就是返回地址（其实是个指针）。

• 那么我们先讲Ref:有没有想过，如果我想访问结点的时候，不想让结点改变，用const修饰，下面这个代码行不行

typedef const __list_iterator<T> const_iterator;

答案是不行，因为迭代器是用来遍历的，它本身肯定需要走啊，这样一修饰，它本身无法移动。

还有人想这样：

const T& operator*() const
{
      return _node->_data;
}

这样虽然可以，而且实现了重载，但是我们必须得需要const  __list_iterator对象才能调用啊,而且const  __list_iterator对象不能调用++(++函数在下面)

__list_iterator<T>& operator++()
{
     _node=_node->next;
     return *this;
}

所以只差一步啊，总不能再大费周章去再写一个const_iterator的模板吧，太麻烦了。

于是有个天才的想法，那就是上面源代码里的模板用了三个参数，巧妙的解决了这个问题，有了这个模板你可以传用const修饰的类型，也可以传（看以下代码）

typedef __list_iterator<T,T&> iterator;
typedef __list_iterator<T,const T&> const_iterator;

对应模板参数里的Ref，是不是太巧妙了，写出这个代码的真是天才。

• 解决了这个问题后，我们讨论为啥模板里还有第三个参数Ptr:

给出下面一个结构体

struct Pos
	{
		int _row;
		int _col;

		Pos(int row = 0, int col = 0)
			:_row(row)
			, _col(col)
		{}
	};

然后实现一个链表

void test_list3()
	{
		std::list<Pos> lt1;
		lt1.push_back({1,1});
		lt1.push_back({2,2});
		lt1.push_back({3,3});
		lt1.push_back({4,4});

		//list<Pos>::iterator it = lt1.begin();
		auto it = lt1.begin();
		while (it != lt1.end())
		{
			
			cout << it->_row << ":" << it->_col << endl;
			++it;
		}
		cout << endl;
	}

进行以上操作可不可以，如果链表模板里只有刚才两个参数，答案是不可以，因为我们需要这个结构体的地址进而访问其中的成员，问题就是我们少了指向结构体的指针，我们只有结点的指针，访问结构体还需要对结点进行解引用进而进行访问结构体里的成员，所以写成下面似乎也可以。

cout << (*it)._row << ":" << (*it)._col << endl;
				

但是不方便，所以我们直接对 ‘->’ 进行实现：

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

所以这才是模板第三个参数的来源和作用：

void test_list3()
	{
		std::list<Pos> lt1;
		lt1.push_back({1,1});
		lt1.push_back({2,2});
		lt1.push_back({3,3});
		lt1.push_back({4,4});

		//list<Pos>::iterator it = lt1.begin();
		auto it = lt1.begin();
		while (it != lt1.end())
		{
			//cout << (*it)._row << ":" << (*it)._col << endl;
			// 为了可读性，这里省略了一个->
			cout << it->_row << ":" << it->_col << endl;
			//cout << it.operator->()->_row << ":" << it.operator->()->_col << endl;
			++it;
		}
		cout << endl;
	}

其实那里有两个 ‘->’，一个是为了取到结构体的地址（指针），另一个是访问符号，访问成员，但是为了可读性，省略了一个。

• 下一个问题就是为什么使用迭代器可以保护链表里的结点：

    因为用户不知道结点的名字是啥啊！

iterator erase(iterator pos)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;

			prev->_next = next;
			next->_prev = prev;
			delete cur;

			--_size;


			//return iterator(next);
			return next;
		}

好比以上这个删除操作，你想通过 pos._node 来看结点，换个其他地方呢，万一有人把_node 写成_pnode，咱们不知道啊。

• 最后一个问题就是有关typename的使用

直接给出代码：

void print(const list<T>& lt)
	{
		// 类模板未实例化，不能去类模板中找后面的东西
		// 编译器就分不清const_iterator是嵌套内类，还是静态成员变量
		// typename告诉编译器，我确认过了这里是类型
		//typename list<T>::const_iterator it = lt.begin();
		auto it = lt.begin();
		while (it != lt.end())
		{
			//*it += 1;
			cout << *it << " ";
			++it;
		}

		cout << endl;
	}

OK,本篇结束！（其实还有一个关于CPU高速缓存命中率的问题，一句话：少用list的sort，因为它命中率低）