【C++】STL——list的使用

前言

这篇文章我们来继续STL的学习，今天我们要学习的是list，也是STL中容器的一员。

和之前一样，我们还是先学习它的使用，然后再对它进行一个深度剖析和模拟实现。

1. list的介绍及使用

1.1 list的介绍

list的文档介绍

list的底层实现其实就是我们之前数据结构学过的带头双向循环链表：

1.2 list的使用

首先我们来学习一下list的使用：

那经过之前string和vector的学习，我们想要学会list的使用，成本就很低了，所以下面我们就带大家快速的过一下，我们的重点还是在于后面的模拟实现。

我们来看一下它的接口：

首先看一下构造：

也是我们熟悉的这几个，默认构造、n个val的构造、迭代器区间的构造以及拷贝构造。

然后看一下它的迭代器：

也是这几个，相信学到现在大家都很熟悉了。

修改操作：

这里面常用的几个接口我们也都比较熟悉。

但是我们看到list这里只有resize，没有reverse了，因为它是链表嘛，就没有扩容这一说了。

那剩余的比较重要的接口我们后面讲到再说。

但是我们会注意到：

list与string和vector最大的区别是啥？

我们会发现list没有重载[]，也就是说我们要遍历和访问list，就只能用迭代器了（范围for的底层也是迭代器）。

所以说，迭代器才是通用的方式，所有的容器都可以用迭代器，而[]只是针对特定容器的特殊方式。

遍历

那经过之前的学习，相信大家就可以直接上手使用list的迭代器了：

int main()
{
    list<int> l;
    l.push_back(1);
    l.push_back(2);
    l.push_back(3);
    l.push_back(3);
    l.push_back(5);
    for (list<int>::iterator it = l.begin(); it != l.end(); ++it)
        cout << *it << " ";
    cout << endl;

    for (auto e : l)
        cout << e << " ";
    cout << endl;

    for (list<int>::reverse_iterator rit = l.rbegin(); rit != l.rend(); ++rit)
        cout << *rit << " ";
    cout << endl;
    return 0;
}

插入删除数据

然后我们来演示一下insert和erase：

我们发现list也没有提供find，所以我们要获取某个位置的迭代器，可以用算法库里面的find：

也是这几个版本，就不给大家全部演示了。

然后erase：

但是注意list的迭代器是双向迭代器：

只能++或者- -，不能+或-：

Operations

然后来看下这几个接口：

首先这个splice ，用的不多，它可以把一个链表的一部分转移到另一个链表

大家需要的时候自己看一下文档就会用了。

然后remove就是删除指定的元素，find+erase：

后面还有个remove_if，这个涉及仿函数，我们先不用管。

然后unique就是去重：

merge可以合并两个有序链表：

然后呢，list也提供了sort：

就是可以对链表进行排序：

最后reverse就是对链表逆置，就不多说了。

那我们接下来思考一个问题：算法库里面不是已经有sort了吗，为什么链表自己还要提供一个sort？

最主要的原因是算法库里的排序list就用不了。

我们发现报了一堆错怎么，回事呢？

我们看到算法库的sort进行了什么，是不是-啊？

但是我们上面说了，**list的迭代器是双向迭代器，是不能进行-操作的。**当然除此之外里面其它操作list也不行。

迭代器的功能分类

所以呢：

虽然库里的sort是一个函数模板，理论而言这里可以传任意类型的参数，但是其内部对使用的迭代器有要求，参数的名字就暗示了我们要传随机迭代器。

当然不同容器对应的迭代器是什么类型跟它的底层结构有关系。

那我们之前文章也提到过：

迭代器我们之前讲的什么正向反向，const迭代器，这些是使用属性；那还有一个特性属性，迭代器严格来说还可以细分为单向迭代器，双向的和随机的，单向的就是只能++不能- -，双向就是可以++也可以- -，那随机就是除了可以++和- -之外还可以+或- 。

那这个单向，双向，随机大家可以认为是迭代器的功能分类：

1、单向迭代器：只能++，不能- -。例如forward_list和unordered_map；

2、双向迭代器：既能++也能–。例如list；

3、随机访问迭代器：能++ 和- -，也能+和-。例如vector和string。

文档里面在Member types我们能看到当前容器的迭代器类型。

🆗，那除了sort，算法库里的：

我们看到reverse参数名字是不是也有暗示，暗示我们要传双向迭代器。

那你传个单向可以吗？

是不是不行啊，因为双向既要支持++还要支持- -，而单向是不是只能++啊：

但是我们传随机可以吗？

是不是可以啊，因为随机是支持++和- -的。

🆗 ，那相信现在大家就明白为什么list要自己提供一个sort 了。

但是，想告诉大家的是：

list提供了一个sort其实是有点没必要的，大多数情况下我们都不会用list的排序。

为什么，因为效率太慢了。

list 的sort性能测试

现在我这里已经有一段写好的代码用来测试vector和list排序的性能，具体实现大家可以不用关心，看一下结果就行了。

现在产生100000个随机数，分别放到vector和list中，然后list调自己提供的sort，vector调库里面的sort，我们来对比一下它们的运行时间：

多运行几次：

我们看到vector是更快一些在它们排一组相同的数据下。

那我们加到1000000个数据再来看：

然后我们再换一种玩法：

我们现在定义两个list，还是上面那些数据，一个list我直接排，另一个怎么做呢？

我先把它拷贝到一个vector里面去排序，然后排完再拷贝回list，我们来看一下：

🆗，我们看到还是比直接在list里排快很多。

所以说：

虽然list提供了sort，但是我们大多数情况下是不会选择用它的。

🆗：

那list的使用我们差不多就讲到这里，大家用到哪些接口如果没有讲到可以自行查阅文档。