简易实现 STL--list

实现 list 的主要思想及过程

首先，实现过程中的所有代码必须放在自己定义的命名空间中。

定义一个结点的结构体类模板，结点的数据类型就应该是模板类型 T，定义的 next指针和 prev指针都应该是模板指针类型，并且结构体类中药有构造函数，确保在 new 结点的时候，不会出现未初始化的情况。

第二步就是定义一个迭代器的类模板，其中模板参数要有三个，分别做数据类型和返回值类型，保证普通迭代器和 const 类型的迭代器都能通用，在泛型编程下，只要保证模板参数的数量足够，编译器就能自动推导需要的数据类型！

最后一步就是写出 list 的类模板，这个其实只需要传一个模板参数即可，在使用迭代器的时候，使用迭代器自己实例化的模板参数来自动推导即可。

因为list 在使用迭代器的时候只需要控制普通迭代器和 const 迭代器的返回类型即可，所以只需要两种不同模板参数的迭代器区分返回值即可。

#include<iostream>
using namespace std;
namespace zyb
{
	template<class T>
	struct list_node
	{
		T _val;
		list_node<T>* _next;
		list_node<T>* _prev;

		list_node(const T& x = T())
			:_val(x),
			_next(nullptr),
			_prev(nullptr)
		{}
	};
	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)
		{
		}
		self operator++(int)
		{
			self tmp = __list_iterator(_node);
			_node = _node->_next;
			return tmp;
		}
		self operator--(int)
		{
			self tmp = __list_iterator(_node);
			_node = _node->_prev;
			return tmp;
		}
		self& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}
		bool operator==(const self& it)
		{
			return it._node == _node;
		}
		bool operator!=(const self& it)
		{
			return it._node != _node;
		}
		Ref operator*()
		{
			return _node->_val;
		}
		Ptr operator->()
		{
			return &(_node->_val);
		}
	}; 
}

泛型编程中模板的再理解?

过程中学习到的一些模板的知识：如何自己实现一个函数，可以打印不同容器中不同的数据类型？

这是实现 list 的不同数据打印的代码，值得注意的是，在 list<T> 前面加了一个 typename? ，包括前面的模板声明，也用的是 typename 这是为什么呢？

如果不加 typename ，因为?list<T>? 就是未实例化的模板，因为类型是不确定的，里面会有好多未确认的类型，并且编译器无法辨别 const_iterator 是 内嵌类型 还是 静态成员变量（只有内嵌类型和静态成员变量才能通过类域去访问），编译器就会报错；那么前面加一个 typename，就相当于一个给编译器的声明，这是一个内嵌类型（保证编译的时候不会报错），等 list<T> 实例化之后，再去对应的类里找到实例化类型来替换。

template<typename T>
	void print_list(const list<T>& lt)
	{
		typename list<T>::const_iterator it1 = lt.begin();
		while (it1 != lt.end())
		{
			cout << *it1 << ' ';
			++it1;
		}
		cout << endl;
		for (auto e : lt)
		{
			cout << e << ' ';
		}
	}

当然，也可以改写为一个针对全部容器打印数据的代码，

Container 的类型根据传入的容器类型来推导出来，相当于对于上面的模板再抽象了一层。

这就是泛型编程！

	template<typename Container>
	void print_container(const Container& x)
	{
		typename Container::const_iterator it1 = x.begin();
		while (it1 != x.end())
		{
			cout << *it1 << ' ';
			++it1;
		}
		cout << endl;
		for (auto e : x)
		{
			cout << e << ' ';
		}
	}