【c++】STL-容器list的使用-平芜编程栈

hello~ 很高兴见到大家! 这次带来的是C++中关于list容器这部分的一些知识点,如果对你有所帮助的话,可否留下你的三连呢?
个人主页: 默|笙

文章目录

一、list的构造
二、迭代器分类
三、Operations成员函数
- 3.1 sort（了解）
- - 高速缓存命中率
- 3.2 其他的一些函数需要注意的点

关于list：

在c++的STL模板库里，list通常被实现为一个带哨兵节点（头节点）的循环双向链表。了解list
使用 list 模板需要包含头文件list。
通过list体会iterator迭代器遍历的优势:它是通用的相似的遍历容器的方式，并且其封装了容器的底层，屏蔽了容器结构的差异和底层实现细节，不会因容器的不同或者差异而更改。—iterator迭代器的封装特性
迭代器的复用特性：实现算法时用迭代器函数模板方式实现，跟底层容器解耦。例如：在实现reverse逆置函数时，我们不用特意为了一个容器去根据它的结构专门为它设计一个算法，而是设计一个通用的算法，所有类型都可以使用。

一、list的构造

接下来，我会讲解除了move构造之外的构造的一些小知识点。

迭代器区间构造：迭代器区间构造它任意类型的类型迭代器实现构造，就比如vector类型，同时，除支持迭代器之外，它也支持通过指针来进行构造（可以认为指针是一种特殊的迭代器）。

//一般都会有这样几个构造list<int>lt1;//默认构造=defaultlist<int>lt2(10,1);//n个val填充构造-tillvector<int>v1={1,2,3,4,5};list<int>lt3(v1.begin(),v1.end());//迭代器区间构造-range，可以传递vector类型指针list<int>lt4={1,2,3,4,5};//初始化列表构造-initializerlist<int>lt5=lt4;//拷贝构造-copy//迭代器区间构造可以传数组的指针inta[]={1,2,11,3,4,5,40};list<int>lt6(a,a+4);//注意格式

编译器的特殊处理：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));constintN=100000;list<int>lt1;vector<int>v;for(inti=0;i<N;++i){autoe=rand()+i;//由于函数特性，rand函数只能生成3万多个随机数，而我们需要10万个lt1.push_back(e);v.push_back(e);}intbegin1=clock();// 排序sort(v.begin(),v.end());intend1=clock();intbegin2=clock();lt1.sort();intend2=clock();printf("vector sort:%d\n",end1-begin1);printf("list sort:%d\n",end2-begin2);

srand(time(0));constintN=1000000;list<int>lt1;list<int>lt2;for(inti=0;i<N;++i){autoe=rand()+i;lt1.push_back(e);lt2.push_back(e);}intbegin1=clock();// 拷贝vectorvector<int>v(lt2.begin(),lt2.end());// 排序sort(v.begin(),v.end());// 拷贝回lt2lt2.assign(v.begin(),v.end());intend1=clock();intbegin2=clock();lt1.sort();intend2=clock();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重新一次次的加载到缓存里。所以说，数组的高速缓冲命中率高，访问效率高，链表则低。