list下

注意：

delete 和delete[]之间不能用错
delete是单个；
delete是一个数组；
vector、string都是delete[]；
list本质不是数组是列表，所以delete

const迭代器

怎么写？

		typedef __list_iterator<T, T&, T*> iterator; // 放public里面不然外面动不了T，就是用不了模板，私有的不能用
		typedef __list_iterator<T,const T&,const T*> const_iterator;//const迭代器

		//迭代器用节点的指针就行了
		iterator begin()
		{
			return iterator(_head->_next);
			//注意这里返回的是迭代器，不是_head头部指针、这个是list类里面的成员变量
			//现在是把头部指针_head传过去，然后迭代器调用他的拷贝函数;
			//这里面就是构造函数、因为传过去的是Node类型;
		}
		iterator end()
		{
			return iterator(_head);
		}
		//const_iterator
		const_iterator begin() const
		{
			return const_iterator(_head->_next); 
		}
		const_iterator end() const
		{
			return const_iterator(_head);
		}

模板里面放多个参数，在传模板时候，如上图，右边框起来上面是普通的迭代器，下面有const，用哪种就会自动传过去,同时Self也是对应的迭代器;

运用场合？

一般const指针是不用的；
什么情况下去用？
传参给另一个函数用的时候会用到；
例如下面功能是打印的成员函数

	void print_list(const list<int>& lt)
	{
		list<int>::const_iterator it = lt.begin();
		while (it != lt.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}

insert

在pos位置插入，这个pos是一个迭代器，插入后这个节点以及前后节点的_next和_prev要注意怎么赋值;
cur是pos指向的当前节点;
newnode是新插入的节点；

		//insert
		//现在要的是列表里面的那两个指针next\prev;
		//迭代器里面就有_node存的是Node*类型;
		void insert(iterator pos,const T& x = T())
		{
			Node* cur = pos._node;//pos是迭代器所以调用他的成员函数用点符号"."虽然类似指针但是不能->,这个是指针用的
			Node* prev = cur->_prev;
			Node* newnode = new Node(x);

			newnode->_next = cur;
			newnode->_prev = prev;
			cur->_prev = newnode;
			prev->_next = newnode;

		}

写完insert，push_back和push_front就可以直接用insert的

		//头插
		void push_front(const T& x = T())
		{
			insert(begin(), x);
		}
		//尾插
		void push_back(const T& x = T())
		{
			//Node* tail = _head->_prev;
			//Node* newnode = new Node(x);

			//tail->_next = newnode;
			//newnode->_prev = tail;
			//newnode->_next = _head;
			//_head->_prev = newnode;
			

			//再pos是end()的时候插入，end()表示最后一个元素的后一个位置，所以插入这个位置就是尾插
			insert(end(), x);
		}

erase

头节点指向的迭代器就是end()；
end()的意思是最后一个元素的后一个位置,那就是_head,这个头节点；
和insert类似,_next/_prev都要重新赋值一下：

		//erase,erase是要返回删除的位置的后一个位置的
		Node* erase(iterator pos)
		{

			//cur里面存现在的地址
			//prev是cur上一个地址
			assert(pos  != end()); //头节点不能删
			Node* cur = pos._node;  
			Node* prev = cur->_prev;
			Node* next = cur->_next;

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

			delete cur;//delete[]必须是数组,所以要注意
			return next;
			

		}

头删除、和尾删除就可以用erase了

		//尾删
		void pop_back()
		{
			//erase(iterator(_head->_prev));
			erase(--end());
		}
		//头删除
		void pop_front()
		{
			erase(begin());
		}

析构函数

析构，栈里面的是先定义的后出去，现进后出；
析构是释放了还要置空；

		void clear()
		{
			Node* cur = _head->_next;

			while (cur != _head)
			{
				_head->_next = cur->_next;
				delete cur;
				cur = _head->_next
			}
			_head = head->next = head->prev;//重新关联起来，双向带头循环列表；
		}
		//析构
		~list()
		{
			clear();
			detete _head;
			_head = nullptr;
		}

clear的作用是清空这个链表里面的内容,_head这个头节点是没有data的，所以是不用动的;
析构是直接这个链表对象空间释放了，所以_head也要释放；

赋值和拷贝构造

区别？

问：string为什么这边写了要先置位nullptr，然而这边的list没有呢？
答：
拷贝构造l1(l2),l1首先要初始化、至少里面是个nullptr,因为他还没有被创建出来；
赋值的话l1 = l2,首先你这个l1是不是已经是先定义出来的，所以不用初始化的;

拷贝构造不能写那个swap,为什么？

答：这样的话在传参数时就是又一个拷贝构造，那就会无限循环

拷贝构造代码

		//拷贝函数l1(l2)
		//首先l1是没有创建出来的，所以要初始化
		list(const list<T>& lt)
		{
			//先初始化，list里面成员函数是什么？_head,_head里面的内容
			Node* _head;
			_head->_next = _head->_prev = _head;

			//往里面插入后面的值就行了
			//方法一
			/*const_iterator it = lt.begin();
			while (it != it.end())
			{
				push_back(*it);//运算符重载过*it了，传过去的是_node->_data
				it++;
			}*/

			//方法二
			for (auto e : lt)//本质调用的迭代器
			{
				push_back(e);
			}

		}

在string和vector里面是这样的,for循环本质使用的是迭代器，有迭代器就有for循环，e理论上就是*it

面试问题

什么是迭代器失效？

迭代器失效具体内容

vector、list的区别？

vector是一个动态增长的数据
优点:支持随机访问operator[],排序、二分查找、堆算法等等可用到;
缺点:空间不够要增容、头部或者中间插入效率低o(n)；

list是一个带头双向循环的链表
优点：任意位置插入效率高o(1);
缺点：不支持随机访问；

总结:list和vector相辅相成、是两个互补的容器

完整代码

test.c

#pragma once
namespace list_test
{
	template<class T>
	//struct__list_node,两个_这种取名方式一般表示一会这个会在别的里面用，在这里就表示，list类里面直接用的类外面定义的struct __list_code这个结构体
	struct __list_node
	{
		__list_node<T>* _next; // 别忘了这里要写<T>
		__list_node<T>* _prev;
		T _data;

		//列表需要构造函数来初始化
		__list_node(const T& x = T())//这个T(),指的是没有传值过来那就直接为0
			:_data(x)
			,_next(nullptr)  
			,_prev(nullptr)
		{}
	};


	//struct迭代器__list_iterator
	template<class T, class Ref, class Ptr>//这个就是三个模板参数
	struct __list_iterator
	{
		typedef __list_node<T> Node;
		typedef __list_iterator<T, Ref, Ptr> Self;
		Node* _node;
		 
		//构造函数，struct怎么写构造函数、就是看这个里面成员函数有哪些
		__list_iterator(Node* node)
			:_node(node)
		{}

		//构造传的是里面的成员函数、拷贝是传的类或者说这个结构体
		//浅拷贝，这个是默认函数、不用写的
		__list_iterator(const Self& it) 
		{
			_node = it._node;
		}

		// operator*，读_node中的data,data的类型是T,所以函数返回值类型是T
		Ref operator*()
		{
			return _node->_data;
		}


		//++
		Self& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		//后置++
		Self operator++(int) //后置++里面就放个int，这是设计出来的伪参数，用来区分前后置用的
		{
			__list_iterator<T> tmp(*this); //直接拷贝函数、这个不用写、因为是浅拷贝，深拷贝才要写
			_node = _node->_next; 
			//++(*this);
			return tmp;
		}

		//--
		Self& operator--()
		{
			_node = _node->_prev; //_node是指针
			return *this; //*this就是迭代器，this是指针指向迭代器
		}
		Self& operator--(int) //后置++里面就放个int，这是设计出来的伪参数，用来区分前后置用的
		{
			Self tmp(*this); //直接拷贝函数、这个不用写、因为是浅拷贝，深拷贝才要写
			//node = _node->_next;
			--(*this);
			return tmp;
		}




		//!=,两个迭代器之间不相等、迭代器里面的成员函数是_node,比的是这两个，就是他指向一个列表的地址，看这两个地址一样吗
		bool operator!=(const Self& it)
		{
			return _node != it._node;
		}

		Ptr operator->()
		{
			return &_node->_data;//返回这个地址
			//指向这个地址，调用时第一个->返回其地址、第二个->返回地址上的值，迭代器做了优化，调用只需要一个->
		}


	};




	template<class T>
	class list
	{
		typedef __list_node<T> Node;
	public:
		typedef __list_iterator<T, T&, T*> iterator; // 放public里面不然外面动不了T，就是用不了模板，私有的不能用
		typedef __list_iterator<T,const T&,const T*> const_iterator;//const迭代器

		//迭代器用节点的指针就行了
		iterator begin()
		{
			return iterator(_head->_next);
			//注意这里返回的是迭代器，不是_head头部指针、这个是list类里面的成员变量
			//现在是把头部指针_head传过去，然后迭代器调用他的拷贝函数;
			//这里面就是构造函数、因为传过去的是Node类型;
		}
		iterator end()
		{
			return iterator(_head);
		}
		//const_iterator
		const_iterator begin() const
		{
			return const_iterator(_head->_next); 
		}
		const_iterator end() const
		{
			return const_iterator(_head);
		}



		//构造函数
		list()
		{
			_head = new Node;//new node //这里面不用写成Node[]，是因为[]是数组用的，这个就里面就开辟一个指针指向的地址空间，[]是一个数组的空间
			_head->_next = _head;
			_head->_prev = _head;



		}


		//insert
		//现在要的是列表里面的那两个指针next\prev;
		//迭代器里面就有_node存的是Node*类型;
		void insert(iterator pos,const T& x = T())
		{
			Node* cur = pos._node;//pos是迭代器所以调用他的成员函数用点符号"."虽然类似指针但是不能->,这个是指针用的
			Node* prev = cur->_prev;
			Node* newnode = new Node(x);

			newnode->_next = cur;
			newnode->_prev = prev;
			cur->_prev = newnode;
			prev->_next = newnode;

		}
		//头插
		void push_front(const T& x = T())
		{
			insert(begin(), x);
		}
		//尾插
		void push_back(const T& x = T())
		{
			//Node* tail = _head->_prev;
			//Node* newnode = new Node(x);

			//tail->_next = newnode;
			//newnode->_prev = tail;
			//newnode->_next = _head;
			//_head->_prev = newnode;
			

			//再pos是end()的时候插入，end()表示最后一个元素的后一个位置，所以插入这个位置就是尾插
			insert(end(), x);
		}


		//erase,erase是要返回删除的位置的后一个位置的
		Node* erase(iterator pos)
		{

			//cur里面存现在的地址
			//prev是cur上一个地址
			assert(pos  != end()); //头节点不能删
			Node* cur = pos._node;  
			Node* prev = cur->_prev;
			Node* next = cur->_next;

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

			delete cur;//delete[]必须是数组,所以要注意
			return next;
			

		}

		//尾删
		void pop_back()
		{
			//erase(iterator(_head->_prev));
			erase(--end());
		}
		//头删除
		void pop_front()
		{
			erase(begin());
		}

		void clear()
		{
			Node* cur = _head->_next;

			while (cur != _head)
			{
				_head->_next = cur->_next;
				delete cur;
				cur = _head->_next
			}
			_head = head->next = head->prev;//重新关联起来，双向带头循环列表；
		}
		//析构
		~list()
		{
			clear();
			detete _head;
			_head = nullptr;
		}

		//拷贝函数l1(l2)
		//首先l1是没有创建出来的，所以要初始化
		list(const list<T>& lt)
		{
			//先初始化，list里面成员函数是什么？_head,_head里面的内容
			Node* _head;
			_head->_next = _head->_prev = _head;

			//往里面插入后面的值就行了
			//方法一
			/*const_iterator it = lt.begin();
			while (it != it.end())
			{
				push_back(*it);//运算符重载过*it了，传过去的是_node->_data
				it++;
			}*/

			//方法二
			for (auto e : lt)//本质调用的迭代器
			{
				push_back(e);
			}

		}


		//赋值运算l1 = l2
		//方法一：
		list<T>& operator=(const list<T>& lt)
		{
			//防止自己给自己赋值
			if (this != &lt)//用地址来比较
			{
				clear();//看clear函数，clear结束后就是初始化后的_head,所以也不用再写一遍_head的初始话
				for (auto e : lt)
					push_back(e);//就一行不用写{}了
				
			}

			return *this;//*this,解引用this迭代器就是这个list类的对象了l1
		}
		//方法二：
		list<T>& operator=(list<T> lt)//这里传参用到拷贝构造，lt是临时对象
		{
			swap(_head, lt._head)
			return *this;//*this,解引用this迭代器就是这个list类的对象了l1
		}


	private:
		Node* _head;
	};


	void test_list1()
	{
		list<int> lt;

		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);

		list<int>::iterator it = lt.begin();
		while (it != lt.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;

	}
	

	struct Date
	{
		int _year = 0;
		int _month = 1;
		int _day = 2;

	};

	void test_list2()
	{
		list<Date> lt;
		lt.push_back(Date());
		lt.push_back(Date());

		list<Date>::iterator it = lt.begin();//调用data，因为现在模板T就是date，传参传过去date是可以的
		while (it != lt.end())
		{
			cout << it->_year << " " << it->_month << " " << it->_day;
			++it;
		}
		cout << endl;
	}

	void print_list(const list<int>& lt)
	{
		list<int>::const_iterator it = lt.begin();
		while (it != lt.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}


	void test_list3()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);

		print_list(lt);


		lt.pop_front();
		lt.pop_back();
		print_list(lt);

	}
}