C++STL--list底层实现，迭代器分类，模拟list的迭代器封装、实现

博主名称deM0one⭐️C专栏 C文章目录C STL list 容器底层原理从零实现一个类 STL 的 list一、引言二、迭代器类型与性能特性2.1 迭代器类型2.2 性能特点2.3 支持双向迭代器的容器三、vector 的成员类型详解四、迭代器分类体系五、list 的内部结构设计5.1 循环双向链表 哨兵节点5.2 push_back 实现六、迭代器的封装与实现6.1 普通人的写法不封装迭代器6.2 仿 STL 的迭代器封装七、总结附录参考资料C STL list 容器底层原理从零实现一个类 STL 的 list一、引言C STLStandard Template Library是 C 标准库的核心组件list作为双向链表容器与vector等顺序容器有本质区别本文将从迭代器类型、内部结构、关键操作实现、迭代器封装四个维度深度解析list的工作原理二、迭代器类型与性能特性2.1 迭代器类型类型说明iterator普通迭代器支持读写reverse_iterator反向迭代器从尾部向前遍历const_iterator常量迭代器只读访问const_reverse_iterator常量反向迭代器2.2 性能特点支持双向遍历可通过和--操作前后移动不支持随机访问无operator[]不能通过下标直接访问元素时间复杂度插入/删除O(1)已知位置查找O(n)2.3 支持双向迭代器的容器list、map、multimapset、multisetvector、string、deque这些支持随机访问迭代器注意STL 从 C98 起就支持上述迭代器类型。三、vector 的成员类型详解以std::vectorT, Alloc为例其成员类型定义如下成员类型定义value_type模板第一个参数Tallocator_type模板第二个参数Allocreferenceallocator_type::referenceconst_referenceallocator_type::const_referencepointerallocator_type::pointerconst_pointerallocator_type::const_pointeriterator指向value_type的随机访问迭代器const_iterator指向const value_type的随机访问迭代器reverse_iteratorreverseiteratorsize_type无符号整数类型关键点vector的迭代器是随机访问迭代器而list的迭代器仅为双向迭代器。四、迭代器分类体系Input ← Output ← Forward ← Bidirectional ← Random Access迭代器类型能力说明Input Iterator只读、单向、只能前进一次Forward Iterator可读写、可多次遍历同一元素Bidirectional Iterator可前可后移动list、map使用Random Access Iterator支持任意位置跳跃vector、deque使用五、list 的内部结构设计5.1 循环双向链表 哨兵节点list内部采用循环双向链表结构并设置一个**哨兵节点sentinel**作为头节点。protected:link_type node;// 哨兵节点指针public:list(){empty_initialize();}voidempty_initialize(){nodeget_node();// 分配哨兵节点node-nextnode;// 自循环node-prevnode;}设计意义哨兵节点简化了边界处理使得空链表和非空链表的处理逻辑保持一致。5.2 push_back 实现voidpush_back(constTx){Node*newnodenewNode(x);Node*tail_head-prev;// 当前尾节点tail-nextnewnode;// 原尾部指向新节点newnode-prevtail;// 新节点指回原尾部newnode-next_head;// 新节点指向哨兵_head-prevnewnode;// 哨兵指回新节点}插入过程图示tail newnode ↓ ↓ [head] ←── 1 ←── 2 ←── 3 ←── 4 ↑ ↑ head newnode在链表尾部插入新节点newnode更新原尾节点tail的next指向新节点新节点的prev指回tail新节点的next指向headhead的prev指向新节点 → 形成闭环六、迭代器的封装与实现6.1 普通人的写法不封装迭代器typedeflist_iteratorTiterator;iteratorbegin(){iteratorit(_head-next);returniterator(_head-next);}iteratorend(){return_head;// 返回哨兵节点}问题直接暴露底层节点指针缺乏封装不符合 STL 规范。6.2 仿 STL 的迭代器封装templateclassTstructlist_iterator{typedeflist_nodeTNode;typedeflist_iteratorTSelf;Node*_node;list_iterator(Node*node):_node(node){}// 解引用操作Toperator*(){return_node-_data;}// 前置递增Selfoperator(){_node_node-next;return*this;}// 不等比较booloperator!(constSelfs){return_node!s._node;}};迭代器遍历图示pos ↓ [head] ←── 1 ←── 2 ←── 3 ←── 4 ↑ head使用迭代器封装底层节点指针提供operator*、operator、operator!等基本操作符合 STL 迭代器协议便于与泛型算法如sort、find配合使用七、总结本文系统梳理了 C STLlist容器的核心设计迭代器类型list使用双向迭代器不支持随机访问内部结构循环双向链表 哨兵节点简化边界处理关键操作empty_initialize初始化哨兵push_back实现尾部插入迭代器封装通过封装节点指针提供符合 STL 规范的迭代器接口掌握这些原理有助于深入理解 STL 设计思想并为手写简易版容器打下坚实基础。附录参考资料《C Primer》第 10 章泛型算法与容器SGI STL 源码剖析cppreference.comstd::list任何的批评和建议欢迎指出我们共同进步