STL: list的底层实现（下）

文章目录list接口函数实现前言一.插入和删除函数1.1任意位置插入函数——insert1.2任意位置删除函数——erase1.3尾插函数——push_back1.4尾删函数——push_back1.5头插函数和头删函数——push_back和pop_front二.清除函数与析构函数——clear和~list三.多种构造函数list接口函数实现前言在我们上篇文章中当你看懂了在list中迭代器的创建时就可以写下面的增删查改的函数了因为有些函数的参数时迭代器也是与库里的函数保持接口一致有兴趣的小伙伴可以看看库里的list的函数这样也能方便理解代码。这是list的库里的函数 https://legacy.cplusplus.com/reference/list/list/?kwlist我把我上篇文章实现的基本框架的代码放到这里方便我下面代码的可读性templateclassT,classRef,classPtrstruct__list_iterator{typedef_list_nodeTnode;typedef__list_iteratorT,Ref,Ptrself;node*_node;self(node*Node):_node(Node){}Refoperator*(){return_node-data;}selfoperator(){_node_node-_next;return*this;}selfoperator(int){selftmp(*this);_node_node-_next;returntmp;}booloperator!(constselfit)const{return_node!it._node;}selfoperator--(){_node_node-_prev;return*this;}selfoperator--(int){selftmp(*this);_node_node-_prev;returntmp;}Ptroperator-(){return_node-data;}};templateclassTclasslist{public:typedef_list_nodeTnode;typedef__list_iteratorT,T,T*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);}voidempty_init(){_headnewnode;_head-_prev_head;_head-_next_head;}list(){empty_init();}一.插入和删除函数1.1任意位置插入函数——insert观察库里的函数我们发现第一个函数就是返回迭代器类型的所以我们仿照它这里面的类型是被typedef过的可以去list标准库里面看iteratorinsert(iterator pos,constTvalT()){node*curpos._node;node*prevcur-_prev;node*newnodenewnode(val);newnode-_nextcur;newnode-_prevprev;cur-_prevnewnode;prev-_nextnewnode;returniterator(newnode);}缺点虽然说是在指定位置前面插入但是lsit的迭代器只能一个一个走,intmain(){autoitl1.begin();it;insert(it,100);}这样才能在第二个位置前面插入100,这个最大的作用就是在其他函数复用代码比如在头插和尾插中调用这个函数就行。注意这个函数里面的代码很简单返回值的话c是支持返回匿名对象的或者可以直接返回newnode它会支持隐式类型转化。1.2任意位置删除函数——erase库里也是迭代器实现我们就实现删除单个结点下面删除迭代器区间的话你们下去也可以自己试试iteratorerase(iterator pos){node*curpos._node;node*prevcur-_prev;node*nextcur-_next;prev-_nextnext;next-_prevprev;deletecur;returniterator(next);注意完成这个删除函数之后去测试一定要小心迭代器失效虽然我们自己写的函数发生了不会报错全凭自己感觉常见的会发生迭代器失效的就是扩容和删除数据在这里删除当前的结点后这个位置的迭代器就失效了不能返回当前的迭代器所以我们在erase中返回的就是下一个结点的迭代器所以我们要重新接收一下intmain{listintl1;//假如l1中存在数据autoitl1.begin();while(it!l1.end()){itl1.erase(it)//重点}}}1.3尾插函数——push_backvoidpush_back(constTval){/* node* newnode new node(val); node* ptail _head-_prev; newnode-_prev ptail; newnode-_next _head; ptail-_next newnode; _head-_prev newnode;*/insert(end(),val);}可以像我的注释掉的代码那样写也可以直接复用刚刚写的,end()返回的是头结点在头结点的前面插入不就是在尾部插入。1.4尾删函数——push_backvoidpop_back(){erase(--end());}删除尾部那不就是头结点的上一个结点复用函数真的很爽1.5头插函数和头删函数——push_back和pop_frontvoidpush_front(constTval){insert(begin(),val);}voidpop_front(){erase(begin());}二.清除函数与析构函数——clear和~list~list(){clear();delete_head;_headnullptr;}voidclear(){autoitbegin();while(it!end()){iterase(it);}}清除结点的clear函数不会把头结点删除所以在析构函数中需要delete 头结点三.多种构造函数3.1拷贝构造函数list(constlistTl1){empty_init();//范围for实现for(constautoe:l1){push_back(e);}//迭代器实现拷贝autoitl1.begin();while(it!l1.end()){push_back(*it);it;}}如果不会范围for的话可以用迭代器来实现本质范围for在底层也是转化为迭代器3.2初始化列表构造函数关键字是initializer_list这是c11后特有的类型list(initializer_listTl1){empty_init();for(constautoe:l1){push_back(e);}有了这个类型在创建对象的时候据可以直接像数组一样的·输入数据listintl1{1,2,3,4,5};这样写l1就有五个结点并且每个结点分别对应这五个数字。3.3多个值的构造函数list(size_t n,constTvalT()){empty_init();for(inti0;in;i){push_back(val);}}