C++ STL list 容器详解（2026 年竞赛/项目实用版）
list 是 STL（Standard Template Library）中最经典的双向链表容器，底层是循环双向链表（非单向），支持高效的插入/删除（O(1)），但不支持随机访问（不像 vector）。适合频繁增删的场景，如队列模拟、LRU 缓存等。
我们分成两大块学（由浅入深）：
- 基础知识 + 使用详解（80% 时间够用）
- 模拟实现（底层源码风格，帮你理解原理 + 面试加分）
先说优缺点对比（为什么用 list 而不用 vector/deque？）
| 容器 | 底层结构 | 插入/删除（中间） | 随机访问 | 空间连续 | 典型场景 |
|---|---|---|---|---|---|
| list | 双向链表 | O(1) | O(n) | 非连续 | 频繁增删、不需随机访问 |
| vector | 动态数组 | O(n) | O(1) | 连续 | 随机访问、尾部增删 |
| deque | 双端队列（块数组） | O(1)（两端） | O(1) | 非连续 | 双端操作 + 随机访问 |
一句话记忆：list 是“链式存储”，每个元素独立节点，增删只改指针，不移数据。
1. 基础知识 + 使用详解
1.1 头文件与声明
#include <list> // 必须包含
using namespace std;
list<int> lst; // 空 list（模板类，支持任意类型 T）
list<string> strLst = {"apple", "banana"}; // 初始化列表（C++11+）1.2 构造方式（常见4种）
list<int> lst1; // 空
list<int> lst2(5, 10); // 5 个 10
list<int> lst3(lst2.begin(), lst2.end()); // 拷贝另一 list 或范围
list<int> lst4 = {1, 2, 3}; // 初始化列表（C++11+）1.3 常用成员函数一览表（按类别分，背下来90%够用）
| 类别 | 函数示例 | 作用 + 时间复杂度 | 注意点 |
|---|---|---|---|
| 大小/判空 | size() / empty() | 返回大小 / 是否空，O(1) | size() 是 O(1)，不像旧版 O(n) |
| 访问 | front() / back() | 首/尾元素引用，O(1) | 无 [] 或 at()，不支持随机访问 |
| 插入 | push_front(x) / push_back(x) | 头/尾插入，O(1) | 双向都快 |
| insert(it, x) / insert(it, n, x) | 指定位置前插入 1/n 个 x，O(1) | it 是迭代器 | |
| 删除 | pop_front() / pop_back() | 删头/尾，O(1) | 无参数，返回 void |
| erase(it) / erase(first, last) | 删迭代器/范围，O(1) 或 O(k) | 返回下一个迭代器 | |
| clear() | 清空，O(n) | – | |
| 修改 | remove(x) | 删所有等于 x 的，O(n) | 全局扫描 |
| unique() | 删连续重复，O(n) | 先 sort() 再 unique() 去重 | |
| swap(other) | 交换两个 list，O(1) | 只换头尾指针 | |
| 排序/反转 | sort() / reverse() | 稳定排序 / 反转，O(n log n) / O(n) | sort() 是成员函数，非 std::sort |
| 合并/转移 | merge(other) | 合并已排序的 other，O(n) | other 清空 |
| splice(it, other) / splice(it, other, srcIt) | 转移 other 全部/单个到 it 前，O(1) | 高效转移，不拷贝 | |
| 迭代器 | begin() / end() / rbegin() / rend() | 正/反向迭代器 | 双向迭代器（bidirectional） |
迭代器注意：list 的迭代器是双向的（++it / –it 都行），但失效规则宽松：只在 erase(it) 时失效该 it，其他操作不影响。
1.4 代码实战示例（敲一遍就懂）
基本操作：
#include <bits/stdc++.h>
using namespace std;
int main() {
list<int> lst = {1, 2, 3};
lst.push_front(0); // {0,1,2,3}
lst.push_back(4); // {0,1,2,3,4}
auto it = lst.begin();
++it; // 指向 1
lst.insert(it, 10); // {0,10,1,2,3,4}
lst.erase(it); // 删 1 → {0,10,2,3,4}，it 失效，但 erase 返回下一个 (2)
lst.remove(10); // 删所有 10 → {0,2,3,4}
lst.sort(); // {0,2,3,4}
lst.reverse(); // {4,3,2,0}
cout << lst.front() << " " << lst.back() << endl; // 4 0
// 遍历（正向）
for (auto& x : lst) cout << x << " "; // 4 3 2 0
cout << endl;
// 反向遍历
for (auto it = lst.rbegin(); it != lst.rend(); ++it) {
cout << *it << " "; // 0 2 3 4
}
}高级：合并 + 去重：
list<int> a = {1, 3, 5};
list<int> b = {2, 4, 4};
a.sort(); b.sort(); // 必须先排序
a.merge(b); // a={1,2,3,4,4,5}, b 清空
a.unique(); // a={1,2,3,4,5} 删连续重复1.5 使用Tips & 防坑
- 不适合随机访问：想访问第 k 个？用 advance(it, k)，但 O(k)，慢！
- 与 vector 互转：
vector<int> vec(lst.begin(), lst.end()); - 多线程：STL list 非线程安全，加锁用。
- 性能：插入/删 O(1)，但遍历 O(n)，空间多用（每个节点有 prev/next 指针）。
- C++11+：支持 emplace_front/back/insert（就地构造，省拷贝）。
2. 模拟实现（底层原理 + 简易版代码）
STL list 底层是带哨兵节点的循环双向链表：
- 节点：struct Node { T data; Node* prev; Node* next; };
- 哨兵（head/tail）：一个 dummy 节点，head->next 是第一个，tail->prev 是最后一个，head->prev = tail, tail->next = head（循环）。
- 为什么循环？简化边界：空 list 时 head->next = tail, tail->prev = head。
简易模拟实现（非完整 STL，只核心函数，帮你理解）：
template <typename T>
class MyList {
private:
struct Node {
T data;
Node* prev;
Node* next;
Node(const T& val = T()) : data(val), prev(nullptr), next(nullptr) {}
};
Node* head; // 哨兵头
Node* tail; // 哨兵尾（实际 STL 合并成一个，但分开易懂）
size_t sz; // 大小
public:
MyList() : sz(0) {
head = new Node();
tail = new Node();
head->next = tail;
tail->prev = head;
}
~MyList() { clear(); delete head; delete tail; }
void clear() {
Node* cur = head->next;
while (cur != tail) {
Node* tmp = cur;
cur = cur->next;
delete tmp;
}
head->next = tail;
tail->prev = head;
sz = 0;
}
size_t size() const { return sz; }
bool empty() const { return sz == 0; }
void push_back(const T& val) {
Node* node = new Node(val);
node->prev = tail->prev;
node->next = tail;
tail->prev->next = node;
tail->prev = node;
++sz;
}
void push_front(const T& val) {
Node* node = new Node(val);
node->next = head->next;
node->prev = head;
head->next->prev = node;
head->next = node;
++sz;
}
void pop_back() {
if (empty()) return;
Node* tmp = tail->prev;
tail->prev = tmp->prev;
tmp->prev->next = tail;
delete tmp;
--sz;
}
void pop_front() {
if (empty()) return;
Node* tmp = head->next;
head->next = tmp->next;
tmp->next->prev = head;
delete tmp;
--sz;
}
T& front() { return head->next->data; }
T& back() { return tail->prev->data; }
// 简单迭代器（只正向，实际 STL 双向）
class iterator {
public:
Node* ptr;
iterator(Node* p = nullptr) : ptr(p) {}
T& operator*() { return ptr->data; }
iterator& operator++() { ptr = ptr->next; return *this; }
bool operator!=(const iterator& other) { return ptr != other.ptr; }
};
iterator begin() { return iterator(head->next); }
iterator end() { return iterator(tail); }
// 插入（在 pos 前插）
iterator insert(iterator pos, const T& val) {
Node* node = new Node(val);
node->prev = pos.ptr->prev;
node->next = pos.ptr;
pos.ptr->prev->next = node;
pos.ptr->prev = node;
++sz;
return iterator(node);
}
// 删除
iterator erase(iterator pos) {
if (pos == end()) return end();
Node* tmp = pos.ptr;
iterator next(tmp->next);
tmp->prev->next = tmp->next;
tmp->next->prev = tmp->prev;
delete tmp;
--sz;
return next;
}
};使用模拟版示例：
MyList<int> ml;
ml.push_back(1); ml.push_back(2);
ml.push_front(0); // {0,1,2}
auto it = ml.begin();
++it; // 指向 1
ml.insert(it, 10); // {0,10,1,2}
ml.erase(it); // 删 1 → {0,10,2}
for (auto x : ml) cout << x << " "; // 需要实现 range-based for（加 const_iterator 等）模拟Tips：
- 内存管理：new/delete，手动防泄漏（实际 STL 用 allocator）。
- 完整版：需加 const_iterator、reverse_iterator、sort（归并排序）、等。
- 为什么哨兵？避免空 list 特判：push_back 时 tail->prev 总是合法。
- 面试点：问“list sort 为什么不用 quicksort？”答：链表不支持随机访问，归并排序适合。
你现在最想练哪部分？
- 多看几个使用例子（e.g., LRU 缓存模拟）？
- 模拟实现的完整版（加 sort/merge）？
- 与 forward_list（单向链表）对比？
- 还是来几道 OJ 题练手（e.g., 链表反转）？
告诉我，继续陪你深挖～ 😊
