[C++]深入剖析list类中迭代器的封装

由浅入深：从底层设计开始分析

1. 设计一个list类

• 如果要设计一个list类，我们需要明白以下几点：
  1.list是一个带头双向循环链表
  2.list类的迭代器不是原生指针，是封装过后的指针，通常情况原生指针只适合连续的内存空间
  3.list类的成员只有一个（或者多加一个size成员），该成员通常命名为 _head，是一个哨兵位

list类包括：iterator类和node类（节点类）

--每个节点用list_node类封装
template<class T>
	struct list_node
	{
		list_node<T>* _next = nullptr;
		list_node<T>* _prev = nullptr;
		T _val;

		list_node(T val = T())
			:_val(val)
		{}
	};
	//---------------------------------------------------------------
	template<class T>
	struct list_iterator
	{
		typedef list_iterator<T> self; self就是迭代器本身，只是为了防止频繁地输入
		     						   list_iterator<T>，从而做的优化
		typedef list_node<T> node;
	public:
		node* _pnode;
	};
	//---------------------------------------------------------------
	template<class T>
	class list
	{
		typedef list_node<T> node;
	public:
		typedef list_iterator<T> iterator;
	private:
		node* _head;
		size_t _size;
	};

• 在这里我们简单实现了一个list类，一个基本的list类包括

1. list_node节点类
2. iterator迭代器类

iterator类不具有const的性质

2.如何让迭代器具有const类型

• 我们在上面迭代器的设计中，并没有直接实现const迭代器，现在让我们来看看目前设计的迭代器

分析目前的类实现

template<class T>
	struct list_iterator
	{
		typedef list_iterator<T> self; self就是迭代器本身，只是为了防止频繁地输入
		     						   list_iterator<T>，从而做的优化
		typedef list_node<T> node;
	public:
		node* _pnode;
	};
	
	在list类中：
	typedef list_iterator<T> iterator;

开始对iterator迭代器进行const设计

现在我们开始设计const类型的迭代器：

①.直接在list类里的替换里加const：

typedef list_iterator<T> iterator;
typedef const list_iterator <T> const_iterator

这种设计和vector有点相似：

vector:
typedef int* iterator;
typedef const int* const_iterator; 

iterator Func(T& 1) || const_iterator Func(T& 1) const  --(判断传入对象是否为const)

• 但是，这种设计有很大的问题，因为const修饰的不是迭代器指向的内容，而是迭代器本身
  如同const int a一样，const list_iterator<T> const_iterator修饰的不是迭代器指向的空间，而是其本身
• 如果修饰了迭代器本身，那么将无法实现++/–等基本操作，因此这种写法显然是不合理的

②设计一个新的const_iterator类，让const类型的迭代器有专门的类使用

• 这种设计虽然能解决问题，但是过于冗余了，为了一个const的迭代器而专门再做一个新的迭代器类，属于吃力不讨好的行为

③[最优解法]直接用模板的知识

list类内：
	typedef list_iterator<T> iterator;
	typedef __list_iterator<const T> const_iterator;

到了这里，问题已经解决了一半
那另外一半呢？

• 当我们实现迭代器的各种功能时（++/- -/==…），需要用到不同的返回值，例如需要返回T&或是T*
  此时也可以进行对应的优化：

list_iterator类内：
	template<class T, class Ref, class Ptr>
	struct __list_iterator
	{
		typedef list_node<T> Node;
		typedef __list_iterator<T, Ref, Ptr> self;
	}；

list类内：
	typedef __list_iterator<T, T&, T*> iterator;
	typedef __list_iterator<T, const T&, const T*> const_iterator;

• 直接在函数模板把所有需要的返回值都加上，返回的时候给对应的模板类型即可
• self就是迭代器本身，也是为了不频繁地调用iterator<T, Ref, Ptr>，选择用self简化代码

[其他]关于迭代器使用->操作符时，编译器的自动优化