List的模拟实现1、节点和链表的定义2、push_back()3、迭代器3.1、迭代器的设计3.2、迭代器其它方法的完善4、插入、删除操作5、链表的析构6、拷贝构造与赋值重载6.1、几个常见的构造方法6.2、拷贝构造与赋值重载的一般写法6.2、拷贝构造与赋值重载的现代写法7、重载-与迭代器的完善7.1、重载-7.2、迭代器的完善代码演示1、节点和链表的定义由于C实现的List是一个带头双向循环链表所以我们这样设计节点templateclassTstructList_node{T _data;structList_node*next;structList_node*prev;// 构造List_node(constTvalT())// 匿名对象做参数:_data(val),_next(nullptr),_prev(nullptr){}};这样初步设计链表templateclassTclasslist{public:usingnodeList_nodeT;// 重命名更方便防止漏类型参数T// 构造list():_head(newnode),_size(0){_head-_prev_head;_head-_next_head;}private:node*_head;// 头节点哨兵位size_t _size;// 记录节点个数};2、push_back()由于链表被创建时就有一个哨兵位所以我们就不需要对链表是否为空的情况进行讨论直接push_back// 尾插voidpush_back(constTval){node*newnodenewnode(val);node*tail_head-_prev;newnode-_next_head;newnode-_prevtail;tail-_nextnewnode;_head-_prevnewnode;_size;}3、迭代器我们实现List的迭代器还能直接使用指针吗之前的vector使用的是连续的int类型空间我们将指针重命名成迭代器就可以很好地完成自增、自减、访问数据。那List呢也是直接用指针吗List使用的是一个个节点。如果我们使用节点指针访问得到的是整个节点而不是其中的数据不符合逻辑节点与节点之间也不是连续的不能通过节点指针的、-来定位某一个节点。我们只能将List的节点封装成类在类中通过运算符重载来重定义行为。迭代器的设计是一种封装。封装的目的是隐藏底层的结构差异以提供一个统一的方法访问容器。类中可以通过运算符重载重定义行为。3.1、迭代器的设计迭代器的本质是对节点指针的封装。templateclassTstructList_iterator// 实现为公有{usingnodeList_nodeT;// 重命名node*_nodeptr;// 底层为节点指针List_iterator(node*nodeptrnode*()):_nodeptr(nodeptr)// 构造{}};迭代器不需要析构。迭代器的拷贝只需浅拷贝。我们加上几个重要的方法重载*、重载前置、重载!。templateclassTstructList_iterator{usingnodeList_nodeT;node*_nodeptr;List_iterator(node*nodeptr):_nodeptr(nodeptr){}Toperator*(){return_nodeptr-_data;}List_iteratorToperator(){_nodeptr_nodeptr-_next;return*this;}booloperator!(constList_iteratorTit){// *this与it一定不一样this和it的_nodeptr可能一样return_nodeptr!it._nodeptr;}// 如果直接this ! it会导致死循环};我们在List中简单实现begin(), end()begin()本质是指向哨兵位的下一个节点指针end()本质是指向哨兵位的节点指针然后我们使用范围for结果是可以正常使用实现了迭代器我们就要实现const_迭代器。我们很容易想到根据迭代器的实现再实现一份const迭代器。templateclassTstructList_const_iterator{usingnodeList_nodeT;node*_nodeptr;List_const_iterator(node*nodeptr):_nodeptr(nodeptr){}constToperator*(){return_nodeptr-_data;}// 只有*重载不一样List_const_iteratorToperator(){_nodeptr_nodeptr-_next;return*this;}booloperator!(constList_const_iteratorTit){return_nodeptr!it._nodeptr;}};照抄出一份const迭代器List_iterator都要改为List_const_iterator太麻烦了。我们可以做一步优化迭代器的类名重命名成Self。// 迭代器templateclassTstructList_iterator{usingnodeList_nodeT;usingSelfList_iteratorT;node*_nodeptr;List_iterator(node*nodeptr):_nodeptr(nodeptr){}Toperator*(){return_nodeptr-_data;}Selfoperator(){_nodeptr_nodeptr-_next;return*this;}booloperator!(constSelf it)const{return_nodeptr!it._nodeptr;}};// const迭代器templateclassTstructList_const_iterator{usingnodeList_nodeT;usingSelfList_const_iteratorT;node*_nodeptr;List_const_iterator(node*nodeptr):_nodeptr(nodeptr){}constToperator*(){return_nodeptr-_data;}Selfoperator(){_nodeptr_nodeptr-_next;return*this;}booloperator!(constSelf it)const{return_nodeptr!it._nodeptr;}};这样一来我们照抄的时候就只需要改变一两个地方。这也体现了复用的思想。值得注意的是构造函数的函数名不能用Self代替。但是我们是否可以再做一步优化乍一看迭代器和const迭代器非常相似只在解引用的返回值有区别因为const迭代器指的是修饰const对象的迭代器而const对象是不能被修改的。我们能否合二为一只在解引用的返回值的返回做区别答案是可以在模板参数列表部分再加一个参数Ref。// 迭代器templateclassT,classRefstructList_iterator{usingnodeList_nodeT;usingSelfList_iterator;node*_nodeptr;List_iterator(node*nodeptr):_nodeptr(nodeptr){}Refoperator*(){return_nodeptr-_data;}Selfoperator(){_nodeptr_nodeptr-_next;return*this;}booloperator!(constSelf it)const{return_nodeptr!it._nodeptr;}};然后我们在List中重命名出迭代器和const迭代器usingiteratorList_iteratorT,T;usingconst_iteratorList_iteratorT,constT;我们就可以非常巧妙地利用一个模板实例化出两个迭代器类。3.2、迭代器其它方法的完善重载前置、–重载后置、–// 前置Selfoperator(){_nodeptr_nodeptr-_next;return*this;}// 后置Selfoperator(int){Self tmp*this;_nodeptr_nodeptr-_next;returntmp;}// 前置--Selfoperator--(){_nodeptr_nodeptr-_prev;return*this;}// 后置--Selfoperator--(int){Self tmp*this;_nodeptr_nodeptr-_prev;returntmp;}重载、!// 重载booloperator(constSelfit)const{return_nodeptrit._nodeptr;}// 重载!booloperator!(constSelf it)const{return_nodeptr!it._nodeptr;}List中的begin()、end()iteratorbegin(){returniterator(_head-_next);}iteratorend(){returniterator(_head);}const_iteratorbegin()const{returnconst_iterator(_head-_next);}const_iteratorend()const{returnconst_iterator(_head);}4、插入、删除操作插入// insertiteratorinsert(iterator pos,constTval)// 返回类型为iterator防止迭代器失效{node*newnodenewnode(val);node*curpos._nodeptr;// pos是迭代器类不能使用-因为没有实现重载-node*prevcur-_prev;newnode-_nextcur;newnode-_prevprev;cur-_prevnewnode;prev-_nextnewnode;_size;returniterator(newnode);}这样一来我们的头插、尾插就可以复用// 尾插voidpush_back(constTval){insert(_head,val);}// 头插voidpush_front(constTval){insert(_head-_next,val);}删除// pop_backvoidpop_back(){erase(_head-_prev);}// pop_front()voidpop_front(){erase(_head-_next);}5、链表的析构const函数const修饰的是*this。实现析构我们可以先实现clear()只保留链表的头节点。我们可以使用迭代器实现// clearvoidclear(){iterator itbegin();while(it!end()){iterase(it);}}析构函数在clear()的基础上只需再销毁哨兵位// 析构~list(){clear();delete_head;_headnullptr;}6、拷贝构造与赋值重载6.1、几个常见的构造方法我们先来实现initializer_list构造// initializer_listlist(constinitializer_listTil){for(autoe:il){push_back(e);}}测试时程序崩溃了。原因是此处的构造没有构造出哨兵位。所以之后的行为都是未定义的。我们不妨另外定义一个函数专门生成哨兵位以后每个构造函数都要调用这个函数voidempty_init(){_headnewnode(T());_head-_prev_head;_head-_next_head;}// initializer_listlist(constinitializer_listTil){empty_init();for(autoe:il){push_back(e);}}我们在实现Print()打印时如果直接这样写会导致编译错误我们可以简单理解出错的原因编译器无法理解此处的it到底是const_iterator对象还是一个静态成员变量。所以我们在listT::const_iterator前加上typename用来告诉编译器const_iterator是一个类型。然后来实现迭代器构造// 迭代器构造templatetypenameInputIteratorlist(InputIterator first,InputIterator last){empty_init();while(first!last){push_back(*first);first;}}再来实现n个值构造list(size_t n,constTvalT()){empty_init();for(size_t i0;in;i){push_back(n);}}由于我们无法采用更好的方式解决此时的n个值构造与迭代器构造匹配混乱的问题所以我们加上一个重载进行补救list(size_t n,constTvalT()){empty_init();for(size_t i0;in;i){push_back(n);}}list(intn,constTvalT()){empty_init();for(inti0;in;i){push_back(n);}}6.2、拷贝构造与赋值重载的一般写法拷贝构造创建哨兵位遍历push_back// 拷贝构造list(constlistTli){empty_init();for(autoe:li){push_back(e);}}赋值重载避免自己给自己赋值清理到留下哨兵位遍历push_back// 赋值重载listToperator(constlistTli){if(this!li){clear();for(autoe:li){push_back(e);}}return*this;}6.2、拷贝构造与赋值重载的现代写法拷贝构造与赋值重载现代写法的核心抢夺别人的成果拷贝构造list(constlistTli){empty_init();// 不能使用tmp(li)这会调用拷贝构造导致无穷递归listTtmp(li.begin(),li.end());swap(tmp);}赋值重载// 现代写法listToperator(listTli){clear();swap(li);return*this;}7、重载-与迭代器的完善7.1、重载-我们之前使用List每一个节点保存的都是比较简单的内置类型。那如果每一个节点存入一个自定义类型呢structA{int_a1;int_a2;A(inta10,inta20):_a1(a1),_a2(a2){}};我们只需传入多个参数进行隐式类型转换就可以完成一些简单的初始化、插入等操作l1.push_back({1,1});l1.push_back({2,2});l1.push_back({3,3});l1.push_back({4,4});使用迭代器打印看看呢显然直接打印A类型的对象是不行的。我们只能依次打印出A类型成员这样就不太简洁因为我们会很自然地理解为(*[指针]).的行为等价于[指针]-。所以这里需要我们实现重载-T*operator-(){return_nodeptr-_data;}乍一看我们可能对当前-的行为有点费解coutit-_a1:it-_a2endl;其实当前-会被处理这是处理后的模样coutit.operator-()-_a1:it.operator-()-_a2endl;迭代器it通过重载-访问到当前it指向链表节点存储的A对象的指针再通过A对象的指针访问到A对象下的成员。7.2、迭代器的完善有了迭代器的重载-就需要有const迭代器的重载-。再写一个重载-吗不需要。我们借助模板templateclassT,classRef,classPtrstructList_iterator{// 重载-Ptroperator-(){return_nodeptr-_data;}};templateclassTclasslist{public:usingiteratorList_iteratorT,T,T*;// 实例化出了两种迭代器类usingconst_iteratorList_iteratorT,constT,constT*;};代码演示代码演示