C中的list是什么意思？

目录核心概念与底层原理初始化与构造独有的操作优势（std::vector 做不到的）头部操作接合（Splicing）专用成员函数迭代器特性std::list 和 std::vector 的选择C++11 新增：std::forword_list 本文首发于我的个人博客：Better Mistakes 版权声明：本文为原创文章，转载请附上原文出处链接及本声明。 由于技术迭代较快，文章内容可能随时更新（含勘误及补充）。为了确保您看到的是最新版本，并获得更好的代码阅读体验，请访问： 🍭 原文链接：https://bfmhno3.github.io/note/list-in-cpp/ 在现代 C++ 开发中，虽然 std::vector 足以应付绝大多数的场景，但是在某些特定场景下，std::list 依旧是不可替代的神器。 核心概念与底层原理 头文件：#include <list> 本质：双向链表（Doubly Linked List） 内存模型：非连续内存。每个元素（节点）都是独立分配在堆上的，节点之间通过指针（prev 和 next）连接 特点： 不支持随机访问：不能使用下标 l[5] 访问元素，必须从头一个一个遍历过去 插入 / 删除极快：只要持有了某个位置的迭代器，在该位置插入或删除元素的操作是 \(O(1)\) 的，且不需要移动其他元素 初始化与构造 用法与 std::vector 非常相似： #include <list> std::list<int> l1; // 空链表 std::list<int> l2 = {1, 2, 3}; // 列表初始化 std::list<int> l3(l2); // 拷贝构造 std::list<int> l4(5, 100); // 5 个 元素，全是 100 独有的操作优势（std::vector 做不到的） 这是 std::list 存在的理由。由于它是链表，它支持一些操作极其高效，或者提供了 std::vector 根本没有的接口。 头部操作 std::vector 在头部插入 / 删除操作极其低效（\(O(N)\)），而 std::list 则是瞬间完成（\(O(1)\)）。 push_front(val)：头部插入 pop_front()：头部删除 接合（Splicing） 可以将一个 std::list 的元素（全部或部分）直接 “剪切” 并 “粘贴” 到另一个 std::list 中，这是纯指针操作，没有数据拷贝，所以速度极快。 std::list<int> list1 = {1, 2, 3}; std::list<int> 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()：删除相邻的重复元素（去重前通常要先 sort） l.reverse()：逆置链表 l.merge(l2)：合并两个已排序的链表（l2 会变空） 迭代器特性 这是决定选择 std::vector 还是 std::list 的关键因素。 类型：双向迭代器（Bidirectional Iterator） 支持：++it、--it、*it 不支持：it + 5，it < other_it（不能跳跃，不能比较大小） 稳定性（Validity）：极高 掺入操作：绝对不会让现有的迭代器失效 删除操作：只有指向被删除节点的那个迭代器会失效，其他的完全不受影响 对比 std::vector：std::vector 一旦扩容，所有迭代器全部失效；中间插入，后面所有迭代器失效。