C STL list 底层剖析从内存布局到反向迭代器的设计哲学这篇不讲push_back怎么用。如果你还在记接口先去翻文档。这里只聊 list 的底层——内存怎么排、迭代器怎么封、反向迭代器为什么是那个鬼样子以及 list 在现代硬件上到底还行不行。一、内存布局为什么 list 不是你想的那样标准只说 list 是双向链表实现可以五花八门。但 glibc 的 libstdc 和 MSVC 的 STL 都选了同一种结构带头结点的双向循环链表。这不是偶然。1.1 节点长什么样templateclassTstruct_List_node{_List_node*_M_next;_List_node*_M_prev;T _M_data;};两个指针 一个 T。没有额外字段紧凑到极致。_M_data放在最后有个好处空 list 的哨兵头结点可以只分配_M_next和_M_prev不构造 T——如果 T 的构造函数有副作用这一点能省不少事。1.2 哨兵头结点一个让代码变优雅的设计空 list 时头结点的_M_next和_M_prev都指向自己head | v -------- | prev |--- | next |--- -------- ^ | ----为什么非要这个哨兵没有哨兵在push_front和push_back时你得分别处理空链表和非空链表两种情况。代码大概长这样// 没有哨兵的丑陋版本voidpush_front(constTval){Node*nnewNode(val);if(_headnullptr){_headn;_tailn;}else{n-_next_head;_head-_prevn;_headn;}}有哨兵之后push_front和push_back走同一条路径——不管链表空不空新节点永远插在哨兵和第一个节点之间或哨兵和最后一个节点之间。代码统一了分支少了bug 也就少了。这是 Dijkstra 说的 “sentinel value eliminates boundary conditions” 的经典应用。1.3 循环结构的隐藏好处头尾相连意味着end()可以直接返回头结点的迭代器不需要额外存储尾指针rbegin()可以直接用end()构造物理上就是同一个位置遍历时不需要判空——空链表begin() end()天然成立二、迭代器不止是个封装了指针的类PPT 里说暂时把迭代器理解成指针但如果你要手写得知道 STL 迭代器体系对它有严格的要求。2.1 迭代器必须暴露的五种类型STL 算法通过iterator_traits来查询迭代器的属性。一个合格的 list 迭代器至少要定义这些templateclassTstructListIterator{typedefbidirectional_iterator_tag iterator_category;// 迭代器分类typedefT value_type;typedefT*pointer;typedefTreference;typedefptrdiff_t difference_type;// ...};iterator_category是最关键的。list 的迭代器是bidirectional_iterator_tag意味着它支持和--但不支持 n或- n。这直接决定了很多算法能不能用在 list 上。比如std::sort的底层是 introsort需要随机访问random_access_iterator_tag所以std::sort(l.begin(), l.end())编译不过。list 自己提供了一个l.sort()内部用归并排序只要求双向迭代器。2.2 operator- 的实现细节迭代器重载-时有个反直觉的点T*operator-(){return(_node-_M_data);}operator-的返回值不是直接当成指针用而是编译器会递归调用。也就是说it-foo()实际等价于(it.operator-())-foo()。这个语法糖是 C 内置的但写迭代器时必须配合它。2.3 为什么 list 迭代器不能是指针vector 的迭代器在很多实现里就是原生指针T*因为 vector 的内存是连续的it 1就是下一个元素。list 的节点散落在堆上节点之间没有地址连续性it必须走_node-_M_next。所以 list 的迭代器必须是类重载和--。这也意味着list 的std::distance是 O(N)。因为distance对 bidirectional iterator 只能一步一步走。对 vector 的 random access iteratordistance直接做指针减法O(1)。三、反向迭代器适配器模式的教科书案例反向迭代器不是重新发明一个反向链表而是适配器Adapter模式的经典应用。它内部持有一个正向迭代器把所有操作转调过去。3.1 为什么 operator* 要先 –这是最容易让人困惑的地方。看代码Refoperator*(){Iteratortmp(_it);--tmp;return*tmp;}直接解引用_it不行吗不行。因为rbegin()的构造方式是reverse_iteratorrbegin(){returnreverse_iterator(end());}end()指向哨兵头结点。如果直接对end()解引用拿到的是哨兵头结点的_M_data——未定义行为。所以reverse_iterator::operator*必须先把内部迭代器回退一步落到真正的最后一个元素上再解引用。3.2 off-by-one 的数学解释正向区间[begin, end)—— begin 指向第一个元素end 指向最后一个元素的下一个位置反向区间[rbegin, rend)—— rbegin 指向最后一个元素rend 指向第一个元素的前一个位置但rbegin的物理位置在end最后一个元素的下一个rend的物理位置在begin第一个元素。也就是说正向 [1] [2] [3] [4] [5] end ^ ^ begin end 反向 rend [5] [4] [3] [2] [1] rbegin ^ ^ rend rbegin注意rbegin物理上在end的位置。为了让它逻辑上指向最后一个元素解引用时必须--。这个设计的代价是base()成员函数返回底层正向迭代器和解引用的位置差一个。*(rit)和*(rit.base())永远指向不同的元素。写代码时如果混用正向和反向迭代器这个坑一定要记住。3.3 为什么 operator 写错了PPT 里的代码有个 bugbooloperator(constSelfl)const{return_it!l._it;}// 错了应该是而不是!。这是一个很隐蔽的笔误编译能过但逻辑是反的。如果你手写反向迭代器这个 bug 会让和!的行为互换调试起来非常痛苦。四、插入与删除指针修改的完整流程4.1 insert 的每一步在位置pos前插入新节点iteratorinsert(iterator pos,constTval){Node*new_nodenewNode(val);Node*curpos._node;Node*prevcur-_M_prev;// 1) 新节点的 next 指向当前节点new_node-_M_nextcur;// 2) 新节点的 prev 指向当前节点的前驱new_node-_M_prevprev;// 3) 前驱节点的 next 指向新节点prev-_M_nextnew_node;// 4) 当前节点的 prev 指向新节点cur-_M_prevnew_node;_size;returniterator(new_node);}四步指针修改没有元素搬移没有扩容。时间复杂度 O(1)。但注意如果pos是通过遍历找到的找到的过程是 O(N)。所以list 插入是 O(1)有个隐含前提——你已经持有指向该位置的迭代器。4.2 erase 的每一步iteratorerase(iterator pos){Node*curpos._node;Node*prevcur-_M_prev;Node*nextcur-_M_next;// 1) 前驱的 next 跳过当前节点prev-_M_nextnext;// 2) 后继的 prev 跳过当前节点next-_M_prevprev;deletecur;--_size;returniterator(next);}也是四步指针修改。返回next的迭代器这就是为什么it l.erase(it)能正确工作。4.3 为什么插入不会导致迭代器失效从上面的代码可以看到insert只修改了插入位置相邻的两个节点的指针。其他节点的_M_next和_M_prev完全没变内存地址也没变。所以所有已存在的迭代器仍然有效。这和 vector 形成鲜明对比vectorinsert可能导致扩容所有元素被搬到新地址所有迭代器全部作废。4.4 为什么删除只让当前迭代器失效erase里只有被删节点的内存被delete了。其他节点的指针被重新连接但节点本身还在原地。所以只有指向被删节点的那个迭代器变成了悬空指针其他迭代器仍然指向有效的节点。五、list vs vector不只是复杂度差异5.1 缓存局部性Cache Localityvector 的元素在内存中连续排列。CPU 读取一个元素时会把附近的一大块内存预取到缓存行通常是 64 字节。遍历 vector 时几乎每次访问都命中缓存。list 的节点散落在堆上彼此之间没有地址关联。遍历 list 时每次it都跳到一个完全随机的地址缓存命中率极低。实际测试中vector 的遍历速度通常比 list 快 5-10 倍哪怕 list 的理论复杂度也是 O(N)。5.2 内存开销一个listint的节点在 64 位系统上至少占 24 字节两个 8 字节指针 4 字节 int 4 字节对齐填充。存储 100 万个 intvector 占 4MBlist 占 24MB 以上。更糟的是每个节点独立new/delete堆分配器会在节点之间插入元数据大小、标志位等进一步浪费内存。小节点还容易造成内存碎片——大量 24 字节的块散落在堆中后续申请大块内存时可能找不到连续空间。5.3 什么时候 list 真的赢了list 的优势场景其实很少需要稳定的迭代器/指针/引用如果你在遍历容器的同时需要保存指向某些元素的指针长期有效list 是更好的选择。vector 一旦扩容所有指针都废了。大量中间插入删除且元素很大如果元素类型是重型对象比如包含大数组的结构体vector 的搬移开销可能超过 list 的缓存劣势。这时 list 更合适。需要 splicelist 提供splice操作可以在 O(1) 时间内把一段链表整体移动到另一个位置不需要拷贝元素。这是 list 独有的能力。除此之外默认选 vector。 Herb Sutter 在《Exceptional C》里也表达过类似观点现代硬件上list 的性能优势被缓存不友好完全抵消了。六、现代 C 中的 listC11 引入了forward_list——单向链表比 list 更轻量。每个节点少一个prev指针内存开销更小。代价是只能单向遍历没有push_back()和反向迭代器。如果你的需求只需要头插/头删或者只需要单向遍历forward_list是比 list 更好的选择。另外C17 的pmr::polymorphic_allocator和 C20 的std::vector配合std::deque风格的分块存储在很多场景下进一步挤压了 list 的生存空间。但这不意味着 list 不重要。它的价值在于教学和设计思想哨兵头结点的边界消除技巧迭代器封装让算法和容器解耦反向迭代器的适配器模式插入删除时的强异常保证strong exception guarantee这些思想在其他数据结构和设计模式里反复出现。搞懂 list 的底层对你理解 STL 的整体架构大有裨益。七、动手验证如果你看完觉得懂了建议写个简化版 list 验证一下。需要实现的最低限度templateclassTclasslist{structNode{T data;Node*prev;Node*next;};Node*_head;// 哨兵size_t _size;public:classiterator;// 正向迭代器classreverse_iterator;// 反向迭代器list();~list();voidpush_back(constTval);voidpush_front(constTval);iteratorinsert(iterator pos,constTval);iteratorerase(iterator pos);iteratorbegin();iteratorend();reverse_iteratorrbegin();reverse_iteratorrend();size_tsize()const;boolempty()const;};跑这几个测试用例空 list 的 begin() end()push_front 和 push_back 交替验证双向连接正确正向遍历、反向遍历输出对比erase 后返回的迭代器能继续遍历大量 insert/erase 后之前保存的未受影响迭代器仍然有效全部通过list 就算真学透了。
C STL list 底层剖析从内存布局到反向迭代器的设计哲学这篇不讲push_back怎么用。如果你还在记接口先去翻文档。这里只聊 list 的底层——内存怎么排、迭代器怎么封、反向迭代器为什么是那个鬼样子以及 list 在现代硬件上到底还行不行。一、内存布局为什么 list 不是你想的那样标准只说 list 是双向链表实现可以五花八门。但 glibc 的 libstdc 和 MSVC 的 STL 都选了同一种结构带头结点的双向循环链表。这不是偶然。1.1 节点长什么样templateclassTstruct_List_node{_List_node*_M_next;_List_node*_M_prev;T _M_data;};两个指针 一个 T。没有额外字段紧凑到极致。_M_data放在最后有个好处空 list 的哨兵头结点可以只分配_M_next和_M_prev不构造 T——如果 T 的构造函数有副作用这一点能省不少事。1.2 哨兵头结点一个让代码变优雅的设计空 list 时头结点的_M_next和_M_prev都指向自己head | v -------- | prev |--- | next |--- -------- ^ | ----为什么非要这个哨兵没有哨兵在push_front和push_back时你得分别处理空链表和非空链表两种情况。代码大概长这样// 没有哨兵的丑陋版本voidpush_front(constTval){Node*nnewNode(val);if(_headnullptr){_headn;_tailn;}else{n-_next_head;_head-_prevn;_headn;}}有哨兵之后push_front和push_back走同一条路径——不管链表空不空新节点永远插在哨兵和第一个节点之间或哨兵和最后一个节点之间。代码统一了分支少了bug 也就少了。这是 Dijkstra 说的 “sentinel value eliminates boundary conditions” 的经典应用。1.3 循环结构的隐藏好处头尾相连意味着end()可以直接返回头结点的迭代器不需要额外存储尾指针rbegin()可以直接用end()构造物理上就是同一个位置遍历时不需要判空——空链表begin() end()天然成立二、迭代器不止是个封装了指针的类PPT 里说暂时把迭代器理解成指针但如果你要手写得知道 STL 迭代器体系对它有严格的要求。2.1 迭代器必须暴露的五种类型STL 算法通过iterator_traits来查询迭代器的属性。一个合格的 list 迭代器至少要定义这些templateclassTstructListIterator{typedefbidirectional_iterator_tag iterator_category;// 迭代器分类typedefT value_type;typedefT*pointer;typedefTreference;typedefptrdiff_t difference_type;// ...};iterator_category是最关键的。list 的迭代器是bidirectional_iterator_tag意味着它支持和--但不支持 n或- n。这直接决定了很多算法能不能用在 list 上。比如std::sort的底层是 introsort需要随机访问random_access_iterator_tag所以std::sort(l.begin(), l.end())编译不过。list 自己提供了一个l.sort()内部用归并排序只要求双向迭代器。2.2 operator- 的实现细节迭代器重载-时有个反直觉的点T*operator-(){return(_node-_M_data);}operator-的返回值不是直接当成指针用而是编译器会递归调用。也就是说it-foo()实际等价于(it.operator-())-foo()。这个语法糖是 C 内置的但写迭代器时必须配合它。2.3 为什么 list 迭代器不能是指针vector 的迭代器在很多实现里就是原生指针T*因为 vector 的内存是连续的it 1就是下一个元素。list 的节点散落在堆上节点之间没有地址连续性it必须走_node-_M_next。所以 list 的迭代器必须是类重载和--。这也意味着list 的std::distance是 O(N)。因为distance对 bidirectional iterator 只能一步一步走。对 vector 的 random access iteratordistance直接做指针减法O(1)。三、反向迭代器适配器模式的教科书案例反向迭代器不是重新发明一个反向链表而是适配器Adapter模式的经典应用。它内部持有一个正向迭代器把所有操作转调过去。3.1 为什么 operator* 要先 –这是最容易让人困惑的地方。看代码Refoperator*(){Iteratortmp(_it);--tmp;return*tmp;}直接解引用_it不行吗不行。因为rbegin()的构造方式是reverse_iteratorrbegin(){returnreverse_iterator(end());}end()指向哨兵头结点。如果直接对end()解引用拿到的是哨兵头结点的_M_data——未定义行为。所以reverse_iterator::operator*必须先把内部迭代器回退一步落到真正的最后一个元素上再解引用。3.2 off-by-one 的数学解释正向区间[begin, end)—— begin 指向第一个元素end 指向最后一个元素的下一个位置反向区间[rbegin, rend)—— rbegin 指向最后一个元素rend 指向第一个元素的前一个位置但rbegin的物理位置在end最后一个元素的下一个rend的物理位置在begin第一个元素。也就是说正向 [1] [2] [3] [4] [5] end ^ ^ begin end 反向 rend [5] [4] [3] [2] [1] rbegin ^ ^ rend rbegin注意rbegin物理上在end的位置。为了让它逻辑上指向最后一个元素解引用时必须--。这个设计的代价是base()成员函数返回底层正向迭代器和解引用的位置差一个。*(rit)和*(rit.base())永远指向不同的元素。写代码时如果混用正向和反向迭代器这个坑一定要记住。3.3 为什么 operator 写错了PPT 里的代码有个 bugbooloperator(constSelfl)const{return_it!l._it;}// 错了应该是而不是!。这是一个很隐蔽的笔误编译能过但逻辑是反的。如果你手写反向迭代器这个 bug 会让和!的行为互换调试起来非常痛苦。四、插入与删除指针修改的完整流程4.1 insert 的每一步在位置pos前插入新节点iteratorinsert(iterator pos,constTval){Node*new_nodenewNode(val);Node*curpos._node;Node*prevcur-_M_prev;// 1) 新节点的 next 指向当前节点new_node-_M_nextcur;// 2) 新节点的 prev 指向当前节点的前驱new_node-_M_prevprev;// 3) 前驱节点的 next 指向新节点prev-_M_nextnew_node;// 4) 当前节点的 prev 指向新节点cur-_M_prevnew_node;_size;returniterator(new_node);}四步指针修改没有元素搬移没有扩容。时间复杂度 O(1)。但注意如果pos是通过遍历找到的找到的过程是 O(N)。所以list 插入是 O(1)有个隐含前提——你已经持有指向该位置的迭代器。4.2 erase 的每一步iteratorerase(iterator pos){Node*curpos._node;Node*prevcur-_M_prev;Node*nextcur-_M_next;// 1) 前驱的 next 跳过当前节点prev-_M_nextnext;// 2) 后继的 prev 跳过当前节点next-_M_prevprev;deletecur;--_size;returniterator(next);}也是四步指针修改。返回next的迭代器这就是为什么it l.erase(it)能正确工作。4.3 为什么插入不会导致迭代器失效从上面的代码可以看到insert只修改了插入位置相邻的两个节点的指针。其他节点的_M_next和_M_prev完全没变内存地址也没变。所以所有已存在的迭代器仍然有效。这和 vector 形成鲜明对比vectorinsert可能导致扩容所有元素被搬到新地址所有迭代器全部作废。4.4 为什么删除只让当前迭代器失效erase里只有被删节点的内存被delete了。其他节点的指针被重新连接但节点本身还在原地。所以只有指向被删节点的那个迭代器变成了悬空指针其他迭代器仍然指向有效的节点。五、list vs vector不只是复杂度差异5.1 缓存局部性Cache Localityvector 的元素在内存中连续排列。CPU 读取一个元素时会把附近的一大块内存预取到缓存行通常是 64 字节。遍历 vector 时几乎每次访问都命中缓存。list 的节点散落在堆上彼此之间没有地址关联。遍历 list 时每次it都跳到一个完全随机的地址缓存命中率极低。实际测试中vector 的遍历速度通常比 list 快 5-10 倍哪怕 list 的理论复杂度也是 O(N)。5.2 内存开销一个listint的节点在 64 位系统上至少占 24 字节两个 8 字节指针 4 字节 int 4 字节对齐填充。存储 100 万个 intvector 占 4MBlist 占 24MB 以上。更糟的是每个节点独立new/delete堆分配器会在节点之间插入元数据大小、标志位等进一步浪费内存。小节点还容易造成内存碎片——大量 24 字节的块散落在堆中后续申请大块内存时可能找不到连续空间。5.3 什么时候 list 真的赢了list 的优势场景其实很少需要稳定的迭代器/指针/引用如果你在遍历容器的同时需要保存指向某些元素的指针长期有效list 是更好的选择。vector 一旦扩容所有指针都废了。大量中间插入删除且元素很大如果元素类型是重型对象比如包含大数组的结构体vector 的搬移开销可能超过 list 的缓存劣势。这时 list 更合适。需要 splicelist 提供splice操作可以在 O(1) 时间内把一段链表整体移动到另一个位置不需要拷贝元素。这是 list 独有的能力。除此之外默认选 vector。 Herb Sutter 在《Exceptional C》里也表达过类似观点现代硬件上list 的性能优势被缓存不友好完全抵消了。六、现代 C 中的 listC11 引入了forward_list——单向链表比 list 更轻量。每个节点少一个prev指针内存开销更小。代价是只能单向遍历没有push_back()和反向迭代器。如果你的需求只需要头插/头删或者只需要单向遍历forward_list是比 list 更好的选择。另外C17 的pmr::polymorphic_allocator和 C20 的std::vector配合std::deque风格的分块存储在很多场景下进一步挤压了 list 的生存空间。但这不意味着 list 不重要。它的价值在于教学和设计思想哨兵头结点的边界消除技巧迭代器封装让算法和容器解耦反向迭代器的适配器模式插入删除时的强异常保证strong exception guarantee这些思想在其他数据结构和设计模式里反复出现。搞懂 list 的底层对你理解 STL 的整体架构大有裨益。七、动手验证如果你看完觉得懂了建议写个简化版 list 验证一下。需要实现的最低限度templateclassTclasslist{structNode{T data;Node*prev;Node*next;};Node*_head;// 哨兵size_t _size;public:classiterator;// 正向迭代器classreverse_iterator;// 反向迭代器list();~list();voidpush_back(constTval);voidpush_front(constTval);iteratorinsert(iterator pos,constTval);iteratorerase(iterator pos);iteratorbegin();iteratorend();reverse_iteratorrbegin();reverse_iteratorrend();size_tsize()const;boolempty()const;};跑这几个测试用例空 list 的 begin() end()push_front 和 push_back 交替验证双向连接正确正向遍历、反向遍历输出对比erase 后返回的迭代器能继续遍历大量 insert/erase 后之前保存的未受影响迭代器仍然有效全部通过list 就算真学透了。
