2.值得注意的函数

list为什么要支持sort，不可以使用algorithm文件里面的吗

 算法库里面使用了first-last 但是很显然list是不支持节点相减的

2.很细节的函数实现 

一个合格的list是支持增删查改的

push_back（）已经实现过了

下面看insert()

 注意到它是有返回值的 ，返回迭代器，在头部增加数据当然是可以的

iterator insert(iterator  pos, const T& x){node* newnode = new node(x);node* cur = pos._pnode;node* prev = cur->_prev;//prev newnode curprev->_next = newnode;newnode->_next = cur;newnode->_prev = prev;cur->_prev = newnode;return iterator(newnode);}

 对应的erase（）

 也是有返回值，并且不能在头结点位置删除，哨兵位不能动

iterator erase(iterator pos){assert(pos != end());node* cur = pos._pnode;node* prev = cur->_prev;node* next = cur->_next;//prev cur nextprev->_next = next;next->_prev = prev;delete cur;return  iterator(next);}

那么头尾的增删就可以复用啦

void pop_back(){erase(--end());}
void pop_front(){erase(begin());}
void push_back(const T& x){//node* newnode  = new node(x);//node* tail = head->_prev;head  tail newnode//tail->_next = newnode;//newnode->_next = head;//newnode->_prev = tail;//head->_prev = newnode;insert(end(), x);}
void push_front(const T& x){insert(begin(), x);}

然后就是clear（），注意头结点不能删

	void clear(){iterator it = begin();while(it!=end()){it=erase(it);}//头节点不能删除}

析构函数

~list(){clear();//此时需要把头节点也删除delete head;head = nullptr;}

下面是拷贝构造

//拷贝构造
//l2=l1list& operator=(const list& l){if (*this != l){clear();for (const auto&e :l){push_back(e);}}return *this;}

为了写着更方便，把头结点的开辟封装成函数

void empty_initialize(){head = new node(T());head->_next = head;head->_prev = head;}

//l2(l1)list(const list & l){empty_initialize();for (const auto& e : l){push_back(e);}}

迭代器还有const版本怎么实现

最简单想到的就是直接在iterator类里面加上一个const修饰*运算符重载

template struct __list_iterator{typedef _list_node node;node* _pnode;__list_iterator(node* p):_pnode(p){}T& operator*(){return _pnode->data;}//在同一个类里面实现就是不行，因为const——iterator只能遍历，不能++/*	const T& operator*() const {return _pnode->data;}*/__list_iterator& operator++(){_pnode = _pnode->_next;return *this;}bool operator!=(const __list_iterator& it){return _pnode != it._pnode;}};

但是这个真的对么？很显然不对，因为iterator可以遍历，++  但是const_iterator只能遍历无法++

所以很自然想到写在两个类里面

template struct __list_iterator{typedef _list_node node;node* _pnode;__list_iterator(node* p):_pnode(p){}T& operator*(){return _pnode->data;}//在同一个类里面实现就是不行，因为const——iterator只能遍历，不能++/*	const T& operator*() const {return _pnode->data;}*/__list_iterator& operator++(){_pnode = _pnode->_next;return *this;}bool operator!=(const __list_iterator& it){return _pnode != it._pnode;}};template struct __list_const_iterator{typedef _list_node node;node* _pnode;__list_const_iterator(node* p):_pnode(p){}const T& operator*() const {return _pnode->data;}__list_const_iterator& operator++(){_pnode = _pnode->_next;return *this;}bool operator!=(const __list_const_iterator& it){return _pnode != it._pnode;}};

 这两个类只在*运算符重载 还有名称上有区别

但是这是我们的想法，看一下源码就知道大佬果然是大佬

直接用两个模板参数解决问题

		template struct __list_iterator{typedef _list_node node;typedef __list_iterator Self;node* _pnode;__list_iterator(node* p):_pnode(p){}Ref operator*(){return _pnode->data;}//在同一个类里面实现就是不行，因为const——iterator只能遍历，不能++/*	const T& operator*() const {return _pnode->data;}*/Self& operator++(){_pnode = _pnode->_next;return *this;}Self& operator--(){_pnode = _pnode->_prev;return *this;}bool operator!=(const Self& it){return _pnode != it._pnode;}};

拷贝构造可有现代写法哦，此时同样需要一个构造函数用迭代器初始化的

l2（l1）相比较来说，现代写法就是多一个工具人帮助复刻l1，然后把数据交换给l2，最后他自己牺牲....

首先是构造函数（用迭代器实现的）

template list(InputIterator first, InputIterator last){empty_initialize();while(first != last){push_back(*first);++first;}}

 然后是swap

	void swap(const list& l){std::swap(head, l.head); //两个链表交换只需交换头结点}

现代写法

//l2(l1)list(const list& l){empty_initialize();list tmp(l.begin(), l.end());swap(tmp); //tmp出作用域销毁}

 l2=l1   这是对于一个已经存在的对象l1，无需构造头结点

//l2=l1  这是对于一个已经存在的对象l1，无需构造头结点list & operator=(const list& l){swap(l);return *this;}

想象一个场景：你需要统计size（），当然这种操作不能频繁进行，因为每一次都要从头开始遍历有很多消耗，那么最简单的办法是什么？！成员变量加上size

 现在凸显出复用的好处了，我虽然实现到一半开始想加上size，也只需要改动几个函数就可以完成功能

 其他全是复用，爽歪歪

可以用size实现两个函数

             size_t _size(){return size;}bool rmpty(){//return head->next==head;return size==0;}

C++兼容c是有前置和后置的（区分于有些语言，觉得前置后置很麻烦就删去后置）

完善一下前面对于迭代器的运算符操作

	//前置Self& operator++(){_pnode = _pnode->_next;return *this;}//后置Self& operator++(int){Self tmp(*this);_pnode = _pnode->_next;return tmp;}//前置Self& operator--(){_pnode = _pnode->_prev;return *this;}//后置Self& operator--(int ){Self tmp(*this);_pnode = _pnode->_prev;return tmp;}

看起来写成这样是不是很完美，但是看一个问题

struct Pos{size_t _row;size_t _col;Pos(size_t row=0,size_t col=0)  //一定要时刻记着写一个默认构造！！！！！！:_row(row),_col(col){}};void test(){list lt;Pos p1(1, 1);lt.push_back(p1);lt.push_back(p1);lt.push_back(p1);lt.push_back(Pos(2, 2)); //匿名函数lt.push_back(Pos(3, 3));list::iterator it = lt.begin();while (it != lt.end()){//it->_row++;cout << *it << " ";}}

思考一下有什么问题？？？

 这很尴尬，首先我们思考一下，为什么C++支持cout，因为可以对内置类型可以直接识别然后输出，但是这里的it是个迭代器

其实这样就可以啦，只需要重载一个->这个运算符

但是我们只有T这个模板类型，没有T*

 然后运算符->重载这样写

Ptr operator->(){return &_pnode->data;}

注意：脑子一定要清醒，我们提供类T是为了list每个节点的数据类型，Ref是T&（当然还有一个const T&），Ptr是T*(还有const T*）

这里面也体现出我们typedef的智慧

这个模板我们改了很多次，但是我typedef之后，直接修改类型，不需要改名字，都是Self！！！

所以直接->访问就可以啦

他的原理就是

3.vector和list对比

4.迭代器失效

vector：insert和erase都有失效问题

lsit：erase会失效

那么string会有失效问题吗？当然，insert和erase都有，和vecor类似，但是一般不关注string失效，因为string的insert和erase常用接口都是下标支持的，迭代器用的少

最后我们的list实现总代码 

.h文件

#pragma once
namespace wrt
{template struct _list_node{_list_node* _prev;_list_node* _next;T data;_list_node(const T& x)  //用x初始化节点:_prev(nullptr),_next(nullptr),data(x){}};template struct __list_iterator{typedef _list_node node;typedef __list_iterator Self;node* _pnode;__list_iterator(node* p):_pnode(p){}Ref operator*(){return _pnode->data;}Ptr operator->(){return &_pnode->data;}//在同一个类里面实现就是不行，因为const——iterator只能遍历，不能++/*	const T& operator*() const {return _pnode->data;}*///前置Self& operator++(){_pnode = _pnode->_next;return *this;}//后置Self& operator++(int){Self tmp(*this);_pnode = _pnode->_next;return tmp;}//前置Self& operator--(){_pnode = _pnode->_prev;return *this;}//后置Self& operator--(int ){Self tmp(*this);_pnode = _pnode->_prev;return tmp;}bool operator!=(const Self& it){return _pnode != it._pnode;}};/*	template struct __list_const_iterator{typedef _list_node node;node* _pnode;__list_const_iterator(node* p):_pnode(p){}const T& operator*() const {return _pnode->data;}__list_const_iterator& operator++(){_pnode = _pnode->_next;return *this;}bool operator!=(const __list_const_iterator& it){return _pnode != it._pnode;}};*/template class list{typedef _list_node node;public://typedef __list_iterator iterator;//typedef __list_const_iterator  const_iterator;typedef __list_iterator iterator;typedef __list_iterator  const_iterator;size_t _size(){return size;}bool rmpty(){//return head->next==head?return size == 0 ;}iterator begin(){return iterator(head->_next);}iterator end(){return iterator(head);}const_iterator begin() const {return iterator(head->_next);}const_iterator end() const {return iterator(head);}void push_back(const T& x){//node* newnode  = new node(x);//node* tail = head->_prev;head  tail newnode//tail->_next = newnode;//newnode->_next = head;//newnode->_prev = tail;//head->_prev = newnode;insert(end(), x);}void push_front(const T& x){insert(begin(), x);}~list(){clear();//此时需要把头节点也删除delete head;head = nullptr;size = 0;}//拷贝构造//l2=l1/*list& operator=(const list& l){if (*this != l){clear();for (const auto&e :l){push_back(e);}}return *this;}*/void empty_initialize(){head = new node(T());head->_next = head;head->_prev = head;size = 0;}list(){empty_initialize();}//l2(l1)/*	list(const list & l){empty_initialize();for (const auto& e : l){push_back(e);}}*///拷贝构造的现代写法template list(InputIterator first, InputIterator last){empty_initialize();while (first != last){push_back(*first);++first;}}void swap(const list& l){std::swap(head, l.head); //两个链表交换只需交换头结点}//l2(l1)list( list& l){empty_initialize();list tmp(l.begin(), l.end());swap(tmp); //tmp出作用域销毁}//l2=l1  这是对于一个已经存在的对象l1，无需构造头结点list & operator=(const list& l){swap(l);return *this;}void clear(){iterator it = begin();while(it!=end()){it=erase(it);}//头节点不能删除size = 0;}void pop_back(){erase(--end());}void pop_front(){erase(begin());}iterator insert(iterator  pos, const T& x){node* newnode = new node(x);node* cur = pos._pnode;node* prev = cur->_prev;//prev newnode curprev->_next = newnode;newnode->_next = cur;newnode->_prev = prev;cur->_prev = newnode;++size;return iterator(newnode);}iterator erase(iterator pos){assert(pos != end());node* cur = pos._pnode;node* prev = cur->_prev;node* next = cur->_next;//prev cur nextprev->_next = next;next->_prev = prev;delete cur;--size;return  iterator(next);}private :node* head;size_t size;};struct Pos{size_t _row;size_t _col;Pos(size_t row=0,size_t col=0)  //一定要时刻记着写一个默认构造！！！！！！:_row(row),_col(col){}};void test(){list lt;Pos p1(1, 1);lt.push_back(p1);lt.push_back(p1);lt.push_back(p1);lt.push_back(Pos(2, 2)); //匿名函数lt.push_back(Pos(3, 3));list::iterator it = lt.begin();while (it != lt.end()){//	cout << *it << " ";//cout << it.operator->()->_row << ":" << it->_col << endl;cout << it->_row << ":" << it->_col << ":" << endl;}}/*void test(){list  lt;lt.push_back(1);lt.push_back(3);lt.push_back(4);lt.push_back(5);lt.push_back(6);lt.push_back(7);lt.insert(lt.begin(), 5);lt.erase(lt.begin());lt.push_back(40);list::iterator it = lt.begin();while (it != lt.end()){cout << *it <<" ";++it;}cout <

#define _CRT_SECURE_NO_WARNINGS
#include 
#include 
#include 
using namespace std;
#include "标头.h"
int main()
{wrt::test();return 0;
}