list

std::list 是 C++ 标准库中的双向链表容器，提供了高效的插入和删除操作。它的设计核心是“节点”：每个元素都存储在一个独立的节点中，这些节点通过指针连接起来形成链表结构。

和 vector 这类连续内存的顺序容器相比，list 的元素在内存中不连续，因此不支持随机访问（不能直接用下标访问第 i 个元素），但在已知位置附近做插入和删除时通常更稳定、开销更低。

头文件与基本特征

使用 list 时，需要包含头文件：

#include <list>

list 的常见特征如下：

特征	说明
底层结构	双向链表
内存布局	节点分散存储，不连续
随机访问	不支持，不能使用 operator[]
头尾插入删除	高效，通常是常数时间
中间插入删除	在已定位到迭代器后高效
遍历方式	主要通过双向迭代器

基本用法

最常见的声明方式如下：

#include <list>

int main() {
	std::list<int> nums;

	nums.push_back(10);
	nums.push_back(20);
	nums.push_front(5);

	return 0;
}

这段代码会得到一个链表：5 -> 10 -> 20。

交互演示（MDX + React）

在 Docusaurus 里，MDX 可以直接嵌入 React 组件。下面这个小面板可以实时演示 list 常见操作对应的状态变化：

std::list 操作演示面板

用数组模拟链表操作结果，帮助理解 push、insert、splice、merge 等接口的行为。

MDX + React

主链表 A

[10, 20, 30]

辅助链表 B

[5, 15, 25]

nextValue40

A.size()3

B.size()3

基础插入 / 删除

定位与顺序操作

链表间转移

说明：这个交互示例用 JavaScript 数组模拟“操作效果”，用于教学展示 API 行为；真正的 std::list 在 C++ 中是双向链表节点结构。

遍历 list

list 一般使用迭代器遍历：

#include <iostream>
#include <list>

int main() {
	std::list<int> nums;
	nums.push_back(10);
	nums.push_back(20);
	nums.push_back(30);

	for (std::list<int>::iterator it = nums.begin(); it != nums.end(); ++it) {
		std::cout << *it << ' ';
	}
	std::cout << '\n';

	return 0;
}

因为不是连续存储，list 的迭代器只支持前进和后退，不支持 it + n 这样的随机跳转。

常用成员函数

list 常见操作接口如下：

函数	作用
begin() / end()	获取首元素和尾后迭代器
rbegin() / rend()	反向迭代器
empty()	判断是否为空
size()	返回元素个数
front() / back()	访问首元素和尾元素
push_front() / push_back()	头插和尾插
pop_front() / pop_back()	删除头元素和尾元素
insert()	在指定位置前插入
erase()	删除指定位置或区间
clear()	清空容器
remove(value)	删除所有等于 value 的元素
unique()	删除连续重复元素
reverse()	反转链表
sort()	对链表排序
merge()	合并两个有序链表
splice()	在链表间转移节点

插入与删除

list 的优势之一是插入删除灵活，尤其是你已经拿到目标位置迭代器时。

#include <list>

int main() {
	std::list<int> nums;
	nums.push_back(1);
	nums.push_back(3);

	std::list<int>::iterator it = nums.begin();
	++it;
	nums.insert(it, 2);  // 在 3 前插入 2

	it = nums.begin();
	++it;
	nums.erase(it);      // 删除 2

	return 0;
}

在 list 里，除了被删除的节点迭代器本身，其它节点迭代器通常保持有效，这是它相对 vector 的一个优势。

remove、unique 与排序

list 提供了一些链表场景很常用的成员算法。

#include <iostream>
#include <list>

int main() {
	std::list<int> nums;
	nums.push_back(3);
	nums.push_back(1);
	nums.push_back(2);
	nums.push_back(2);
	nums.push_back(3);

	nums.sort();    // 1 2 2 3 3
	nums.unique();  // 1 2 3（仅去掉连续重复）
	nums.remove(2); // 1 3

	for (std::list<int>::iterator it = nums.begin(); it != nums.end(); ++it) {
		std::cout << *it << ' ';
	}
	std::cout << '\n';

	return 0;
}

注意 unique() 只删除相邻重复元素。如果想“全局去重”，一般先 sort() 再 unique()。

splice 与 merge

list 最有特色的接口之一是 splice()，它可以把节点从一个链表直接转移到另一个链表，通常不需要逐个拷贝元素。

#include <iostream>
#include <list>

int main() {
	std::list<int> a;
	a.push_back(1);
	a.push_back(2);

	std::list<int> b;
	b.push_back(10);
	b.push_back(20);

	std::list<int>::iterator pos = a.end();
	a.splice(pos, b);  // 把 b 的全部节点转移到 a 末尾

	for (std::list<int>::iterator it = a.begin(); it != a.end(); ++it) {
		std::cout << *it << ' ';
	}
	std::cout << '\n';

	return 0;
}

merge() 用于合并两个有序链表：

#include <list>

int main() {
	std::list<int> a;
	a.push_back(1);
	a.push_back(3);
	a.push_back(5);

	std::list<int> b;
	b.push_back(2);
	b.push_back(4);
	b.push_back(6);

	a.merge(b);  // 合并后 a: 1 2 3 4 5 6, b 为空

	return 0;
}

使用 merge() 前，两条链表应按同一比较规则有序。

自定义排序规则

list::sort() 可以接收比较器：

#include <list>

struct Greater {
	bool operator()(int lhs, int rhs) const {
		return lhs > rhs;
	}
};

int main() {
	std::list<int> nums;
	nums.push_back(1);
	nums.push_back(3);
	nums.push_back(2);

	nums.sort(Greater());

	return 0;
}

这会按降序排列。

list 与 vector 的选择

可以这样快速判断：

1. 主要需求是随机访问、下标读取、缓存友好遍历：优先 vector。
2. 经常在中间位置插入/删除，并且已有迭代器定位：可以考虑 list。
3. 需要频繁头插头删：list 比 vector 更自然。
4. 数据量大但多为顺序读，插删不多：通常还是 vector 更常见。

使用注意

1. list 不支持下标访问，不要写 nums[i]。
2. list 的 sort() 是成员函数，不要直接用依赖随机访问迭代器的 std::sort(nums.begin(), nums.end())。
3. unique() 只去除连续重复元素。
4. merge() 和 splice() 会改变源链表内容，调用后源容器可能变空或局部被转移。
5. 链表节点分散存储，虽然插删灵活，但遍历局部性通常不如 vector。

小结

std::list 适合“频繁插删、特别是中间和头部插删”的场景。它通过双向链表提供稳定的节点操作能力，并且有 splice、merge 这类顺序容器不具备的接口。掌握迭代器遍历、插删、排序和去重后，就能覆盖大多数 list 的日常使用场景。