STL:list

list 是什么？

list 本质是：双向链表

std::list<int> l = {1,2,3};

底层结构

nullptr <- [1] <-> [2] <-> [3] -> nullptr

特点：

不连续内存

每个节点单独分配（malloc/new）

list 的核心特性

插入/删除超级快

auto it = l.begin(); l.insert(it, 10); l.erase(it);

时间复杂度：O(1)

原因：
只需要改指针，不用移动数据

不支持随机访问

l[0]; ❌ 不存在

只能：

auto it = l.begin(); ++it;

时间复杂度： O(n)

迭代器稳定

auto it = l.begin(); l.push_back(10); // it 仍然有效 ✅

原因：
 每个节点独立，不会搬家！

list 常用接口

插入

l.push_back(10); l.push_front(5); l.insert(it, 100);

删除

l1.merge(l2);

l.pop_back(); l.pop_front(); l.erase(it); l.remove(10); // 删除所有值为10的

特有操作（vector 没有）

splice（链表拼接）

list<int> l1 = {1,2,3}; list<int> l2 = {4,5}; l1.splice(l1.begin(), l2);

结果：

l1:   4 5 1 2 3
l2:    空

时间复杂度：O(1)

merge（有序链表合并）

l1.merge(l2);

sort（链表排序）

l.sort();

注意：
  std::sort 不能用在 list 上！

为什么 list 很少用？

虽然 O(1) 插入很诱人，但实际：

 缺点很多：

cache 不友好

节点分散，CPU 访问慢

内存浪费

每个节点多两个指针

 malloc 开销大

每次插入都要分配内存