目录前言一. 认识list二. list的使用技巧1. 迭代器的分类2. list的迭代器类型3. list::sort的效率陷阱三. list的模拟实现1. list的主体框架2. list迭代器的完整实现2.1 const迭代器2.2 第三个模板参数3. 成员函数的实现修改部分构造函数析构函数前言继上一篇文章讲解的vector之后这篇文章将带大家学习和实现下一个STL的容器——list。通过前文我们知道vector的底层是一个动态顺序表主要是通过数组或者说一块连续的内部空间存储数据。而list则和vector不同list的底层是一个链表一个带头双向循环的链表而因为链表本质是通过一个个物理上不连续的节点组成所以list的实现和vector的实现有很大的不同就拿单个数据存储的方式来说vector存储一个数据是直接开辟空间直接储存而list则需要封装一个节点进行数据间接的存储。本文知识点迭代器的种类list的成员函数sort的效率陷阱list的迭代器的封装通过模板参数控制list的普通迭代器和const迭代器operator-的实现一. 认识listlist参考文档地址上文中我们已经初步认识了list知晓了它的本质/底层就是一个链表这里也可以看看C标准库中给出的list的定义如下图所示。图 1-1文档的说明是“list是一个允许在任意位置以常数时间进行插入和删除操作的顺序容器同时它还支持双向迭代”。从这段说明也可以证明list是一个链表的说法而关于“双向迭代”在后面会讲解这里先知道这个特性即可。list的修改类的成员函数如下图因为list提供的这些函数接口和vector那里的函数接口的效果和使用几乎是一模一样的所以本文就不再重复讲解了。vector文章参考图 1-2二. list的使用技巧1. 迭代器的分类C标准库中对list一句简短的说明中除了描述list的基本特性外还给出了它另外的一个特性“list支持双向迭代”那这里的双向迭代是什么意思要讲清楚list的这个性质得先了解一个新的知识迭代器的分类。在之前我们对迭代器的了解仅仅只是使用它对容器进行遍历和修改容器的数据知道迭代器是一个类似指针的东西但是确不清楚迭代器之间也有自己的分类即不同容器的迭代器的类型可能是不相同的。或许有的人会和我之前一样由于每个容器的迭代器的名称都是iterator所以就理所当然的认为每个容器的迭代器都是一样的统一的种类但是事实就是我错了。迭代器一般被分为3类单向迭代器双向迭代器随机迭代器。分类表格如下迭代器类型支持的操作单向迭代器双向迭代器–随机迭代器–-单向迭代器其实也就是只能往一个方向走的迭代器所以单向迭代器只支持这也就限制了它只能一直向前走直到走到容器的结尾。双向迭代器就是可以往前后两个方向走的迭代器所以它支持和--这两个运算符。随机迭代器权限最高可以通过迭代器-之间的运算访问容器中任意一个位置它同时也支持双向迭代器的功能。为什么要对迭代器分类那说了迭代器的分类之后你是否想过为什么要将迭代器进行分类呢这是由于不同的容器的特性迫使C标准库需要给迭代器进行分类。举个例子如果要访问一个容器的第pos位置的值对于底层是数组的容器可以直接使用起始位置的迭代器 pos就能访问到其访问的逻辑也就是指针的加减而对于底层是链表的容器它还可以使用刚刚的方法访问到第pos位置的值吗不行因为底层为链表的容器和底层为数组的容器访问第pos位置的值的逻辑完全不一样了而如果容器的底层是树的话那差别就更加大了。所以正是因为不同的容器要到达相同的目标所使用的方法和付出的代价不同所以需要给它们的迭代器进行归类也就是需要给迭代器分类。迭代器的分类可以从标准库提供的一些函数接口看出。如图2-12-2所示这里的函数参数的名字都有迭代器种类的提示reverse函数需要传递双向迭代器sort函数需要传递随机迭代器。虽然这两个函数都是模板函数理论上可以传递任意种类的迭代器但是如果传递的迭代器的功能和参数中需要的迭代器的功能匹配不上编译就会不通过。例如reverse函数需要传递双向迭代器才能正常执行函数功能如果此时传递一个红黑树的迭代器单向迭代器编译就会不通过。图 2-1图 2-2⚠注意当函数参数指明需要传递双向迭代器时传递随机迭代器函数也可以正常运行这是因为随机迭代器的功能包含了双向迭代器的功能。随机迭代器和双向迭代器都包含了单向迭代器的功能。2. list的迭代器类型这里回归到上面的问题“list支持双向迭代”这句话是什么意思呢在知道了迭代器的分类之后其实大概也可以猜出这句话要表达的意思了即list迭代器是双向迭代器。C标准库中也对这个结论再次进行了说明如图 2-3所示。图 2-33. list::sort的效率陷阱由图 2-2我们得知C算法库(algorithm)中的sort函数需要传递随机迭代器才可以让函数正常调用而list的迭代器是双向迭代器这也就代表list不能使用算法库中的sort函数进行排序。而为了让list也能使用库函数排序所以C标准库为list封装了一个成员函数sort之后表述为list::sort。这看似标准库为 list 封装了 list::sort 可以让 list 的排序很方便但是 list::sort 在实际的场景中其实并不常用也并不实用而造成这个的原因是因为 list::sort 的效率非常的低我们可以使用下面这段代码对list::sort的性能进行测试代码中分别为vector容器和list容器插入了100万个随机数vector使用std::sort排序list使用list::sort排序通过clock函数记录两个排序在Debug版本下所用的时间如图 2-4所示。srand(time(0));intN1000000;listintlt;vectorintv;for(inti0;iN;i){intxrand()i;lt.push_back(x);v.push_back(x);}intbegin1clock();sort(v.begin(),v.end());intend1clock();intbegin2clock();lt.sort();intend2clock();coutvector: end1-begin1endl;coutlist: end2-begin2endl;注为了方便读者阅读代码中省略了头文件和main函数图 2-4这里看上去时间没有相差很多甚至使用std::sort排序的vector所用的时间还更久这里先不着急下结论我们再测试一下在Release版本下std::sort和list::sort的性能对比如图 2-5所示。这里两个函数的性能之差就体现出来了std::sort比list::sort的效率快了一倍多。那在Debug版本下list::sort的效率也还可以啊为什么就直接定论list::sort效率很低这是因为我们给用户的发行版本是Release版本所以我们在乎的只是在Release版本下程序的效率而list::sort在Release版本下效率很低那对于实际的工程项目来说它就是效率低没有实用性。而如果过于的在乎Debug版本下list::sort的效率那就是本末倒置了。图 2-5总结list::sort在Release版本下的效率很低在实际的场景中尽量不要使用三. list的模拟实现1. list的主体框架在实现list这个STL容器之前得理清楚它得大框架。首先需要明确list的底层是一个带头双向循环链表。那既然是链表就一定离不开节点的结构所以其次就是确定好list节点的结构。最后定义好成员变量和迭代器而对于list来说迭代器的实现可不像vector那样简单因为list的结构是一个个的节点关于list的迭代器的实现在后文重点讲解现在要先搭好大框架。list节点结构list的节点结构的内部和数据结构中实现的带头双向循环链表一样都是一个数据两个指针但是这里需要注意的是因为后续在list类中会频繁对节点进行操作所以将节点结构写成struct。开放节点的成员变量以方便list访问。templateclassTstructlist_node{T data;list_nodeT*prev;list_nodeT*next;list_node(constTvalT()):data(val),next(nullptr),prev(nullptr){}};list成员变量因为list是带头双向循环链表所以只需要有链表的头节点就可以拿到链表任意位置的数据所以list的成员函数只需要一个指向头节点的指针即可。templateclassTclasslist{public:typedeflist_nodeTNode;private:Node*_head;};list普通迭代器的实现到list的迭代器的实现就有问题了因为迭代器的操作需要模拟指针的操作而list不像vector一样可以直接使用指针作为迭代器list是由一个个结构体链表节点组成的只能提供指向一个链表节点的指针。所以如果它想像其它迭代器一样*迭代器就可以拿到数据的值就可以指向下一个数据就需要将指向链表节点的指针封装成一个类作为迭代器的类型。如下代码所示这段代码将链表节点类型的指针Node*封装成一个类作为list的迭代器的类型其中需要说明的地方有3个。因为迭代器必须要Node*类型的变量初始化才能知道它指向哪个位置所以类中只有一个参数为Node*的构造函数使用其它方式初始化迭代器都会报错。类中为了支持和其它容器迭代器一样的操作对*!做了运算符重载使得迭代器的基本遍历功能可以使用。但是因为list是双向迭代器所以它应该还要有后置前置--后置--等运算符重载这里为了方便读者阅读暂时只实现核心的运算符重载。因为后续类中有很多地方会使用__list_iteratorT而如果后面出了变故需要改变类模板的参数就有很多的地方需要修改所以为了避免这种问题直接将__list_iterator起别名为Self。templateclassTstruct__list_iterator{typedeflist_nodeTNode;typedef__list_iteratorTSelf;// 成员变量Node*_node;// 成员函数Self(Node*node):_node(node){}Toperator*(){return_node-data;}Selfoperator(){_node_node-next;return*this;}booloperator!(constSelfit){return_node!it._node;}};list的主体框架将上面实现的list的框架的核心结合起来就实现了list的大框架代码如下namespaceyzx{templateclassTstructlist_node// 节点结构{T data;list_nodeT*prev;list_nodeT*next;// 构造函数list_node(constTvalT()):data(val),next(nullptr),prev(nullptr){}};templateclassTstruct__list_iterator// 迭代器{typedeflist_nodeTNode;typedef__list_iteratorTSelf;// 成员变量Node*_node;// 成员函数Self(Node*node):_node(node){}Toperator*(){return_node-data;}booloperator!(constSelfit){return_node!it._node;}Selfoperator(){_node_node-next;return*this;}};templateclassTclasslist{public:typedeflist_nodeTNode;typedef__list_iteratorTiterator;voidempty_init()// 用于list的空初始化{_headnewNode;_head-prev_head;_head-next_head;}list(){empty_init();}private:Node*_head;};}2. list迭代器的完整实现在完善了list类的大框架之后下一步就是开始精工细作实现list的一些核心的功能这里因为list的迭代器比较特殊且之后的很多成员函数内部都需要复用迭代器来实现和简化代码所以我们先将list的迭代器的所有功能实现完再开始其它成员函数的实现。2.1 const迭代器首先要知道const迭代器的含义不是使用const修饰迭代器本身而是不能通过*迭代器的方式修改容器的数据但是迭代器本身是可以变化的所以可以首先排除下面代码的这种实现方法。typedef__list_iteratorTiterator;typedefconst__list_iteratorTconst_iterator;直接将上面的方法排除之后不难想到既然是*迭代器不能修改那么const迭代器和普通迭代器的关键区分点就应该在operator*上普通迭代器的operator*是返回T那是否const迭代器就是返回const T就可以了呢我们姑且认为这种方法可行但是如果只改变返回值这两个函数却不能构成函数重载而要如果要构成函数重载就需要将返回值为const T的那个运算符重载函数改为const成员函数如下代码所示。Toperator*(){return_node-data;}constToperator*()const{return_node-data;}这段的代码咋一看没啥问题可是如果仔细想想就会发现下面的这个函数只有当迭代器本身被const修饰才会被调用也就是只有const __list_iteratorT才能调用到这第二个函数那么这个运算符重载不就是对上面的错误的方法的补充吗所以这种方案是不可行的。而正确的实现const迭代器的方法也很简单直接为迭代器的类模板增加一个参数即可如下代码所示templateclassT,classRefstruct__list_iterator// 迭代器{typedeflist_nodeTNode;typedef__list_iteratorT,RefSelf;// 成员变量Node*_node;// 成员函数Self(Node*node):_node(node){}Refoperator*(){return_node-data;}};typedef__list_iteratorT,Titerator;// 普通迭代器typedef__list_iteratorT,constTconst_iterator;// const迭代器类模板中直接增加了一个参数Ref而operator*的函数返回值直接就返回Ref的类型这也就代表我们是可以在模板类的实例化时直接控制operator*的返回值的而有了这样的方法就可以通过使用不同的参数实例化这个模板类来区分普通迭代器和const迭代器。2.2 第三个模板参数普通迭代器和const迭代器实现了之后迭代器就还差一个较为特别的东西没有实现即operator-。因为迭代器的操作需要模仿指针的操作所以实现这个运算符重载是很有必要的。operator-operator-的函数的实现很简单就是直接返回数据的地址也可以说返回指向数据data的指针。这里operator-其实可以和operator*做对比operator-是返回数据的地址而operator *是返回数据的引用使用这两种方式都可以访问到迭代器指向位置的数据只是它们的使用方法不同而已。普通迭代器的operator-是直接返回指向数据的指针也就是T*而const迭代器的operator-则不同因为const迭代器不能修改容器内的数据所以需要返回const T*而这个问题又可以和operator*进行类比了。因为operator*函数曾经面临过这种的情况普通迭代器和const迭代器对于一个相同的函数其返回值不同所以operator-的解决方案也使用operator*的解决方案为类模板再增加一个参数也就是第三个模板参数。templateclassT,classRef,classPtrstruct__list_iterator// 迭代器{typedeflist_nodeTNode;typedef__list_iteratorT,Ref,PtrSelf;// 成员变量Node*_node;// 成员函数Self(Node*node):_node(node){}Refoperator*(){return_node-data;}Ptroperator-(){return(_node-data);}};所以最终版本的迭代器的声明如下代码所示typedef__list_iteratorT,T,T*iterator;// 普通迭代器typedef__list_iteratorT,constT,constT*const_iterator;// const迭代器总结其实到这里会发现list迭代器其实并没有很大的难度也就是需要单独的封装一个类而已。而关于普通迭代器和const迭代器只需记住当遇到类中同一个成员函数如果因为普通迭代器和const迭代器的区分使得函数返回值不同就给类模板增加一个参数使得类实例化时就可以为普通迭代器和const迭代器区分。迭代器的成员函数的补充Selfoperator(int){Selftmp(_node);_node_node-next;returntmp;}Selfoperator--(){_node_node-prev;return*this;}Selfoperator--(int){Selftmp(_node);_node_node-prev;returntmp;}booloperator(constSelfit)const{return_nodeit._node;}3. 成员函数的实现list的迭代器实现完之后list的核心点就算讲解完了其它的成员函数的实现相较而言都更简单没有那么多坑点下面实现几个list较为常用的成员函数。修改部分insert这里insert的实现和数据结构带头双向链表的insert的实现基本上就是一样的时间复杂度也是O(1)的。不一样的是这里为了统一迭代器失效这个规定这里insert和erase都有迭代器类型返回值。insert返回的是指向插入位置的迭代器erase返回的是指向删除位置的下一个元素的位置的迭代器。iteratorinsert(iterator pos,constTval){Node*nodepos._node;Node*newnodenewNode(val);// 链接newnode节点newnode-prevnode-prev;newnode-nextnode;node-prev-nextnewnode;node-prevnewnode;// 使用newnode构造一个iterator的临时对象做返回值returnnewnode;}eraseiteratorerase(iterator pos){Node*nodepos._node;node*prevnode-prev;node*nextnode-next;// 解除node节点的链接prev-nextnext;next-prevprev;deletenode;nodenullptr;returnnext;}push_backvoidpush_back(constTval){insert(end(),val);}构造函数list(constinitializer_listTil){empty_init();for(constautoe:il){push_back(e);}}析构函数~list(){autoitbegin();while(it!end()){erase(it);it;}delete_head;_headnullptr;}最后相信你已经可以看出来了实现了insert和erase这两个关键函数后其它的成员函数或多或少都可以直接复用这两个函数而这也是我只实现了一部分成员函数的原因因为其它的成员函数的实现基本上也都是这样直接复用其它成员函数即可。对于想要对list的实现一探究竟的读者我将list的实现的完整的代码放在下面需要的可以自取。list实现的完整代码