前言std::list头文件list是 C 标准库里的双向链表doubly linked list。 它最核心的特性只有一句话在任意位置插入和删除元素都是常数时间且除了被删除的那个迭代器 其他迭代器和指向元素的引用全部保持有效。大多数人对它的误解集中在两头。一头是把list当成更慢的vector 觉得既然vector有连续内存和缓存局部性list就没有存在价值 另一头是以为list是万能容器到处都用它结果在只需要尾部追加的场景下 白白付出每个元素两个指针的空间代价和一次次缓存缺失。list真正的价值在三个场景一是在中间频繁插入删除不用像vector那样搬移整段 二是元素很大或者是不可拷贝的插入删除时不想付出移动/拷贝成本 三是需要迭代器稳定性比如把迭代器存在别处、以后再回来操作这个元素。 本文讲清它的成员函数、独门武器splice/sort/merge/unique以及那些真会踩的坑。一、结构、复杂度与迭代器类别std::list的迭代器是双向迭代器bidirectional iterator支持和-- 但不支持it n、it - n、it[n]也不能用比较两个迭代器。 要在list上移动 n 步必须用std::advanceiterator或std::next复杂度是 O(n)。以 libstdc 为例它的std::list是带哨兵节点sentinel的双向循环链表 每个元素一个节点节点里除了数据就是next和prev两个指针。std::list的size()从 C11 起保证常数复杂度C98 允许某些实现做成线性。操作std::vectorstd::list尾部追加均摊 O(1)O(1)头部插入O(n)O(1)中间插入已有迭代器O(n)要搬移O(1)按值查找O(n)O(n)随机访问v[i]O(1)不支持每个元素的额外开销无两个指针实现相关缓存局部性好连续内存差节点分散插入是否失效迭代器是可能全部失效否删除是否失效迭代器被删位置之后全部失效只有被删的那个失效二、常用成员函数std::list的成员函数大致分四组类别成员函数构造与容量list()、size()、empty()、max_size()、clear()元素访问front()、back()修改push_front、push_back、pop_front、pop_back、emplace_front、emplace_back、emplace、insert、erase、resize、assign、swap链表专属splice、sort、merge、remove、remove_if、unique、reverse几个版本细节值得留意erase从 C11 起返回被删元素的下一个迭代器C98 返回void因此it l.erase(it);是惯用法。emplace_front和emplace_back从C17起返回新元素的引用push_front/push_back一直返回void。insert(pos, value)里定位是 O(n)要靠遍历走到pos只有插入本身是 O(1)。list没有operator[]也没有随机访问。三、独门武器splice、sort、merge、unique这四个成员函数是std::list区别于其他容器的关键。splice把一个链表或其中一段的节点整体摘到另一个链表上。 它不拷贝也不移动元素内容只改指针所以是常数时间整段范围版本是线性的因为要数长度。 这是把元素从一个容器移到另一个容器最便宜的方式void splice(const_iterator pos, list other); // 整个 othervoid splice(const_iterator pos, list other, const_iterator it); // 单个元素void splice(const_iterator pos, list other, const_iterator first, const_iterator last); // 区间前置条件有三个都必须满足other是右值引用版本同理 两条链表的get_allocator()必须相等否则行为未定义 区间版本里pos不能落在[first, last)内否则行为未定义 单元素版本里如果pos it或pos it函数什么都不做。sort是链表版本的排序。它不能换成std::sort因为std::sort需要随机访问迭代器 拿std::list的迭代器去调用会直接编译失败。成员sort是稳定stable的 复杂度 O(N log N) 次比较整个过程只改指针、不搬移元素libstdc 的实现是自底向上的归并排序。merge把另一条已排序的链表合并进来稳定且不拷贝元素。前提是两条链表都已按 同一个比较器排好序标准以前置条件的形式给出不满足时行为未定义 在 GCC/Clang 的实现里如果传进来的是自己函数什么都不做。unique只删除相邻的重复元素。不先排序的话它只能去掉连续出现的重复 分散在链表各处的相同元素一个都去不掉。它返回void接受一个可选的二元谓词。另外要注意remove/remove_if是成员函数返回void语义是删除所有满足条件的元素 和算法库里的std::remove/std::remove_if完全是两回事——后者不改变容器大小。四、完整示例// 适用C17GCC 13 / Clang 17 / MSVC 19.3x 均可编译// 编译g -stdc17 -Wall -Wextra -pedantic list_demo.cpp -o list_demo#include iterator // std::advance#include iostream#include list#include stringtemplate class Tvoid print(const std::string title, const std::listT l) {std::cout title : ;for (const T v : l) {std::cout v ;}std::cout (size l.size() )\n;}int main() {std::liststd::string a{cat, dog, fish};std::liststd::string b{ant, bee, cow};print(a, a);print(b, b);// 1) 插入。emplace_front / emplace_back 在 C17 起返回新元素的引用a.emplace_front(bat);a.emplace_back(std::string(eel));auto pos a.begin();std::advance(pos, 2); // list 迭代器没有 it n必须用 std::advancea.insert(pos, duck);print(a 插入后, a);// 2) splice把 b 的节点整体摘到 a 中不拷贝字符串b 变空auto where a.begin();where; // where 指向 cata.splice(where, b); // b 的所有元素插到 where 之前print(a splice 后, a);print(b splice 后, b);// 3) sort必须用成员版本比较器须满足严格弱序a.sort(); // 无参版本用 operator 升序print(a 排序后, a);// 4) unique只删相邻重复所以要先 sorta.insert(a.end(), cat);a.sort();a.unique();print(a unique 后, a);// 5) remove_if删除所有满足谓词的元素成员函数版本a.remove_if([](const std::string s) { return s.size() 3; });print(a 删除长度 3 后, a);// 6) 迭代器稳定性只删第一个元素指向其他元素的迭代器仍然有效auto anchored a.begin();anchored; // 指向第二个元素a.erase(a.begin()); // 只让 a.begin() 失效if (anchored ! a.end()) {std::cout erase 后锚点仍有效: *anchored \n;}// 7) merge两条已排序链表合并稳定被合并方变空std::liststd::string c{apple, banana};a.sort();c.sort();a.merge(c);print(a merge 后, a);print(c merge 后, c);return 0;}程序里每一步的结果b在splice后为空、unique前必须先sort、merge后源链表被清空都是std::list语义的直接体现跑一遍比读十遍记得更牢。常见坑点用std::sort排std::list❌std::sort(l.begin(), l.end());——std::sort要求随机访问迭代器list的迭代器是双向的 编译期就报错典型信息是找不到operator-。✅l.sort();或l.sort(comp);—— 用成员版本稳定且不搬移元素。unique之前没排序❌std::listint l{1, 2, 1, 2, 1}; l.unique();—— 结果还是1 2 1 2 1因为都不相邻。✅l.sort(); l.unique();—— 先排序让重复元素相邻。把list.remove和std::remove搞混❌std::remove(l.begin(), l.end(), 3);—— 算法版本不改变容器大小 只是把不匹配的元素往前挪尾部留下待删除的残骸。✅l.remove(3);—— 成员版本真的删除所有等于 3 的元素并更新size()。在splice的区间版本里把pos放在区间内❌l.splice(it, l, it, l.end());——pos落在[first, last)内这是未定义行为。✅ 让pos明确落在区间之外例如l.splice(l.end(), l, l.begin(), it);——pos是l.end()不在区间[l.begin(), it)里last本身不包含在区间内恒成立。跨分配器splice❌ 两条list用了不同的分配器例如一个是std::pmr::list绑到 pool A 另一个绑到 pool B仍直接splice—— 行为未定义。✅ 只对get_allocator()相等的两条链表做splice。边遍历边 erase 却不接管返回值❌for (auto it l.begin(); it ! l.end(); it) { if (bad(*it)) l.erase(it); }——it已经失效it是未定义行为症状通常是崩溃或跳过元素。✅for (auto it l.begin(); it ! l.end(); ) { if (bad(*it)) it l.erase(it); else it; }以为list的迭代器永远有效❌ 删除某元素后继续使用指向那个元素的迭代器 —— 它已经失效解引用是未定义行为。✅ 记住规则list的插入和splice不失效任何迭代器erase只失效被删元素的迭代器前提是这个元素确实还在链表里。在只需要尾部追加的场景硬用list❌ 把list当通用容器存十万个int然后逐个遍历求和 —— 每个节点多两个指针 节点在堆上分散遍历时缓存缺失远多于std::vector。✅ 需要顺序遍历、随机访问或连续内存时用std::vector 只有在中间频繁插入删除或必须保持迭代器稳定时才选std::list。总结主题关键结论迭代器类别双向迭代器没有/-/[]定位要std::advance插入删除已有迭代器时 O(1)且不失效其他迭代器splice常数时间搬运节点但要求分配器相同、pos不在被搬运区间内sort必须用成员版本稳定只改指针merge两条链表都要已排序合并后源链表变空unique只删相邻重复通常要先sort选型中间频繁增删、元素大、要迭代器稳定时选它否则优先vectorstd::list不是一个更好的vector而是一个在特定维度上做交换的容器 它用每个元素两个指针的额外空间、以及更差的缓存局部性 换来了常数时间的中间插入删除和极强的迭代器稳定性。 想清楚你的程序到底需要哪一边选型就不会纠结了。
前言std::list头文件list是 C 标准库里的双向链表doubly linked list。 它最核心的特性只有一句话在任意位置插入和删除元素都是常数时间且除了被删除的那个迭代器 其他迭代器和指向元素的引用全部保持有效。大多数人对它的误解集中在两头。一头是把list当成更慢的vector 觉得既然vector有连续内存和缓存局部性list就没有存在价值 另一头是以为list是万能容器到处都用它结果在只需要尾部追加的场景下 白白付出每个元素两个指针的空间代价和一次次缓存缺失。list真正的价值在三个场景一是在中间频繁插入删除不用像vector那样搬移整段 二是元素很大或者是不可拷贝的插入删除时不想付出移动/拷贝成本 三是需要迭代器稳定性比如把迭代器存在别处、以后再回来操作这个元素。 本文讲清它的成员函数、独门武器splice/sort/merge/unique以及那些真会踩的坑。一、结构、复杂度与迭代器类别std::list的迭代器是双向迭代器bidirectional iterator支持和-- 但不支持it n、it - n、it[n]也不能用比较两个迭代器。 要在list上移动 n 步必须用std::advanceiterator或std::next复杂度是 O(n)。以 libstdc 为例它的std::list是带哨兵节点sentinel的双向循环链表 每个元素一个节点节点里除了数据就是next和prev两个指针。std::list的size()从 C11 起保证常数复杂度C98 允许某些实现做成线性。操作std::vectorstd::list尾部追加均摊 O(1)O(1)头部插入O(n)O(1)中间插入已有迭代器O(n)要搬移O(1)按值查找O(n)O(n)随机访问v[i]O(1)不支持每个元素的额外开销无两个指针实现相关缓存局部性好连续内存差节点分散插入是否失效迭代器是可能全部失效否删除是否失效迭代器被删位置之后全部失效只有被删的那个失效二、常用成员函数std::list的成员函数大致分四组类别成员函数构造与容量list()、size()、empty()、max_size()、clear()元素访问front()、back()修改push_front、push_back、pop_front、pop_back、emplace_front、emplace_back、emplace、insert、erase、resize、assign、swap链表专属splice、sort、merge、remove、remove_if、unique、reverse几个版本细节值得留意erase从 C11 起返回被删元素的下一个迭代器C98 返回void因此it l.erase(it);是惯用法。emplace_front和emplace_back从C17起返回新元素的引用push_front/push_back一直返回void。insert(pos, value)里定位是 O(n)要靠遍历走到pos只有插入本身是 O(1)。list没有operator[]也没有随机访问。三、独门武器splice、sort、merge、unique这四个成员函数是std::list区别于其他容器的关键。splice把一个链表或其中一段的节点整体摘到另一个链表上。 它不拷贝也不移动元素内容只改指针所以是常数时间整段范围版本是线性的因为要数长度。 这是把元素从一个容器移到另一个容器最便宜的方式void splice(const_iterator pos, list other); // 整个 othervoid splice(const_iterator pos, list other, const_iterator it); // 单个元素void splice(const_iterator pos, list other, const_iterator first, const_iterator last); // 区间前置条件有三个都必须满足other是右值引用版本同理 两条链表的get_allocator()必须相等否则行为未定义 区间版本里pos不能落在[first, last)内否则行为未定义 单元素版本里如果pos it或pos it函数什么都不做。sort是链表版本的排序。它不能换成std::sort因为std::sort需要随机访问迭代器 拿std::list的迭代器去调用会直接编译失败。成员sort是稳定stable的 复杂度 O(N log N) 次比较整个过程只改指针、不搬移元素libstdc 的实现是自底向上的归并排序。merge把另一条已排序的链表合并进来稳定且不拷贝元素。前提是两条链表都已按 同一个比较器排好序标准以前置条件的形式给出不满足时行为未定义 在 GCC/Clang 的实现里如果传进来的是自己函数什么都不做。unique只删除相邻的重复元素。不先排序的话它只能去掉连续出现的重复 分散在链表各处的相同元素一个都去不掉。它返回void接受一个可选的二元谓词。另外要注意remove/remove_if是成员函数返回void语义是删除所有满足条件的元素 和算法库里的std::remove/std::remove_if完全是两回事——后者不改变容器大小。四、完整示例// 适用C17GCC 13 / Clang 17 / MSVC 19.3x 均可编译// 编译g -stdc17 -Wall -Wextra -pedantic list_demo.cpp -o list_demo#include iterator // std::advance#include iostream#include list#include stringtemplate class Tvoid print(const std::string title, const std::listT l) {std::cout title : ;for (const T v : l) {std::cout v ;}std::cout (size l.size() )\n;}int main() {std::liststd::string a{cat, dog, fish};std::liststd::string b{ant, bee, cow};print(a, a);print(b, b);// 1) 插入。emplace_front / emplace_back 在 C17 起返回新元素的引用a.emplace_front(bat);a.emplace_back(std::string(eel));auto pos a.begin();std::advance(pos, 2); // list 迭代器没有 it n必须用 std::advancea.insert(pos, duck);print(a 插入后, a);// 2) splice把 b 的节点整体摘到 a 中不拷贝字符串b 变空auto where a.begin();where; // where 指向 cata.splice(where, b); // b 的所有元素插到 where 之前print(a splice 后, a);print(b splice 后, b);// 3) sort必须用成员版本比较器须满足严格弱序a.sort(); // 无参版本用 operator 升序print(a 排序后, a);// 4) unique只删相邻重复所以要先 sorta.insert(a.end(), cat);a.sort();a.unique();print(a unique 后, a);// 5) remove_if删除所有满足谓词的元素成员函数版本a.remove_if([](const std::string s) { return s.size() 3; });print(a 删除长度 3 后, a);// 6) 迭代器稳定性只删第一个元素指向其他元素的迭代器仍然有效auto anchored a.begin();anchored; // 指向第二个元素a.erase(a.begin()); // 只让 a.begin() 失效if (anchored ! a.end()) {std::cout erase 后锚点仍有效: *anchored \n;}// 7) merge两条已排序链表合并稳定被合并方变空std::liststd::string c{apple, banana};a.sort();c.sort();a.merge(c);print(a merge 后, a);print(c merge 后, c);return 0;}程序里每一步的结果b在splice后为空、unique前必须先sort、merge后源链表被清空都是std::list语义的直接体现跑一遍比读十遍记得更牢。常见坑点用std::sort排std::list❌std::sort(l.begin(), l.end());——std::sort要求随机访问迭代器list的迭代器是双向的 编译期就报错典型信息是找不到operator-。✅l.sort();或l.sort(comp);—— 用成员版本稳定且不搬移元素。unique之前没排序❌std::listint l{1, 2, 1, 2, 1}; l.unique();—— 结果还是1 2 1 2 1因为都不相邻。✅l.sort(); l.unique();—— 先排序让重复元素相邻。把list.remove和std::remove搞混❌std::remove(l.begin(), l.end(), 3);—— 算法版本不改变容器大小 只是把不匹配的元素往前挪尾部留下待删除的残骸。✅l.remove(3);—— 成员版本真的删除所有等于 3 的元素并更新size()。在splice的区间版本里把pos放在区间内❌l.splice(it, l, it, l.end());——pos落在[first, last)内这是未定义行为。✅ 让pos明确落在区间之外例如l.splice(l.end(), l, l.begin(), it);——pos是l.end()不在区间[l.begin(), it)里last本身不包含在区间内恒成立。跨分配器splice❌ 两条list用了不同的分配器例如一个是std::pmr::list绑到 pool A 另一个绑到 pool B仍直接splice—— 行为未定义。✅ 只对get_allocator()相等的两条链表做splice。边遍历边 erase 却不接管返回值❌for (auto it l.begin(); it ! l.end(); it) { if (bad(*it)) l.erase(it); }——it已经失效it是未定义行为症状通常是崩溃或跳过元素。✅for (auto it l.begin(); it ! l.end(); ) { if (bad(*it)) it l.erase(it); else it; }以为list的迭代器永远有效❌ 删除某元素后继续使用指向那个元素的迭代器 —— 它已经失效解引用是未定义行为。✅ 记住规则list的插入和splice不失效任何迭代器erase只失效被删元素的迭代器前提是这个元素确实还在链表里。在只需要尾部追加的场景硬用list❌ 把list当通用容器存十万个int然后逐个遍历求和 —— 每个节点多两个指针 节点在堆上分散遍历时缓存缺失远多于std::vector。✅ 需要顺序遍历、随机访问或连续内存时用std::vector 只有在中间频繁插入删除或必须保持迭代器稳定时才选std::list。总结主题关键结论迭代器类别双向迭代器没有/-/[]定位要std::advance插入删除已有迭代器时 O(1)且不失效其他迭代器splice常数时间搬运节点但要求分配器相同、pos不在被搬运区间内sort必须用成员版本稳定只改指针merge两条链表都要已排序合并后源链表变空unique只删相邻重复通常要先sort选型中间频繁增删、元素大、要迭代器稳定时选它否则优先vectorstd::list不是一个更好的vector而是一个在特定维度上做交换的容器 它用每个元素两个指针的额外空间、以及更差的缓存局部性 换来了常数时间的中间插入删除和极强的迭代器稳定性。 想清楚你的程序到底需要哪一边选型就不会纠结了。
