【c++】STL-容器list的使用

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

关于list：

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

一、list的构造

在这里插入图片描述

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

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

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

1. 编译器的特殊处理：list的结构是由一个一个的节点组成的，但在监视窗口里，它却跟物理空间连续的数组一样显示数据而非一个一个节点，这是因为编译器的特殊处理。它的底层并不是这样。

在这里插入图片描述

二、迭代器分类

我们能够通过函数原型观察到，迭代器也是有分类的,那么它有哪些类型呢？

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

1. 迭代器可以根据功能分为**输入（只读）(Input)、输出（只写）(Output)、单向(Forward)，双向(Bidirectional)和随机(Random)**五类迭代器，且它们之间存在一定的包含关系。
2. 单向类迭代器**支持++操作，双向类迭代器支持++与–操作，随机类迭代器支持++、–、+与-**操作。vector的迭代器是随机迭代器，list的迭代器是双向迭代器。
3. 可以认为单向(Forward)迭代器是特殊的只读(Input)迭代器，双向(Bidirectional)迭代器是特殊的单向(Forward)迭代器，随机迭代器(Random)是特殊的双向(Bidirectional)迭代器。

在这里插入图片描述

1. 按照上图，若一个函数要求的是Input迭代器，那么Input后面被包含的迭代器也符合要求；依此类推，要求Forward迭代器的，Bidirectional和Random迭代器都符合要求，要求Random迭代器的，只有Random迭代器符合要求。

三、Operations成员函数

在这里插入图片描述

3.1 sort（了解）

由于算法库里的sort要求Random迭代器，list 和 vector类型都无法使用，所以list和 vector 里有专门实现的它的sort函数。

在这里插入图片描述

在这里插入图片描述

1. 在release版本下，list的sort运行效率比vector的sort要低很多，一般不推荐使用前者，尤其是数据量大的时候。
2. 推荐先将list内的数据拷贝到vector里面，然后用vector里的sort排完序之后再拷贝回去，比使用list的sort要快。 可以用下面两段代码来验证：

srand(time(0));
const int N = 100000;

list<int> lt1;
vector<int> v;

for (int i = 0; i < N; ++i)
{
	auto e = rand() + i;//由于函数特性，rand函数只能生成3万多个随机数，而我们需要10万个
	lt1.push_back(e);
	v.push_back(e);
}

int begin1 = clock();
// 排序
sort(v.begin(), v.end());
int end1 = clock();

int begin2 = clock();
lt1.sort();
int end2 = clock();

printf("vector sort:%d\n", end1 - begin1);
printf("list sort:%d\n", end2 - begin2);

在这里插入图片描述

srand(time(0));
const int N = 1000000;

list<int> lt1;
list<int> lt2;

for (int i = 0; i < N; ++i)
{
	auto e = rand() + i;
	lt1.push_back(e);
	lt2.push_back(e);
}

int begin1 = clock();
// 拷贝vector
vector<int> v(lt2.begin(), lt2.end());
// 排序
sort(v.begin(), v.end());

// 拷贝回lt2
lt2.assign(v.begin(), v.end());

int end1 = clock();

int begin2 = clock();
lt1.sort();
int end2 = clock();

printf("list copy vector sort copy list sort:%d\n", end1 - begin1);
printf("list sort:%d\n", end2 - begin2);

在这里插入图片描述

1. 这与cpu高速缓存命中率有关，那么什么是高速缓存命中率？

高速缓存命中率

1. cpu访问内存：（cpu太快，它会先加载到三级缓存里面）

1. 数据在不在缓存，在缓存就叫命中，不在就叫不命中. 2. 不在缓存，先加载到缓存，再访问。

1. cpu一次不是只读取一个字节,而是读取好些个字节,具体多少跟硬件的设计有关系。

在这里插入图片描述

1. 如图：由于结构的差异，对于数组（vector这种），cpu只需要加载一次缓存，后面的数据就都命中了（加载到缓存）；但对于链表（list这种），cpu虽然也会加载一长段连续的内存，但之后的节点大概率不在这段内存里，对于之后的数据都是不命中，都需要cpu重新一次次的加载到缓存里。所以说，数组的高速缓冲命中率高，访问效率高，链表则低。

3.2 其他的一些函数需要注意的点

1. merge(合并）：使用的时候必须得保证有序。
2. unique(去重）：相同的只留下一个，前提也是要先排序。
3. remove(删除）：会删除所有的给定值，不要求有序。
4. splice（接合）：可以剪切部分节点粘贴到指定位置。
5. 因为用的不多，可以先了解一下，需要用的时候去查就行。

今天的分享就到此结束啦,如果对读者朋友们有所帮助的话,可否留下宝贵的三连呢~~ 如果可以, 那就让我们共同努力, 一起走下去!