C STLlist 容器详解与模拟实现——从双向链表到反向迭代器文章目录C STLlist 容器详解与模拟实现——从双向链表到反向迭代器1 list 的基本概念2 list 的构造2.1 构造空 list2.2 构造 n 个相同元素2.3 拷贝构造2.4 使用迭代器区间构造3 list 的迭代器4 begin 和 end4.1 begin4.2 end5 list 的反向迭代器5.1 rbegin5.2 rend6 正向迭代器和反向迭代器7 list 的容量相关接口7.1 empty7.2 size8 list 的元素访问8.1 front8.2 back9 list 的插入和删除10 push_front11 pop_front12 push_back13 pop_back14 insert15 erase16 swap17 clear18 list 的迭代器失效19 list 插入时的迭代器失效20 list 删除时的迭代器失效21 erase 后为什么不能继续使用原迭代器22 erase 的正确使用方式23 list 的模拟实现24 为什么 list 使用双向链表25 带头结点的双向循环链表26 list 反向迭代器的实现思路27 typename 的作用28 ReverseListIterator 的构造29 反向迭代器的解引用30 反向迭代器的 operator-31 反向迭代器的 32 反向迭代器的后置 33 反向迭代器的 --34 list 和 vector 的底层结构对比vectorlist35 vector 和 list 的随机访问36 vector 和 list 的插入删除37 vector 和 list 的空间利用率38 vector 和 list 的迭代器39 vector 和 list 的迭代器失效40 vector 和 list 的使用场景41 vector 和 list 核心区别42 list 使用时最需要掌握的几个点1 list 的基本概念list是 C STL 中提供的双向链表容器它的底层结构可以理解为带头结点的双向循环链表与vector最大的区别在于底层结构不同vector ↓ 动态顺序表 ↓ 一段连续的内存空间 list ↓ 带头结点的双向循环链表 ↓ 每个节点单独开辟空间因此两者在访问元素、插入删除、迭代器以及空间利用率等方面都有明显区别2 list 的构造使用list之前需要包含头文件#includelist基本定义方式std::listintlt;也可以使用using namespace std#includeiostream#includelistusingnamespacestd;intmain(){listintlt;return0;}2.1 构造空 listlist();创建一个空的list例如listintlt;此时lt ↓ 空链表2.2 构造 n 个相同元素list(size_type n,constvalue_typevalvalue_type());作用是构造一个包含n个元素的list每个元素的值都是val例如listintlt(5,10);得到10 10 10 10 10如果只写listintlt(5);对于int类型来说相当于创建 5 个值为0的元素2.3 拷贝构造list(constlistx);用于使用一个已有的list初始化另一个listlistintlt1;lt1.push_back(10);lt1.push_back(20);lt1.push_back(30);listintlt2(lt1);此时lt1 10 20 30 lt2 10 20 30两个list是不同的对象2.4 使用迭代器区间构造list(InputIterator first,InputIterator last);使用[first, last)区间中的元素构造list注意区间是[first, last)包含first不包含last例如intarray[]{1,2,3,4,5};listintlt(array,array5);结果1 2 3 4 53 list 的迭代器迭代器是使用list时非常重要的内容可以暂时把迭代器理解成一个类似指针的对象它指向list中的某个节点例如listintlt;lt.push_back(10);lt.push_back(20);lt.push_back(30);listint::iterator itlt.begin();此时it ↓ 10 - 20 - 30通过*it可以访问当前迭代器指向节点中的数据4 begin 和 end4.1 beginlt.begin()返回指向第一个元素的迭代器例如listintlt;lt.push_back(10);lt.push_back(20);lt.push_back(30);listint::iterator itlt.begin();cout*itendl;输出104.2 endlt.end()返回最后一个元素的下一个位置注意end()并不指向最后一个有效元素例如10 - 20 - 30 - end所以遍历一般写成listint::iterator itlt.begin();while(it!lt.end()){cout*it ;it;}输出10 20 305 list 的反向迭代器除了正向迭代器之外list还提供反向迭代器主要使用rbegin()rend()5.1 rbeginlt.rbegin()返回指向最后一个有效元素的反向迭代器5.2 rendlt.rend()表示反向遍历结束的位置例如正向 begin ↓ 10 - 20 - 30 ↑ end 反向 rbegin ↓ 10 - 20 - 30 ↑ rend因此可以使用listint::reverse_iterator itlt.rbegin();while(it!lt.rend()){cout*it ;it;}输出30 20 106 正向迭代器和反向迭代器这是list迭代器中非常重要的一点正向迭代器it;表示向后移动10 → 20 → 30反向迭代器it;表示向前移动30 → 20 → 10也就是说正向迭代器 ↓ 向后移动 反向迭代器 ↓ 向前移动核心关系反向迭代器的 正向迭代器的 -- 反向迭代器的 -- 正向迭代器的 7 list 的容量相关接口7.1 emptylt.empty()用于判断list是否为空返回值为boolif(lt.empty()){coutlist为空endl;}7.2 sizelt.size()返回list中有效节点的数量例如listintlt;lt.push_back(10);lt.push_back(20);lt.push_back(30);coutlt.size()endl;结果38 list 的元素访问8.1 frontlt.front()返回第一个节点中数据的引用例如listintlt;lt.push_back(10);lt.push_back(20);lt.push_back(30);coutlt.front()endl;输出10由于返回的是引用所以可以直接修改第一个元素lt.front()100;此时100 20 308.2 backlt.back()返回最后一个节点中数据的引用例如coutlt.back()endl;输出最后一个元素也可以修改lt.back()300;9 list 的插入和删除list最重要的特点之一就是插入和删除效率较高常用接口包括push_front pop_front push_back pop_back insert erase swap clear10 push_frontpush_front(val)在list的头部插入元素例如listintlt;lt.push_front(10);lt.push_front(20);lt.push_front(30);最终结果30 20 1011 pop_frontpop_front()删除list的第一个元素例如listintlt;lt.push_back(10);lt.push_back(20);lt.push_back(30);lt.pop_front();结果20 3012 push_backpush_back(val)在list尾部插入元素例如listintlt;lt.push_back(10);lt.push_back(20);lt.push_back(30);结果10 20 3013 pop_backpop_back()删除最后一个元素例如listintlt;lt.push_back(10);lt.push_back(20);lt.push_back(30);lt.pop_back();结果10 2014 insertinsert(position,val)在position位置插入元素例如listintlt;lt.push_back(10);lt.push_back(20);lt.push_back(30);autoposlt.begin();pos;lt.insert(pos,100);原来10 20 30插入后10 100 20 30这里的关键是pos表示插入位置15 eraseerase(position)删除position位置的节点例如listintlt;lt.push_back(10);lt.push_back(20);lt.push_back(30);autoposlt.begin();pos;lt.erase(pos);原来10 20 30删除后10 3016 swaplt1.swap(lt2);用于交换两个list中的元素例如listintlt1;lt1.push_back(10);lt1.push_back(20);listintlt2;lt2.push_back(30);lt2.push_back(40);lt1.swap(lt2);交换后lt1 30 40 lt2 10 2017 clearlt.clear();清空list中的有效元素例如listintlt;lt.push_back(10);lt.push_back(20);lt.push_back(30);lt.clear();执行之后list为空18 list 的迭代器失效迭代器可以暂时理解成类似指针的东西因此当迭代器所指向的节点被删除以后这个迭代器就不能继续使用这就是迭代器失效list的底层结构是带头结点的双向循环链表因此它和vector的迭代器失效规则不同19 list 插入时的迭代器失效对于list插入节点不会导致原来的迭代器失效因为插入节点不会让其他节点的位置发生整体变化例如10 - 20 - 30在20前面插入10010 - 100 - 20 - 30原来的节点仍然存在因此指向原有节点的迭代器仍然有效20 list 删除时的迭代器失效删除节点时只有指向被删除节点的迭代器失效其他节点的迭代器不会受到影响例如10 - 20 - 30如果删除2010 - 30那么指向 20 的迭代器 ↓ 失效 指向 10 的迭代器 ↓ 仍然有效 指向 30 的迭代器 ↓ 仍然有效21 erase 后为什么不能继续使用原迭代器错误写法voidTestListIterator1(){intarray[]{1,2,3,4,5};listintl(array,array5);autoitl.begin();while(it!l.end()){l.erase(it);it;}}问题在于l.erase(it);执行之后it所指向的节点已经被删除所以it已经失效此时继续it;就属于使用失效迭代器22 erase 的正确使用方式一种写法是利用erase的返回值autoitl.begin();while(it!l.end()){itl.erase(it);}erase删除当前节点后返回被删除节点的下一个位置因此可以直接重新赋值给it另外一种写法是autoitl.begin();while(it!l.end()){l.erase(it);}这里要注意执行顺序it会先保存当前迭代器然后让it指向下一个位置随后使用保存下来的旧迭代器进行删除因此可以避免继续使用已经失效的迭代器23 list 的模拟实现想要自己模拟实现list首先需要理解它的底层结构list的底层可以理解为带头结点的双向循环链表一个节点通常包含templateclassTstructListNode{ListNodeT*_next;ListNodeT*_prev;T _data;};其中_next ↓ 下一个节点 _prev ↓ 上一个节点 _data ↓ 节点中的数据24 为什么 list 使用双向链表单链表节点只有data next而双向链表节点拥有data prev next这样就可以向后走 ↓ next 向前走 ↓ prev因此非常适合实现list的正向和反向迭代器25 带头结点的双向循环链表list的一个重要特点是存在头结点可以抽象成┌──────────────────────┐ ↓ │ head head ↙ ↑ prev next ↓ │ 节点1 ⇄ 节点2 ⇄ 节点3更准确地理解head-_next ↓ 第一个有效节点 head-_prev ↓ 最后一个有效节点当链表为空时head-_next head head-_prev head因此它形成一个循环结构26 list 反向迭代器的实现思路反向迭代器没有必要完全重新实现一套迭代器可以直接利用已经存在的正向迭代器核心思想就是反向迭代器 ↓ 内部包含一个正向迭代器 ↓ 对正向迭代器进行包装例如templateclassIteratorclassReverseListIterator{private:Iterator _it;};这里的Iterator _it;就是内部保存的正向迭代器27 typename 的作用模拟反向迭代器时会出现typedeftypenameIterator::Ref Ref;typedeftypenameIterator::Ptr Ptr;这里的typename非常重要因为Iterator::Ref中的Ref到底是什么编译器在模板实例化之前无法确定它可能是类型也可能是静态成员变量所以需要使用typename明确告诉编译器Iterator::Ref是一个类型28 ReverseListIterator 的构造ReverseListIterator(Iterator it):_it(it){}传入一个正向迭代器然后保存到成员变量_it因此反向迭代器本质上是对正向迭代器的一层封装29 反向迭代器的解引用核心代码Refoperator*(){Iteratortemp(_it);--temp;return*temp;}为什么这里需要先执行--temp;原因是反向迭代器和正向迭代器的当前位置定义存在差异反向迭代器需要通过正向迭代器的前一个位置来得到当前元素所以反向迭代器的 * ↓ 正向迭代器先 -- ↓ 再解引用30 反向迭代器的 operator-Ptroperator-(){return(operator*());}作用是让迭代器支持类似指针的it-成员访问方式31 反向迭代器的 Selfoperator(){--_it;return*this;}注意这里是--_it;而不是_it;因为反向迭代器 正向迭代器 --所以反向遍历时it;实际上会让内部的正向迭代器向前移动32 反向迭代器的后置 Selfoperator(int){Selftemp(*this);--_it;returntemp;}这里的关键是Selftemp(*this);先保存当前迭代器然后--_it;让当前迭代器移动最后returntemp;返回移动之前的状态这就是前置和后置运算符的区别33 反向迭代器的 –前置Selfoperator--(){_it;return*this;}后置Selfoperator--(int){Selftemp(*this);_it;returntemp;}因为反向迭代器 -- 正向迭代器 所以这里使用的是_it34 list 和 vector 的底层结构对比vector动态顺序表 ↓ 连续空间list带头结点的双向循环链表 ↓ 节点动态开辟底层结构的不同直接导致了两者特性的不同35 vector 和 list 的随机访问vector支持随机访问例如vectorintv{10,20,30,40,50};coutv[3]endl;可以直接通过下标访问时间复杂度为O(1)而list不支持随机访问不能使用lt[3]这种方式如果需要访问某个位置的元素需要从节点开始逐个移动因此时间复杂度为O(N)36 vector 和 list 的插入删除vector底层是连续空间如果在中间插入一个元素后面的元素通常需要整体移动例如10 20 30 40在20后面插入100需要调整后面的元素因此任意位置插入和删除的效率通常为O(N)并且插入过程中还有可能发生扩容扩容可能涉及开辟新空间 ↓ 拷贝原有元素 ↓ 释放旧空间因此扩容还会产生额外开销list使用链表结构插入节点时不需要搬移其他节点主要是修改节点之间的链接关系因此任意位置插入和删除的时间复杂度可以达到O(1)这里的前提是已经拿到了对应位置的迭代器如果还需要先遍历到目标位置那么寻找位置本身仍然需要O(N)37 vector 和 list 的空间利用率vector使用连续空间因此空间连续 缓存利用率较高 不容易产生大量内存碎片而list的节点通常是动态开辟的不同节点可能位于不同的内存位置因此容易产生内存碎片 缓存利用率相对较低38 vector 和 list 的迭代器vector的迭代器本质上可以理解为原生态指针因为vector中的元素存储在连续空间所以可以直接通过指针进行访问而list的迭代器需要对节点指针进行封装因为list中的节点并不是连续存储的39 vector 和 list 的迭代器失效vector在插入元素时如果发生扩容原来的空间可能被释放于是原来的迭代器就会失效因此vector插入元素后需要注意迭代器是否仍然有效删除元素时被删除位置以及受到移动影响的位置也需要注意迭代器失效问题list则不同插入节点不会导致其他节点的迭代器失效删除节点时只有指向被删除节点的迭代器失效其他节点的迭代器仍然有效40 vector 和 list 的使用场景如果程序更加关注高效存储 随机访问并且不太关注中间位置的插入和删除通常会使用vector如果程序存在大量的插入 删除并且不关注随机访问可以考虑list41 vector 和 list 核心区别对比方面vectorlist底层结构动态顺序表带头结点的双向循环链表存储方式连续空间节点动态开辟随机访问支持不支持随机访问复杂度O(1)O(N)任意位置插入删除通常 O(N)已知位置迭代器时 O(1)是否需要搬移元素可能需要不需要扩容可能发生不需要整体扩容缓存利用率较高较低内存碎片相对较少相对较多迭代器可理解为原生指针对节点指针进行封装插入导致迭代器失效扩容时需要特别注意不会导致其他节点迭代器失效删除导致迭代器失效需要注意元素移动只有被删除节点对应的迭代器失效42 list 使用时最需要掌握的几个点list ↓ 带头结点的双向循环链表核心接口push_front pop_front push_back pop_back insert erase front back empty size swap clear迭代器begin()end()rbegin()rend()最重要的迭代器失效规则插入 ↓ 不会导致其他节点迭代器失效 删除 ↓ 只有指向被删除节点的迭代器失效反向迭代器的核心思想反向迭代器 ↓ 封装正向迭代器 ↓ 反向迭代器 ↓ 内部正向迭代器 -- 反向迭代器 -- ↓ 内部正向迭代器 vector与list的本质区别vector ↓ 连续空间 ↓ 随机访问快 ↓ 中间插入删除可能需要搬移元素 list ↓ 链式结构 ↓ 不支持随机访问 ↓ 已知节点位置时插入删除方便