【STL_list 模拟】——打造属于自己的高效链表容器
一、list节点
list是一个双向循环带头的链表,所以链表节点结构如下:
template<class T>struct ListNode{T val;ListNode* next;ListNode* prve;ListNode(int x){val = x;next = prve = this;}};
二、list迭代器
2.1、list迭代器与vector迭代器区别
list迭代器与vector迭代器不一样,不能使用简单的原生指针了;
vector中迭代器可以使用原生指针,因为vector的存储空间是连续的,可以通过指针+/-/++/–找到下一个(上一个)位置;而list(链表)我们知道存储空间是不连续的,不能通过指针++/—找到下一个(上一个)节点;那我们就不能使用原生指针。
2.2、list迭代器实现
既然原生指针不能满足我们的需求,那我们就要用其他的方法来实现迭代器,这时候类的封装的意义就体现出来了;我们只需要对原生指针进行封装,然后使用运算符重载来修改迭代器++/–这些行为,这样就可以满足我们的需求了。
具体代码如下:
template<class T, class Ref, class Str>class list_iterator{typedef ListNode Node;typedef list_iterator iterator;public:list_iterator(Node* node){_node = node;}//前置++iterator operator++(){Node tmp(_node);_node = _node->_next;return tmp;}//后置++iterator operator++(int){_node = _node->_next;return *this;}//前置--iterator operator--(){Node tmp(_node);_node = _node->_prve;return tmp;}iterator operator++(int){_node = _node->_prve;return *this;}bool operator==(const iterator& it){return _node == it._node;}bool operator!=(const iterator& it){return _node != it._node;}Ref operator*(){return _node->val;}Ptr operator->(){return &(_node->_val);}private:Node* _node;};
三、list实现
3.1、构造函数

先看一下list构造函数的接口
| 构造函数 | 接口说明 |
|---|---|
| list() | 默认构造函数,构造一个空的list |
| list (size_type n, const value_type& val =value_type()) | 用n个val值构造list |
| list (InputIterator first, InputIterator last) | 还有一段迭代器区间初始化 |
| list (const list& x) | 拷贝构造函数 |
这里我们实现的list是带头双向循环链表,具体结构与之前的双向链表相同。
在构造之前,我们需要先构造一个头结点,这里就写一个函数 empty_init 来构造这个头结点。
empty_init(){_head = new Node();_head->_next = _head;_head->_prve = _head;}
默认构造函数
list()
{empty_init();_size = 0;
}
用n个val值构造
list(size_t n, const T& val)
{/*_head = new Node();_head->_next = _head;_head->_prve = _head;*/empty_init();for (size_t i = 0; i < n; i++){Node* newnode = new Node(val);newnode->_next = _head->_next;newnode->_prve = _head->_next;_head->_next->_prve = newnode;_head->_next = newnode;}_size = n;
}
迭代器区间构造
使用迭代器区间构造,这里复用一下后面的push_back直接尾插来构造。
template<class InputIterator>
list(InputIterator first, InputIterator last)
{empty_init();_size = 0;while (first != last){push_back(*first);_size++;}
}
void push_back(const T& val)
{Node* newnode = new Node(val);newnode->_next = _head;newnode->_prve = _head->_prve;_head->_prve->_next = newnode;_head->_prve = newnode;
}
拷贝构造函数
拷贝构造,这里直接复用上面迭代器构造即可。
list(const list& l){empty_init();list(l.begin(), l.end());_size = l.size();}
3.2、迭代器
//iteratoriterator end(){//return _head->_next;return iterator(_head);}iterator begin(){//return _head;return iterator(_head->_next);}const_iterator end() const{//return _head->_next;return const_iterator(_head);}const_iterator begin() const{//return _head;return const_iterator(_head->_next);}
这里迭代器返回值,可以直接返回节点指针(因为单参数的构造函数支持隐式类型转换)。
3.3、Capacity

主要就是empty和size(判断空和数据个数)
//Capacitybool empty(){return _head == _head->_next;}size_t size(){/*size_t ret = 0;Node* ptail = _head->_next;while (ptail != head){ret++;ptail = ptail->_next;}return ret;*/return _size;}
这里遍历链表来计算数据个数,代价太大了,我们直接写一个成员变量,在初始化,插入和删除时修改,会方便很多。
3.4、增删查改

这里增删查改就实现其中的一部分,其他的不太常用。
3.4.1、push_back、push_front、pop_back、pop_front
头插尾插,头删尾删,对于list而言,只需要修改指针的指向;
void push_back(const T& val)
{Node* newnode = new Node(val);newnode->_next = _head;newnode->_prve = _head->_prve;_head->_prve->_next = newnode;_head->_prve = newnode;_size++;
}
void push_front(const T& val)
{Node* newnode = new Node(val);newnode->_next = _head->_next;newnode->_prve = _head;_head->_next->_prve = newnode;_head->_next = newnode;_size++;
}//删
void pop_back()
{if (!empty()){Node* del = _head->_prve;_head->_prve->_prve->_next = _head;_head->_prve = _head->_prve->_prve;delete del;_size--;}
}
void pop_front()
{if (!empty()){Node* del = _head->_next;_head->_next->_next->_prve = _head;_head->_next = _head->_next->_next;delete del;_size--;}
}
3.4.2、insert

insert在指定位置插入数据,看它的参数列表,大概就知道,要在迭代器position 迭代器位置(之前)插入数据(1个或者n个),或者插入一段迭代器区间的数据。
//insert
void insert(iterator pos, const T& val)
{Node* newnode = new Node(val);Node* tmp = pos._node;newnode->_next = tmp;newnode->_prve = tmp->_prve;tmp->_prve->_next = newnode;tmp->_prve = newnode;++_size;
}
void insert(iterator pos, size_t n, const T& val)
{for(size_t i = 0; i < n; i++){Node* newnode = new Node(val);Node* tmp = pos._node;newnode->_next = tmp;newnode->_prve = tmp->_prve;tmp->_prve->_next = newnode;tmp->_prve = newnode;}_size+=n;
}
void insert(iterator pos, int n, const T& val)
{for(size_t i = 0; i < n; i++){Node* newnode = new Node(val);Node* tmp = pos._node;newnode->_next = tmp;newnode->_prve = tmp->_prve;tmp->_prve->_next = newnode;tmp->_prve = newnode;}
}
这里需要注意:
看到这里可能会疑惑,为什么实现了两个插入n个数据 的insert函数;
因为,当数据类型是int时,下面模版实例化出的函数(iterator , int , int)比这里实现的(iterator , size_t , int)更加匹配;编译器就会去调用更加匹配的函数,就会出错。这里就是为了防止这种出错。
插入迭代器的数据,与使用迭代器区间构造初始化相似,list只需改变指针指向即可。
template<class InputIterator>void insert(iterator pos, InputIterator first, InputIterator last){while (first != last){Node* newnode = new Node(*first);Node* tmp = pos._node;newnode->_next = tmp;newnode->_prve = tmp->_prve;tmp->_prve->_next = newnode;tmp->_prve = newnode;++first;}}
3.4.3、erase
erase删除一个节点,我们要修改前后节点的指针指向。
iterator erase(iterator pos)
{assert(pos != end());Node* del = pos._node;Node* next = del->_next;Node* prve = del->_prve;next->_prve = prve;prve->_next = next;delete del;return next;
}
在我们删除节点之后,之前的迭代器就会失效,为了解决迭代器失效问题,我们就使用返回值,返回新的迭代器。
3.4.4、swap
这里实现的list只有一个成员函数(头结点的指针),直接交换即可。
void swap(list& l){std::swap(_head, l._head);}
3.4.5、clear
clear函数,清理数据,(保留头结点)。
//清除数据void clear(){iterator it = begin();while (it != end()){it = erase(it);}}
3.5、析构函数
析构函数相对就比较简单了,我们清理完数据,再释放头结点即可。
~list(){clear();delete _head;}
到这里,list的模拟实现就完成了;这里只是实现了其中的一部分内容,感兴趣的可以继续深入了解学习。
我的博客即将同步至腾讯云开发者社区,邀请大家一同入驻:https://cloud.tencent.com/developer/support-plan?invite_code=2oul0hvapjsws
ear函数,清理数据,(保留头结点)。
//清除数据void clear(){iterator it = begin();while (it != end()){it = erase(it);}}
3.5、析构函数
析构函数相对就比较简单了,我们清理完数据,再释放头结点即可。
~list(){clear();delete _head;}
到这里,list的模拟实现就完成了;这里只是实现了其中的一部分内容,感兴趣的可以继续深入了解学习。
我的博客即将同步至腾讯云开发者社区,邀请大家一同入驻:https://cloud.tencent.com/developer/support-plan?invite_code=2oul0hvapjsws
相关文章:
【STL_list 模拟】——打造属于自己的高效链表容器
一、list节点 list是一个双向循环带头的链表,所以链表节点结构如下: template<class T>struct ListNode{T val;ListNode* next;ListNode* prve;ListNode(int x){val x;next prve this;}};二、list迭代器 2.1、list迭代器与vector迭代器区别…...
Java 基础教学:高级特性与实战-集合框架
Java 集合框架提供了一套性能优良、使用方便的接口和类,用于存储和操作群组数据。最常用的集合接口有 List、Set 和 Map。 List List 接口可以存储一系列有序的元素,并且可以包含重复的元素。List 的实现类常用的有 ArrayList 和 LinkedList。 ArrayL…...
单片机原理及应用笔记:C51数组与项目实践
作者介绍 刘滋瑞,男,银川科技学院计算机与人工智能学院,2022级计算机与科学技术8班本科生,单片机原理及应用课程第九组。 指导老师:王兴泽 电子邮箱:602054774qq.com 前言 本篇文章是参考《单片机原理…...
综合项目--博客
一。基础配置: 1.配置主机名,静态IP地址 2.开启防火墙配置 3.部分开启selinux并且配置 4.服务器之间使用同ntp.aliyun.com进行世家能同步 5.服务器之间实现SSH绵密登陆 二。业务需求 1.Sever-NFS-DNS主机配置NFS服务器,将博客网站资源…...
ARM64的Mac Node.js前置工作,nvm在线安装
1,通过 终端 ping raw.githubusercontent.com 获取到ip地址185.199.110.133 2,终端输入sudo vi /etc/hosts,打开hosts文件 3,在最后添加 185.199.110.133 raw.githubusercontent.com 保存后退出 3.1,清除环境 完全…...
C++《list的模拟实现》
在上一篇C《list》专题当中我们了解了STL当中list类当中的各个成员函数该如何使用,接下来在本篇当中我们将试着模拟实现list,在本篇当中我们将通过模拟实现list过程中深入理解list迭代器和之前学习的vector和string迭代器的不同,接下来就开始…...
Kubernetes的概述与架构
Kubernetes 的概述 Kubernetes 是一个可移植、可扩展的开源平台,用于管理容器化的工作负载和服务,方便进行声明式配置和自动化。Kubernetes 拥有一个庞大且快速增长的生态系统,其服务、支持和工具的使用范围广泛。 Kubernetes 这个名字源于…...
Elasticsearch实战应用:构建高效的全文搜索引擎
Elasticsearch实战应用:构建高效的全文搜索引擎 在当今信息爆炸的时代,如何快速、准确地从海量数据中检索出所需信息成为了企业和开发者面临的重要挑战。Elasticsearch作为一款开源的分布式搜索引擎,凭借其强大的全文搜索、实时分析和可扩展…...
达梦数据库和人大金仓数据库对数据库的运行查看情况
1、查看服务器自身资源使用情况 查看内存: free -g 查看整体负载: top 查看磁盘io : iostat -d -x 1 2、查看数据库占用服务器内存情况,登录DM管理工具,达梦数据库使用的内存大致等于 BUFFER MPOOL,对应的 SQL 语句为:…...
Spring Boot解决 406 错误之返回对象缺少Getter/Setter方法引发的问题
目录 前言1. 问题背景2. 问题分析2.1 检查返回对象 3. 解决方案3.1 确保Controller返回Result类型3.2 测试接口响应 4. 原理探讨5. 常见问题排查与优化建议结语 前言 在Spring Boot开发中,接口请求返回数据是系统交互的重要环节,尤其在开发RESTful风格的…...
Automa入门教程详解(Automa工作流概述)
一、什么是工作流? 工作流其实就是一组功能模块,通过彼此的连接来完成一系列的自动化操作流程。你可以把它理解为一个流程图,系统会根据你设置的顺序,从触发块开始,一步一步地执行,直到最后一个模块。这让…...
Python并发编程库:Asyncio的异步编程实战
Python并发编程库:Asyncio的异步编程实战 在现代应用中,并发和高效的I/O处理是影响系统性能的关键因素之一。Python的asyncio库是专为异步编程设计的模块,提供了一种更加高效、易读的并发编程方式,适用于处理大量的I/O密集型任务…...
vueui vxe-form 分享实现表单项的联动禁用,配置式表单方式的用法
官网文档:https:/vxeui.com 实现表单项的联动禁用 在使用 vxe-form 时,有时候需要将表单项直接进行关联操作,比如某一项选择后,另外一项设置为禁用状态不可选择,使用插槽的话神容易实现,本章是分享配置式的…...
供应SW1655集成功率管的高频率、高性能同步整流
概述 SW1655 是一款集成 N 沟道 MOSFET 的高频率、高性能同步整流功率开关。针对离线式反激 变换器的副边同步整流应用,替代肖特基整流二极管,可以显著提高系统效率的同时,实现高集 成度与高功率密度。 SW1655 具有 VCC 自供电功能&#…...
电动机出现故障后怎么处理?
在工业生产中,电动机作为重要的驱动设备,其运行状态直接关系到生产线的效率和稳定性。然而,由于各种因素的影响,电动机在运行过程中可能会出现多种故障。那么,电动机出现故障后怎么处理? 一、电动机在工业…...
练习LabVIEW第四十题
学习目标: 用labvIEW做一个循环闪烁指示灯,要能够在前面板调节周期和占空比。 开始编写: 前面板 一个布尔指示灯一维数组,两个数值输入控件; 程序框图 添加一个while循环,循环内添加初始化数组&…...
蓝牙BLE开发——红米手机无法搜索蓝牙设备?
解决 红米手机,无法搜索附近蓝牙设备 具体型号当时忘记查看了,如果你遇到有以下选项,记得打开~ 设置权限...
UE5.4 PCG Layered Biomes插件
B站学习链接 官方文档 一、PCGSpawn Preset:负责管理PCG要用到的植被资产有哪些 二、BiomesSettings:设置要使用的植被资产Layer、Spawn参数 1.高度Layer参数: 2.地形Layer:我这里用地形样条线绘制了一块地形Layer 绘制点和…...
搭建你的私人云盘:使用File Browser与cpolar实现公网传输文件
文章目录 前言1.下载安装File Browser2.启动访问File Browser3.安装cpolar内网穿透3.1 注册账号3.2 下载cpolar客户端3.3 登录cpolar web ui管理界面3.4 创建公网地址 4.固定公网地址访问 前言 File Browser是一个开源的文件管理器和文件共享工具,它可以帮助用户轻…...
QT/QT QUICK与前端WEB开发的区别
开发框架与目标: QT/QT QUICK:跨平台应用程序开发框架,用于创建图形用户界面(GUI),特别适用于移动和嵌入式设备。前端WEB开发:主要关注Web应用的用户界面,使用HTML、CSS、JavaScript等技术。…...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...
idea大量爆红问题解决
问题描述 在学习和工作中,idea是程序员不可缺少的一个工具,但是突然在有些时候就会出现大量爆红的问题,发现无法跳转,无论是关机重启或者是替换root都无法解决 就是如上所展示的问题,但是程序依然可以启动。 问题解决…...
无法与IP建立连接,未能下载VSCode服务器
如题,在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈,发现是VSCode版本自动更新惹的祸!!! 在VSCode的帮助->关于这里发现前几天VSCode自动更新了,我的版本号变成了1.100.3 才导致了远程连接出…...
条件运算符
C中的三目运算符(也称条件运算符,英文:ternary operator)是一种简洁的条件选择语句,语法如下: 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true,则整个表达式的结果为“表达式1”…...
实现弹窗随键盘上移居中
实现弹窗随键盘上移的核心思路 在Android中,可以通过监听键盘的显示和隐藏事件,动态调整弹窗的位置。关键点在于获取键盘高度,并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...
Reasoning over Uncertain Text by Generative Large Language Models
https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...
代码规范和架构【立芯理论一】(2025.06.08)
1、代码规范的目标 代码简洁精炼、美观,可持续性好高效率高复用,可移植性好高内聚,低耦合没有冗余规范性,代码有规可循,可以看出自己当时的思考过程特殊排版,特殊语法,特殊指令,必须…...
MacOS下Homebrew国内镜像加速指南(2025最新国内镜像加速)
macos brew国内镜像加速方法 brew install 加速formula.jws.json下载慢加速 🍺 最新版brew安装慢到怀疑人生?别怕,教你轻松起飞! 最近Homebrew更新至最新版,每次执行 brew 命令时都会自动从官方地址 https://formulae.…...
【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制
目录 节点的功能承载层(GATT/Adv)局限性: 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能,如 Configuration …...
如何配置一个sql server使得其它用户可以通过excel odbc获取数据
要让其他用户通过 Excel 使用 ODBC 连接到 SQL Server 获取数据,你需要完成以下配置步骤: ✅ 一、在 SQL Server 端配置(服务器设置) 1. 启用 TCP/IP 协议 打开 “SQL Server 配置管理器”。导航到:SQL Server 网络配…...
