基本介绍

在 C++ 标准库（STL）中，std::list 是一个基于双向链表实现的序列容器。它与 std::vector、std::deque 等连续存储容器不同，提供了在序列中高效插入和删除元素的能力，尤其是在序列中间位置操作时优势明显。

1. `std::list` 的底层原理

std::list 是由一组双向链表节点组成，每个节点包含：

元素数据本身
指向前一个节点的指针（prev）
指向后一个节点的指针（next）

整个链表通过节点指针串联起来，头节点的 prev 和尾节点的 next 通常指向特殊的哨兵节点或 nullptr。

结构示意

nullptr <- [Node1] <-> [Node2] <-> [Node3] -> nullptr

链表不保证元素在内存上的连续存储，每个节点单独分配内存。

2. 主要接口和用法

#include <list>
#include <iostream>int main() {std::list<int> lst = {1, 2, 3};// 头部插入lst.push_front(0);// 尾部插入lst.push_back(4);// 插入到指定位置（通过迭代器）auto it = std::next(lst.begin(), 2);lst.insert(it, 99);// 遍历for (auto val : lst) {std::cout << val << " ";}// 输出: 0 1 99 2 3 4// 删除元素lst.remove(99);// 清空lst.clear();return 0;
}

常用接口

push_front / push_back / emplace_front / emplace_back：头尾插入
pop_front / pop_back：头尾删除
insert：在指定位置插入元素
erase：删除指定位置元素
remove / remove_if：删除满足条件的元素
splice：将另一个链表的部分或全部节点移动到当前链表中（无需复制，效率极高）
双向迭代器支持，允许双向遍历

3. 性能特征与对比

操作	`std::list`	`std::vector`	备注
插入/删除头尾	O(1)	头部 O(n)，尾部 O(1)
插入/删除中间	O(1) (有迭代器)	O(n)	`list`不需移动元素
随机访问	不支持（无 `operator[]`）	O(1)	`list`只能顺序访问
内存占用	较大（节点指针额外开销）	较小，连续内存
缓存局部性	差	好	影响访问效率

std::list 适合频繁中间插入/删除，且不需要随机访问的场景。

4. 典型使用场景

需要频繁在序列中间插入、删除元素，且已知具体位置的迭代器（如链表实现的任务队列）
实现算法时需要快速拆分、合并链表（splice 功能）
保持迭代器或引用稳定，插入删除时不会使其他元素迭代器失效（与 vector 不同）

5. 高级用法与优化建议

5.1 利用 `splice` 高效合并链表

splice 是 std::list 独有且非常高效的操作。它允许将另一个链表的节点直接接入当前链表，避免拷贝和内存分配。

std::list<int> a = {1, 2, 3};
std::list<int> b = {4, 5, 6};// 将b的全部节点接入a的末尾，b变为空链表
a.splice(a.end(), b);

5.2 避免不必要的内存分配

每个节点都单独分配内存，频繁插入大量元素时可能导致性能瓶颈。可以考虑：

批量插入，减少频繁的调用
在性能要求极高时，考虑自定义内存池

5.3 迭代器有效性保证

std::list 插入和删除不会使其他节点的迭代器失效，适合要求迭代器长时间稳定的算法。

5.4 避免误用

不要用 std::list 做需要随机访问的场景
不要为了“感觉好”就盲目使用链表，很多时候 std::vector 更优

6. 其他常用成员函数

size()：返回元素个数
empty()：判断是否为空
assign(n, val)：赋值n个val
remove(val)：删除所有等于val的元素
unique()：去除连续重复元素
reverse()：反转链表
sort()：排序

7. 示例：LRU缓存

#include <list>
#include <unordered_map>
using namespace std;class LRUCache {
public:LRUCache(int capacity) : cap(capacity) {}int get(int key) {auto it = mp.find(key);if (it == mp.end()) return -1;cache.splice(cache.begin(), cache, it->second);return it->second->second;}void put(int key, int value) {auto it = mp.find(key);if (it != mp.end()) {it->second->second = value;cache.splice(cache.begin(), cache, it->second);} else {if (cache.size() == cap) {mp.erase(cache.back().first);cache.pop_back();}cache.emplace_front(key, value);mp[key] = cache.begin();}}private:int cap;list<pair<int, int>> cache;unordered_map<int, list<pair<int, int>>::iterator> mp;
};