目录

1.list的基本使用

2.list模拟实现

3.反向迭代器

1.list的基本使用

链表不支持下标访问了，只有迭代器和范围for

正向迭代器

#include 
#include
using namespace std;

int main()
{
	list lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	//链表遍历不支持下标了
	list::iterator it = lt.begin();
	while(it!=lt.end())
	{
		cout << (*it)<<" ";
		it++;
	}
	cout << endl;
	
	for (auto &e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
	return 0;
}

反向迭代器

#include 
#include
using namespace std;

int main()
{
	list lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	//链表遍历不支持下标了
	list::reverse_iterator rit = lt.rbegin();
	while(rit != lt.rend())
	{
		cout << *rit<<" ";
		rit++;
	}
	cout << endl;

	return 0;
}

去重

去重必须先排序，否则去重去不干净。

#include 
#include
using namespace std;

int main()
{
	list lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(3);
	lt.push_back(5);
	lt.push_back(5);
	lt.push_back(4);
	//排序
	lt.sort();
	//去重
	lt.unique();
	//链表遍历不支持下标了
	list::iterator it = lt.begin();
	while (it != lt.end())
	{
		cout << (*it) << " ";
		it++;
	}
	cout << endl;

	return 0;
}

转移链表 

把链表 lt2转移到链表lt1

#include 
#include
using namespace std;

int main()
{
	list lt1;
	lt1.push_back(1);
	lt1.push_back(2);
	lt1.push_back(3);
	list lt2;
	lt2.push_back(4);
	lt2.push_back(5);
	lt2.push_back(6);
	
	lt1.splice(lt1.begin(), lt2);//把链表lt2转移到lt1
    //打印链表lt1
	list::iterator it1 = lt1.begin();
	while (it1 != lt1.end())
	{
		cout << (*it1) << " ";
		it1++;
	}
	cout << endl;

	return 0;
}

2.list模拟实现

#pragma once

#include "reverse_iterator.h"
//双向带头循环链表
namespace Ls
{
	//结点
	template
	struct List_Node
	{

		List_Node* _prev;
		List_Node* _next;
		T _data;



		List_Node(const T& val=T())
			:_prev(nullptr)
			,_next(nullptr)
			, _data(val)
		{

		}
	};
	//迭代器不仅可以是指针，也可以是一个自定义类型
	//迭代器
	template //使用Ref参数解决了重载* 的const问题。Ptr解决的->重载的const问题
	struct list_iterator
	{
		typedef List_Node Node;
		typedef list_iterator self;
		Node* _node;

		//拷贝构造和赋值重载、析构都不需要自己实现
		//我们只需要浅拷贝就可以了。
		//list::iterator it = lt.begin(); 浅拷贝就够了
		//析构函数也不需要，你用迭代器只是访问，你给我释放了。。。
		//迭代器是借助结点的指针访问修改链表。结点是属于链表，不属于迭代器，所以不管释放
		list_iterator(Node* x)
			:_node(x)
		{

		}
		Ref 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;
		}	

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

	//list
	template
	class list
	{
		typedef List_Node Node;
		
	public:
		//这里就是推到类型的。
		//模板参数作用主要体现这里，主要区分const的*、->重载 和 可修改的*、->,
		typedef list_iterator iterator;
		typedef list_iterator const_iterator;
		typedef reverse_iterator const_reverse_iterator;
		typedef reverse_iterator reverse_iterator;

		//默认构造函数
		list()
		{
			_head = new Node;
			_head->_prev = _head;
			_head->_next = _head;
		}


		//需要注意这里，这里的list(size_t n,const T& val=T())会和list(InputIterator first, InputIterator last)
		//发生冲突。请看测试案例test7

		//构造函数并初始化为n个val值
		list(size_t n,const T& val=T())
		{
			_head = new Node;
			_head->_prev = _head;
			_head->_next = _head;
			for (size_t i = 0; i < n; i++)
			{
				push_back(val);
			}
		}
		template 
		list(InputIterator first, InputIterator last)
		{
			_head = new Node;
			_head->_prev = _head;
			_head->_next = _head;
			while (first!=last)
			{
				push_back(*first);
				first++;
			}
		}
		//为了解决list(size_t n,const T& val=T())和list(InputIterator first, InputIterator last)的冲突
		list(int n, const T& val = T())
		{
			_head = new Node;
			_head->_prev = _head;
			_head->_next = _head;
			for (int i = 0; i < n; i++)
			{
				push_back(val);
			}
		}
		
		lt2(lt1)
		拷贝构造传统写法
		//list(const list& lt)
		//{
		//	//先建立一个头节点，这里需要注意一下
		//	_head = new Node;
		//	_head->prev = _head;
		//	_head->next = _head;
		//	for (auto e:lt)
		//	{
		//		push_back(e);
		//	}
		//}

		//lt2(lt1)
		//拷贝构造现代写法
		list(const list& lt)
		{
			//此时lt2的_head是随机值，交换后会出问题
			//第一种解决方法，不行，因为_head是空，在调用clear()时，会去调用begin().对空指针解引用了。
			//_head = nullprt;（不行）
			//必须要给_head一个结点，这样就都可以了。
			_head = new Node;
			_head->_prev = _head;
			_head->_next = _head;
			list tmp(lt.begin(),lt.end());//构造一个临时对象
			std::swap(_head, tmp._head);
		}

		lt1=lt2;赋值重载传统写法
		//list& operator=(const list& lt)
		//{
		//	if (this != <)
		//	{
		//		clear();
		//		for (auto e : lt)
		//		{
		//			push_back(e);
		//		}
		//		return *this;
		//	}
		//}

		//lt1=lt2 赋值重载现代写法
		list& operator=(list tmp)
		{
			std::swap(_head,tmp._head);
			return *this;
		}


		~list()
		{
			clear();//清除链表数据
			//再清除头节点
			delete _head;
			_head = nullptr;
		}

		//清除链表数据，不清除头节点
		void clear()
		{
			iterator it = begin();
			while (it!=end())
			{
				iterator del =it++ ;
				delete del._node;
			}
			_head->_next = _head;
			_head->_prev = _head;
			//或者
			//while (it!=end())
			
		}

		void push_back(const T& val)
		{
			Node* newnode = new Node(val);//会去调用Node的默认构造函数
			Node*tail = _head->_prev;
			tail->_next = newnode;
			newnode->_prev = tail;
			newnode->_next = _head;
			_head->_prev = newnode;
			//可以复用
			//insert(end(),val);//在end前面插入数据
			//end()返回的是头节点迭代器
		}

		iterator begin()
		{
			return iterator(_head->_next);
		}
		iterator end()
		{
			return iterator(_head);
		}

		const_iterator begin()const
		{
			return const_iterator(_head->_next);
		}
		const_iterator end()const
		{
			return const_iterator(_head);
		}

		reverse_iterator rbegin()
		{
			return reverse_iterator(end());//会调用reverse_iterator类的构造函数
		}

		reverse_iterator rend()
		{
			return reverse_iterator(begin());
		}
		const_reverse_iterator cbegin()
		{
			return const_reverse_iterator(end());//会调用reverse_iterator类的构造函数
		}
		const_reverse_iterator cend()
		{
			return const_reverse_iterator(begin());
		}


		//在pos位置之前插入数据
		//在C++库中会返回一个值，返回新插入结点的迭代器
		//迭代器不会失效，pos对象成员是指针变量，存放的指针没有变
		iterator insert(iterator pos ,const T& x)
		{
			Node* cur = pos._node;
			Node*newnode = new Node(x);//会去调用Node的构造函数
			Node* prev = cur->_prev;
			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;
			return iterator(newnode);//会去调用迭代器的构造函数

		}
		//erase会返回刚刚被删除位置的迭代器，即被删除结点的下一个结点的迭代器
		//erase后pos位置的迭代器一定会失效因为空间都被释放了，野指针了
		iterator erase(iterator pos)
		{
			assert(pos != end());//不能把头节点弄没

			Node *next= pos._node->_next;
			Node* prev = pos._node->_prev;
			prev->_next = next;
			next->_prev = prev;
			delete pos._node;
			return iterator(next);
		}

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




		//类型的意义
		void f()
		{
			Node* pnode = _head->_next;
			iterator it = _head->_next;
			*pnode;//返回的是结点。不是数据
			*it;//调用函数重载*，返回的是数据

			++pnode;//跳过一个结构体的大小，但是不知道后面地址存的是什么啊。
			++it;//调用函数重载，指向下一个结点。
			//Node*原生指针和一个迭代器对象，他们占的空间大小都是一样的。
			//都是4个字节，并且存的值也是一样。但是对它们使用运算符的意义和结果是不一样的。
		}

	private:
		Node* _head;
	};

	void test1()
	{
		list l1;
		l1.push_back(1);
		l1.push_back(2);
		l1.push_back(3);
		l1.push_back(4);
	}

	void test2()
	{
		list lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		lt.push_back(5);
		lt.push_back(6);
		list::iterator it = lt.begin();
		while (it!=lt.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}

	//此时我是用迭代器打印，发现不行
	void pirnt_list(const list& lt)
	{
		//lt是一个const 对象，必须使用const迭代器
		list::const_iterator it = lt.begin();
		while (it != lt.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}

	struct Date
	{
		int _year;
		int _month;
		int _day;

		Date(int year=0, int month=0, int day=0)
			:_year(year)
			,_month(month)
			,_day(day)
		{

		}
	};

	void test3()
	{
		list lt;//当list存储的是自定类型是。光使用*是不行的
		lt.push_back(Date(2022,1,3));
		lt.push_back(Date(2022,1,4));
		list::iterator it = lt.begin();
		while (it!=lt.end())
		{
			cout << (*it)._year << "/"<<(*it)._month << "/" << (*it)._day << " ";
			//迭代器是模仿指针，让它像指针一样使用。重载->
			cout << it->_year << "/" << it->_month << "/" << it->_day << " ";
			//这里本来应该是it->->去前一个->应该去调用重载，后一个是结构体指针。但是这样写运算符可读行太差了
			//但是这里好像少了一个->，因为编译器优化了，省略了一个->
			//所有类型重载->都是这样的，都会被优化，省略一个->
			it++;
		}
		cout << endl;

	}

	void test4()
	{
		list lt;
		lt.f();
	}


	void test5()
	{
		list lt;
		lt.push_back(1);
		lt.push_back(2);
		list::iterator it = lt.begin();
		lt.insert(it,30);
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;

	}

	void test6()
	{
		list lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		lt.pop_back();
		lt.pop_front();
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	void test7()
	{
		list lt1(5,Date(2022,1,3));//它是没有问题的
		//为什么呢？
		//当 list lt1(5, Date(2022, 1, 3)) 在调用构造函数的时候，编译器会去找最匹配的。
		//list(InputIterator first, InputIterator last)这个是两种类型都一样，不会去调用这个
		//因为第一个5是整形，第二个是Date自定义类型的，不匹配；
		//list(size_t n,const T& val=T()) 这一个第一个虽然是无符号，这里会发生强转，相对匹配了
		//第二个参数直接匹配了
		//但是是最匹配的，随意会去调用这个
		for (auto e:lt1)
		{
			cout << e._year << "/" << e._month << "/" << e._day << endl;
		}

		list lt2(5,1);//这里除问题了。
		//为什呢？
		//当list lt2(5,1)去调用构造函数的时候。因为5和1都是整形，编译器会去调动最匹配的构造函数
		//list(InputIterator first, InputIterator last)， 正好是相同的类型，所以编译器就匹配上了。
		//然而我们是想调用list(size_t n,const T& val=T())，所以和list(InputIterator first, InputIterator last)发生了冲突
		//解决办法：函数重载一个list(int n, const T& val = T())，就没问题了
		//编译器就是有匹配的就找匹配的。
	}


	void test8()
	{
		list lt1;
		lt1.push_back(1);
		lt1.push_back(2);
		lt1.push_back(3);
		lt1.push_back(4);
		list::reverse_iterator rit1 = lt1.rbegin();
		while (rit1 != lt1.rend())
		{
			cout << *rit1 << " ";
			++rit1;
		}
		cout << endl;

		list  lt2;
		lt2.push_back(Date(2022,1,3));
		lt2.push_back(Date(2022, 1, 4));
		lt2.push_back(Date(2022, 1, 5));
		lt2.push_back(Date(2022, 1, 6));

		list::reverse_iterator rit2 = lt2.rbegin();
		while (rit2 != lt2.rend())
		{
			cout << rit2->_year << "/" << rit2->_month << "/" << rit2->_day << endl;
			++rit2;
		}
		cout << endl;
	}
}

3.反向迭代器

其实反向迭代器是对正向迭代器的又一层封装。只需要各种容器提供正向迭代器就可以完成方向迭代器的实现。这里链表提供了正向的迭代器。比如vector容器可以直接修改这里，也可以实现

typedef list_iterator iterator;
typedef list_iterator const_iterator;
typedef reverse_iterator const_reverse_iterator;
typedef reverse_iterator reverse_iterator;

反向迭代器需要注意的是解引用的重载。

#pragma once

namespace Ls
{
	template 
	class reverse_iterator
	{
		typedef reverse_iterator self;
	public:
		reverse_iterator(Iterator it)
			:_it(it)//这里会去调用正向迭代器的拷贝构造函数
		{

		}

		Ref operator*()
		{
			Iterator tmp = _it;//这里会去调用正向迭代器拷贝构造函数
			return *--tmp;//这里会去调用正向迭代器的--重载和*重载
		}
		//rit->_year;
		Ptr operator->()
		{
			return &(operator*());
		}


		//reverse_iterator rit   ++rit;
		self&  operator++()
		{
			--_it;//这里调用正向迭代器--重载
			return *this;
		}

		self&  operator--()
		{
			++_it;//这里调用正向迭代器++重载
			return *this;
		}
		//rit1 == rit2;
		bool operator==(const self& rit)const
		{
			return _it == rit._it;//去调用正向迭代器的==重载
		}
		bool operator!=(const self& rit)const
		{
			return _it != rit._it; // 去调用正向迭代器的 != 重载
		}


	private:
		Iterator _it;
	};
}

C++库中是如何实现的？

掌握上面3个参数的就可以。减少了学习版本。 

在C++的库中，实现时是使用的萃取的方法，但是萃取一般很少用到了解就行，知道内嵌类型的使用。所以可以修改为以下方式，但是这种方式只适用于list，因为vector的迭代器是内置类型(整形指针等)没有模板参数，不支持这种。所以C++库中使用了萃取，但是萃取真的很少使用，这里只是了解这种用法。简化了，其他都一样

	template 
	struct list_iterator
	{
		typedef List_Node Node;
		typedef list_iterator self;
		Node* _node;

		//内嵌类型，把模板参数typedef成内嵌
		typedef Ref reference;
		typedef Ptr pionter;
    }

反向迭代器中就是这样使用了：

这里的typename作用是：因为这里使用的都是类模板，有可能没有实例化，编译器会报错，typename可以告诉编译器，你编译先过，等类模板实例化后再来找对应的类型。

#pragma once

namespace Ls
{
	//template 
	template
	class reverse_iterator
	{
		//typedef reverse_iterator self;
		typedef reverse_iterator self;
	public:
		reverse_iterator(Iterator it)
			:_it(it)//这里会去调用正向迭代器的拷贝构造函数
		{

		}

		//Ref operator*()
		typename Iterator::reference operator*()
		{
			Iterator tmp = _it;//这里会去调用正向迭代器拷贝构造函数
			return *--tmp;//这里会去调用正向迭代器的--重载和*重载
		}
		//rit->_year;

		//Ptr operator->()
		typename Iterator::pionter operator->()
		{
			return &(operator*());
		}


		//reverse_iterator rit   ++rit;
		self&  operator++()
		{
			--_it;//这里调用正向迭代器--重载
			return *this;
		}

		self&  operator--()
		{
			++_it;//这里调用正向迭代器++重载
			return *this;
		}
		//rit1 == rit2;
		bool operator==(const self& rit)const
		{
			return _it == rit._it;//去调用正向迭代器的==重载
		}
		bool operator!=(const self& rit)const
		{
			return _it != rit._it; // 去调用正向迭代器的 != 重载
		}


	private:
		Iterator _it;
	};
}

如果觉得这里 typename Iterator::reference 和typename Iterator::pionter 太长，在反向迭代器类中可以typedef一下：

template
	class reverse_iterator
	{
		//typedef reverse_iterator self;
		typedef reverse_iterator self;
		typedef typename Iterator::reference reference;
		typedef typename Iterator::pionter pionter;

       public:
        
        //Ref operator*()
		reference operator*()
		{
			Iterator tmp = _it;//这里会去调用正向迭代器拷贝构造函数
			return *--tmp;//这里会去调用正向迭代器的--重载和*重载
		}
		//rit->_year;

		//Ptr operator->()
		pionter operator->()
		{
			return &(operator*());
		}
    }

链表类中只需要传一个模板参数：

	template
	class list
	{
		typedef List_Node Node;
		
	public:
		//这里就是推到类型的。
		//模板参数作用主要体现这里，主要区分const的*、->重载 和 可修改的*、->,
		typedef list_iterator iterator;
		typedef list_iterator const_iterator;
		//typedef reverse_iterator const_reverse_iterator;
		//typedef reverse_iterator reverse_iterator;
		typedef reverse_iterator const_reverse_iterator;
		typedef reverse_iterator reverse_iterator;

    }