【C++】 初阶篇 STL list的模拟实现

一、list的模拟实现

1.1list的节点结构、容器结构、迭代器结构

我们需要自己写一个list,首先在list类外,还需要两个类,一个节点,一个迭代器。节点类和迭代器类为list类服务。(ps:说实话list部分真的还挺难写的,我自己给绕晕了好几次,主要在多了结构和迭代器都比较难,但是跨过这两个就会好很多了)

我们先从小的开始。

  • 节点结构
//节点类template<classT>structlist_node{typedeflist_node<T>Node;// 节点类型别名list_node();~list_node();T _val;// 节点数据域Node*_prev;// 后继节点指针Node*_next;// 前驱节点指针};

这个节点可以存放任何类型的数据,所以它得是一个模板。list_node有三部分构成:数据,指向下一个节点的指针,指向上一个节点的指针。

  • 迭代器结构

因为我们在上一篇文章中说道他的++、--、*不再是原生指针了,所以我们要对他进行封装。

这段迭代器结构目前还不完整,后面的讲解会逐步完善链表迭代器的实现:

//迭代器类template<classT>struct_list_iterator{typedeflist_node<T>Node;// 节点类型别名_list_iterator();~_list_iterator();Node*_node;// 指向链表节点的指针};
  • 容器结构
//链表类template<classT>classlist{typedeflist_node<T>Node;// 节点类型别名public:list();~list();private:Node*_head;size_t _size;};
  • 链表的迭代器为啥不能直接用原生指针?

因为链表的原生指针(比如list_node*)只能访问节点本身,而迭代器需要模拟 “像普通指针一样解引用取数据、++/--遍历” 的行为 —— 链表节点里存的是_val(实际数据),原生指针解引用得到的是整个节点,不是数据;且链表的 “下一个元素” 需要通过_next指针跳转,原生指针的++是地址 + 1(不符合链表的节点连接逻辑),所以得封装迭代器类来重载*、++等运算符,不能直接用原生指针。

  • 迭代器结构为啥用struct?

迭代器结构体用struct,是因为迭代器只是遍历容器的工具 —— 哪怕直接定义迭代器对象,没有对应的容器支撑,也没法实际访问有效数据,所以不用刻意封装成私有,用struct让成员(比如这里的_node指针)直接暴露,能简化后续迭代器功能的实现。

  • 迭代器为啥不能写析构函数?

不能为迭代器编写析构函数 —— 因为节点的内存是由容器管理的,迭代器只是 “借用节点指针来访问元素”,本身并不持有节点的所有权。若在迭代器析构时释放节点,会导致容器内的节点被非法销毁,进而引发内存错误。

1.2list的默认函数

  • list构造函数
//list构造函数list(){_head=newNode;_head->_prev=_head;// 头节点前驱指向自身(循环链表)_head->_next=_head;// 头节点后继指向自身(循环链表)_size=0;// 链表初始长度为0}
  • list拷贝构造函数
// list拷贝构造函数list(constlist<T>&lt){_head=newNode;//先创建一个头结点_head->_prev=_head;// 头节点前驱指向自身(循环链表)_head->_next=_head;// 头节点后继指向自身(循环链表)_size=0;// 链表初始长度为0//遍历lt的每个元素,逐个尾插到新链表中,这个要支持迭代器for(auto&e:lt){push_back(e);}}

push_back这个函数我们后面实现。

  • list赋值运算符重载
//list的交换函数voidswap(list<T>&lt){std::swap(_head,lt._head);std::swap(_size,lt._size);}//list赋值运算符重载//已经有了实体// l1=l2list<T>&operator=(list<T>lt)// 传值调用,自动拷贝出临时对象lt{swap(lt);// 交换当前对象与临时对象的资源return*this;// 返回当前对象,临时对象会自动销毁旧资源}
  • list析构函数
// 清空链表中所有有效元素(保留头节点)voidclear(){iterator it=begin();// 获取链表起始迭代器while(it!=end())// 遍历所有有效元素{it=erase(it);// 删除当前元素,erase返回下一个元素的迭代器}_size=0;// 重置有效元素个数为0}// 链表析构函数:释放所有资源~list(){clear();// 先清空所有有效元素delete_head;// 释放头节点的堆内存_head=nullptr;// 将头节点指针置空,避免野指针}

二、迭代器结构(重点)

//迭代器结构体template<classT>struct_list_iterator{typedeflist_node<T>Node;// 节点类型别名typedef_list_iterator<T>iterator;//迭代器类型别名// 构造:用节点指针初始化迭代器_list_iterator(Node*node):_node(node){}Node*_node;// 指向链表节点的指针};

(迭代器本身就是一个封装指针,所以不需要拷贝构造,浅拷贝够用)

我们已经写出来的接下来我们要实现让他可以像指针一样使用。

2.1operator*

原本的指针解引用返回具体内置类型值,但是这里的链表节点时一个结构体,所以必须重载解引用。如下代码,我们让解引用返回的是结构体内部的数据。

T&operator*(){return_node->_val;}

2.2operator++和--

分别包装了向前找一个节点返回和向后找一个节点返回的逻辑。

iterator&operator++(){_node=_node->_next;return*this;}iteratoroperator++(int){iterator tmp=*this;_node=_node->_next;returntmp;}iterator&operator--(){_node=_node->_prev;return*this;}iteratoroperator--(int){iterator tmp=*this;_node=_node->_prev;returntmp;}

前置++和--的逻辑很相似:都是直接修改当前迭代器的节点指针(_node),然后返回自身的引用。

比如前置++是把_node指向 “下一个节点”,前置--是指向 “前一个节点”;返回自身引用的好处是支持链式操作(比如++(++it)、--(--it)),而且没有临时对象的开销,效率更高。

后置++和--的核心是 “先返回原状态,再移动”:

函数参数里的int是个占位符(没有实际意义,只是用来区分前置 / 后置),实现时会先创建一个临时迭代器tmp保存当前状态,然后移动_node到下一个 / 前一个节点,最后返回这个临时迭代器。

这样外部使用时,it++拿到的是 “移动前的迭代器”,而it本身已经完成了移动 —— 不过因为会创建临时对象,它的效率比前置版本略低。

2.3operator==与!=

相等与不相等的判断依据固定在对于节点的比较。

booloperator==(constiterator&it)const{return_node==it._node;}booloperator!=(constiterator&it)const{return_node!=it._node;}

这两个运算符的逻辑很直接:判断两个迭代器的_node指针是否指向同一个节点。

operator!=返回_node != it._node,表示 “两个迭代器是否指向不同节点”;

operator==返回_node == it._node,表示 “两个迭代器是否指向同一个节点”。其中operator!=后面加了const,是为了保证 “调用这个函数时不会修改当前迭代器的状态”,更符合 const 正确性的规范。

2.4operator->

重载这个运算符,是为了应对数据是结构体的场景:当存储的数据是结构体时,仅用operator*解引用后,没办法直接访问结构体的成员(得通过.来访问);而重载->后,就能直接通过迭代器用->访问结构体成员,用起来更便捷。

但这里又有个问题:我们通过operator->拿到的是_node节点的指针,而不是节点里存储的结构体成员 —— 这显然不是我们想要的访问效果。

我们看这段代码的实际效果:当用迭代器it访问结构体A的成员时,理论上应该写it->->_a2(因为operator->()返回的是A*指针,需要再用->访问成员),但编译器做了特殊处理 —— 自动省略了一个->,所以直接写it->_a1/it->_a2就能正常访问。

这背后的逻辑是:operator*()返回的是A&引用(所以可以用(*it)._a1访问),而operator->()返回的是A*指针;为了让迭代器的用法和原生指针一致(原生指针可以直接用->访问成员),C++ 编译器对迭代器的operator->做了 “语法糖” 优化,允许省略一次->,让it->_a2等价于(it.operator->())->_a2,用起来更自然简洁。

T*operator->(){return&(_node->_val);//c++会多处理一次所以返回地址即可}

2.5begin、end

// 普通正向迭代器:指向第一个有效元素iteratorbegin(){returniterator(_head->_next);}// 普通正向迭代器:指向尾后位置(头节点)iteratorend(){returniterator(_head);}

三、更高维度的范式编程

首先我们知道有const的迭代器,那么我们要是再写一个const迭代器的类吗太麻烦了,所以 STL 库引入了 3 个参数来解决。

// 链表迭代器模板类(T:元素类型 Ref:元素引用类型 Ptr:元素指针类型)template<classT,classRef,classPtr>

ok,我们看一下为什么会这样

那么我们先修改一下之前的代码

//迭代器类template<classT,classRef,classPtr>struct_list_iterator{typedeflist_node<T>Node;// 节点类型别名typedef_list_iterator<T,Ref,Ptr>self;// 迭代器自身类型别名,简化后续使用_list_iterator(Node*node):_node(node){}self&operator++(){_node=_node->_next;return*this;}selfoperator++(int){self tmp=*this;_node=_node->_next;returntmp;}self&operator--(){_node=_node->_prev;return*this;}selfoperator--(int){self tmp=*this;_node=_node->_prev;returntmp;}Refoperator*(){return_node->_val;}booloperator==(constself&it)const{return_node==it._node;}booloperator!=(constself&it)const{return_node!=it._node;}Ptroperator->(){return&(_node->_val);//c++会多处理一次所以返回地址即可}Node*_node;// 指向链表节点的指针};

Ptr、Ref模板参数的作用?

Ptr的作用在此体现:区分普通迭代器返回的T*(可读写结构体成员)和const迭代器返回的const T*(只读),实现一套模板复用,保证const迭代器的安全性。

至于为啥要将迭代器重命名为self,是因为它的完整类型名太长了,用self代替能简化代码书写。

四、list增删查改

4.1push_back

voidpush_back(constT&x){Node*newnode=newNode(x);Node*tail=_head->_prev;tail->_next=newnode;newnode->_prev=tail;_head->_prev=newnode;newnode->_next=_head;++_size;}

先找到链表的尾节点tail(通过头节点_head的_prev拿到),再创建新节点newnode;

接着把tail的_next指向新节点、新节点的_prev指向tail,完成新节点和原尾节点的连接;

最后让新节点的_next指向头节点、头节点的_prev指向新节点,维持链表的循环结构 —— 这样新节点就成了新的尾节点,尾插完成。

4.2insert

// pos位置之前插入iteratorinsert(iterator pos,constT&x){Node*cur=pos._node;//迭代器指向的节点Node*prev=cur->_prev;Node*newnode=newNode(x);prev->_next=newnode;newnode->_next=cur;cur->_prev=newnode;newnode->_prev=prev;++_size;returniterator(newnode);//返回新节点的迭代器}

先从迭代器pos里拿到它指向的节点cur,再找到cur的前驱节点prev,同时创建新节点newnode;

把prev的_next指向新节点、新节点的_next指向cur,再让cur的_prev指向新节点、新节点的_prev指向prev—— 这样就把新节点 “夹” 在了prev和cur之间;

最后更新链表长度_size,并返回新节点对应的迭代器,方便后续操作。

4.3push_front

voidpush_front(constT&x){insert(begin(),x);}

直接复用insert,在begin()(头节点迭代器)前插入元素x,既简化代码又保证逻辑一致。

4.4pop_back

voidpop_back(){// 断言:确保链表不为空(避免删除空链表的元素)assert(_head->_next!=_head);// 找到要删除的尾节点Node*del=_head->_prev;// 找到尾节点的前驱节点(新的尾节点)Node*tail=del->_prev;// 建立新尾节点和头节点的双向连接,断开原尾节点tail->_next=_head;_head->_prev=tail;// 释放原尾节点的内存deletedel;// 更新链表元素个数_size--;}

先断言链表非空,找到尾节点和它的前驱节点,重新建立前驱节点与头节点的循环连接,释放原尾节点内存,最后更新链表长度。

4.5erase

// pos位置删除iteratorerase(iterator pos){// 断言:确保删除的不是尾后迭代器(无效节点)assert(pos!=end());// 提取待删除节点curNode*cur=pos._node;// 找到cur的前驱和后继节点Node*prev=cur->_prev;Node*next=cur->_next;// 建立前驱和后继的双向连接,跳过待删除节点prev->_next=next;next->_prev=prev;// 释放待删除节点内存deletecur;// 更新链表元素个数--_size;// 返回后继节点迭代器,避免迭代器失效returniterator(next);}

先断言避免删除无效节点,找到待删节点的前后节点并重新建立连接,释放待删节点内存,更新链表长度后返回后继节点迭代器防止失效。

4.6pop_front

voidpop_front(){// 复用erase函数,删除头节点(begin()对应的迭代器)erase(begin());}

直接复用erase函数,删除begin()对应的头节点,既简化代码又保证逻辑一致。

4.7clear

// 清空链表中所有有效元素(保留头节点)voidclear(){iterator it=begin();// 获取链表起始迭代器while(it!=end())// 遍历所有有效元素{it=erase(it);// 删除当前元素,erase返回下一个元素的迭代器}_size=0;// 重置有效元素个数为0}

4.8empty

boolempty()const{return_size==0;}

相关新闻

【C++】 初阶篇 STL list的使用

【C++】 初阶篇 STL list的使用

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

2026/11/10 23:27:40 阅读更多 →
车间班组标准化作业提质体系

车间班组标准化作业提质体系

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

2026/11/15 17:49:27 阅读更多 →
ACORN算法的各种密码分析方法全面盘点

ACORN算法的各种密码分析方法全面盘点

ACORN算法的各种密码分析方法全面盘点ACORN算法作为CAESAR竞赛的最终入选算法之一&#xff0c;自提出以来受到了广泛的密码分析。目前针对它的密码分析方法已相当全面&#xff0c;涵盖了从数学结构到物理实现的多个层面。需要说明的是&#xff0c;现有攻击主要针对简化轮数的AC…

2026/11/15 22:04:25 阅读更多 →

最新新闻

Electron桌面应用开发实战:从环境搭建到打包发布全流程

Electron桌面应用开发实战:从环境搭建到打包发布全流程

做前端这些年&#xff0c;我大部分时间都在跟浏览器标签页打交道&#xff0c;直到第一次把桌面应用跑起来&#xff0c;才发现原来自己一直被限制在地址栏和刷新按钮围起来的框框里。Electron这个词&#xff0c;最开始是在某段时间频繁出现在同事的讨论里&#xff0c;一个用HTML…

2026/11/18 13:59:04 阅读更多 →
滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

简介&#xff1a;亚太天能T109滑盖智能锁产品说明书是一份PDF格式的官方技术文档&#xff0c;主要面向智能锁安装人员、终端用户及售后维护者&#xff0c;帮助快速掌握产品安装、配置与常见故障处理。全包仅1个PDF文件&#xff0c;大小4.37MB&#xff0c;内容结构清晰&#xff…

2026/11/18 15:33:23 阅读更多 →
PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

上个月我在调试一台高速AGV的驱动系统&#xff0c;整车要求空载跑到8m/s&#xff0c;电机转速已经拉到额定点&#xff0c;驱动器的输出电压也顶到了母线电压极限附近。再往上踩速度指令&#xff0c;转速纹丝不动&#xff0c;三相电流反而开始震荡。那会儿我的第一反应就是&…

2026/11/18 17:05:28 阅读更多 →
C++核心知识点:从内存管理到STL的实战指南

C++核心知识点:从内存管理到STL的实战指南

C 这门语言我前前后后折腾了十几年&#xff0c;用它写过嵌入式驱动、做过游戏服务端&#xff0c;也搭过基础组件库。每次看到新人一头扎进"C 核心知识点"这个搜索词&#xff0c;我其实挺感慨的——这门语言的难点从来不是语法多&#xff0c;而是知识点之间的耦合太深…

2026/11/18 14:33:19 阅读更多 →
T109滑盖智能锁怎么装?安装调试与故障排查全攻略

T109滑盖智能锁怎么装?安装调试与故障排查全攻略

简介&#xff1a;亚太天能T109滑盖智能锁产品说明书以PDF格式发布&#xff0c;适合智能锁用户、安装人员与售后维修人员阅读。内容围绕T109系列指纹密码刷卡锁展开&#xff0c;先介绍前面板、后面板、锁体、机械钥匙、电池盒盖等部件名称与功能&#xff0c;再给出完整安装步骤&…

2026/11/18 17:05:28 阅读更多 →
LLM知识降熵:从信息垄断到理解权下放

LLM知识降熵:从信息垄断到理解权下放

你有没有过这种经历&#xff1a;翻开源码注释、论文摘要或者一份专业报告&#xff0c;每个字都认识&#xff0c;连在一起却像天书。想找人聊聊&#xff0c;身边要么没人懂&#xff0c;要么懂的懒得跟你解释。后来我试着把同一段内容丢给一个大语言模型&#xff0c;几秒钟之后&a…

2026/11/18 14:13:08 阅读更多 →

日新闻

周新闻

月新闻