【C++】【STL】双向链表你还在手撕代码❓️STL list容器那些藏在文档里的实用方法，你用过几个❓️
目录
3.4、将一个链表的元素或元素范围移动到另一个链表的指定位置——splice
前言：
list容器提供了关于双向链表相关操作的各种接口函数，这样就会大大提高我们工作和学习的效率。只要我们学会了这些实用接口（增删查改）的使用，就再也不用自己去实现了，回想自己手撕代码的心酸过程😅，想必大家已经迫不及待地想要去学习了。
注意：标有⭐的内容需要重点掌握！！！
我们话不多说，进入正题👇️👇️👇️
1、list简介
在 C++ 标准库中，std::list 是一个双向链表容器。定义在头文件#include<list>中，它的元素在内存中不是连续存储的，而是通过节点之间的指针相互链接，这使得它在插入和删除操作上有独特的优势。
std::list 是一个双向链表容器，即其底层结构为双向链表（带头双向循环链表），需要注意，双向链表的头节点（哨兵位）只用来占位，而不存储有效数据。所以，双向链表的头插即是在上图的d1节点之前插入节点；头删即删除d1节点；尾插即在d3节点之后插入节点；尾删即删除d3节点。⭐核心特性双向链表结构：每个元素包含前驱和后继指针，支持双向遍历动态内存分配：元素分散存储，无需预先分配固定大小的内存高效的插入删除：在任意位置插入 / 删除元素的时间复杂度为 O(1)（已知位置时）不支持随机访问：访问特定元素需要从头 / 尾遍历，时间复杂度为 O(n)
🌟🌟std::list的文档（方便大家随时查阅相关接口函数）：
https://legacy.cplusplus.com/reference/list/list/（强调一下：自己查文档很重要呦！！！）
2、常用接口介绍
2.1、list类对象的常用构造
实现list对象在定义的同时初始化
| 构造函数（construct）（⭐） | 功能 |
list() | 默认构造，构造空链表（即哨兵位） |
list(const list<value_type>& lt) | 拷贝构造，用已经存在的对象 lt 初始化 |
list(size_t n, const value_type& val=value_type()) | 填充构造函数，用n个value_type类型的值去初始化 |
list(InputIterator first,InputIterator last) | 迭代器区间构造，使用迭代器范围 [first, last) 内的元素来初始化 list对象 |
list(std::initializer_list<value_type> ilist) | 初始化列表构造函数（C++11 引入） |
void test1() { list<int> lt1; // 构造空链表 list<int> lt2(5, 1); // 使用5个1初始化lt2 list<int> lt3(lt2); // 构造lt3对象，并用lt2初始化 list<int> lt4(lt2.begin(), lt2.end()); // 使用lt2的迭代器区间初始化lt4 list<int> lt5({ 1,2,3,4,5 }); // 使用初始化列表初始化lt5 }2.2、list对象容量操作
| 函数 | 功能 |
| ⭐size() | 获取双向链表的有效节点个数 |
| ⭐empty() | 判断链表是否为空 |
void test2() { list<int> lt({ 1,2,3,4,5 }); cout << lt.size() << endl; if (lt.empty()) cout << "为空" << endl; else cout << "非空" << endl; }2.3、list iterator（迭代器）
此处，大家可暂时将迭代器理解成一个指针，该指针指向list中的某个节点。
| 函数 | 功能 |
| ⭐lt.begin() | begin获取头节点下一个节点的迭代器（地址） |
| ⭐lt.end() | end获取头节点的迭代器（地址） |
| lt.rbegin() | rbegin()返回的是反向迭代器，指向链表的头节点 |
| lt.rend() | rend获取头节点下一个节点的迭代器（地址） |
2.5、链表的遍历
在前面的string容器和vector容器中，由于两者的底层结构均为数组，所以，string和vector都重载了 "[ ]"运算符，通过下标的方式来访问某个元素。但是，由于list底层结构为双向链表，导致他的元素在内存中并不是连续存储的，所以我们不能用下标的方式来访问。
下面我来演示一下链表的遍历方式：
⭐方法一：范围for + auto
void test3() { list<int> lt({ 1,2,3,4,5 }); for (auto e : lt) { cout << e << " "; } } 输出结果：
⭐方法二：迭代器
void test4() { list<int> lt({ 1,2,3,4,5 }); list<int>::iterator it = lt.begin(); while (it != lt.end()) { cout << *it << " "; it++; } }输出结果：
2.4、链表的增删查改
| 函数 | 功能 |
| ⭐front | 获取d1节点的值 |
| ⭐back | 获取d3节点的值 |
| ⭐push_front(const value_type x) | 在d1节点之前插入值为x的新节点 |
| ⭐pop_front | 删除d1节点 |
| ⭐push_back(const value_type x) | 在d3节点之后插入一个值为x的新节点 |
| ⭐pop_back | 删除d3节点 |
| ⭐insert(iterator pos, const value_type x) | 在pos指向的节点之前插入一个值为x的新节点 |
| ⭐erase(iterator pos) | 删除pos指向的节点 |
| swap | 交换两个对象的值 |
| ⭐clear | 清理链表中的有效节点 |
3、拓展接口说明
3.1、尾插——emplace_back
前面我们已经介绍了一个尾插的接口（push_back），那为什么list容器还要实现一个emplace_back尾插接口呢？
假设我们额外定义一个AA类，然后，将AA类型的数据分别使用push_back和emplace_back尾插到lt对象，看会发生什么？下面我们来看具体的示例
struct AA { AA(int a1 = 1, int a2 = 1) :_a1(a1) ,_a2(a2) {} int _a1; int _a2; };void test5() { AA a1; list<AA> lt; lt.push_back(a1); lt.push_back(AA(20, 20)); lt.push_back(30, 30); // 报错 }
这里有一种应用emplace_back特殊情景，此时只有emplace_back才能够实现。当我们想要直接将构造a对象的数据作为参数传给尾插函数时，push_back就会报错，而emplace_back则支持这种操作。
// emplace_back void test6() { list<AA> lt; lt.emplace_back(30, 30); }
通过调试，可以看到emplace_back将用来构造a对象的参数30和30插入了链表。
3.2、合并两个已排序的链表——merge
需要注意：merge只能用来合并两个已经排好序的链表，同时，合并之后一个链表将会为空。
void test7() { std::list<double> first, second; first.push_back(3.1); first.push_back(2.2); first.push_back(2.9); second.push_back(3.7); second.push_back(7.1); second.push_back(1.4); // 保证有序 first.sort(); second.sort(); // 将已经有序的second合并到first链表 first.merge(second);// (second is now empty) for (auto e : first) cout << e << " "; }
3.3、移除链表中连续的重复元素——unique
注意：只能连续的重复元素去掉，并只保留一个。
void test8() { list<int> lt; lt.push_back(1); lt.push_back(5); lt.push_back(5); lt.push_back(4); lt.push_back(5); lt.push_back(6); for (auto e : lt) cout << e << " "; cout << endl; lt.unique(); // 去重 for (auto e : lt) cout << e << " "; }
3.4、将一个链表的元素或元素范围移动到另一个链表的指定位置——splice
注意：移动之后一个链表将会为空。
void test9() { std::list<int> mylist1, mylist2; std::list<int>::iterator it; for (int i = 1; i <= 4; ++i) mylist1.push_back(i); for (int i = 1; i <= 3; ++i) mylist2.push_back(i * 10); it = mylist1.begin(); ++it; mylist1.splice(it, mylist2); // 链表mylist2节点转移给链表mylist1的第二个节点之前 for (auto e : mylist1) { cout << e << " "; } }
3.5、链表元素的排序——sort
我们知道C++在标准库中已经实现了排序算法，为什么list还要再自己实现呢？这就是因为迭代器的性质造成的。下面我们来介绍一下迭代器的类型
根据前面对string和vector的学习，我们知道，根据迭代器的功能，将迭代器分为：
// iterator————普通对象 // const_iterator————const对象 // reverse_iterator————普通对象的反向迭代器 // const_reverse_iterator————const对象的反向迭代器根据迭代器性质将迭代器分为：
// 按性质分为：（向上兼容） /*随机迭代器：string/vector/deque... 支持++ / -- / + / - ； 双向迭代器：list/map/set... 支持++ / -- ； 单向迭代器：forward_list/unordered_map 支持++ */#include<algorithm> // sort的头文件 void test01() { list<int> lt; lt.push_back(6); lt.push_back(3); lt.push_back(5); lt.push_back(2); lt.push_back(1); // sort :仅支持随机迭代器 //sort(lt.begin(), lt.end()); // list类对象的迭代器为双向迭代器，所以报错 string st("ahdncxvjsvf"); sort(st.begin(), st.end()); // string类对象的迭代器为随机迭代器 cout << st << endl; // reverse : 支持双向迭代器（也兼容随机迭代器） reverse(lt.begin(), lt.end()); reverse(st.begin(), st.end()); }void test02() { list<int> lt; lt.push_back({6, 3, 5, 2, 1}); // list容器中的sort lt.sort(); for (auto e : lt) cout << e << " "; }
4、总结
list容器提供了丰富而且非常实用的接口，我相信只要我们自己不断查文档，并不断应用，就一定能够掌握这些接口的用法。那么，本期的分享就到此结束，如果大家觉得写的还不错的话，点个小爱心❤️支持一下吧👇️👇️👇️，我们下期再见🤗🤗🤗
