在现代 C 开发中虽然std::vector足以应付绝大多数的场景但是在某些特定场景下std::list依旧是不可替代的神器。核心概念与底层原理头文件#include list本质双向链表Doubly Linked List内存模型非连续内存。每个元素节点都是独立分配在堆上的节点之间通过指针prev和next连接特点不支持随机访问不能使用下标l[5]访问元素必须从头一个一个遍历过去插入 / 删除极快只要持有了某个位置的迭代器在该位置插入或删除元素的操作是 (1) 的且不需要移动其他元素初始化与构造用法与std::vector非常相似#include list std::listint l1; // 空链表 std::listint l2 {1, 2, 3}; // 列表初始化 std::listint l3(l2); // 拷贝构造 std::listint l4(5, 100); // 5 个 元素全是 100独有的操作优势std::vector做不到的这是std::list存在的理由。由于它是链表它支持一些操作极其高效或者提供了std::vector根本没有的接口。头部操作std::vector在头部插入 / 删除操作极其低效()而std::list则是瞬间完成(1)。push_front(val)头部插入pop_front()头部删除接合Splicing可以将一个std::list的元素全部或部分直接 “剪切” 并 “粘贴” 到另一个std::list中这是纯指针操作没有数据拷贝所以速度极快。std::listint list1 {1, 2, 3}; std::listint list2 {4, 5, 6}; auto it list1.begin(); it; // 指向 2 // 将 list2 的所有元素 “移动” 到 list1 的 2 前面 // list2 变空list1 变为 {1, 4, 5, 6, 2, 3} list1.splice(it, list2);专用成员函数由于std::list无法随机访问标准库算法如std::sort对它无效。因此list自带了一套经过优化的成员函数l.sort()排序稳定排序底层通常是归并排序。注意千万别读std::list用std::sort(l.begin(), l.end())编译会报错l.remove(val)删除所有等于val的元素l.remove_if(pred)删除满足条件的元素l.unique()删除相邻的重复元素去重前通常要先 sortl.reverse()逆置链表l.merge(l2)合并两个已排序的链表l2会变空迭代器特性这是决定选择std::vector还是std::list的关键因素。类型双向迭代器Bidirectional Iterator支持it、--it、*it不支持it 5it other_it不能跳跃不能比较大小稳定性Validity极高掺入操作绝对不会让现有的迭代器失效删除操作只有指向被删除节点的那个迭代器会失效其他的完全不受影响对比std::vectorstd::vector一旦扩容所有迭代器全部失效中间插入后面所有迭代器失效。std::list和std::vector的选择这是一个经典的 Trade-off权衡问题特性std::vectorstd::list随机访问(1)支持[]不支持()尾部插入(1)(1)头部/中间插入()很慢要挪动数据(1)很快前提是有迭代器内存布局连续Cache 命中率高分散Cache 命中率低额外内存较少少量预留空间较大每个元素都要存两个指针迭代器失效容易失效几乎不失效结论95% 的情况用std::vector现代 CPU 的缓存机制非常依赖内存连续性。即使是在中间插入对于小对象如intstd::vector往往也比std::list快因为std::list的遍历会导致大量的 Cache Miss。以下情况可以用std::list需要频繁在头部或中间插入 / 删除且元素总数很多对象非常大拷贝代价极高虽然 C11 移动语义缓解了这个问题核心需求你需要保存指向某个元素的迭代器并且在后续操作中无论怎么插入删除其他元素希望这个迭代器一直有效C11 新增std::forword_listC11 引入了std::forword_list单向链表特点只有next指针没有prev指针优势比std::list更省内存少存一个指针劣势只能向前遍历功能受限场景极其追求内存优化的哈希表桶实现等