C++学习之STL学习：list的模拟实现

        在上一篇学习了list的使用后，在本篇我们将通过模拟实现的方式深入了解list的底层运作原理。

        作者的个人gitee：楼田莉子 (riko-lou-tian) - Gitee.com

        感兴趣的读者可以看一看

目录

前置准备

        结点的定义

        链表类的定义

迭代器 

        普通迭代器

        const迭代器 

        list中关于迭代器的声明 

        误区：

相关函数

        push_back

        insert

        erase

源代码

前置准备

        结点的定义

        我们需要定义一个结点的类（参考之前双向链表那篇博客：数据结构学习之双向循环链表-CSDN博客），因为这个类中的成员我们都想要访问，如果想要方便写的话，可以用struct（struct中默认为公开），并且用命名空间封装

namespace Boogiepop
{template<class T>//当我们不需要也不想要让访问限定符限制的时候//可以用struct来定义类，而不是用classstruct list_node{T _data;			//数据list_node<T>* _next;//指向下一个节点的指针list_node<T>* _prev;//指向前一个节点的指针};
}

        同时因为list模拟实现中使用了模板，所以函数的定义也只能在.h文件中（） 

        同时切记，模板只能给对应的类或函数使用，是“一次性”的，想再次使用一样的模板必须重新定义

        链表类的定义

template<class T>
class list
{typedef list_node<T> node;
public://构造函数list(){_head = new node;_head->_next = _head;_head->_prev = _head;}
private:node* _head;		//指向头节点的指针};

迭代器 

        双链表迭代器相关图解：

         迭代器用node*封装无法达到预期行为；用类封装node*重载运算符，就可以控制迭代器的行为。

        迭代器行为模拟的是普通指针访问数组的行为

        普通迭代器

	//迭代器template<class T,class Ref>//当我们不需要也不想要让访问限定符限制的时候//可以用struct来定义类，而不是用class//普通迭代器struct _list_iterator{typedef list_node<T> node;typedef _list_iterator<T, Ref> Self;node* _node;//构造迭代器_list_iterator(node* node) :_node(node){}//解引用不是结点//用引用返回可以修改这个数值T& operator*(){return _node->_data;}////不能实现，因为const list_iterator对象才能调用这个重载////但是在这种情况下const list_iterator对象不能调用++和--//const T& operator*()const//{//	return _node->_data;//}//迭代器++//前置++Self& operator++(){_node = _node->_next;return *this;}//后置Self& operator++(int){_list_iterator<T,Ref> tmp (*this);//浅拷贝_node = _node->_next;return *this;}//前置--Self& operator--(){_node = _node->prev;return *this;}//后置--Self& operator--(int){Self tmp (*this);//浅拷贝_node = _node->prev;return *this;}//返回是否相等bool operator!=(const Self& it)const{return _node!= it._node; }bool operator==(const Self& it)const{return _node == it._node;}};

        const迭代器 

	//const迭代器template<class T,class Ref>//当我们不需要也不想要让访问限定符限制的时候//可以用struct来定义类，而不是用classstruct _list_const_iterator{typedef list_node<T> node;typedef _list_const_iterator<T, Ref> Self;node* _node;//构造迭代器_list_const_iterator(node* node) :_node(node){}//解引用不是结点//用引用返回可以修改这个数值const Self& operator*(){return _node->_data;}//迭代器++//前置++Self& operator++(){_node = _node->_next;return *this;}//后置Self& operator++(int){Self tmp(*this);//浅拷贝_node = _node->_next;return *this;}//前置--Self& operator--(){_node = _node->prev;return *this;}//后置--Self& operator--(int){Self tmp(*this);//浅拷贝_node = _node->prev;return *this;}//返回是否相等bool operator!=(const Self& it)const{return _node != it._node;}bool operator==(const Self& it)const{return _node == it._node;}};

        list中关于迭代器的声明 

//链表
template<class T>
class list
{typedef list_node<T> node;
public://普通迭代器typedef _list_iterator<T,Ref> iterator;//const迭代器typedef const _list_iterator<T,Ref> const_iterator;//返回迭代器iterator begin(){return iterator(_head->_next);}//返回迭代器iterator end(){return iterator(_head);}//其余部分在此处省略。。。。。。
}

 测试：

void test1()
{Boogiepop::list<int> list;list.push_back(1);list.push_back(2);list.push_back(3);list.push_back(4);list.push_back(5);Boogiepop::list<int>::iterator it = list.begin();while (it != list.end()){cout << *it << " ";++it;}cout<<endl;
}

        普通迭代器可以修改指向的内容，const迭代器不可以修改指向的内容

        误区：

        1、

        这么写是不对的，这样迭代器本身无法修改,无法进行++和--

typedef const iterator const_iterator;

        string和vector可以这么干是因为const修饰的指向的内容 

        但是list只能重新搞一个类型实现

         2、还有这种情况，写重载能否实现？答案是不能

T& operator*()
{return _node->_data;
}
const T& operator*()const
{return _node->_data;
}

        因为：

T& operator*()
{return _node->_data;
}
//不能实现，因为const list_iterator对象才能调用这个重载
//但是在这种情况下const list_iterator对象不能调用++和--
const T& operator*()const
{return _node->_data;
}

        

相关函数

        push_back

void push_back(const T&x)
{node* new_node = new node(x);//头结点node* tail=_head->_prev;//尾节点tail->_next = new_node;new_node->_prev = tail;new_node->_next = _head;_head->_prev = new_node;
}

        insert

void insert(iterator pos, const T& x)
{node* cur = pos._node;node*new_node = new node(x);node*prev = cur->_prev;//prev  new_node  curprev->_next = new_node;new_node->_next = cur;cur->_prev = new_node;new_node->_prev = prev;
}

        erase

iterator erase(iterator pos)
{node* cur=pos._next;node*prev=cur->_prev;node*next=cur->_next;prev->_next=next;next->_prev=prev;delete cur;return iterator(next);//也可以这么写return next
}

源代码

list.h

#pragma once
#include<iostream>
using namespace std;
namespace Boogiepop
{//节点template<class T>//当我们不需要也不想要让访问限定符限制的时候//可以用struct来定义类，而不是用classstruct list_node{T _data;			//数据list_node<T>* _next;//指向下一个节点的指针list_node<T>* _prev;//指向前一个节点的指针//构造函数list_node(const T& x = T()) :_data(x), _next(nullptr), _prev(nullptr){}};//迭代器template<class T, class Ref>//当我们不需要也不想要让访问限定符限制的时候//可以用struct来定义类，而不是用class//普通迭代器struct _list_iterator{typedef list_node<T> node;typedef _list_iterator<T, Ref> Self;node* _node;//构造迭代器_list_iterator(node* node) :_node(node){}//解引用不是结点//用引用返回可以修改这个数值T& operator*(){return _node->_data;}////不能实现，因为const list_iterator对象才能调用这个重载////但是在这种情况下const list_iterator对象不能调用++和--//const T& operator*()const//{//	return _node->_data;//}//迭代器++//前置++Self& operator++(){_node = _node->_next;return *this;}//后置Self& operator++(int){_list_iterator<T, Ref> tmp(*this);//浅拷贝_node = _node->_next;return *this;}//前置--Self& operator--(){_node = _node->prev;return *this;}//后置--Self& operator--(int){Self tmp(*this);//浅拷贝_node = _node->prev;return *this;}//返回是否相等bool operator!=(const Self& it)const{return _node != it._node;}bool operator==(const Self& it)const{return _node == it._node;}};//const迭代器template<class T, class Ref>//当我们不需要也不想要让访问限定符限制的时候//可以用struct来定义类，而不是用class//普通迭代器struct _list_const_iterator{typedef list_node<T> node;typedef _list_const_iterator<T, Ref> Self;node* _node;//构造迭代器_list_const_iterator(node* node) :_node(node){}//解引用不是结点//用引用返回可以修改这个数值const Self& operator*(){return _node->_data;}//迭代器++//前置++Self& operator++(){_node = _node->_next;return *this;}//后置Self& operator++(int){Self tmp(*this);//浅拷贝_node = _node->_next;return *this;}//前置--Self& operator--(){_node = _node->prev;return *this;}//后置--Self& operator--(int){Self tmp(*this);//浅拷贝_node = _node->prev;return *this;}//返回是否相等bool operator!=(const Self& it)const{return _node != it._node;}bool operator==(const Self& it)const{return _node == it._node;}};//链表template<class T, class Ref>class list{typedef list_node<T> node;typedef _list_iterator<T, Ref> Self;typedef _list_const_iterator<T, Ref> const_Self;public://普通迭代器typedef _list_iterator<T, Ref> iterator;//const迭代器typedef const _list_iterator<T, Ref> const_iterator;//返回迭代器iterator begin(){return iterator(_head->_next);}//返回迭代器iterator end(){return iterator(_head);}//构造函数list(){_head = new node;_head->_next = _head;_head->_prev = _head;}//拷贝构造函数list(const list<T>& lt){_head = new node;_head->_next = _head;_head->_prev = _head;for (const auto& x : lt){push_back(x);}}//花括号初始化list(initializer_list<T> il){_head = new node;_head->_next = _head;_head->_prev = _head;for (const auto& x : lt){push_back(x);}}//=运算符重载list<T>& operator=(const list<T>& lt){if (this != &lt){clear();for (const auto& x : lt){push_back(x);}}return *this;}//析构函数//释放结点~list(){clear();delete _head;_head = nullptr;}void push_back(const T& x){node* new_node = new node(x);//头结点node* tail = _head->_prev;//尾节点tail->_next = new_node;new_node->_prev = tail;new_node->_next = _head;_head->_prev = new_node;}//交换数据void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}//插入元素void insert(iterator pos, const T& x){node* cur = pos._node;node* new_node = new node(x);node* prev = cur->_prev;//prev  new_node  curprev->_next = new_node;new_node->_next = cur;cur->_prev = new_node;new_node->_prev = prev;}void push_back(const T& x){insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_front(){erase(begin());}void pop_back(){erase(--end());}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}iterator erase(iterator pos){node* cur = pos._next;node* prev = cur->_prev;node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;return iterator(next);//也可以这么写return next}//返回链表大小size_t size()const{}private:node* _head;		//指向头节点的指针};
};

       

        提示：类的模板没有实例化不能去类模板中找后面的东西编译器无法区分const_iterator 是嵌套内类还是静态成员变量，typename是告诉编译器确认过是类型

        本期内容就到这里，感兴趣的可以点个赞谢谢

封面图自取： 

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.pswp.cn/bicheng/87888.shtml
繁体地址，请注明出处：http://hk.pswp.cn/bicheng/87888.shtml

如若内容造成侵权/违法违规/事实不符，请联系多彩编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

不引入变量 异或交换的缺点

不引入变量 异或交换的缺点

文章目录选择排序正确代码交换两个数位置的方法引入中间变量不引入中间变量&#xff0c;使用异或的方法错误原因优化代码选择排序正确代码 // 数组中交换i和j位置的数public static void swap(int[] arr, int i, int j) {int tmp arr[i];arr[i] arr[j];arr[j] tmp;}// 选择排…
阅读更多...
VS Code中使用Git的方法：环境配置与Git操作

VS Code中使用Git的方法：环境配置与Git操作

本文介绍在Windows电脑的VS Code中&#xff0c;配置Git环境并使用Git命令、功能的方法。 1 环境部署 首先&#xff0c;我们需要分别安装Git环境与VS Code软件。这里需要注意&#xff0c;即使是在VS Code中使用Git&#xff0c;也需要我们首先在电脑上单独配置好Git的环境&#…
阅读更多...
在 Windows 上安装和运行 Apache Kafka

在 Windows 上安装和运行 Apache Kafka

Apache Kafka是一款开源应用程序&#xff0c;用于实时处理海量数据流。Apache Kafka 是一个发布-订阅消息系统。消息系统允许您在进程、应用程序和服务器之间发送消息。广义上讲&#xff0c;Apache Kafka 是一款可以定义主题并进行进一步处理的软件。 下载和安装 Apache Kafk…
阅读更多...
【嵌入式电机控制#8】编码器测速实战

【嵌入式电机控制#8】编码器测速实战

一、编码器测速重要参数有刷电机编码器参数&#xff08;其他的后面会慢慢提及&#xff0c;也可以在某宝看&#xff09;1. 编码器分辨率&#xff08;PPR&#xff09;2. 编码器工作电压 3. 电机减速比 例如 30&#xff1a;1 指的就是电机减速轴转1圈&#xff0c;编码器转30圈。注…
阅读更多...
在C#中，可以不实例化一个类而直接调用其静态字段

在C#中，可以不实例化一个类而直接调用其静态字段

这是因为静态成员&#xff08;static members&#xff09;属于类本身&#xff0c;而不是类的实例。这是静态成员的核心特性1. 静态成员属于类&#xff0c;而非实例当用static关键字修饰字段、方法或属性时&#xff0c;这些成员会绑定到类级别&#xff0c;而不是实例级别。它们在…
阅读更多...
Win11 安装 Visual Studio（保姆教程 - 更新至2025.07）

Win11 安装 Visual Studio（保姆教程 - 更新至2025.07）

Visual Studio 安装&#xff08;保姆教程 - 更新至2025.07&#xff09; 前言安装须知安装过程1. 下载安装包2. 安装3. 注册4. 创建桌面快捷方式 前言 本教程针对 非计算机相关专业的小白用户 &#xff0c;手把手教你如何基于 win11 操作系统 安装 Visual Studio 2022。安装搭载…
阅读更多...
工商银行杭州软开校招面经分享

工商银行杭州软开校招面经分享

近年来，央国企成为了很多求职者的首选，无论是校招还是社招。不过，在选择央国企的时候，还是尽量要选择垄断性或者盈利多的。 昨天看到一份 2024 年中国企业 500 强榜单中提到的最赚钱的十家央国企的名单，给大家分享一下。 排名企业名称成立时间主要业务描述2024年营收（万…
阅读更多...
李宏毅genai笔记：推理

李宏毅genai笔记：推理

0 思考越多效果越好 可以把算力投入在training的时候&#xff0c;也可以投入在testing上面 连起来的线表示表现是差不多的&#xff0c;越高分&#xff08;越右上方&#xff09;越好 同样-1000分&#xff0c;可以训练时候用力较少&#xff0c;test的时候多用点算力 但是training…
阅读更多...
使用SSH隧道连接远程主机

使用SSH隧道连接远程主机

概述 SSH（Secure Shell 的缩写）是一种网络协议，通过使用身份验证机制，是两台计算机进行加密通信。 SSH 主要用途是登录服务器，还可以作为加密通信的中介，充当两台服务器之间的通信加密跳板，这个功能称为端口转发（port forwarding），又称 SSH 隧道（tunnel）。 端口…
阅读更多...
数据结构---链表理解（二）

数据结构---链表理解（二）

文章目录 二、链表2.1 链表初始化2.2 单链表2.2.1 单链表---头插法2.2.2 单链表---单链表遍历2.2.3 单链表---尾插法2.2.4 单链表---在指定位置插入数据2.2.5 单链表---删除指定位置节点2.2.6 单链表---获取链表长度2.2.7 单链表---释放链表 二、链表 暂时到这一步你就理解为&a…
阅读更多...
Playnite使用指北 —— 一个优秀的本地化游戏管理工具

Playnite使用指北 —— 一个优秀的本地化游戏管理工具

为何我们使用 Playnite&#xff1f; 首先我们需要知道 Playnite 是什么&#xff0c;如果你有过用 emby 等管理过电影影视的经验&#xff0c;你可能会对这种工具感到熟悉&#xff1a; Playnite 是一个开源的本地化的游戏管理软件&#xff0c;可以实现多平台的管理&#xff08;S…
阅读更多...
时间与空间复杂度详解：算法效率的度量衡

时间与空间复杂度详解：算法效率的度量衡

一、为什么需要复杂度分析&#xff1f; 想象你正在开发一个手机通讯录应用&#xff0c;需要实现联系人搜索功能。你有两种算法可以选择&#xff1a; // 算法A&#xff1a;线性搜索 public Contact linearSearch(List<Contact> contacts, String name) {for (Contact c …
阅读更多...
408第三季part2 - 计算机网络 - 交换机

408第三季part2 - 计算机网络 - 交换机

理解 题目 如果你这么做 那你完了&#xff0c;因为这种叫存储转发 直通只转目的地址 b 再次理解 A发数据到交换机里想给B 然后交换表会记录A的MAC地址和端口 然后因为交换表找不到B&#xff0c;所以A会把BCD全部肘一遍&#xff08;广播&#xff09;&#xff0c;最终只有B会…
阅读更多...
从零开始开发纯血鸿蒙应用之探析仓颉语言与ArkTS的差异

从零开始开发纯血鸿蒙应用之探析仓颉语言与ArkTS的差异

探析仓颉语言与ArkTS的差异 〇、前言一、IDE 的支持程度不同二、内置组件的使用方式不同三、页面路由实现方式的不同四、总结 〇、前言 截止到本文发布的日期为止&#xff0c;鸿蒙官方所推荐的开发原生鸿蒙应用的语言&#xff0c;有两种&#xff0c;分别是扩展自 Typescript 的…
阅读更多...
Cursor/VScode ,点击运行按钮，就打开新的终端，如何设置为在当前终端运行文件而不是重新打开终端----一招搞定篇

Cursor/VScode ,点击运行按钮，就打开新的终端，如何设置为在当前终端运行文件而不是重新打开终端----一招搞定篇

我发现就是&#xff0c;我运行.py&#xff0c;点击完运行按钮&#xff0c;就给我重新打开一个终端&#xff0c;然后新的终端是在base环境中的&#xff0c;就跟麻烦 还得在当前终端输入python3 test.py 来运行文件。能不能修改。1、打开cursor或者vscode 。 同时按下 ctrlshiftp…
阅读更多...
【STM32实践篇】：I2C驱动编写

【STM32实践篇】：I2C驱动编写

文章目录I2C 物理层I2C 协议层1. 数据有效性2. 起始和停止信号3. 应答响应4. 总线的寻址方式5. 数据传输5.1 主机向从机发送数据5.2 主机由从机中读数据5.3 I2C通信复合格式I2C 驱动编写1. 配置 SCL 和 SDA2. I2C起始信号和停止信号3. 等待从设备应答4. 主机发送ACK和NACK信号5…
阅读更多...
ragflow本地部署教程linux Ubuntu系统

ragflow本地部署教程linux Ubuntu系统

以下是一份在 Ubuntu 系统上本地部署 RAGFlow 的详细教程。 一、基础环境准备 1.硬件要求 –CPU ≥ 4核 –RAM ≥ 16 GB –磁盘空间 ≥ 50 GB&#xff08;建议 SSD&#xff09; 2.系统配置 更新系统 sudo apt update && sudo apt upgrade -y 设置内核参数&#xff…
阅读更多...
[netty5: WebSocketClientHandshaker WebSocketClientHandshakerFactory]-源码分析

[netty5: WebSocketClientHandshaker WebSocketClientHandshakerFactory]-源码分析

在阅读这篇文章前&#xff0c;推荐先阅读以下内容&#xff1a; [netty5: WebSocketFrame]-源码分析[netty5: WebSocketFrameEncoder & WebSocketFrameDecoder]-源码解析 WebSocketClientHandshakerFactory WebSocketClientHandshakerFactory 是用于根据 URI 和协议版本创…
阅读更多...
4.2 如何训练⼀个 LLM

4.2 如何训练⼀个 LLM

⼀般⽽⾔&#xff0c;训练⼀个完整的 LLM 需要经过图1中的三个阶段——Pretrain、SFT 和 RLHF。 4.2.1 Pretrain 预训练任务与架构 任务类型&#xff1a;采用因果语言模型&#xff08;CLM&#xff09;&#xff0c;通过预测下一个 token 进行训练&#xff0c;与传统预训练模型…
阅读更多...
Qt中的QObject::moveToThread方法详解

Qt中的QObject::moveToThread方法详解

一、QObject::moveToThread方法QObject::moveToThread()是Qt框架中一个非常重要的功能&#xff0c;它允许改变QObject及其子对象的线程关联性。这个功能在多线程编程中特别有用&#xff0c;可以将耗时操作移到工作线程执行&#xff0c;避免阻塞主线程/GUI线程。基本用法void QO…
阅读更多...
最新文章

Copyright @ 2022~2023