C++算法
C++ STL list 容器常用接口与拓展用法详解
C++ STL list 容器基于双向链表实现，元素非连续存储。本文介绍其核心特性（动态分配、O(1) 插入删除）、常用接口（构造、容量、迭代器、遍历、增删改查）及拓展接口（emplace_back、merge、unique、splice、sort）。通过示例代码演示了 list 在内存管理、排序及合并操作中的具体应用，帮助开发者高效使用标准库容器。
C++ STL list 容器基于双向链表实现，元素非连续存储。本文介绍其核心特性（动态分配、O(1) 插入删除）、常用接口（构造、容量、迭代器、遍历、增删改查）及拓展接口（emplace_back、merge、unique、splice、sort）。通过示例代码演示了 list 在内存管理、排序及合并操作中的具体应用，帮助开发者高效使用标准库容器。
在 C++ 标准库中，std::list 是一个双向链表容器。定义在头文件 <list> 中，它的元素在内存中不是连续存储的，而是通过节点之间的指针相互链接，这使得它在插入和删除操作上有独特的优势。
std::list 是一个双向链表容器，即其底层结构为双向链表（带头双向循环链表），需要注意，双向链表的头节点（哨兵位）只用来占位，而不存储有效数据。所以，双向链表的头插即是在 d1 节点之前插入节点；头删即删除 d1 节点；尾插即在 d3 节点之后插入节点；尾删即删除 d3 节点。
核心特性
实现 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
}
| 函数 | 功能 |
|---|---|
size() | 获取双向链表的有效节点个数 |
empty() | 判断链表是否为空 |
void test2() {
list<int> lt({ 1,2,3,4,5 });
cout << lt.size() << endl;
if (lt.empty()) cout << "为空" << endl;
else cout << "非空" << endl;
}
此处，大家可暂时将迭代器理解成一个指针，该指针指向 list 中的某个节点。
| 函数 | 功能 |
|---|---|
lt.begin() | begin 获取头节点下一个节点的迭代器（地址） |
lt.end() | end 获取头节点的迭代器（地址） |
lt.rbegin() | rbegin() 返回的是反向迭代器，指向链表的头节点 |
lt.rend() | rend 获取头节点下一个节点的迭代器（地址） |
| 函数 | 功能 |
|---|---|
front | 获取第一个节点的值 |
back | 获取最后一个节点的值 |
push_front(const value_type x) | 在头部插入值为 x 的新节点 |
pop_front | 删除头部节点 |
push_back(const value_type x) | 在尾部插入一个值为 x 的新节点 |
pop_back | 删除尾部节点 |
insert(iterator pos, const value_type x) | 在 pos 指向的节点之前插入一个值为 x 的新节点 |
erase(iterator pos) | 删除 pos 指向的节点 |
swap | 交换两个对象的值 |
clear | 清理链表中的有效节点 |
由于 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++;
}
}
前面我们已经介绍了一个尾插的接口（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);
}
需要注意：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 << " ";
}
注意：只能连续的重复元素去掉，并只保留一个。
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 << " ";
}
注意：移动之后一个链表将会为空。
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 << " ";
}
}
我们知道 C++ 在标准库中已经实现了排序算法，为什么 list 还要再自己实现呢？这就是因为迭代器的性质造成的。下面我们来介绍一下迭代器的类型。
根据前面对 string 和 vector 的学习，我们知道，根据迭代器的功能，将迭代器分为：
根据迭代器性质将迭代器分为：
#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 << " ";
}
list 容器提供了丰富而且非常实用的接口，只要我们不断查文档，并不断应用，就一定能够掌握这些接口的用法。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online