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_iteratorconst_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->_datait++;}*///方法二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_iteratortemplate<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,所以函数返回值类型是TRef 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_iteratorconst_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->_datait++;}*///方法二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);}
}