一、list的模拟实现1.1list的节点结构、容器结构、迭代器结构我们需要自己写一个list首先在list类外还需要两个类一个节点一个迭代器。节点类和迭代器类为list类服务。ps说实话list部分真的还挺难写的我自己给绕晕了好几次主要在多了结构和迭代器都比较难但是跨过这两个就会好很多了我们先从小的开始。节点结构//节点类templateclassTstructlist_node{typedeflist_nodeTNode;// 节点类型别名list_node();~list_node();T _val;// 节点数据域Node*_prev;// 后继节点指针Node*_next;// 前驱节点指针};这个节点可以存放任何类型的数据所以它得是一个模板。list_node有三部分构成数据指向下一个节点的指针指向上一个节点的指针。迭代器结构因为我们在上一篇文章中说道他的、--、*不再是原生指针了所以我们要对他进行封装。这段迭代器结构目前还不完整后面的讲解会逐步完善链表迭代器的实现//迭代器类templateclassTstruct_list_iterator{typedeflist_nodeTNode;// 节点类型别名_list_iterator();~_list_iterator();Node*_node;// 指向链表节点的指针};容器结构//链表类templateclassTclasslist{typedeflist_nodeTNode;// 节点类型别名public:list();~list();private:Node*_head;size_t _size;};链表的迭代器为啥不能直接用原生指针因为链表的原生指针比如list_node*只能访问节点本身而迭代器需要模拟 “像普通指针一样解引用取数据、/--遍历” 的行为 —— 链表节点里存的是_val实际数据原生指针解引用得到的是整个节点不是数据且链表的 “下一个元素” 需要通过_next指针跳转原生指针的是地址 1不符合链表的节点连接逻辑所以得封装迭代器类来重载*、等运算符不能直接用原生指针。迭代器结构为啥用struct迭代器结构体用struct是因为迭代器只是遍历容器的工具 —— 哪怕直接定义迭代器对象没有对应的容器支撑也没法实际访问有效数据所以不用刻意封装成私有用struct让成员比如这里的_node指针直接暴露能简化后续迭代器功能的实现。迭代器为啥不能写析构函数不能为迭代器编写析构函数 —— 因为节点的内存是由容器管理的迭代器只是 “借用节点指针来访问元素”本身并不持有节点的所有权。若在迭代器析构时释放节点会导致容器内的节点被非法销毁进而引发内存错误。1.2list的默认函数list构造函数//list构造函数list(){_headnewNode;_head-_prev_head;// 头节点前驱指向自身循环链表_head-_next_head;// 头节点后继指向自身循环链表_size0;// 链表初始长度为0}list拷贝构造函数// list拷贝构造函数list(constlistTlt){_headnewNode;//先创建一个头结点_head-_prev_head;// 头节点前驱指向自身循环链表_head-_next_head;// 头节点后继指向自身循环链表_size0;// 链表初始长度为0//遍历lt的每个元素逐个尾插到新链表中,这个要支持迭代器for(autoe:lt){push_back(e);}}push_back这个函数我们后面实现。list赋值运算符重载//list的交换函数voidswap(listTlt){std::swap(_head,lt._head);std::swap(_size,lt._size);}//list赋值运算符重载//已经有了实体// l1l2listToperator(listTlt)// 传值调用自动拷贝出临时对象lt{swap(lt);// 交换当前对象与临时对象的资源return*this;// 返回当前对象临时对象会自动销毁旧资源}list析构函数// 清空链表中所有有效元素保留头节点voidclear(){iterator itbegin();// 获取链表起始迭代器while(it!end())// 遍历所有有效元素{iterase(it);// 删除当前元素erase返回下一个元素的迭代器}_size0;// 重置有效元素个数为0}// 链表析构函数释放所有资源~list(){clear();// 先清空所有有效元素delete_head;// 释放头节点的堆内存_headnullptr;// 将头节点指针置空避免野指针}二、迭代器结构重点//迭代器结构体templateclassTstruct_list_iterator{typedeflist_nodeTNode;// 节点类型别名typedef_list_iteratorTiterator;//迭代器类型别名// 构造用节点指针初始化迭代器_list_iterator(Node*node):_node(node){}Node*_node;// 指向链表节点的指针};迭代器本身就是一个封装指针所以不需要拷贝构造浅拷贝够用我们已经写出来的接下来我们要实现让他可以像指针一样使用。2.1operator*原本的指针解引用返回具体内置类型值但是这里的链表节点时一个结构体所以必须重载解引用。如下代码我们让解引用返回的是结构体内部的数据。Toperator*(){return_node-_val;}2.2operator和--分别包装了向前找一个节点返回和向后找一个节点返回的逻辑。iteratoroperator(){_node_node-_next;return*this;}iteratoroperator(int){iterator tmp*this;_node_node-_next;returntmp;}iteratoroperator--(){_node_node-_prev;return*this;}iteratoroperator--(int){iterator tmp*this;_node_node-_prev;returntmp;}前置和--的逻辑很相似都是直接修改当前迭代器的节点指针_node然后返回自身的引用。比如前置是把_node指向 “下一个节点”前置--是指向 “前一个节点”返回自身引用的好处是支持链式操作比如(it)、--(--it)而且没有临时对象的开销效率更高。后置和--的核心是 “先返回原状态再移动”函数参数里的int是个占位符没有实际意义只是用来区分前置 / 后置实现时会先创建一个临时迭代器tmp保存当前状态然后移动_node到下一个 / 前一个节点最后返回这个临时迭代器。这样外部使用时it拿到的是 “移动前的迭代器”而it本身已经完成了移动 —— 不过因为会创建临时对象它的效率比前置版本略低。2.3operator与!相等与不相等的判断依据固定在对于节点的比较。booloperator(constiteratorit)const{return_nodeit._node;}booloperator!(constiteratorit)const{return_node!it._node;}这两个运算符的逻辑很直接判断两个迭代器的_node指针是否指向同一个节点。operator!返回_node ! it._node表示 “两个迭代器是否指向不同节点”operator返回_node it._node表示 “两个迭代器是否指向同一个节点”。其中operator!后面加了const是为了保证 “调用这个函数时不会修改当前迭代器的状态”更符合 const 正确性的规范。2.4operator-重载这个运算符是为了应对数据是结构体的场景当存储的数据是结构体时仅用operator*解引用后没办法直接访问结构体的成员得通过.来访问而重载-后就能直接通过迭代器用-访问结构体成员用起来更便捷。但这里又有个问题我们通过operator-拿到的是_node节点的指针而不是节点里存储的结构体成员 —— 这显然不是我们想要的访问效果。我们看这段代码的实际效果当用迭代器it访问结构体A的成员时理论上应该写it--_a2因为operator-()返回的是A*指针需要再用-访问成员但编译器做了特殊处理 —— 自动省略了一个-所以直接写it-_a1/it-_a2就能正常访问。这背后的逻辑是operator*()返回的是A引用所以可以用(*it)._a1访问而operator-()返回的是A*指针为了让迭代器的用法和原生指针一致原生指针可以直接用-访问成员C 编译器对迭代器的operator-做了 “语法糖” 优化允许省略一次-让it-_a2等价于(it.operator-())-_a2用起来更自然简洁。T*operator-(){return(_node-_val);//c会多处理一次所以返回地址即可}2.5begin、end// 普通正向迭代器指向第一个有效元素iteratorbegin(){returniterator(_head-_next);}// 普通正向迭代器指向尾后位置头节点iteratorend(){returniterator(_head);}三、更高维度的范式编程首先我们知道有const的迭代器那么我们要是再写一个const迭代器的类吗太麻烦了所以 STL 库引入了 3 个参数来解决。// 链表迭代器模板类T元素类型 Ref元素引用类型 Ptr元素指针类型templateclassT,classRef,classPtrok我们看一下为什么会这样那么我们先修改一下之前的代码//迭代器类templateclassT,classRef,classPtrstruct_list_iterator{typedeflist_nodeTNode;// 节点类型别名typedef_list_iteratorT,Ref,Ptrself;// 迭代器自身类型别名简化后续使用_list_iterator(Node*node):_node(node){}selfoperator(){_node_node-_next;return*this;}selfoperator(int){self tmp*this;_node_node-_next;returntmp;}selfoperator--(){_node_node-_prev;return*this;}selfoperator--(int){self tmp*this;_node_node-_prev;returntmp;}Refoperator*(){return_node-_val;}booloperator(constselfit)const{return_nodeit._node;}booloperator!(constselfit)const{return_node!it._node;}Ptroperator-(){return(_node-_val);//c会多处理一次所以返回地址即可}Node*_node;// 指向链表节点的指针};Ptr、Ref模板参数的作用Ptr的作用在此体现区分普通迭代器返回的T*可读写结构体成员和const迭代器返回的const T*只读实现一套模板复用保证const迭代器的安全性。至于为啥要将迭代器重命名为self是因为它的完整类型名太长了用self代替能简化代码书写。四、list增删查改4.1push_backvoidpush_back(constTx){Node*newnodenewNode(x);Node*tail_head-_prev;tail-_nextnewnode;newnode-_prevtail;_head-_prevnewnode;newnode-_next_head;_size;}先找到链表的尾节点tail通过头节点_head的_prev拿到再创建新节点newnode接着把tail的_next指向新节点、新节点的_prev指向tail完成新节点和原尾节点的连接最后让新节点的_next指向头节点、头节点的_prev指向新节点维持链表的循环结构 —— 这样新节点就成了新的尾节点尾插完成。4.2insert// pos位置之前插入iteratorinsert(iterator pos,constTx){Node*curpos._node;//迭代器指向的节点Node*prevcur-_prev;Node*newnodenewNode(x);prev-_nextnewnode;newnode-_nextcur;cur-_prevnewnode;newnode-_prevprev;_size;returniterator(newnode);//返回新节点的迭代器}先从迭代器pos里拿到它指向的节点cur再找到cur的前驱节点prev同时创建新节点newnode把prev的_next指向新节点、新节点的_next指向cur再让cur的_prev指向新节点、新节点的_prev指向prev—— 这样就把新节点 “夹” 在了prev和cur之间最后更新链表长度_size并返回新节点对应的迭代器方便后续操作。4.3push_frontvoidpush_front(constTx){insert(begin(),x);}直接复用insert在begin()头节点迭代器前插入元素x既简化代码又保证逻辑一致。4.4pop_backvoidpop_back(){// 断言确保链表不为空避免删除空链表的元素assert(_head-_next!_head);// 找到要删除的尾节点Node*del_head-_prev;// 找到尾节点的前驱节点新的尾节点Node*taildel-_prev;// 建立新尾节点和头节点的双向连接断开原尾节点tail-_next_head;_head-_prevtail;// 释放原尾节点的内存deletedel;// 更新链表元素个数_size--;}先断言链表非空找到尾节点和它的前驱节点重新建立前驱节点与头节点的循环连接释放原尾节点内存最后更新链表长度。4.5erase// pos位置删除iteratorerase(iterator pos){// 断言确保删除的不是尾后迭代器无效节点assert(pos!end());// 提取待删除节点curNode*curpos._node;// 找到cur的前驱和后继节点Node*prevcur-_prev;Node*nextcur-_next;// 建立前驱和后继的双向连接跳过待删除节点prev-_nextnext;next-_prevprev;// 释放待删除节点内存deletecur;// 更新链表元素个数--_size;// 返回后继节点迭代器避免迭代器失效returniterator(next);}先断言避免删除无效节点找到待删节点的前后节点并重新建立连接释放待删节点内存更新链表长度后返回后继节点迭代器防止失效。4.6pop_frontvoidpop_front(){// 复用erase函数删除头节点begin()对应的迭代器erase(begin());}直接复用erase函数删除begin()对应的头节点既简化代码又保证逻辑一致。4.7clear// 清空链表中所有有效元素保留头节点voidclear(){iterator itbegin();// 获取链表起始迭代器while(it!end())// 遍历所有有效元素{iterase(it);// 删除当前元素erase返回下一个元素的迭代器}_size0;// 重置有效元素个数为0}4.8emptyboolempty()const{return_size0;}
一、list的模拟实现1.1list的节点结构、容器结构、迭代器结构我们需要自己写一个list首先在list类外还需要两个类一个节点一个迭代器。节点类和迭代器类为list类服务。ps说实话list部分真的还挺难写的我自己给绕晕了好几次主要在多了结构和迭代器都比较难但是跨过这两个就会好很多了我们先从小的开始。节点结构//节点类templateclassTstructlist_node{typedeflist_nodeTNode;// 节点类型别名list_node();~list_node();T _val;// 节点数据域Node*_prev;// 后继节点指针Node*_next;// 前驱节点指针};这个节点可以存放任何类型的数据所以它得是一个模板。list_node有三部分构成数据指向下一个节点的指针指向上一个节点的指针。迭代器结构因为我们在上一篇文章中说道他的、--、*不再是原生指针了所以我们要对他进行封装。这段迭代器结构目前还不完整后面的讲解会逐步完善链表迭代器的实现//迭代器类templateclassTstruct_list_iterator{typedeflist_nodeTNode;// 节点类型别名_list_iterator();~_list_iterator();Node*_node;// 指向链表节点的指针};容器结构//链表类templateclassTclasslist{typedeflist_nodeTNode;// 节点类型别名public:list();~list();private:Node*_head;size_t _size;};链表的迭代器为啥不能直接用原生指针因为链表的原生指针比如list_node*只能访问节点本身而迭代器需要模拟 “像普通指针一样解引用取数据、/--遍历” 的行为 —— 链表节点里存的是_val实际数据原生指针解引用得到的是整个节点不是数据且链表的 “下一个元素” 需要通过_next指针跳转原生指针的是地址 1不符合链表的节点连接逻辑所以得封装迭代器类来重载*、等运算符不能直接用原生指针。迭代器结构为啥用struct迭代器结构体用struct是因为迭代器只是遍历容器的工具 —— 哪怕直接定义迭代器对象没有对应的容器支撑也没法实际访问有效数据所以不用刻意封装成私有用struct让成员比如这里的_node指针直接暴露能简化后续迭代器功能的实现。迭代器为啥不能写析构函数不能为迭代器编写析构函数 —— 因为节点的内存是由容器管理的迭代器只是 “借用节点指针来访问元素”本身并不持有节点的所有权。若在迭代器析构时释放节点会导致容器内的节点被非法销毁进而引发内存错误。1.2list的默认函数list构造函数//list构造函数list(){_headnewNode;_head-_prev_head;// 头节点前驱指向自身循环链表_head-_next_head;// 头节点后继指向自身循环链表_size0;// 链表初始长度为0}list拷贝构造函数// list拷贝构造函数list(constlistTlt){_headnewNode;//先创建一个头结点_head-_prev_head;// 头节点前驱指向自身循环链表_head-_next_head;// 头节点后继指向自身循环链表_size0;// 链表初始长度为0//遍历lt的每个元素逐个尾插到新链表中,这个要支持迭代器for(autoe:lt){push_back(e);}}push_back这个函数我们后面实现。list赋值运算符重载//list的交换函数voidswap(listTlt){std::swap(_head,lt._head);std::swap(_size,lt._size);}//list赋值运算符重载//已经有了实体// l1l2listToperator(listTlt)// 传值调用自动拷贝出临时对象lt{swap(lt);// 交换当前对象与临时对象的资源return*this;// 返回当前对象临时对象会自动销毁旧资源}list析构函数// 清空链表中所有有效元素保留头节点voidclear(){iterator itbegin();// 获取链表起始迭代器while(it!end())// 遍历所有有效元素{iterase(it);// 删除当前元素erase返回下一个元素的迭代器}_size0;// 重置有效元素个数为0}// 链表析构函数释放所有资源~list(){clear();// 先清空所有有效元素delete_head;// 释放头节点的堆内存_headnullptr;// 将头节点指针置空避免野指针}二、迭代器结构重点//迭代器结构体templateclassTstruct_list_iterator{typedeflist_nodeTNode;// 节点类型别名typedef_list_iteratorTiterator;//迭代器类型别名// 构造用节点指针初始化迭代器_list_iterator(Node*node):_node(node){}Node*_node;// 指向链表节点的指针};迭代器本身就是一个封装指针所以不需要拷贝构造浅拷贝够用我们已经写出来的接下来我们要实现让他可以像指针一样使用。2.1operator*原本的指针解引用返回具体内置类型值但是这里的链表节点时一个结构体所以必须重载解引用。如下代码我们让解引用返回的是结构体内部的数据。Toperator*(){return_node-_val;}2.2operator和--分别包装了向前找一个节点返回和向后找一个节点返回的逻辑。iteratoroperator(){_node_node-_next;return*this;}iteratoroperator(int){iterator tmp*this;_node_node-_next;returntmp;}iteratoroperator--(){_node_node-_prev;return*this;}iteratoroperator--(int){iterator tmp*this;_node_node-_prev;returntmp;}前置和--的逻辑很相似都是直接修改当前迭代器的节点指针_node然后返回自身的引用。比如前置是把_node指向 “下一个节点”前置--是指向 “前一个节点”返回自身引用的好处是支持链式操作比如(it)、--(--it)而且没有临时对象的开销效率更高。后置和--的核心是 “先返回原状态再移动”函数参数里的int是个占位符没有实际意义只是用来区分前置 / 后置实现时会先创建一个临时迭代器tmp保存当前状态然后移动_node到下一个 / 前一个节点最后返回这个临时迭代器。这样外部使用时it拿到的是 “移动前的迭代器”而it本身已经完成了移动 —— 不过因为会创建临时对象它的效率比前置版本略低。2.3operator与!相等与不相等的判断依据固定在对于节点的比较。booloperator(constiteratorit)const{return_nodeit._node;}booloperator!(constiteratorit)const{return_node!it._node;}这两个运算符的逻辑很直接判断两个迭代器的_node指针是否指向同一个节点。operator!返回_node ! it._node表示 “两个迭代器是否指向不同节点”operator返回_node it._node表示 “两个迭代器是否指向同一个节点”。其中operator!后面加了const是为了保证 “调用这个函数时不会修改当前迭代器的状态”更符合 const 正确性的规范。2.4operator-重载这个运算符是为了应对数据是结构体的场景当存储的数据是结构体时仅用operator*解引用后没办法直接访问结构体的成员得通过.来访问而重载-后就能直接通过迭代器用-访问结构体成员用起来更便捷。但这里又有个问题我们通过operator-拿到的是_node节点的指针而不是节点里存储的结构体成员 —— 这显然不是我们想要的访问效果。我们看这段代码的实际效果当用迭代器it访问结构体A的成员时理论上应该写it--_a2因为operator-()返回的是A*指针需要再用-访问成员但编译器做了特殊处理 —— 自动省略了一个-所以直接写it-_a1/it-_a2就能正常访问。这背后的逻辑是operator*()返回的是A引用所以可以用(*it)._a1访问而operator-()返回的是A*指针为了让迭代器的用法和原生指针一致原生指针可以直接用-访问成员C 编译器对迭代器的operator-做了 “语法糖” 优化允许省略一次-让it-_a2等价于(it.operator-())-_a2用起来更自然简洁。T*operator-(){return(_node-_val);//c会多处理一次所以返回地址即可}2.5begin、end// 普通正向迭代器指向第一个有效元素iteratorbegin(){returniterator(_head-_next);}// 普通正向迭代器指向尾后位置头节点iteratorend(){returniterator(_head);}三、更高维度的范式编程首先我们知道有const的迭代器那么我们要是再写一个const迭代器的类吗太麻烦了所以 STL 库引入了 3 个参数来解决。// 链表迭代器模板类T元素类型 Ref元素引用类型 Ptr元素指针类型templateclassT,classRef,classPtrok我们看一下为什么会这样那么我们先修改一下之前的代码//迭代器类templateclassT,classRef,classPtrstruct_list_iterator{typedeflist_nodeTNode;// 节点类型别名typedef_list_iteratorT,Ref,Ptrself;// 迭代器自身类型别名简化后续使用_list_iterator(Node*node):_node(node){}selfoperator(){_node_node-_next;return*this;}selfoperator(int){self tmp*this;_node_node-_next;returntmp;}selfoperator--(){_node_node-_prev;return*this;}selfoperator--(int){self tmp*this;_node_node-_prev;returntmp;}Refoperator*(){return_node-_val;}booloperator(constselfit)const{return_nodeit._node;}booloperator!(constselfit)const{return_node!it._node;}Ptroperator-(){return(_node-_val);//c会多处理一次所以返回地址即可}Node*_node;// 指向链表节点的指针};Ptr、Ref模板参数的作用Ptr的作用在此体现区分普通迭代器返回的T*可读写结构体成员和const迭代器返回的const T*只读实现一套模板复用保证const迭代器的安全性。至于为啥要将迭代器重命名为self是因为它的完整类型名太长了用self代替能简化代码书写。四、list增删查改4.1push_backvoidpush_back(constTx){Node*newnodenewNode(x);Node*tail_head-_prev;tail-_nextnewnode;newnode-_prevtail;_head-_prevnewnode;newnode-_next_head;_size;}先找到链表的尾节点tail通过头节点_head的_prev拿到再创建新节点newnode接着把tail的_next指向新节点、新节点的_prev指向tail完成新节点和原尾节点的连接最后让新节点的_next指向头节点、头节点的_prev指向新节点维持链表的循环结构 —— 这样新节点就成了新的尾节点尾插完成。4.2insert// pos位置之前插入iteratorinsert(iterator pos,constTx){Node*curpos._node;//迭代器指向的节点Node*prevcur-_prev;Node*newnodenewNode(x);prev-_nextnewnode;newnode-_nextcur;cur-_prevnewnode;newnode-_prevprev;_size;returniterator(newnode);//返回新节点的迭代器}先从迭代器pos里拿到它指向的节点cur再找到cur的前驱节点prev同时创建新节点newnode把prev的_next指向新节点、新节点的_next指向cur再让cur的_prev指向新节点、新节点的_prev指向prev—— 这样就把新节点 “夹” 在了prev和cur之间最后更新链表长度_size并返回新节点对应的迭代器方便后续操作。4.3push_frontvoidpush_front(constTx){insert(begin(),x);}直接复用insert在begin()头节点迭代器前插入元素x既简化代码又保证逻辑一致。4.4pop_backvoidpop_back(){// 断言确保链表不为空避免删除空链表的元素assert(_head-_next!_head);// 找到要删除的尾节点Node*del_head-_prev;// 找到尾节点的前驱节点新的尾节点Node*taildel-_prev;// 建立新尾节点和头节点的双向连接断开原尾节点tail-_next_head;_head-_prevtail;// 释放原尾节点的内存deletedel;// 更新链表元素个数_size--;}先断言链表非空找到尾节点和它的前驱节点重新建立前驱节点与头节点的循环连接释放原尾节点内存最后更新链表长度。4.5erase// pos位置删除iteratorerase(iterator pos){// 断言确保删除的不是尾后迭代器无效节点assert(pos!end());// 提取待删除节点curNode*curpos._node;// 找到cur的前驱和后继节点Node*prevcur-_prev;Node*nextcur-_next;// 建立前驱和后继的双向连接跳过待删除节点prev-_nextnext;next-_prevprev;// 释放待删除节点内存deletecur;// 更新链表元素个数--_size;// 返回后继节点迭代器避免迭代器失效returniterator(next);}先断言避免删除无效节点找到待删节点的前后节点并重新建立连接释放待删节点内存更新链表长度后返回后继节点迭代器防止失效。4.6pop_frontvoidpop_front(){// 复用erase函数删除头节点begin()对应的迭代器erase(begin());}直接复用erase函数删除begin()对应的头节点既简化代码又保证逻辑一致。4.7clear// 清空链表中所有有效元素保留头节点voidclear(){iterator itbegin();// 获取链表起始迭代器while(it!end())// 遍历所有有效元素{iterase(it);// 删除当前元素erase返回下一个元素的迭代器}_size0;// 重置有效元素个数为0}4.8emptyboolempty()const{return_size0;}
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
