C++ list 容器详解：从入门到精通
💬 欢迎讨论：学习过程中有问题吗？随时在评论区与我交流。你们的互动是我创作的动力！
👍 支持我：如果你觉得这篇文章对你有帮助，请点赞、收藏并分享给更多朋友吧！
🚀 一起成长：欢迎分享给更多对 C++ 感兴趣的小伙伴，让我们共同进步！
前言
C++ 标准模板库（STL）中的 list 容器是一个双向链表结构，它提供了高效的插入和删除操
作。与 vector 不同，list 中的元素不是连续存储的，因此可以在任何位置高效插入和删除元素，而无需移动其他元素。虽然它在随机访问方面不如 vector 高效，但在大量的插入和删除操作场景中具有不可替代的优势。
本文将通过详细的示例代码，从基础到进阶，逐步讲解如何使用 C++ 中的 list 容器，并探讨其特性与常用操作。
第一章：C++ list 容器简介
1.1 C++ STL 容器概述
C++ 提供了丰富的标准模板库 (STL)，其中包括顺序容器（如 vector、deque）和关联容器（如 map、set）。
list 是一种链表结构的顺序容器，它的底层实现是双向链表。这使得 list 在插入和删除操作上比 vector 更加高效，但由于不支持随机访问，因此访问特定位置的元素时效率较低。
1.2 list 的特点
- 双向链表：
list底层是一个双向链表，能够高效地进行插入和删除操作。 - 不支持随机访问：由于链表的结构特点，
list只能顺序访问，随机访问效率低下。 - 动态增长：
list不需要预留空间，它会根据需要动态分配内存。
#include <list> #include <iostream> using namespace std; int main() { list<int> lst = {1, 2, 3, 4, 5}; for (int val : lst) { cout << val << " "; } return 0; }
第二章：list 的构造方法
2.1 常见构造函数
C++
list提供了多种构造函数，允许用户根据不同需求初始化链表。
| 构造函数 | 功能 |
list() |
构造一个空的 list |
list(size_type n, const T& val) |
构造一个包含 n 个值为 val 的元素的 list |
list(const list& x) |
拷贝构造函数，构造与 x 相同的 list |
list(InputIterator first, InputIterator last) |
使用 [first, last) 区间内的元素构造 list |
2.1.1 示例：不同构造方法
#include <iostream> #include <list> using namespace std; int main() { list<int> lst1; // 空 list list<int> lst2(5, 100); // 5个值为100的元素 list<int> lst3(lst2); // 拷贝构造 list<int> lst4 = {1, 2, 3, 4, 5}; // 初始化列表 for (int val : lst4) { cout << val << " "; // 输出: 1 2 3 4 5 } return 0; }
2.1.2 相关文档
第三章：list 迭代器的使用
list 支持多种迭代器类型，允许我们遍历、访问和修改链表中的元素。迭代器可以看作指向 list 中节点的指针，遍历时可以用迭代器依次访问链表中的每一个节点。
3.1 常见迭代器
| 迭代器类型 | 功能 |
begin() |
返回指向链表第一个元素的迭代器 |
end() |
返回指向链表末尾的迭代器 |
rbegin() |
返回指向链表最后一个元素的反向迭代器 |
rend() |
返回指向链表第一个元素之前的反向迭代器 |
cbegin() |
返回常量迭代器，不能修改元素 |
cend() |
返回常量迭代器，指向链表末尾 |
3.1.1 示例：使用正向和反向迭代器遍历 list
#include <iostream> #include <list> using namespace std; int main() { list<int> lst = {1, 2, 3, 4, 5}; // 使用正向迭代器遍历 for (auto it = lst.begin(); it != lst.end(); ++it) { cout << *it << " "; // 输出: 1 2 3 4 5 } cout << endl; // 使用反向迭代器遍历 for (auto rit = lst.rbegin(); rit != lst.rend(); ++rit) { cout << *rit << " "; // 输出: 5 4 3 2 1 } cout << endl; return 0; }
3.1.2 相关文档
第四章：list 的容量与大小操作
4.1 容量管理接口
list 提供了常用的容量管理接口，方便用户操作链表的大小和判断链表状态。
| 方法名 | 功能描述 |
empty() |
检测 list 是否为空 |
size() |
返回 list 中元素的数量 |
max_size() |
返回 list 可容纳的最大元素数 |
resize(n) |
调整 list 的大小为 n |
4.1.1 示例：容量操作
#include <iostream> #include <list> using namespace std; int main() { list<int> lst = {1, 2, 3, 4, 5}; cout << "Size: " << lst.size() << endl; // 输出当前元素个数 cout << "Is empty: " << (lst.empty() ? "Yes" : "No") << endl; // 判断是否为空 lst.resize(3); // 调整大小为3，保留前3个元素 for (int val : lst) { cout << val << " "; // 输出: 1 2 3 } return 0; }
4.1.2 相关文档
第五章：list 的元素访问
5.1 元素访问方法
list 提供了几种常用的方法用于访问链表中的元素。
| 方法名 | 功能 |
front() |
返回 list 的第一个元素 |
back() |
返回 list 的最后一个元素 |
5.1.1 示例：访问第一个与最后一个元素
#include <iostream> #include <list> using namespace std; int main() { list<int> lst = {1, 2, 3, 4, 5}; cout << "First element: " << lst.front() << endl; // 访问第一个元素 cout << "Last element: " << lst.back() << endl; // 访问最后一个元素 return 0; }
5.1.2 相关文档
第六章：list 的插入、删除与修改
6.1 插入操作list 容器提供了多种插入操作，包括在前部、尾部插入元素，或在指定位置插入。与 vector 不同的是，list 插入时不需要移动其他元素，只修改指针，因此插入效率非常高。
| 方法名 | 功能描述 |
push_front() |
在 list 的前部插入元素 |
push_back() |
在 list 的末尾插入元素 |
insert(position, val) |
在指定位置插入元素 |
6.1.1 示例：使用 push_back() 和 push_front() 插入元素
push_front() 和 push_back() 是将元素插入到链表前部和尾部的常用方法。由于 list 是双向链表，头部和尾部操作的效率都非常高，为 O(1)。
#include <iostream> #include <list> using namespace std; int main() { list<int> lst = {1, 2, 3}; // 在前部插入元素 lst.push_front(0); // 在末尾插入元素 lst.push_back(4); for (int val : lst) { cout << val << " "; // 输出: 0 1 2 3 4 } return 0; }
6.1.2 示例：使用 insert() 在指定位置插入元素
insert() 用于在链表中指定位置插入元素。该方法需要提供一个迭代器指向要插入的位置。
#include <iostream> #include <list> using namespace std; int main() { list<int> lst = {1, 3, 4}; // 在第二个位置插入2 auto it = lst.begin(); ++it; lst.insert(it, 2); for (int val : lst) { cout << val << " "; // 输出: 1 2 3 4 } return 0; }
6.1.3 插入元素的常见问题
- 迭代器失效：在
list中进行插入操作时，插入不会使已有迭代器失效，因为list是双向链表，插入时只修改指针。 - 尾部插入效率：在链表尾部插入元素的效率始终为 O(1)，无需移动其他元素，这点不同于
vector。 - 插入到特定位置的效率：虽然
insert()操作本身是 O(1)，但查找特定插入位置的时间复杂度是 O(n)，这取决于你如何获取迭代器。
6.1.4 相关文档
6.2 删除操作
list 提供了多种删除元素的方式，包括从前部和尾部删除，删除指定位置的元素，以及一次性清空整个链表。
| 方法名 | 功能描述 |
pop_front() |
删除 list 的第一个元素 |
pop_back() |
删除 list 的最后一个元素 |
erase() |
删除指定位置的元素 |
clear() |
清空 list |
6.2.1 示例：删除 list 中的首尾元素
pop_front() 和 pop_back() 用于删除 list 中的第一个或最后一个元素。与插入操作类似，这两种操作的时间复杂度都是 O(1)，不会影响其他元素的指针。
#include <iostream> #include <list> using namespace std; int main() { list<int> lst = {1, 2, 3, 4, 5}; // 删除第一个元素 lst.pop_front(); // 删除最后一个元素 lst.pop_back(); for (int val : lst) { cout << val << " "; // 输出: 2 3 4 } return 0; }
6.2.2 示例：删除指定位置的元素
erase() 用于删除指定位置的元素。它需要提供一个指向该位置的迭代器。
#include <iostream> #include <list> using namespace std; int main() { list<int> lst = {1, 2, 3, 4, 5}; // 查找要删除的元素 auto it = lst.begin(); advance(it, 2); // 移动到第三个元素 // 删除第三个元素 lst.erase(it); for (int val : lst) { cout << val << " "; // 输出: 1 2 4 5 } return 0; }
6.2.3 示例：清空 list
clear() 是一种非常彻底的清除操作，它会删除 list 中的所有元素。值得注意的是，clear() 仅会删除有效节点，不会删除链表的头节点（即 list 对象本身）。
#include <iostream> #include <list> using namespace std; int main() { list<int> lst = {1, 2, 3, 4, 5}; // 清空 list lst.clear(); cout << "Size after clear: " << lst.size() << endl; // 输出: 0 cout << "Is list empty? " << (lst.empty() ? "Yes" : "No") << endl; // 输出: Yes return 0; }
6.2.4 删除操作的常见问题
- 迭代器失效：在
list中，删除操作只会导致指向被删除元素的迭代器失效，其他迭代器不受影响。删除后如果需要继续使用迭代器，应该使用erase()的返回值，指向下一个有效元素。 - clear() 是否删除头节点：
clear()不会删除list的头节点。调用clear()后，list对象依然存在，只是里面的所有元素被删除，list的结构保持完好。
.2.5 相关文档
【C++篇】深度剖析C++ STL：玩转 list 容器，解锁高效编程的秘密武器2:https://developer.aliyun.com/article/1617552?spm=a2c6h.13148508.setting.19.b8d84f0euVDBkf
