【C++】list利用详解

        本篇介绍一下list链表的利用，后续也是会对list举行模拟实现的。list是链表内里的双向链表。
1.文档介绍

list - C++ Reference

https://legacy.cplusplus.com/reference/list/list/
list中的接口比较多，此处类似，只须要掌握如何正确的利用，然后再去深入研究背后的原理，已达到可扩展的本领。以下为list中一些常见的重要接口。

2.list常见接口

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

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

复制代码

析构函数自动调用

2.2 Capacity:

 2.3 Element access:

 2.4 Modifiers:

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

1. //一个A类
2. struct A
3. {
4. public:
5.     A(int a1 = 1, int a2 = 2)
6.         :_a1(a1)
7.         ,_a2(a2)
8.     {}
9. private:
10.     int _a1;
11.     int _a2;
12. };

复制代码

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

1. list<A> lt;

复制代码

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

复制代码

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

复制代码

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

1. 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自己的接口，不是算法库内里的。

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

复制代码

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

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

复制代码

reverse用哪个都可以。

1. list<int> lt;
2. lt.push_back(1);
3. lt.push_back(4);
4. lt.push_back(9);
5. lt.push_back(6);
6. lt.push_back(3);
8. lt.sort();

复制代码

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

无论是list自己实现的sort照旧算法库内里的，默认排升序。我们想实现降序就要用到仿函数。
有less和greater这样的两个类模板，less是升序，greater是降序。用法如下。

1. list<int> lt;
2. lt.push_back(1);
3. lt.push_back(4);
4. lt.push_back(9);
5. lt.push_back(6);
6. lt.push_back(3);
8. greater<int> gt; //降序
9. lt.sort(gt);

复制代码

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

复制代码

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

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

复制代码

4.2 merge 合并

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

1. list<int> lt1, lt2;
2. lt1.push_back(1);
3. lt1.push_back(4);
4. lt1.push_back(9);
5. lt1.push_back(6);
7. lt2.push_back(2);
8. lt2.push_back(5);
9. lt2.push_back(3);
10. lt2.push_back(8);
12. lt1.sort();//排序
13. lt2.sort();
15. lt1.merge(lt2);//合并

复制代码

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

4.3 unique 去重

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

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

复制代码

4.4 remove和remove_if

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

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

4.5 splice 粘接

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

1. list<int> mylist1, mylist2;
2. list<int>::iterator it;
4. for (int i = 1; i <= 4; ++i)
5.     mylist1.push_back(i);      // mylist1: 1 2 3 4
7. for (int i = 1; i <= 3; ++i)
8.     mylist2.push_back(i * 10); // mylist2: 10 20 30
10. it = mylist1.begin();
11. ++it;                          // points to 2
13. mylist1.splice(it, mylist2);   // mylist1: 1 10 20 30 2 3 4

复制代码

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

1. list<int> lt;
2. lt.push_back(1);
3. lt.push_back(2);
4. lt.push_back(3);
5. lt.push_back(4);
6. lt.push_back(5);
7. lt.push_back(6);
8. for (auto e : lt)
9. {
10.     cout << e << " ";
11. }
12. cout << endl;
14. int x = 0;
15. cin >> x;
16. auto it = find(lt.begin(), lt.end(), x);
18. if (it != lt.end())
19. {
20.     lt.splice(lt.begin(), lt, it); //把lt里的it转移到lt的begin前面
21. }
22. for (auto e : lt)
23. {
24.     cout << e << " ";
25. }
26. cout << endl;

复制代码

 假如要把5背面的值全部转移到前面去，背面第3和4个参数就是一段迭代器区间。
其他代码稳定，if内里改变。

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

复制代码

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

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

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。