list的使用(常用)本质:带头双向链表Member functionsconstructvoidtest01(){//默认构造listintlt1;//n个val构造listintlt2(10,1);//迭代器区间构造vectorintv1{1,2,3,4,5,6};listintlt3(v1.begin(),v1.end());//拷贝构造listintlt4(lt3);//initializer_list(C11语法)listintlt5{1,2,3,4,5};}iterator分类功能通用: * !单向(forward)单链表/哈希表双向(bidirectional)/–双向链表list/红黑树随机(random)/–//-string/vector/双端队列deque一个算法,不是所有的容器都可以使用,算法对迭代器是有一些要求算法迭代器名字就是要求(暗示)voidtest02(){//迭代器//1.封装:通用的,相似的遍历容器的方式,并且封装了容器底层,屏蔽容器结构的差异//2,通用/复用,实现算法时用迭代器函数模板方式实现,跟底层容器结构解耦listintlt1{1,2,3,4,5};listint::iterator it1lt1.begin();while(it1!lt1.end()){cout*it1 ;it1;}coutendl;//范围forfor(autoe:lt1){coute ;}coutendl;//sort(迭代器理解)//list自己实现sort//效果没有vector好inta[]{0,-3,90,-8,88,55};sort(a,asizeof(a)/sizeof(int));for(autox:a){coutx ;}coutendl;}Modifierspush_backpush_frontresizeOperationsvoidtest04(){listintlt1{1,2,3,4,5};lt1.push_back(10);lt1.push_front(10);lt1.resize(20,9);listintlt2{1,20,13,-4,5};lt1.sort();//尽量少用lt2.reverse();lt2.sort();//merge之前两个容器都要先排好序lt1.merge(lt2);for(autoe:lt1){coute ;}coutendl;//去重lt1.unique();for(autoe:lt1){coute ;}coutendl;//removelt1.remove(5);for(autoe:lt1){coute ;}coutendl;}以上省略一些使用接口,因为在使用时并不常用.想要更多了解使用可查看官方文档:(https://legacy.cplusplus.com/reference/list/list/)此处的重点为list的模拟实现,实现的过程过结合list的源码可以带给我们更多感悟和启发,进一步加深我们对C这一编程语言的两大特点(封装和面对对象)的理解.list模拟实现list.h#define_CRT_SECURE_NO_WARNINGS#pragmaonce#includeiostreamusingnamespacestd;namespacemySTL{templateclassTstructlist_node{T _data;list_nodeT*_next;list_nodeT*_prev;//全缺省构造list_node(constTxT()):_data(x),_next(nullptr),_prev(nullptr){}};////普通迭代器//templateclass T//struct _list_iterator//{// typedef list_nodeT Node;// Node* _node;// _list_iterator(Node* node)// :_node(node)// { }// //// T operator*() {// return _node-_data;// }// _list_iteratorT operator() {// _node _node-_next;// return *this;// }// _list_iteratorT operator(int) {// _list_iteratorT tmp(*this);// _node _node-_next;// return tmp;// }// _list_iteratorT operator--() {// _node _node-_prev;// return *this;// }// _list_iteratorT operator--(int) {// _list_iteratorT tmp(*this);// _node _node-_prev;// return tmp;// }// bool operator!(const _list_iteratorT it) {// return _node ! it._node;// }// bool operator(const _list_iteratorT it) {// return _node it._node;// }////};////const迭代器//templateclass T//struct const_list_iterator//{// typedef list_nodeT Node;// Node* _node;// const_list_iterator(Node* node)// :_node(node)// {// }// //// const T operator*() {// return _node-_data;// }// const_list_iteratorT operator() {// _node _node-_next;// return *this;// }// const_list_iteratorT operator(int) {// const_list_iteratorT tmp(*this);// _node _node-_next;// return tmp;// }// const_list_iteratorT operator--() {// _node _node-_prev;// return *this;// }// const_list_iteratorT operator--(int) {// const_list_iteratorT tmp(*this);// _node _node-_prev;// return tmp;// }// bool operator!(const _list_iteratorT it) {// return _node ! it._node;// }// bool operator(const _list_iteratorT it){// return _node it._node;// }//};//最终迭代器实现templateclassT,classRef,classPtrstruct_list_iterator{typedeflist_nodeTNode;Node*_node;_list_iterator(Node*node):_node(node){}//Refoperator*(){return_node-_data;}_list_iteratorT,Ref,Ptroperator(){_node_node-_next;return*this;}_list_iteratorT,Ref,Ptroperator(int){_list_iteratorT,Ref,Ptrtmp(*this);_node_node-_next;returntmp;}_list_iteratorT,Ref,Ptroperator--(){_node_node-_prev;return*this;}_list_iteratorT,Ref,Ptroperator--(int){_list_iteratorT,Ref,Ptrtmp(*this);_node_node-_prev;returntmp;}booloperator!(const_list_iteratorT,Ref,Ptrit){return_node!it._node;}booloperator(const_list_iteratorT,Ref,Ptrit){return_nodeit._node;}Ptroperator-(){return_node-_data;}};templateclassTclasslist{public:typedeflist_nodeTNode;typedef_list_iteratorT,T,T*iterator;//不行const修饰迭代器本身,不能实现//typedef const _list_iteratorT iterator;typedef_list_iteratorT,constT,constT*const_iterator;//同一个类模板实例化的两个类型iteratorbegin(){returniterator(_head-_next);}iteratorend(){returniterator(_head);}const_iteratorbegin()const{returnconst_iterator(_head-_next);}const_iteratorend()const{returnconst_iterator(_head);}list(){_headnewNode;_head-_next_head;_head-_prev_head;}//insert(在pos前面插入)iteratorinsert(iterator pos,constTval){Node*curpos._node;Node*precur-_prev;// 先把原来的前驱存下来Node*newnodenewNode(val);newnode-_prevpre;newnode-_nextcur;pre-_nextnewnode;cur-_prevnewnode;returniterator(newnode);}//eraseiteratorerase(iterator pos){Node*curpos._node;Node*prevpos._node-_prev;Node*nextpos._node-_next;prev-_nextnext;next-_prevprev;deletecur;returniterator(next);}//析构~list(){iterator _itbegin();while(_it!end()){_iterase(_it);}//等价于cleardelete_head;_headnullptr;}//push_back/*void push_back(const T val) { Node* newnode new Node(val); Node* tail _head-_prev; newnode-_next _head; newnode-_prev tail; tail-_next newnode; _head-_prev newnode; }*/voidpush_back(constTval){insert(end(),val);}voidpush_front(constTval){insert(begin(),val);}voidpop_back(){erase(--end());}voidpop_front(){erase(begin());}//clearvoidclear(){iterator itbegin();while(it!end()){iterase(it);}}//深拷贝list(constlistTlt){_headnewNode;_head-_next_head;_head-_prev_head;for(constautoe:lt){push_back(e);}}//list(initializer_listTil){_headnewNode;_head-_next_head;_head-_prev_head;for(constautoe:il){push_back(e);}}//lt1lt2/*listT operator(const listT lt) { if (this ! lt) { clear(); for (const auto e : il) { push_back(e); } } return *this; }*/voidswap(listTlt){std::swap(_head,lt._head);}listToperator(constlistTlt){swap(lt);return*this;}//sizesize_tsize()const{size_t n0;for(autoe:*this){n;}returnn;}private:Node*_head;};}test.h#define_CRT_SECURE_NO_WARNINGS#includelist.hnamespacemySTL{voidtest01(){listintlt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);listint::iterator itlt1.begin();while(it!lt1.end()){cout*it ;it;}coutendl;}structPos{int_row;int_col;Pos(introw0,intcol0):_row(row),_col(col){}};voidtest02(){listPoslt1;//隐式类型转换lt1.push_back({2,2});lt1.push_back({3,3});lt1.push_back({4,4});auto_itlt1.begin();lt1.insert(_it,{1,1});for(autoe:lt1){coute._row:e._colendl;}lt1.push_back({9,9});lt1.push_front({8,8});for(autoitlt1.begin();it!lt1.end();it){coutit-_row:it-_colendl;}lt1.pop_back();for(autoitlt1.begin();it!lt1.end();it){coutit-_row:it-_colendl;}}templateclassTvoidprint(constlistTlt){// 类模板未实例化不能去类模板中找后面的东西// 编译器就分不清const_iterator是嵌套内类还是静态成员变量// typename告诉编译器我确认过了这里是类型//typename listT::const_iterator it lt.begin();autoitlt.begin();while(it!lt.end()){//*it 1;cout*it ;it;}coutendl;}}intmain(){//mySTL::test01();mySTL::test02();return0;}