C++STL中list的使用详解

博主：小蓝
发布时间：2025 年 09 月 13 日
74 次浏览
暂无评论
595字数
分类： Linux 技术杂烩

下面把 C++ STL 中的 std::list（双向链表）从“何时用、怎么用、易踩坑”一次讲清，并给出可直接运行的小例子与对照表 ✅

## 一、核心结论（先给答案）🙂

* std::list 适合**频繁在已知位置插入/删除**、需要 O(1) **拼接/剪切**（`splice`）的场景。
* 不适合随机访问（没有 `operator[]`，迭代器是**双向**）。
* 自 C++11 起，`size()` 为 O(1)；插入/删除不会使其它元素的**指针/引用/迭代器失效**（除被操作的那些）。
* 由于节点分散，**缓存亲和性差**，遍历/排序常不如 `vector` 快。

---

## 二、最小用法：增删查遍历（可直接运行）🚀

```cpp
#include <list>
#include <iostream>
using namespace std;

int main() {
    list<int> L = {3, 1, 4};
    L.push_front(2);     // 头插
    L.push_back(5);      // 尾插
    auto it = L.begin(); ++it;
    L.insert(it, 9);     // 在第二个位置前插入 9
    for (int x : L) cout << x << ' '; // 遍历
    cout << "\nsize=" << L.size() << endl;
}
```

**解释**：

* `push_front/push_back/insert` 都是 已知迭代器位置的 O(1) 操作（定位迭代器本身可能是 O(n)）。
* `for (int x : L)` 使用范围 for 遍历；`size()` 在 C++11+ 为 O(1)。

---

## 三、边遍历边删除的正确写法（避免迭代器失效）🧩

```cpp
#include <list>
#include <iostream>
using namespace std;

int main() {
    list<int> L = {1,2,3,4,5,6};
    for (auto it = L.begin(); it != L.end(); ) {
        if (*it % 2 == 0) it = L.erase(it);  // erase 返回“下一个”迭代器
        else ++it;
    }
    for (int x : L) cout << x << ' '; // 1 3 5
}
```

**解释**：

* `erase` 仅使**被删除元素**的迭代器失效，其它元素迭代器仍有效；**必须**用返回值继续遍历，避免跳过元素或解引用失效。

---

## 四、list 的王牌：splice/merge/sort/unique/remove

```cpp
#include <list>
#include <iostream>
using namespace std;

int main() {
    list<int> A = {1,3,5}, B = {2,4,6,6};
    auto pos = next(A.begin());     // 指向元素 3
    A.splice(pos, B);               // O(1) 把 B 所有节点“接入”到 A 的 pos 前
    A.sort();                       // 就地归并排序，稳定（链表专属）
    A.unique();                     // 去相邻重复（需要已排序以去重所有重复）
    list<int> C = {7,8,9};
    A.splice(A.end(), C, C.begin()); // O(1) 移动 C 的首节点到 A 尾部
    for (int x : A) cout << x << ' ';
}
```

**解释**：

* `splice` 是 list 的杀手锏：**不拷贝、不移动元素**，仅改指针即可把**整段/单个节点**在两个 `list` 间挪动，复杂度 O(1)（两容器类型与分配器兼容）。
* `sort()` 针对链表实现的**归并排序**，复杂度 `O(n log n)`，**稳定**；不同于 `std::sort`（需要随机访问）。
* `unique()` 仅去**相邻**重复；若要彻底去重，请先 `sort()` 再 `unique()`。
* `remove(v)` / `remove_if(pred)` 直接遍历删除匹配元素，等价于 `erase-remove` 惯用法，但 list 自带更优接口。

---

## 五、何时选 list？一图决策

```mermaid
flowchart LR
A[是否需要随机访问?] -->|是| V[vector/deque 更合适]
A -->|否| B[是否大量在中间位置插入/删除?]
B -->|是| C[优先 <span style="color:red">list</span>]
B -->|否| D[是否需要 O(1) 跨容器拼接?]
D -->|是| C
D -->|否| V
```

---

## 六、对比速查表（vditor/Markdown 支持）

| 能力/容器        | list               | vector                | deque  |
| ---------------- | ------------------ | --------------------- | ------ |
| 随机访问         | 否                 | 是                    | 部分   |
| 中间插入/删除    | O(1)（已定位）     | O(n)                  | O(n)   |
| 末端插入/删除    | O(1)               | 摊销 O(1)/尾删 O(1)   | O(1)   |
| `splice`跨容器 | O(1)               | 不支持                | 不支持 |
| 迭代器稳定性     | 稳定（除被删节点） | 扩容/插入可能全部失效 | 中     |
| 遍历性能/缓存    | 较差               | 较好                  | 一般   |
| `size()`复杂度 | O(1)（C++11+）     | O(1)                  | O(1)   |

---

## 七、常见坑与优化建议 ⚠️

* **排序**：不要对 `list` 用 `std::sort`，应使用 `list::sort`。
* **彻底去重**：先 `sort()` 再 `unique()`，否则只能去掉**相邻**重复。
* **性能误区**：中间插入虽是 O(1)，但**遍历到插入点是 O(n)**；若需要按索引频繁定位，`vector` 更快。
* **内存开销**：每个节点额外两个指针，**高碎片**；大量小元素时需权衡。
* **线程**：与大多数 STL 容器一样，**多线程需外部同步**。

---

## 八、应用小抄（代码片段与解释）

```cpp
// 1) 就地构造（避免拷贝/移动）：emplace_* 家族
list<pair<int,string>> L;
L.emplace_back(1, "one");   // 直接在尾部构造 pair<int,string>
L.emplace_front(0, "zero"); // 直接在头部构造
```

**解释**：`emplace_*` 传构造参数到节点内，避免临时对象，利于性能与异常安全。

```cpp
// 2) 范围插入与拼接
list<int> a = {1,2,3}, b = {4,5,6};
a.insert(next(a.begin()), {9,9});       // 在第二个位置前插入两个 9
a.splice(a.end(), b, b.begin(), b.end()); // 把 b 的所有节点接到 a 尾部（b 清空）
```

**解释**：`insert` 复制/移动元素；`splice` 零拷贝移动**节点本身**，保持引用/指针有效。

```cpp
// 3) 自定义比较/去重策略
list<string> s = {"A","a","B","b","b"};
s.sort([](auto& x, auto& y){ return strcasecmp(x.c_str(), y.c_str()) < 0; });
s.unique([](auto& x, auto& y){ return strcasecmp(x.c_str(), y.c_str()) == 0; });
```

**解释**：自定义比较器/等价器，配合 `sort+unique` 完成**不区分大小写**的排序与去重。

---

## 九、一句话总结

当你需要**稳定迭代器**、**O(1) 拼接剪切**、**频繁在已知位置改链**时，选 std::list；若关注**遍历/随机访问性能**，优先考虑 `vector/deque`。合理取舍，效率与可维护性两全 ✨