【C++】list使用详解

        本篇介绍一下list链表的使用，后续也是会对list进行模拟实现的。list是链表里面的双向链表。

1.文档介绍

list - C++ Referencehttps://legacy.cplusplus.com/reference/list/list/

list中的接口比较多，此处类似，只需要掌握如何正确的使用，然后再去深入研究背后的原理，已达到可扩展的能力。以下为list中一些常见的重要接口。

2.list常见接口

有了string和vector的基础，现在我们对这些接口一看名字就知道作用，所以就不做过多解释。如果不熟悉，建议先看【C++】string类接口使用（万字详解）

2.1 构造和析构

list<int> l1; 
list<int> l2(4, 1);
list<int> l3(++l2.begin(), --l2.end());
list<int> l4 = l2;

析构函数自动调用

2.2 Capacity:

 2.3 Element access:

 2.4 Modifiers:

顺便说一句，emplace_back 和 push_back 功能上是一样的，只有一点区别，在某些场景下会让emplace_back高效一些。

比如下面的场景。

//一个A类
struct A
{
public:
    A(int a1 = 1, int a2 = 2)
        :_a1(a1)
        ,_a2(a2)
    {}
private:
    int _a1;
    int _a2;
};

push_back和 emplace_back都可以像下面这样用。

list<A> lt;

//有名对象
A a1(1, 1);
lt.push_back(a1);
//匿名对象
lt.push_back(A(2, 2));

//有名对象
A a1(1, 1);
lt.emplace_back(a1);
//匿名对象
lt.emplace_back(A(2, 2));

但是，emplace_back 支持如下写法。push_back不可以这样写。

lt.emplace_back(2, 2);

上面这种写法就是支持直接传构造A对象的参数，这里不是隐式类型转换。这就是push_back和 emplace_back的最大差别。

2.5 Iterators:

链表的迭代器需要注意的是：不能用下标+[]来遍历了，因为链表的底层是不连续的。

如果不知道这些接口的功能，建议可以先看一下string的使用，里面对文档做了详细介绍。【C++】string类接口使用（万字详解）_c++ string接口支持的操作-CSDN博客

3.迭代器iterator的性质分类

3.1 性质分类

迭代器从性质上可以分为：单向、双向、随机。

经典的随机迭代器：vector / string / deque ...

标志：支持++ / -- / + / -

经典的双向迭代器：list / map / set ...

标志：支持++ / -- ，不支持+和-

经典的单向迭代器：forward_list(单向的链表)  / unordered_xxx(哈希) ...

标志：只支持++

3.2 如何看容器的iterator的性质

在文档的 Member types 部分可以看。

上面这个图是list的文档，list的迭代器类型是bidirectional，就是双向的意思。

我们再看一下vector的迭代器类型。

vector就是一个random_access随机访问迭代器。

在看一个unordered_map。

unordered_map就是一个forward单向迭代器。

3.3 iterator性质的影响

迭代器的性质来决定可以使用哪些算法，算法对迭代器是有要求的。

算法相关文档：<algorithm> - C++ Reference   使用时要包含头文件 #include<algorithm>

拿里面的sort举例。

sort要求迭代器类型是一个随机迭代器 ，因为sort底层需要支持+和-的操作。

再比如说reverse。

 要求传的是双向迭代器。

但是！不一定只能是双向迭代器，随机迭代器也可以，只要支持++和--就行，但是forward单向迭代器不可以，因为它只支持++,不支持--。

再看find。

 find要求传InputIterator，这是什么类型？

iterator引申出input和output，这是不存在的迭代器，没有直接对应的类型，只读和只写。 这是比较抽象的两个东西。

总而言之，InputIterator就是可以给单向、双向、随机三类的任意一种类型迭代器。

如果说在用算法的时候，给了错误的迭代器，是会直接报错的。

4.list不常见的接口

4.1 list自己的reverse和sort

这个reverse和sort是list自己的接口，不是算法库里面的。

list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);

lt.reverse();

 如果是用算法库里面的reverse，就像下面这么写。

reverse(lt.begin(), lt.end());

reverse用哪个都可以。

list<int> lt;
lt.push_back(1);
lt.push_back(4);
lt.push_back(9);
lt.push_back(6);
lt.push_back(3);

lt.sort();

 list自己实现sort是因为算法库里面的sort要求传随机迭代器，但是list是双向迭代器，list用不了算法库里面的sort。

4.1.1 仿函数

无论是list自己实现的sort还是算法库里面的，默认排升序。我们想实现降序就要用到仿函数。

有less和greater这样的两个类模板，less是升序，greater是降序。用法如下。

list<int> lt;
lt.push_back(1);
lt.push_back(4);
lt.push_back(9);
lt.push_back(6);
lt.push_back(3);

greater<int> gt; //降序
lt.sort(gt);

less<int> ls;
lt.sort(ls); //升序

这里也可以用匿名对象，如下。

//匿名对象
lt.sort(greater<int>());//降序
lt.sort(less<int>());//升序

4.2 merge 合并

merge功能是合并两个有序的链表。

list<int> lt1, lt2;
lt1.push_back(1);
lt1.push_back(4);
lt1.push_back(9);
lt1.push_back(6);

lt2.push_back(2);
lt2.push_back(5);
lt2.push_back(3);
lt2.push_back(8);

lt1.sort();//排序
lt2.sort();

lt1.merge(lt2);//合并

可以看到，合并之后被合并的链表就空了。

4.3 unique 去重

unique是给链表去重的，把重复的数去掉，只保留一个，但是也要有序链表。

list<int> lt;
//已经有序
lt.push_back(1);
lt.push_back(4);
lt.push_back(4);
lt.push_back(6);
lt.push_back(9);
lt.unique();//去重

4.4 remove和remove_if

 删除链表节点。找到val了就删除，没找到也不会报错。

按要求删除节点，比如说是偶数就删除。这里也是要用到仿函数，我们后续仔细说。

4.5 splice 粘接

其实本质上是转移节点。被转移的节点或者迭代器区间插入在position之前。

list<int> mylist1, mylist2;
list<int>::iterator it;

for (int i = 1; i <= 4; ++i)
    mylist1.push_back(i);      // mylist1: 1 2 3 4

for (int i = 1; i <= 3; ++i)
    mylist2.push_back(i * 10); // mylist2: 10 20 30

it = mylist1.begin();
++it;                          // points to 2

mylist1.splice(it, mylist2);   // mylist1: 1 10 20 30 2 3 4

 splice也可以转移自己的节点给自己。比如说我们要把下面链表的5转移到头节点去。

list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
lt.push_back(6);
for (auto e : lt)
{
    cout << e << " ";
}
cout << endl;

int x = 0;
cin >> x;
auto it = find(lt.begin(), lt.end(), x);

if (it != lt.end())
{
    lt.splice(lt.begin(), lt, it); //把lt里的it转移到lt的begin前面
}
for (auto e : lt)
{
    cout << e << " ";
}
cout << endl;

 如果要把5后面的值全部转移到前面去，后面第3和4个参数就是一段迭代器区间。

其他代码不变，if里面改变。

if (it != lt.end())
{
    //把lt里的it后面的全部转移到lt的begin前面
    lt.splice(lt.begin(), lt, it, lt.end()); 
}

所以，splice可以把一个链表的节点转移到另一个链表，也可以调整当前链表的节点顺序。 

list的使用就介绍这么多，下篇再见~