hello~ 很高兴见到大家! 这次带来的是C中关于list容器这部分的一些知识点,如果对你有所帮助的话,可否留下你的三连呢?个 人 主 页: 默|笙文章目录一、list的构造二、迭代器分类三、Operations成员函数3.1 sort了解高速缓存命中率3.2 其他的一些函数需要注意的点关于list在c的STL模板库里list通常被实现为一个带哨兵节点头节点的循环双向链表。了解list使用 list 模板需要包含头文件list。通过list体会iterator迭代器遍历的优势:它是通用的相似的遍历容器的方式并且其封装了容器的底层屏蔽了容器结构的差异和底层实现细节不会因容器的不同或者差异而更改。—iterator迭代器的封装特性迭代器的复用特性实现算法时用迭代器函数模板方式实现跟底层容器解耦。例如在实现reverse逆置函数时我们不用特意为了一个容器去根据它的结构专门为它设计一个算法而是设计一个通用的算法所有类型都可以使用。一、list的构造接下来我会讲解除了move构造之外的构造的一些小知识点。迭代器区间构造迭代器区间构造它任意类型的类型迭代器实现构造就比如vector类型同时除支持迭代器之外它也支持通过指针来进行构造可以认为指针是一种特殊的迭代器。//一般都会有这样几个构造listintlt1;//默认构造defaultlistintlt2(10,1);//n个val填充构造-tillvectorintv1{1,2,3,4,5};listintlt3(v1.begin(),v1.end());//迭代器区间构造-range可以传递vector类型指针listintlt4{1,2,3,4,5};//初始化列表构造-initializerlistintlt5lt4;//拷贝构造-copy//迭代器区间构造可以传数组的指针inta[]{1,2,11,3,4,5,40};listintlt6(a,a4);//注意格式编译器的特殊处理list的结构是由一个一个的节点组成的但在监视窗口里它却跟物理空间连续的数组一样显示数据而非一个一个节点这是因为编译器的特殊处理。它的底层并不是这样。二、迭代器分类我们能够通过函数原型观察到迭代器也是有分类的,那么它有哪些类型呢迭代器可以根据功能分为**输入只读(Input)、输出只写(Output)、单向(Forward)双向(Bidirectional)和随机(Random)**五类迭代器且它们之间存在一定的包含关系。单向类迭代器**支持操作双向类迭代器支持与–操作随机类迭代器支持、–、与-**操作。vector的迭代器是随机迭代器list的迭代器是双向迭代器。可以认为单向(Forward)迭代器是特殊的只读(Input)迭代器双向(Bidirectional)迭代器是特殊的单向(Forward)迭代器随机迭代器(Random)是特殊的双向(Bidirectional)迭代器。按照上图若一个函数要求的是Input迭代器那么Input后面被包含的迭代器也符合要求依此类推要求Forward迭代器的Bidirectional和Random迭代器都符合要求要求Random迭代器的只有Random迭代器符合要求。三、Operations成员函数3.1 sort了解由于算法库里的sort要求Random迭代器list 无法使用所以 list 里有专门实现的它的sort函数。在release版本下list的sort运行效率比vector的sort要低很多一般不推荐使用前者尤其是数据量大的时候。推荐先将list内的数据拷贝到vector里面然后用vector里的sort排完序之后再拷贝回去比使用list的sort要快。可以用下面两段代码来验证srand(time(0));constintN100000;listintlt1;vectorintv;for(inti0;iN;i){autoerand()i;//由于函数特性rand函数只能生成3万多个随机数而我们需要10万个lt1.push_back(e);v.push_back(e);}intbegin1clock();// 排序sort(v.begin(),v.end());intend1clock();intbegin2clock();lt1.sort();intend2clock();printf(vector sort:%d\n,end1-begin1);printf(list sort:%d\n,end2-begin2);srand(time(0));constintN1000000;listintlt1;listintlt2;for(inti0;iN;i){autoerand()i;lt1.push_back(e);lt2.push_back(e);}intbegin1clock();// 拷贝vectorvectorintv(lt2.begin(),lt2.end());// 排序sort(v.begin(),v.end());// 拷贝回lt2lt2.assign(v.begin(),v.end());intend1clock();intbegin2clock();lt1.sort();intend2clock();printf(list copy vector sort copy list sort:%d\n,end1-begin1);printf(list sort:%d\n,end2-begin2);这与cpu高速缓存命中率有关那么什么是高速缓存命中率高速缓存命中率cpu访问内存cpu太快它会先加载到三级缓存里面1. 数据在不在缓存在缓存就叫命中不在就叫不命中.2. 不在缓存先加载到缓存再访问。cpu一次不是只读取一个字节,而是读取好些个字节,具体多少跟硬件的设计有关系。如图由于结构的差异对于数组vector这种cpu只需要加载一次缓存后面的数据就都命中了加载到缓存但对于链表list这种cpu虽然也会加载一长段连续的内存但之后的节点大概率不在这段内存里对于之后的数据都是不命中都需要cpu重新一次次的加载到缓存里。所以说数组的高速缓冲命中率高访问效率高链表则低。3.2 其他的一些函数需要注意的点merge(合并使用的时候必须得保证有序。unique(去重相同的只留下一个前提也是要先排序。remove(删除会删除所有的给定值不要求有序。splice接合可以剪切部分节点粘贴到指定位置。因为用的不多可以先了解一下需要用的时候去查就行。今天的分享就到此结束啦,如果对读者朋友们有所帮助的话,可否留下宝贵的三连呢~~如果可以, 那就让我们共同努力, 一起走下去!