102 std::list (双向链表容器)
作者Lou Xiao, deepseek创建时间2025-04-02 17:20:19更新时间2025-04-02 17:20:19
1. 基本概念
std::list 是 C++ 标准模板库(STL)中的一个双向链表容器。
1.1 主要特性
- 双向链表结构：每个元素包含指向前驱和后继的指针
- 非连续存储：元素在内存中不连续存储
- 高效插入/删除：在任何位置插入或删除元素的时间复杂度为 O(1)
- 随机访问效率低：访问特定位置的元素需要 O(n) 时间
- 动态大小：可根据需要自动调整大小
1.2 头文件
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
#include <list>
2. 构造函数
| 构造函数 | 描述 |
|---|---|
list() | 默认构造函数，创建空列表 |
list(size_type n) | 创建包含 n 个默认构造元素的列表 |
list(size_type n, const T& value) | 创建包含 n 个 value 的列表 |
list(const list& other) | 拷贝构造函数 |
list(list&& other) | 移动构造函数 (C++11) |
list(InputIt first, InputIt last) | 用迭代器范围构造 |
list(std::initializer_list<T> init) | 初始化列表构造 (C++11) |
3. 常用成员函数
3.1 元素访问
| 函数 | 描述 | 时间复杂度 |
|---|---|---|
front() | 访问第一个元素 | O(1) |
back() | 访问最后一个元素 | O(1) |
3.2 容量查询
| 函数 | 描述 | 时间复杂度 |
|---|---|---|
empty() | 检查是否为空 | O(1) |
size() | 返回元素数量 | O(1) (C++11前可能为 O(n)) |
max_size() | 返回最大可能元素数量 | O(1) |
3.3 修改器
| 函数 | 描述 | 时间复杂度 |
|---|---|---|
push_front(const T& value) | 在头部插入元素 | O(1) |
push_front(T&& value) | 移动语义插入头部 (C++11) | O(1) |
pop_front() | 删除头部元素 | O(1) |
push_back(const T& value) | 在尾部插入元素 | O(1) |
push_back(T&& value) | 移动语义插入尾部 (C++11) | O(1) |
pop_back() | 删除尾部元素 | O(1) |
insert(iterator pos, const T& value) | 在指定位置插入元素 | O(1) |
emplace(iterator pos, Args&&... args) | 在指定位置构造元素 (C++11) | O(1) |
erase(iterator pos) | 删除指定位置元素 | O(1) |
erase(iterator first, iterator last) | 删除范围元素 | O(n) |
clear() | 清空所有元素 | O(n) |
swap(list& other) | 交换两个列表内容 | O(1) |
3.4 操作
| 函数 | 描述 | 时间复杂度 |
|---|---|---|
merge(list& other) | 合并两个已排序列表 | O(n) |
sort() | 排序列表元素 | O(n log n) |
reverse() | 反转列表顺序 | O(n) |
unique() | 删除连续重复元素 | O(n) |
remove(const T& value) | 删除所有等于 value 的元素 | O(n) |
remove_if(Predicate pred) | 删除满足条件的元素 | O(n) |
splice(iterator pos, list& other) | 将 other 的所有元素移动到当前列表的 pos 位置 | O(1) |
4. 迭代器
std::list 提供双向迭代器：
| 迭代器 | 描述 |
|---|---|
begin(), cbegin() | 返回指向第一个元素的迭代器 |
end(), cend() | 返回指向末尾(最后一个元素之后)的迭代器 |
rbegin(), crbegin() | 返回指向最后一个元素的反向迭代器 |
rend(), crend() | 返回指向开头(第一个元素之前)的反向迭代器 |
5. 示例代码
5.1 基本使用
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
#include <iostream>
2
#include <list>
3
4
int main() {
5
// 创建并初始化列表
6
std::list<int> l = {1, 2, 3, 4, 5};
7
8
// 添加元素
9
l.push_back(6);
10
l.push_front(0);
11
12
// 遍历列表
13
for (int n : l) {
14
std::cout << n << " ";
15
}
16
std::cout << "\n"; // 输出: 0 1 2 3 4 5 6
17
18
// 插入元素
19
auto it = l.begin();
20
std::advance(it, 2); // 移动到第三个元素
21
l.insert(it, 99);
22
23
// 删除元素
24
l.remove(3); // 删除所有值为3的元素
25
26
// 排序
27
l.sort();
28
29
// 反转
30
l.reverse();
31
32
return 0;
33
}
5.2 合并和拼接示例
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
#include <iostream>
2
#include <list>
3
4
int main() {
5
std::list<int> list1 = {1, 3, 5};
6
std::list<int> list2 = {2, 4, 6};
7
8
// 合并两个已排序列表
9
list1.merge(list2);
10
// list1: {1, 2, 3, 4, 5, 6}, list2: 空
11
12
std::list<int> list3 = {7, 8, 9};
13
14
// 拼接
15
auto it = list1.begin();
16
std::advance(it, 3); // 移动到第四个元素
17
list1.splice(it, list3);
18
// list1: {1, 2, 3, 7, 8, 9, 4, 5, 6}, list3: 空
19
20
return 0;
21
}
6. 性能考虑
6.1 优点
- 在任何位置插入/删除元素都非常高效 (O(1))
- 插入和删除不会使迭代器失效(除了被删除元素的迭代器)
- 不需要连续内存，适合大元素或频繁插入删除的场景
6.2 缺点
- 不支持随机访问，访问特定位置元素需要 O(n) 时间
- 每个元素需要额外存储前后指针，内存开销较大
- 缓存不友好，因为元素在内存中不连续
7. 与其它容器的比较
| 特性 | std::list | std::vector | std::deque |
|---|---|---|---|
| 存储结构 | 双向链表 | 动态数组 | 分段数组 |
| 随机访问 | 慢 (O(n)) | 快 (O(1)) | 快 (O(1)) |
| 头部插入/删除 | 快 (O(1)) | 慢 (O(n)) | 快 (O(1)) |
| 尾部插入/删除 | 快 (O(1)) | 快 (O(1)) | 快 (O(1)) |
| 中间插入/删除 | 快 (O(1)) | 慢 (O(n)) | 慢 (O(n)) |
| 内存使用 | 高 (每个元素额外指针) | 低 | 中等 |
| 迭代器失效 | 仅删除元素影响 | 插入/删除可能使所有迭代器失效 | 中间插入/删除可能使所有迭代器失效 |
8. 最佳实践
适用场景：
- 需要频繁在任意位置插入/删除元素
- 不需要随机访问元素
- 元素较大，移动成本高
- 需要保证迭代器长期有效(除了被删除元素)
不适用场景：
- 需要频繁随机访问元素
- 内存受限的环境
- 对缓存性能要求高的场景
性能提示：
- 对于小型元素，
std::vector通常性能更好 - 使用
emplace系列函数避免不必要的拷贝 - 考虑使用
std::advance或std::next移动迭代器
- 对于小型元素，
std::list 常用 API 的整理表格
| 名称 | 用途 | 原型 | 代码示例 | 注释 |
|---|---|---|---|---|
push_back | 在链表尾部插入元素 | void push_back(const T& value); | std::list<int> l; l.push_back(42); | 添加元素到末尾，时间复杂度 O(1)。 |
push_front | 在链表头部插入元素 | void push_front(const T& value); | l.push_front(10); | 添加元素到头部，时间复杂度 O(1)。 |
pop_back | 删除链表尾部元素 | void pop_back(); | l.pop_back(); | 删除最后一个元素，链表不能为空。 |
pop_front | 删除链表头部元素 | void pop_front(); | l.pop_front(); | 删除第一个元素，链表不能为空。 |
insert | 在指定位置插入元素 | iterator insert(iterator pos, const T& value); | auto it = l.begin(); l.insert(it, 99); | 在迭代器 pos 前插入元素，返回新元素迭代器。 |
erase | 删除指定位置的元素 | iterator erase(iterator pos); | it = l.begin(); it = l.erase(it); | 删除迭代器 pos 指向的元素，返回下一个元素的迭代器。 |
size | 返回链表元素数量 | size_type size() const; | std::cout << l.size(); | 时间复杂度 O(n)（C++11 前），可能 O(1)（实现依赖）。 |
empty | 检查链表是否为空 | bool empty() const; | if (l.empty()) { /*...*/ } | 等价于 size() == 0，但可能更高效。 |
clear | 清空链表 | void clear(); | l.clear(); | 删除所有元素，时间复杂度 O(n)。 |
front | 访问第一个元素 | T& front(); | int x = l.front(); | 返回引用，链表不能为空。 |
back | 访问最后一个元素 | T& back(); | int y = l.back(); | 返回引用，链表不能为空。 |
splice | 移动元素到另一个链表 | void splice(iterator pos, list& other); | std::list<int> l2; l2.splice(l2.begin(), l); | 将 other 的所有元素移动到 pos 前，other 变为空。 |
remove | 删除所有等于指定值的元素 | void remove(const T& value); | l.remove(42); | 遍历整个链表，删除所有匹配项。 |
sort | 对链表排序 | void sort(); | l.sort(); | 默认升序排序，时间复杂度 O(n log n)。 |
merge | 合并两个已排序链表 | void merge(list& other); | std::list<int> l2{1,3}; l.merge(l2); | other 必须已排序，合并后 other 为空。 |
unique | 删除连续重复元素 | void unique(); | l.unique(); | 通常需先排序，保留第一个出现的元素。 |
reverse | 反转链表元素顺序 | void reverse(); | l.reverse(); | 时间复杂度 O(n)。 |
补充说明：
- 时间复杂度：
std::list的插入/删除操作通常为 O(1)（已知迭代器位置时）。 - 迭代器失效：只有被删除元素的迭代器会失效，其他迭代器不受影响。
- 自定义比较：
sort和merge可传入比较函数（如l.sort(std::greater<int>())）。
文章目录