C++之list

目录

一、关于list

二、list相关函数

三、相关函数的使用

1、构造函数

2、push_back

3、迭代器

4、push_front

5、pop_back

6、insert

7、erase

关于迭代器失效问题

8、splice

9、remove

10、sort

---

一、关于list

list和string、vector一样，都是容器，都有很强的相似性，再学习完string和vector后，list应该也要能做到精准的使用

list实际是带头双向循环链表

二、list相关函数

三、相关函数的使用

list的使用和string、vector都差不多，下面就简单举一些样例理解即可

1、构造函数

一般都是第一种构造：无参构造

---

2、push_back

push_back尾插

---

3、迭代器

list不同于string、vector，不能用[]遍历，因为没有连续的存储空间，只能用迭代器遍历

如下：

当然支持迭代器就支持范围for，范围for底层就是迭代器

正向迭代器是上面演示的，反向迭代器用法一样：

---

4、push_front

push_front是头插（时间复杂度是O(1)）

---

5、pop_back

pop_back是尾删

原本是4 3 2 1 尾删两次变为了4 3

---

6、insert

insert是插入数据

第一种是pos位置插入val

第二种是pos位置插入n个val

第三种是插入一个迭代器区间

并且insert和erase是与find结合起来使用的

同样和vector一样，find是在algorithm的头文件里包含的，find没有找到就会返回last，所以需要用if语句判断是否找到

即如下图，在2的前面插入20

---

7、erase

erase是删除数据

并且erase没有找到的话也是返回last，所以也要和insert一样，用if语句判断

如下图，删除2

---

关于迭代器失效问题

迭代器是类似指针的一个东西，迭代器失效是指对应的指针已经被销毁，而依然使用被销毁的那段空间

就如上面的insert迭代器就不失效，因为insert插入到2前面的位置，只是在链表中增加一个结点，并不改变他们的关系，并且指针指向的空间并没有被销毁

而erase 2 以后，就发生了迭代器失效的问题了，因为删除2，2结点的位置已经释放了，而指针依旧指向那个位置，如果继续使用，则会发生程序崩溃的问题，如下所示：

在pos位置已经删除2，相当于pos所指向的位置已经释放了，又继续使用pos，改变pos位置的值

这时一执行，就会报以下错误：

这就是典型的迭代器失效问题

---

8、splice

splice是转移数据

我们只列举第一种用法，是将x链表的内容转移到pos位置

有两个链表，一个链表l是1 2 3 4，一个链表r是5 6 7，我们找到l链表的pos位置，即第二个数据的位置，在该位置转移了整个r链表的数据，所以变为了1 5 6 7 2 3 4

---

9、remove

remove是删除值为val的数据

现在有一个链表是1 2 3 4 4 4，我们remove(4)

观察结果可知，remove是删除所有值为4的数

---

10、sort

sort是排序算法

在vector中我们说到过，头文件algorithm中也有sort算法，但为什么list需要自己给一个sort算法呢？

理由很简单，因为algorithm头文件中的sort只支持存储空间连续的容器，因为排序算法中的sort实际是快排，而list存储空间并不是，所以得自己实现

直接l.sort()即可，默认升序

而如果想排降序，则用sort的第二个用法，即传入仿函数函数

升序的仿函数是less，降序是greater，但是用greater时需要包含头文件functional

如下图所示，传入匿名对象即可：