std::list是 C 标准库list中的双向链表容器。它不要求元素连续存储每个元素单独放在一个节点里节点中保存前驱指针、后继指针和实际值。1. 核心特点底层结构双向链表每个节点独立分配。访问元素只能顺序访问不支持随机访问没有operator[]和at()。插入删除在已知迭代器位置插入/删除单个元素是O(1)且不会导致其他元素的迭代器失效。查找按值查找是O(n)。迭代器双向迭代器支持、--但不支持it n、it - n、比较。内存开销每个元素额外保存两个指针通常比std::vector更占内存。缓存友好性节点分散遍历时缓存局部性差通常比vector慢。2. 常用操作cpp#include list std::listint l {1, 2, 3}; l.push_back(4); // 尾部插入 l.push_front(0); // 头部插入 l.pop_back(); // 删除尾部 l.pop_front(); // 删除头部 l.insert(it, 10); // 在 it 前插入返回新元素迭代器 l.emplace(it, 10); // 在 it 前直接构造 l.erase(it); // 删除 it返回下一个迭代器 l.clear(); // 清空 l.front(); // 第一个元素 l.back(); // 最后一个元素 l.empty(); // 是否为空 l.size(); // 元素个数C11 后 O(1)链表特有操作cppl.sort(); // 成员函数稳定排序O(n log n) l.reverse(); // 反转 l.unique(); // 删除连续重复元素通常先 sort l.remove(3); // 删除所有等于 3 的元素 l.remove_if(pred); // 删除所有满足谓词的元素 l.merge(other); // 合并两个有序 list源 list 变空 l.splice(pos, other);// 把 other 的节点移动到 *this不拷贝元素注意std::sort不能用于std::list因为std::sort需要随机访问迭代器。必须用成员函数l.sort()。3. 迭代器失效规则insert、emplace、push_front、push_back不使任何迭代器失效。erase、pop_front、pop_back只使指向被删除元素的迭代器失效。splice、merge、sort、reverse不使迭代器失效只是重新链接节点。clear使所有迭代器失效。这是std::list相比std::vector的一大优势vector插入时可能重新分配导致所有迭代器失效。4. 与 vector 的简单对比特性std::liststd::vector存储非连续双向链表连续动态数组随机访问不支持O(n)支持O(1)中间插入删除O(1)已知位置O(n)迭代器失效插入不失效删除只失效被删插入可能全部失效内存开销每元素两个指针较小可能有预留容量缓存友好差好适用场景频繁中间插入删除、稳定迭代器频繁随机访问、尾部操作、遍历大多数情况下std::vector因为缓存友好实际性能可能更好。只有确实需要频繁在中间插入删除并且已经持有迭代器时std::list才更有优势。#include iostream #include list #include string #include algorithm #include iterator int main() { // 1. 基本操作 std::liststd::string tasks {write, test, deploy}; tasks.push_front(plan); tasks.push_back(monitor); auto it std::find(tasks.begin(), tasks.end(), test); if (it ! tasks.end()) { tasks.insert(it, code); // 在 test 前插入 code } std::cout tasks: ; for (const auto t : tasks) { std::cout t ; } std::cout \n; tasks.remove(deploy); // 删除所有 deploy std::cout after remove: ; for (const auto t : tasks) { std::cout t ; } std::cout \n; // 2. 排序、去重、反转 std::listint nums {3, 1, 2, 2, 5, 4}; nums.sort(); // list 成员函数稳定排序 nums.unique(); // 删除连续重复元素 nums.reverse(); // 反转 std::cout nums: ; for (int n : nums) { std::cout n ; } std::cout \n; // 3. splice把 b 的节点移动到 a 中不拷贝元素 std::listint a {1, 2, 3}; std::listint b {10, 20, 30}; auto pos std::next(a.begin()); // 指向 2 a.splice(pos, b); // 把 b 全部插入到 pos 之前 std::cout a: ; for (int n : a) { std::cout n ; } std::cout \n; std::cout b empty: std::boolalpha b.empty() \n; return 0; }
