C++ STL std::list 详解与应用指南

std::list 是 C++ 标准模板库（STL）中的双向链表容器。与 std::vector（动态数组）不同，它的内存是不连续的。

1. 核心特性与迭代器

1.1 迭代器类型：双向迭代器 (Bidirectional Iterator)

这是 list 最需要注意的地方，它的迭代器不像 vector 那样支持随机访问。

  • 不支持的操作：
    • it + 5, it - 3 (算术加减)
    • it[2] (下标访问)
    • it1 < it2 (大小比较，只能判断 != 或 ==)
    • std::sort(list.begin(), list.end()) (标准库的通用排序无法处理它)
  • 支持的操作：
    • it++, ++it, it--, --it
    • *it (解引用)
    • it1 == it2, it1 != it2

1.2 辅助函数 (移动迭代器)

由于不能直接 +n，如果需要移动多步，必须使用 <iterator> 头文件中的函数：

  • std::next(it, n): 返回向前移动 $n$ 步后的迭代器（$O(n)$ 复杂度）。
  • std::prev(it, n): 返回向后回退 $n$ 步后的迭代器。

1.3 迭代器失效 (Iterator Invalidation)

这是 list 的巨大优势：

  • 插入操作：不会使任何现有的迭代器失效。
  • 删除操作：只会使被删除的那个节点的迭代器失效，其他指向栈中元素的迭代器依然有效。
    • 对比 Vector：Vector 在扩容或中间插入删除时，可能会让所有迭代器失效。

2. 常用通用方法 (Common Methods)

这些方法在大多数 STL 容器中都存在。

方法 描述 时间复杂度
push_back(val) 在尾部添加元素 $O(1)$
push_front(val) 在头部添加元素 $O(1)$
pop_back() 删除尾部元素 $O(1)$
pop_front() 删除头部元素 $O(1)$
front(), back() 访问头部、尾部元素 $O(1)$
insert(it, val) 在迭代器 it 之前插入 val $O(1)$
erase(it) 删除迭代器 it 指向的元素，返回下一个元素的迭代器 $O(1)$
empty() 判断是否为空 $O(1)$
size() 返回元素个数 (C++11 后保证为 $O(1)$) $O(1)$
clear() 清空所有元素 $O(N)$

注意：erase 的正确用法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
// 错误写法：it 失效后无法进行 ++
// for (auto it = lst.begin(); it != lst.end(); it++) { if(...) lst.erase(it); }

// 正确写法：利用 erase 的返回值
for (auto it = lst.begin(); it != lst.end(); ) {
    if (need_delete(*it)) {
        it = lst.erase(it); // erase 返回被删元素的下一个位置
    } else {
        it++;
    }
}
````

---

## 3. `list` 特有的“黑科技”方法

由于链表特殊的节点结构，它拥有一些 `vector` 没有的高效操作，主要涉及节点的**拼接**和**重组**，不需要拷贝数据，只是改变指针指向。

### 3.1 `splice` (拼接/接合) - 最强功能

将元素从一个 list 移动到另一个 list（或者同一个 list 的不同位置），**零拷贝**，仅修改指针。

- `void splice(const_iterator pos, list& other);`
    
    - 将 `other` 中**所有**元素移动到 `pos` 之前。`other` 变为空。
        
- `void splice(const_iterator pos, list& other, const_iterator it);`
    
    - 将 `other` 中的 **`it` 指向的那个元素**切下来，移动到 `pos` 之前。
        
- `void splice(const_iterator pos, list& other, const_iterator first, const_iterator last);`
    
    - 将 `other` 中范围 `[first, last)` 的元素移动到 `pos` 之前。
        

### 3.2 `remove` 和 `remove_if`

- `lst.remove(val)`: 删除链表中所有等于 `val` 的元素。
    
- `lst.remove_if(pred)`: 删除所有满足条件 `pred` 的元素。
    
    - _区别_：`vector` 删除特定值需要用 `remove` 算法配合 `erase` (Erase-Remove Idiom)，而 `list` 直接成员函数搞定，且速度更快。
        

### 3.3 `unique` (去重)

- `lst.unique()`: 删除**连续**的重复元素，只保留第一个。
    
    - _注意_：如果想通过 `unique` 去除所有重复元素，必须先排序！
        

### 3.4 `merge` (合并)

- `lst1.merge(lst2)`: 将两个**已排序**的链表合并。
    
    - 合并后 `lst2` 变为空，元素全部归并到 `lst1` 中且保持有序。
        

### 3.5 `sort` (排序)

- `lst.sort()`: 对链表进行升序排序。
    
- `lst.sort(cmp)`: 自定义比较函数。
    
    - **重要**：不能用 `std::sort(lst.begin(), lst.end())`，必须用成员函数 `lst.sort()`。它通常使用归并排序实现，复杂度 $O(N \log N)$。
        

### 3.6 `reverse` (反转)

- `lst.reverse()`: 翻转链表，复杂度 $O(N)$。
    

---

## 4. 适合用 `list` 处理的题目类型

当你看到以下关键词或需求时，应优先考虑使用 `std::list`：

### 4.1 强交互的模拟题 (如刚才的“栈中消除”题)

- **特征**：需要在序列的**任意中间位置**频繁进行删除或插入操作，且不需要随机访问（不需要直接问“第 $k$ 个数是多少”）。
    
- **优势**：利用 `insert` 和 `erase` 的 $O(1)$ 特性，配合辅助数组存储迭代器位置。
    

### 4.2 LRU 缓存 (Least Recently Used Cache)

- **特征**：需要维护一个固定大小的队列，最近访问的元素移到队头，最久未访问的在队尾被淘汰。
    
- **实现**：使用 `std::list` 存储数据，使用 `std::map<key, list::iterator>` 存储键到链表节点的映射。
    
    - 当访问某节点时，使用 `splice` 将其直接剪切并拼接到链表头部（$O(1)$）。
        
    - 删除尾部时，直接 `pop_back()`。
        

### 4.3 大整数运算 / 多项式加减 (稀疏)

- **特征**：每一项包含指数和系数，且操作通常只涉及头部、尾部或按顺序遍历合并。
    
- **优势**：`merge` 功能可以很好地处理两个有序多项式的相加。
    

### 4.4 约瑟夫环 (Josephus Problem) - 变种

- **特征**：虽然经典的数学解法更好，但在模拟 $N$ 较小且规则复杂（如经常变方向、中间有人加入）的约瑟夫环时，`list` 是最自然的模型。
    
- **操作**：循环遍历，`erase` 掉出局的人，迭代器指向下一个。
    

---

## 5. 代码示例：splice 与 迭代器操作

C++

```cpp
#include <iostream>
#include <list>
#include <algorithm>

using namespace std;

int main() {
    list<int> list1 = {1, 2, 3};
    list<int> list2 = {10, 20, 30};

    auto it = list1.begin();
    advance(it, 1); // it 指向 2

    // 1. splice 用法: 将 list2 中的 20 移动到 list1 的 2 前面
    auto it2 = list2.begin();
    advance(it2, 1); // it2 指向 20
    
    // list1 变为: 1, 20, 2, 3
    // list2 变为: 10, 30
    // 注意：it2 这个迭代器依然有效，现在它指向 list1 中的 20
    list1.splice(it, list2, it2);

    cout << "List 1: ";
    for(int x : list1) cout << x << " "; // 输出: 1 20 2 3
    cout << endl;

    // 2. remove_if 用法: 删除所有偶数
    list1.remove_if([](int n){ return n % 2 == 0; });
    
    cout << "List 1 after remove_if: ";
    for(int x : list1) cout << x << " "; // 输出: 1 3
    cout << endl;
    
    return 0;
}

6. 总结：List vs Vector

特性 std::list std::vector
底层实现 双向链表 (节点分散) 动态数组 (内存连续)
随机访问 ([]) 不支持 支持 $O(1)$
头部插入/删除 $O(1)$ $O(N)$
中间插入/删除 $O(1)$ (前提是已知迭代器) $O(N)$
内存开销 极大 (每个元素存2个指针) 极小
缓存友好性 差 (Cache Miss 高) 优 (连续内存)
迭代器失效 仅被删元素失效 扩容时全部失效