【C++】list利用详解
https://i-blog.csdnimg.cn/direct/43dd24de72604b8aa6a82ff05753a804.gif本篇介绍一下list链表的利用，后续也是会对list举行模拟实现的。list是链表内里的双向链表。
1.文档介绍
list - C++ Referencehttps://csdnimg.cn/release/blog_editor_html/release2.3.7/ckeditor/plugins/CsdnLink/icons/icon-default.png?t=O83Ahttps://legacy.cplusplus.com/reference/list/list/
list中的接口比较多，此处类似，只须要掌握如何正确的利用，然后再去深入研究背后的原理，已达到可扩展的本领。以下为list中一些常见的重要接口。
2.list常见接口
有了string和vector的基础，现在我们对这些接口一看名字就知道作用，所以就不做过多解释。假如不熟悉，发起先看【C++】string类接口利用（万字详解）
2.1 构造和析构
https://i-blog.csdnimg.cn/direct/ac39d4d8bfc34100ba918c7004c1fbf9.png
https://i-blog.csdnimg.cn/direct/a5f3af8782a148f8802010dc95601cf3.png
list<int> l1;
list<int> l2(4, 1);
list<int> l3(++l2.begin(), --l2.end());
list<int> l4 = l2; https://i-blog.csdnimg.cn/direct/8c354385c8954d1393d5e65c724c5d90.png
析构函数自动调用
https://i-blog.csdnimg.cn/direct/0bd9d0f103a84ab18d23c58ebf85b6e1.png
2.2 Capacity:
https://i-blog.csdnimg.cn/direct/d1b22186755d456c943cd2001a420368.pnghttps://i-blog.csdnimg.cn/direct/b5b4b8091cd44aa8b9113ae3d4446c5b.png
2.3 Element access:
https://i-blog.csdnimg.cn/direct/6da9a8803ff64c1aa0223fff2652b39c.png
https://i-blog.csdnimg.cn/direct/ef30f1a942e640e982bc60b5db19f63d.png
2.4 Modifiers:
https://i-blog.csdnimg.cn/direct/aa776eb3e40a40feb11abd8538acd784.png
https://i-blog.csdnimg.cn/direct/265a35a8c42b45cebb0abc69b8a2cc92.png
顺便说一句，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:
https://i-blog.csdnimg.cn/direct/ea85222b9e564a7b93025ce25015fb8a.png
https://i-blog.csdnimg.cn/direct/ee4dd93d50724a4781034516664a9171.png
链表的迭代器须要注意的是：不能用下标+[]来遍历了，因为链表的底层是不连续的。
假如不知道这些接口的功能，发起可以先看一下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 部分可以看。
https://i-blog.csdnimg.cn/direct/cfc3fd54062945ca8cdd38c9534d6165.png
上面这个图是list的文档，list的迭代器类型是bidirectional，就是双向的意思。
我们再看一下vector的迭代器类型。
https://i-blog.csdnimg.cn/direct/d1ac694ce193413f8eb75fb296c2fd49.png
vector就是一个random_access随机访问迭代器。
在看一个unordered_map。
https://i-blog.csdnimg.cn/direct/516cf0bd672841afa930b28666da6ecc.png
unordered_map就是一个forward单向迭代器。
3.3 iterator性质的影响
迭代器的性质来决定可以利用哪些算法，算法对迭代器是有要求的。
算法相干文档：<algorithm> - C++ Reference 利用时要包罗头文件 #include<algorithm>
拿内里的sort举例。
https://i-blog.csdnimg.cn/direct/6b63a9821e624ea4b538049a430a63f7.png
https://i-blog.csdnimg.cn/direct/62f9dc21462042468bb5a4dab826e7c7.png
sort要求迭代器类型是一个随机迭代器 ，因为sort底层须要支持+和-的操纵。
再好比说reverse。
https://i-blog.csdnimg.cn/direct/e529a1b2d01b43c1afacda426a47fc9f.png
https://i-blog.csdnimg.cn/direct/346c808c286b4a93ab9745c181564adf.png 要求传的是双向迭代器。
但是！不肯定只能是双向迭代器，随机迭代器也可以，只要支持++和--就行，但是forward单向迭代器不可以，因为它只支持++,不支持--。
再看find。
https://i-blog.csdnimg.cn/direct/37d599d340d144fbbc493b8c309e8c92.png
https://i-blog.csdnimg.cn/direct/1ce956a9a7c342f491c743cdcaaa7a1b.png find要求传InputIterator，这是什么类型？
https://i-blog.csdnimg.cn/direct/84b601f6a974485f966f5a12c66ecc7e.gif
iterator引申出input和output，这是不存在的迭代器，没有直接对应的类型，只读和只写。 这是比较抽象的两个东西。
https://i-blog.csdnimg.cn/direct/8ff990c1ec524b5e8a86ffdb9e1864e6.png
总而言之，InputIterator就是可以给单向、双向、随机三类的恣意一种类型迭代器。
假如说在用算法的时间，给了错误的迭代器，是会直接报错的。
4.list不常见的接口
https://i-blog.csdnimg.cn/direct/ee33d56133984bbeb08ed6c77c001242.png
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(); https://i-blog.csdnimg.cn/direct/c00f0e7452c7472bb555c617c5167a0a.png
假如是用算法库内里的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(); https://i-blog.csdnimg.cn/direct/07131d034c1e44a584964217ad6f9e3e.png
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功能是合并两个有序的链表。
https://i-blog.csdnimg.cn/direct/b2cfcfb37b51454488188029f3d6d3b7.png
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);//合并 https://i-blog.csdnimg.cn/direct/8018cb83d1e746f7a063a7ee0ce2974a.png
可以看到，合并之后被合并的链表就空了。
4.3 unique 去重
unique是给链表去重的，把重复的数去掉，只保存一个，但是也要有序链表。
https://i-blog.csdnimg.cn/direct/0e0b4f08519c4066b35cbac309ae84ba.png
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();//去重 https://i-blog.csdnimg.cn/direct/a80a1d7e43df4ca88d0201d4d1eb4c16.png
4.4 remove和remove_if
https://i-blog.csdnimg.cn/direct/b78d12d417bd4b599ff07b21307f3412.png
删除链表节点。找到val了就删除，没找到也不会报错。
https://i-blog.csdnimg.cn/direct/1ed00c6b33e948ccbe95f6c2482dd523.png
按要求删除节点，好比说是偶数就删除。这里也是要用到仿函数，我们后续仔细说。
4.5 splice 粘接
https://i-blog.csdnimg.cn/direct/160fba3620fa4dcd8c19b201099ebe05.png
实在本质上是转移节点。被转移的节点大概迭代器区间插入在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 https://i-blog.csdnimg.cn/direct/b92dc9dd95ce4709b370f06d966cce9c.png
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; https://i-blog.csdnimg.cn/direct/50369dad36bd45cdacc4c43a83016ea7.png
假如要把5背面的值全部转移到前面去，背面第3和4个参数就是一段迭代器区间。
其他代码稳定，if内里改变。
if (it != lt.end())
{
//把lt里的it后面的全部转移到lt的begin前面
lt.splice(lt.begin(), lt, it, lt.end());
} https://i-blog.csdnimg.cn/direct/68e9f8d316224249b4ac60f616323cc3.png
所以，splice可以把一个链表的节点转移到另一个链表，也可以调整当前链表的节点顺序。
list的利用就介绍这么多，下篇再见~
https://i-blog.csdnimg.cn/direct/1535754f6980447bbe1f21e17deb552c.gif
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]