list模拟实现【C++】

全部的实现代码放在了文章末尾

准备工作

创建两个文件，一个头文件mylist.hpp，一个源文件test.cpp

【因为模板的声明和定义不能分处于不同的文件中，所以把成员函数的声明和定义放在了同一个文件mylist.hpp中】
mylist.hpp：存放包含的头文件，命名空间的定义，成员函数和命名空间中的函数的定义

test.cpp：存放main函数，以及测试代码

包含头文件

1. iostream：用于输入输出

2. assert.h：用于使用报错函数assert

定义命名空间

在文件mylist.hpp中定义上一个命名空间mylist
把list类和它的成员函数放进命名空间封装起来，防止与包含的头文件中的函数/变量重名的冲突问题

类的成员变量

参考了stl源码中的list的实现，stl中list的底层链表是双向带头循环链表
【可以看我这篇文章了解双向带头循环链表的实现：链表的极致——带头双向循环链表】
成员变量只有一个，就是指向双向带头循环链表的头节点的指针。

节点类：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PgC6iunX-1720663070797)(https://i-blog.csdnimg.cn/direct/667727a5535e4a7c95e931618f6a1662.png#pic_center)]

为什么节点类是用struct而不是class呢？

因为节点类里面的成员变量在实现list的时候需要经常访问，所以需要节点类的成员变量是公有的【使用友元也可以，但是比较麻烦】
struct的默认访问权限就是公有，不用加访问限定符了，stl中实现的节点类也是struct
class的默认访问权限是私有的

list类：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ZKrXfgK4-1720663070798)(https://i-blog.csdnimg.cn/direct/2546f7b1d9fe49029c3dc6aa0fd84f00.png#pic_center)]

为什么要写get_head_node?

因为插入节点之前必须要有头节点
所以把创建初始头节点的操作写成了一个函数，用于
所有构造函数插入节点之前进行申请头节点

迭代器

因为list存储数据的方式是创建一个一个的节点存储数据
所以存储数据的空间不是连续的，所以不能直接用指针作为迭代器

因为指向一个节点的指针直接++,是不一定能指向下一个节点的

所以要把迭代器实现成一个类，这样才可以正确地支持++，- -，*等操作

迭代器在list类里的实例化和重命名

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qjqNyMDi-1720663070799)(https://i-blog.csdnimg.cn/direct/506afbbbf0534c61b435d2d371e2113d.png#pic_center)]

普通迭代器

template<class T, class R, class F>
struct Iterator
{
	把自己的类型重命名一下
	typedef Iterator<T, R, F> Self;


	成员变量的类型是 双向带头循环链表的节点类型
	listnode<T>* _n;

	Iterator(listnode<T>*l=nullptr) 构造函数
	{
		_n = l;
	}
	Self& operator++()前置++
	{
		++就是指向下一个节点
		_n = _n->_next;
		return *this;
	}
	Self operator++(int)  后置++
	{
		Self tmp =*this;  先记录一下++之前的值

		_n = _n->_next;  再++

		return tmp;
	}
	Self& operator--()  前置--
	{
		--就是指向上一个节点
		_n = _n->_prev;
		return *this;
	}
	Self operator--(int) 后置--
	{
		Self tmp = *this; 先记录一下--之前的值

		_n = _n->_prev;  再--
		return tmp;
	}

	R operator*()const
	{
		 类比指针
		*就是获取  节点中存储的数据
		return _n->_data;
	}
	F operator->()const
	{
		返回  节点中 存储数据的成员变量的  地址
		return &(_n->_data);
	}
	bool operator!=(const Self&obj)const
	{
		return _n != obj._n;
	}
	bool operator==(const Self& obj)
	{
		return !(*this != obj);
	}
};

operator->()的作用是什么？

为了实现：
当节点中存储的数据是自定义类型的变量时，可以直接使用 迭代器->访问自定义类型中的成员
【原来访问需要调用两次->，为了可读性，省略了一个->】

例
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kD0EkJ8j-1720663070800)(https://i-blog.csdnimg.cn/direct/68c293cf351f423fb9a05da5b82d6196.png#pic_center)]

const迭代器

const迭代器与普通迭代器的区别是什么？
区别就只有==不能通过const迭代器改变节点中存储的数据==

转换一下就是：

1. 不能使用迭代器的operator*()改变节点中存储的数据，即把operator*()的返回值改成const T&就可以了
2. 不能使用迭代器的operator->()改变节点中存储的数据的成员，即把operator->()的返回值改成const T*就可以了

所以const迭代器与普通迭代器的区别就只有两个函数的返回值类型不同，所以增加两个模板参数：R和F

普通迭代器实例化时:R就是T&，F就是T*
const迭代器实例化：R就是const T&，F就是const T*

反向迭代器

反向迭代器与普通迭代器的实现上的区别就是：
普通迭代器++是指向下一个节点
反向迭代器++是指向上一个节点
普通迭代器- -是指向上一个节点
反向迭代器- -是指向下一个节点

template<class T, class R, class F>
struct Reverse_iterator
{
	把自己的类型重命名一下
	typedef Reverse_iterator<T, R, F> Self;

	成员变量的类型是 双向带头循环链表的节点类型
	listnode<T>* _n;


	Reverse_iterator(listnode<T>* l) 构造函数
	{
		_n = l;
	}

	Self& operator++()
	{
		反向迭代器++，是移动到  前  一个节点
		_n = _n->_prev;
		return *this;
	}
	Self operator++(int)
	{
		Self tmp = *this;
		_n = _n->_prev;
		return tmp;
	}
	Self& operator--()
	{
		反向迭代器--，是移动到  后  一个节点
		_n = _n->_next;
		return *this;
	}
	Self operator--(int)
	{
		Self tmp = *this;
		_n = _n->_next;
		return tmp;
	}
	R operator*()const
	{
		return _n->_data;
	}
	F operator->()const
	{
		return &(_n->_data) ;
	}
	bool operator!=(const Self& obj)const
	{
		return _n!=obj._n;
	}
	bool operator==(const Self& obj)const
	{
		return !(*this != obj);
	}
};

迭代器的获取

iterator begin()
{
	头节点的下一个节点 才是第一个节点
	return _head->_next;
}

const修饰的对象只能调用const修饰的成员函数
const_iterator begin()const
{
	头节点的下一个节点 才是第一个节点
	return _head->_next;
}

iterator end()
{
	最后一个节点的下一个节点是  头节点
	因为是循环链表
	return _head;
}

const修饰的对象只能调用const修饰的成员函数
const_iterator end()const
{
	return _head;
}


reverse_iterator rend()
{
	反向迭代器的rend返回的是第一个节点的   前一个节点
	return _head;
}

const修饰的对象只能调用const修饰的成员函数
const_reverse_iterator rend()const
{
	return _head;
}
reverse_iterator rbegin()
{
	反向迭代器的rbegin()返回的是  最后一个节点
	最后一个节点是  头节点的前一个
	因为是循环链表
	return _head->_prev;
}

const_reverse_iterator rbegin()const
{
	return _head->_prev;
}

构造函数

默认构造

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-1GgtecBB-1720663070800)(https://i-blog.csdnimg.cn/direct/90c95c5207f2461193a7424ceaff1e9a.png#pic_center)]

使用n个val构造

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wtIPk0if-1720663070801)(https://i-blog.csdnimg.cn/direct/e72aeab61a5e4eac938b0b20fb9645f4.png#pic_center)]

迭代器区间构造

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Xfp8vYpy-1720663070802)(https://i-blog.csdnimg.cn/direct/9c03aa701d1e4067bf92b0fa220e0918.png#pic_center)]

解决迭代器区间构造 和 用n个val构造的冲突

当重载了迭代器区间构造和使用n个val构造的时候
如果传入的两个参数都是int类型的话就会报错

为什么？
因为在模板函数构成重载时，编译器会调用更合适的那一个
什么叫更合适？
就是不会类型转

如果传入的两个参数都是int类型，那么调用的应该是使用n个值构造，因为没有int类型的迭代器

但是使用n个值构造的第一个参数是size_t , int传进去要隐式类型转换
而调用迭代器区间构造，两个int的实参传进去，就会直接把InputIterator推导成int，不会发生类型转换，所以编译器会调用迭代器区间构造

解决方法：
再重载一个使用n个值构造的函数，把第一个参数改成int，这样根据模板偏特化，就会在都不类型转换时优先调用第一个参数特化成int的那个构造函数
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qYHmqtjL-1720663070802)(https://i-blog.csdnimg.cn/direct/1dd1ac43d7e7464c9d36b43f26922525.png#pic_center)]

initializer_list构造

写了这个构造函数，就可以支持直接使用{}初始化了
例
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nzwhbmge-1720663070803)(https://i-blog.csdnimg.cn/direct/d80c8432dcf048999e714c96ff24d94b.png#pic_center)]

initializer_list是iostream库里面的自定义类型，它可以直接接收{ }里面的值 进行初始化，而且有迭代器

所以可以直接使用迭代器循环+尾插进行对list的构造
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jMz3wcLb-1720663070803)(https://i-blog.csdnimg.cn/direct/a4069ab1989e43528048b1a7e1aec98f.png#pic_center)]

拷贝构造

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-et0I5RLp-1720663070804)(https://i-blog.csdnimg.cn/direct/dbb9b340399c400f8081c14424aabfb6.png#pic_center)]

析构函数

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ymsiGjft-1720663070804)(https://i-blog.csdnimg.cn/direct/5d56f67c54924a40b357464baeb17539.png#pic_center)]

swap

只需要交两个list对象的头指针中存储的地址就可以了

因为两个list对象都有头结点，交换了头指针中存储的地址，就相当于把这两个对象的头指针的指向交换了，
而链表的所有节点都是由头节点出发去找到的

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jY0TYhg6-1720663070805)(https://i-blog.csdnimg.cn/direct/f2a37ed2853348448b1ceb75e46d787d.png#pic_center)]

void swap(list& obj)
{
	调用库里面的swap，交换头指针
	std::swap(_head, obj._head);
}

赋值运算符重载

list& operator= (list obj)
{
	swap(obj);

	return *this;
}

为什么上面的两句代码就可以完成深拷贝呢？
这是因为：

使用了传值传参，会在传参之前调用拷贝构造，再把拷贝构造出的临时对象作为参数传递进去

赋值运算符的左操作数，*this再与传入的临时对象obj交换，就直接完成了拷贝

在函数结束之后，存储在栈区的obj再函数结束之后，obj生命周期结束

obj调用析构函数，把指向的从*this那里交换来的不需要的空间销毁

erase

删除pos迭代器指向的节点

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lEoZYbB4-1720663070805)(https://i-blog.csdnimg.cn/direct/52c9e57f560f4af8b67d46f3bd0c7f4c.png#pic_center)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-L3ji5vVM-1720663070808)(https://i-blog.csdnimg.cn/direct/cf348bb14b83422f9bb24da46f5d11a1.png#pic_center)]

为什么要返回next？

因为使用了erase之后的迭代器会失效，需要提供更新的方法

为什么使用了erase之后的迭代器会失效？

因为pos指向的节点erase之后，节点被释放了

stl库里面规定erase的返回值是指向删除数据的下一个数据的迭代器，下一个数据就是next指向的数据，所以返回next【没有接收返回值的迭代器，在检测较严格的编译器中，不管指向的位置是否正确，都会禁止使用，使用了就报错】

删除迭代器区间

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-WQ0tx5C9-1720663070809)(https://i-blog.csdnimg.cn/direct/af38f109bbbf4a578c86b6cba3001a80.png#pic_center)]

insert

在迭代器pos之前插入一个节点

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-SyriqhUO-1720663070810)(https://i-blog.csdnimg.cn/direct/66a804199ba14c179a1dd878db168ea8.png#pic_center)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-BFOPpreV-1720663070810)(https://i-blog.csdnimg.cn/direct/600ce34d9a304e4286959dbba11c880c.png#pic_center)]

为什么要返回newnode?

list的迭代器pos在使用完insert之后其实是不会失效的

但是为了与其他容器的nsert的返回值进行统一，所以也返回了指向新插入的节点的迭代器

在迭代器pos之前插入一个迭代器区间的数据

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-R7FlTK7F-1720663070811)(https://i-blog.csdnimg.cn/direct/d2549108a9314de4a9c74e4bdedb5ab2.png#pic_center)]

push_back

复用insert即可

void push_back(const T&val)
{
	insert(end(), val);
}

push_front

复用insert即可

void push_front(const T& val)
{
	insert(begin(), val);
}

pop_front

复用erese即可

void pop_front()
{
	erase(begin());
}

pop_back

复用erese即可

void pop_back()
{
	erase(--end());
}

size

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3YbqziMa-1720663070811)(https://i-blog.csdnimg.cn/direct/0b7f0e559d16473ea5dbccc5c14e1730.png#pic_center)]

empty

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-59VtLmPm-1720663070811)(https://i-blog.csdnimg.cn/direct/e2df88fd61c74ca0b90abe613cdd9e6a.png#pic_center)]

back

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-N7sLJXsd-1720663070812)(https://i-blog.csdnimg.cn/direct/3774472c4f38438db90590472b159be5.png#pic_center)]

front

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Jarz2two-1720663070812)(https://i-blog.csdnimg.cn/direct/3f74f58427864bf0bac0e5a93d555454.png#pic_center)]

assign

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-9gevGVoC-1720663070814)(https://i-blog.csdnimg.cn/direct/4620fd900e984ce3900311a61ab68762.png#pic_center)]

resize

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-69kXAjpz-1720663070814)(https://i-blog.csdnimg.cn/direct/d199dc1abebb4b17b161006eea102d00.png#pic_center)]

clear

复用erase

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NdJzlJjt-1720663070815)(https://i-blog.csdnimg.cn/direct/154c04d0e7504bc684e9d2ab98667ae0.png#pic_center)]

全部代码

#include<iostream>
#include<assert.h>

using namespace std;

namespace mylist
{
	template<class T>
	struct listnode//双向带头循环链表的节点类
	{
		T _data;//节点存储的数据

		listnode* _next;//指向下一个节点的指针

		listnode* _prev;//指向前一个节点的指针
	};
	
	

	template<class T, class R, class F>
	struct Iterator
	{
		//把自己的类型重命名一下
		typedef Iterator<T, R, F> Self;

		//成员变量的类型是 双向带头循环链表的节点类型
		listnode<T>* _n;


		Iterator(listnode<T>*l=nullptr)//构造函数
		{
			_n = l;
		}
		Self& operator++()//前置++
		{
			//++就是指向下一个节点
			_n = _n->_next;
			return *this;
		}
		Self operator++(int)//后置++
		{
			Self tmp =*this;//先记录一下++之前的值

			_n = _n->_next;//再++

			return tmp;
		}
		Self& operator--()//前置--
		{
			//--就是指向上一个节点
			_n = _n->_prev;
			return *this;
		}
		Self operator--(int)//后置--
		{
			Self tmp = *this;//先记录一下--之前的值

			_n = _n->_prev;//再--
			return tmp;
		}

		R operator*()const
		{
			//类比指针
			//*就是获取  节点中存储的数据
			return _n->_data;
		}
		F operator->()const
		{
			//返回  节点中 存储数据的成员变量的  地址
			return &(_n->_data);
		}
		bool operator!=(const Self&obj)const
		{
			return _n != obj._n;
		}
		bool operator==(const Self& obj)
		{
			return !(*this != obj);
		}
	};

	template<class T, class R, class F>
	struct Reverse_iterator
	{
		//把自己的类型重命名一下
		typedef Reverse_iterator<T, R, F> Self;

		//成员变量的类型是 双向带头循环链表的节点类型
		listnode<T>* _n;


		Reverse_iterator(listnode<T>* l)//构造函数
		{
			_n = l;
		}

		Self& operator++()
		{
			//反向迭代器++，是移动到  前  一个节点
			_n = _n->_prev;
			return *this;
		}
		Self operator++(int)
		{
			Self tmp = *this;
			_n = _n->_prev;
			return tmp;
		}
		Self& operator--()
		{
			//反向迭代器--，是移动到  后  一个节点
			_n = _n->_next;
			return *this;
		}
		Self operator--(int)
		{
			Self tmp = *this;
			_n = _n->_next;
			return tmp;
		}
		R operator*()const
		{
			return _n->_data;
		}
		F operator->()const
		{
			return &(_n->_data) ;
		}
		bool operator!=(const Self& obj)const
		{
			return _n!=obj._n;
		}
		bool operator==(const Self& obj)const
		{
			return !(*this != obj);
		}
	};

	template<class T>
	class list
	{
		//把双向带头循环链表的节点类型重命名成node
		typedef listnode<T> node;

	private:
		node* _head;//唯一的成员变量

		//获取初始头结点
		node* get_head_node()
		{
			//申请一个节点大小的空间
			node* tmp = new node;

			//最开始的头节点的prev和next都指向自己
			tmp->_next = tmp;
			tmp->_prev = tmp;

			return tmp;
		}

	public:
		
		typedef  Iterator<T, T&, T*> iterator;//普通迭代器

		typedef  Iterator<T, const T&, const T*>  const_iterator;//const迭代器

		typedef  Reverse_iterator<T, T&, T*>  reverse_iterator;//反向迭代器

		typedef  Reverse_iterator<T, const T&, const T*> const_reverse_iterator;//const反向迭代器


		list()
		{
			//获取头结点
			//为之后的插入操作做准备
			_head=get_head_node();
		}


		list(size_t n, const T& val=T())
		{
			//必须先获取头节点，才能进行插入数据
			_head = get_head_node();

			for (int i = 0; i < n; i++)
			{
				push_back(val);//尾插n次
			}
		}


		template <class InputIterator>
		list(InputIterator first, InputIterator last)
		{
			//必须先获取头节点，才能进行插入数据
			_head = get_head_node();

			while (first != last)
			{
				//把解引用之后的值，一个一个尾插进去
				push_back(*first);
				first++;
			}
		}


		list(int n, const T& val = T())
		{
			//必须先获取头节点，才能进行插入数据
			_head = get_head_node();


			for (int i = 0; i < n; i++)
			{
				push_back(val);
			}
		}


		list(initializer_list<T> il)
		{
			//必须先获取头节点，才能进行插入数据
			_head = get_head_node();

			auto it = il.begin();
			while (it != il.end())
			{
				//把解引用之后的值，一个一个尾插进去
				push_back(*it);
				it++;
			}
		}


		list(const list& obj)
		{
			//必须先获取头节点，才能进行插入数据
			_head = get_head_node();

			//使用const迭代器接收  const修饰的对象的迭代器
			const_iterator it = obj.begin();

			while (it != obj.end())
			{
				//把解引用之后的获得的值，一个一个尾插进去
				push_back(*it);
				it++;
			}
		}


		~list()
		{
			//先把list里面除了头结点
			//以外的节点全部删除
			clear();

			//再把头结点申请的空间释放
			delete _head;

			_head = nullptr;
		}


		list& operator= (list obj)
		{
			swap(obj);

			return *this;
		}


		void swap(list& obj)
		{
			//调用库里面的swap，交换头指针
			std::swap(_head, obj._head);
		}


		iterator begin()
		{
			//头节点的下一个节点 才是第一个节点
			return _head->_next;
		}

		//const修饰的对象只能调用const修饰的成员函数
		const_iterator begin()const
		{
			//头节点的下一个节点 才是第一个节点
			return _head->_next;
		}

		iterator end()
		{
			//最后一个节点的下一个节点是  头节点
			//因为是循环链表
			return _head;
		}
		//const修饰的对象只能调用const修饰的成员函数
		const_iterator end()const
		{
			return _head;
		}


		reverse_iterator rend()
		{
			//反向迭代器的rend返回的是第一个节点的   前一个节点
			return _head;
		}
		//const修饰的对象只能调用const修饰的成员函数
		const_reverse_iterator rend()const
		{
			return _head;
		}
		reverse_iterator rbegin()
		{
			//反向迭代器的rbegin()返回的是  最后一个节点
			//最后一个节点是  头节点的前一个
			//因为是循环链表
			return _head->_prev;
		}


		const_reverse_iterator rbegin()const
		{
			return _head->_prev;
		}
		

		void push_back(const T&val)
		{
			/*node* tail = _head->_prev;

			node* newnode = new node;
			newnode->_data = val;
			newnode->_next = _head;
			newnode->_prev = tail;

			tail->_next = newnode;

			_head->_prev = newnode;*/
			insert(end(), val);
		}


		iterator erase(iterator pos)
		{
			//不能  把 头节点 给删了
			assert(pos!=end());

			//记录pos的前一个节点（prev） 
			// 和后一个节点（next）
			node* prev = pos._n->_prev;
			node* next = pos._n->_next;
			
			//让prev的下一个节点变成next
			prev->_next = next;

			//让prev的上一个节点变成next
			next->_prev = prev;

			//释放pos指向的节点
			delete pos._n;

			//返回被删除的节点的下一个节点
			//用于更新迭代器
			return next;
		}


		iterator erase(iterator first, iterator last)
		{
			iterator it = first;
			while (it != last)
			{
				//删除it指向的节点
				//删除后让it接收返回值，进行更新
				it = erase(it);
			}
			//返回被删除的  最后一个节点  的下一个节点
			//用于更新迭代器
			return last;
		}

		bool empty() const
		{
			//size==0就   是空    返回true
			//size!=0就   不是空  返回false
			return size() ==0 ;
		}

		size_t size()const 
		{
			//用count记录节点个数
			size_t count = 0;

			//使用const迭代器接收  const修饰的对象的迭代器
			const_iterator it = begin();

			//遍历链表
			while (it != end())
			{
				count++;
				++it;
			}
			return count;
		}

		T& back()
		{
			//list不能为空，为空就报错
			assert(!empty());

			//end（）返回的迭代器指向  头结点
			//头结点的上一个节点就是，最后一个节点
			//因为是循环链表
			return *(--end());
		}

		//const修饰的成员，只能调用const修饰的成员函数
		const T& back() const
		{
			assert(!empty());

			return *(--end());
		}


		T& front()
		{
			//list不能为空，为空就报错
			assert(!empty());

			//begin()返回的迭代器  就指向第一个节点
			return *begin();
		}

		//const修饰的成员，只能调用const修饰的成员函数
		const T& front()const
		{
			assert(!empty());

			return *begin();
		}


		template <class InputIterator>
		void assign(InputIterator first, InputIterator last)
		{
			//先把数据现有的节点(除了头结点)都删除
			clear();

			//再循环把数据一个一个尾插进去
			while (first != last)
			{
				//尾插
				push_back(*first);
				first++;
			}
		}
		

		void assign(size_t n, const T& val)
		{
			clear();

			for (int i = 0; i < n; i++)
			{
				push_back(val);
			}
		}
		void assign(int n, const T& val)
		{
			clear();

			for (int i = 0; i < n; i++)
			{
				push_back(val);
			}
		}

		iterator insert(iterator pos, const T& val)
		{
			//记录指向 pos 前一个节点的指针
			node* prev = pos._n->_prev;

			//申请新节点的空间
			node* newnode = new node;
			//存储数据
			newnode->_data = val;

			newnode->_next = pos._n;
			newnode->_prev = prev;

			prev->_next = newnode;
			pos._n->_prev = newnode;

			//返回指向新插入的节点的迭代器
			//用于更新迭代器
			return newnode;
		}


		template <class InputIterator>
		void insert(iterator pos, InputIterator first, InputIterator last)
		{
			while (first!=last)
			{
				//循环插入即可
				//因为list的迭代器使用完insert之后 不会失效
				//所以不用接收返回值  也可以
			    insert(pos,*first);
				first++;
			}
		}


		void push_front(const T& val)
		{
			insert(begin(), val);
		}
		void pop_front()
		{
			erase(begin());
		}
		void pop_back()
		{
			erase(--end());
		}


		void resize(size_t n, const T& val = T())
		{
			//获取一下size，加快后续比较效率
			//因为获取size()的时间复杂度为  O(N)
			size_t size = this->size();

			if (n > size)
			{
                //缺失的数据用val填上
				//填到size()==n为止
				while (size < n)
				{
					push_back(val);
					++size;
				}
			}
			else 
			{
				//把多出来的数据（节点）删除
				//删除到n==size()为止
				while (n < size)
				{
					pop_back();
					n++;
				}
			}
		}

		void clear()
		{
			//[begin(),end())之间的数据
			//就是所有的有效数据(节点)
			//复用erase删除即可
			erase(begin(), end());
		}
	};
}