C++奇迹之旅:深度解析list的模拟实现

请添加图片描述

文章目录

  • 📝前言
  • 🌠list节点
    • 🌉list
  • 🌠迭代器的创建
    • 🌉const迭代器
  • 🌠代码
  • 🚩总结


📝前言

🌠list节点

我们先建立一个列表里的节点类listnode,用来构造list的节点使用:

// 这个宏定义用于禁用编译器的安全警告。
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <assert.h>
using namespace std;namespace own
{// 定义一个模板结构 listnode,代表链表中的节点template<typename T>struct listnode{// 指向前一个节点的指针listnode<T>* _prev;// 指向下一个节点的指针listnode<T>* _next;// 节点中存储的数据T _data;// 构造函数,初始化链表节点listnode(const T& data = T()): _prev(nullptr) // 前一个节点指针初始化为 nullptr, _next(nullptr) // 下一个节点指针初始化为 nullptr, _data(data)    // 节点中存储的数据初始化为传入的值(或默认值){}};
}

🌉list

在这里插入图片描述
list主要框架:

	template<typename T>class list{typedef listnode<T> Node;public:typedef ListIterator<T> iterator;typedef Listconst_Iterator<T> const_Iterator;list(){_head = new Node();_head->_prev = _head;_head->_next = _head;}iterator begin(){//iterator it(head->next);//return itreturn iterator(_head->_next);}iterator end(){return iterator(_head);}const_Iterator begin() const{//iterator it(head->next);//return itreturn const_Iterator(_head->_next);}const_Iterator end() const{return const_Iterator(_head);}private:Node* _head;};

begin使用迭代器iterator返回第一个数据,end返回最后一个数据的下一个位置,也就是头结点。

void test_list01()
{list<int> first;for (int i = 0; i < 4; i++){first.push_back(i);}//ListIterator<int> it = first.begin();list<int>::iterator it = first.begin();while (it != first.end()){cout << *it << " ";++it;}cout << endl;for (auto e : first){cout << e << " ";}cout << endl;
}

在这里插入图片描述
为了方便使用iterator,需要重新typedef命名:

typedef ListIterator<T> iterator;
typedef Listconst_Iterator<T> const_Iterator;

🌠迭代器的创建

在这里插入图片描述
在这里插入图片描述
我们使用模拟实现vector时,迭代器类型使用的是T*,因为vector底层是数组,地址连续,但是list不能使用T*,因为指针不能直接++,或–;也不能直接使用Node进行++或–,因此Node不符合遍历的行为,需要Listlterator类封装Node*,再通过重载运算符控制他的行为,具体原因也有以下:

  1. 内存布局

    • vector 中,元素是连续存储在内存中的,因此可以使用指针(如 T*)进行简单的算术运算(如 ++--)来访问相邻元素。
    • list 中,元素是分散存储的,每个节点通过指针连接到前一个和下一个节点。节点之间的内存地址不连续,因此不能简单地通过指针算术来访问相邻节点。
  2. 迭代器的设计

    • 对于 vector,迭代器通常是一个指向数组元素的指针(如 T*),可以直接进行指针运算。
    • 对于 list,迭代器需要封装一个指向节点的指针(如 Node*),并提供自定义的 ++-- 操作符来遍历链表。这是因为在链表中,节点之间的关系是通过指针而不是通过内存地址的连续性来维护的。
  3. 迭代器的有效性

    • 在链表中,插入和删除操作可能会导致迭代器失效。使用 Node* 作为迭代器类型时,删除节点后,指向该节点的迭代器将变得无效。因此,链表的迭代器需要在操作后返回一个新的有效迭代器(如在 erase 方法中返回下一个节点的迭代器)。
template<typename T>
struct ListIterator
{typedef listnode<T> Node;typedef ListIterator<T> self;Node* _node;ListIterator(Node* node):_node(node){}bool operator!=(const self& it){return _node != it._node;}bool operator==(const self& it){return _node = it._node;}};

我们先实现list的简单构造函数,接下来是迭代器++和–

//++it
self& operator++()
{_node = _node->_next;return *this;
}//it++
self operator++(int)
{self tmp(*this);_node = _node->_next;return tmp;
}self& operator--()
{_node = _node->_prev;return *this;
}self operator--(int)
{self tmp(*this);_node = _node->_prev;return tmp;
}

那么迭代器怎么访问数据的两种方法:
对于pos类:

struct Pos
{int _row;int _col;Pos(int row = 0, int col = 0):_row(row),_col(col){}
};

先把数据插入的多种方法:

void test_list2()
{list<Pos> lt1;A aa1(100,100);A aa2 = {100,100};lt1.push_back(aa1);lt1.push_back(aa2);lt1.push_back({100,100})lt1.push_back(Pos(100, 100));
}

我们使用其中一种方法插入数据就行:

void test_list2()
{list<Pos> lt1;lt1.push_back(Pos(100, 100));lt1.push_back(Pos(200, 200));lt1.push_back(Pos(300, 300));list<Pos>::iterator it = lt1.begin();while (it != lt1.end()){cout << (*it)._row << ":" << (*it)._col << endl;++it;}cout << endl;
}

这里数据是struct公有的,解引用得到的可以通过.访问符进行访问

cout << (*it)._row << ":" << (*it)._col << endl;

这里访问方式就是指针解引用用.访问符进行取数据:

A* ptr = &aa1;
(*ptr)._a1;

在这里插入图片描述
第二种:
还有使用->访问:

cout << it->_row << ":" << it->_col << endl;

但是这样需要重载operator->运算符

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

返回的是_data的地址
在这里插入图片描述
实际上它是有两个->的,第一个是oeprator()->,第二个是->

cout << it.operator->()->_row << ":" << it.operator->()->_col << endl;

这里隐藏了一个箭头,一个是重载,一个是原生指针的访问操作
在你提供的 test_list02 函数中,确实存在一个关于箭头操作符(->)的重载和原生指针访问的混合使用。让我们详细分析一下这个情况。

🌉const迭代器

typedef Listconst_Iterator<const T> const_Iterator;

对于这个cons_itertator直接这样加是不行的,无法编译成功,const不能调用非const成员函数

我们增加const版本的迭代器

typedef Listconst_Iterator<T> const_Iterator;
const_Iterator begin() const
{//iterator it(head->next);//return itreturn const_Iterator(_head->_next);
}const_Iterator end() const
{return const_Iterator(_head);
}

这里实现const迭代器呢?
第一种:单独实现一个类,修改正常版本的迭代器:

template<typename T>
class Listconst_Iterator
{typedef listnode<T> Node;typedef Listconst_Iterator<T> self;
public:Node* _node;Listconst_Iterator(Node* node):_node(node){}//++itself& operator++(){_node = _node->_next;return *this;}//it++self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}self& operator--(){_node = _node->_prev;return _node;}self operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}const T* operator->(){return &_node->_data;}const T& operator*(){return _node->_data;}bool operator!=(const self& it){return _node != it._node;}bool operator==(const self& it){return _node = it._node;}};

我们目的是不修改指向的值,只需要在这两个函数前面加上const即可:

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

在这里插入图片描述
第二种:合并两个迭代器

template<typename T,class ptr,class ref>
struct ListIterator
{typedef listnode<T> Node;typedef ListIterator<T, ptr, ref> self;Node* _node;ListIterator(Node* node):_node(node){}ptr operator->(){return &_node->_data;}ref operator*(){return _node->_data;}bool operator!=(const self& it){return _node != it._node;}bool operator==(const self& it){return _node = it._node;}};
  1. 模板定义
template<typename T, class ptr, class ref>
struct ListIterator
  • ListIterator 是一个模板结构体,接受三个模板参数:
    • T:表示链表中存储的数据类型。
    • ptr:表示指向 T 类型的指针类型(通常是 T*)。
    • ref:表示对 T 类型的引用类型(通常是 T&)。
  1. 类型别名
typedef listnode<T> Node;
typedef ListIterator<T, ptr, ref> self;
  • Node 是一个类型别名,表示链表节点的类型,即 listnode<T>
  • self 是一个类型别名,表示当前迭代器类型 ListIterator<T, ptr, ref>,用于在成员函数中引用自身类型。
ptr operator->()
{return &_node->_data;
}
  • 重载了箭头操作符 operator->(),使得可以通过迭代器访问节点中的数据。
  • 返回 _node 指向的节点的 _data 成员的地址,允许使用 it-> 语法来访问数据。
ref operator*()
{return _node->_data;
}
  • 重载了解引用操作符 operator*(),使得可以通过迭代器直接访问节点中的数据。
  • 返回 _node 指向的节点的 _data 成员,允许使用 *it 语法来访问数据。

最后我们需要在使用list里重新定义:

	template<typename T>class list{typedef listnode<T> Node;public://typedef ListIterator<T> iterator;//typedef Listconst_Iterator<T> const_Iterator;typedef ListIterator<T, T*, T&> iterator;typedef ListIterator<T, const T*, const T&> const_Iterator;list(){_head = new Node();_head->_prev = _head;_head->_next = _head;}......}

搞定了这些就是插入的删除的一些操作了

insert()
在这里插入图片描述

insert在这里不会出现迭代器失效,我们可以按照库里的写法进行模仿:

//没有iterator失效
iterator insert(iterator pos, const T& x)
{Node* cur = pos._node;Node* newnode = new Node(x);Node* prev = cur->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;return iterator(newnode);
}

erase

//erase 后pos失效了,pos指向的节点就被释放了
iterator erase(iterator pos)
{Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;return iterator(next);
}

erase()函数完成后,it所指向的节点已被删除,所以it无效,在下一次使用it时,必须先给其赋值erase删除返回的是下一个位置的迭代器

🌠代码

list.h

# define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <assert.h>using namespace std;namespace own
{template<typename T>struct listnode{listnode<T>* _prev;listnode<T>* _next;T _data;listnode(const T& data = T()):_prev(nullptr), _next(nullptr), _data(data){}};template<typename T,class ptr,class ref>struct ListIterator{typedef listnode<T> Node;typedef ListIterator<T, ptr, ref> self;Node* _node;ListIterator(Node* node):_node(node){}//++itself& operator++(){_node = _node->_next;return *this;}//it++self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}self& operator--(){_node = _node->_prev;return *this;}self operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}ptr operator->(){return &_node->_data;}ref operator*(){return _node->_data;}bool operator!=(const self& it){return _node != it._node;}bool operator==(const self& it){return _node = it._node;}};//template<typename T>//class Listconst_Iterator//{//	typedef listnode<T> Node;//	typedef Listconst_Iterator<T> self;//public://	Node* _node;//	Listconst_Iterator(Node* node)//		:_node(node)//	{}//	//++it//	self& operator++()//	{//		_node = _node->_next;//		return *this;//	}//	//it++//	self operator++(int)//	{//		self tmp(*this);//		_node = _node->_next;//		return tmp;//	}//	self& operator--()//	{//		_node = _node->_prev;//		return _node;//	}//	self operator--(int)//	{//		self tmp(*this);//		_node = _node->_prev;//		return tmp;//	}//	const T* operator->()//	{//		return &_node->_data;//	}//	const T& operator*()//	{//		return _node->_data;//	}//	bool operator!=(const self& it)//	{//		return _node != it._node;//	}//	bool operator==(const self& it)//	{//		return _node = it._node;//	}//};template<typename T>class list{typedef listnode<T> Node;public://typedef ListIterator<T> iterator;//typedef Listconst_Iterator<T> const_Iterator;typedef ListIterator<T, T*, T&> iterator;typedef ListIterator<T, const T*, const T&> const_Iterator;list(){_head = new Node();_head->_prev = _head;_head->_next = _head;}iterator begin(){//iterator it(head->next);//return itreturn iterator(_head->_next);}iterator end(){return iterator(_head);}const_Iterator begin() const{//iterator it(head->next);//return itreturn const_Iterator(_head->_next);}const_Iterator end() const{return const_Iterator(_head);}void push_back(const T& val = T()){/*Node* newnode = new Node(val);Node* tail = _head->_prev;tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;*/insert(end(), val);}void pop_back(){erase(--end());}void push_front(const T& val = T()){insert(begin(), val);}void pop_front(){erase(begin());}//没有iterator失效iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* newnode = new Node(x);Node* prev = cur->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;return iterator(newnode);}//erase 后pos失效了,pos指向的节点就被释放了iterator erase(iterator pos){Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;return iterator(next);}private:Node* _head;};void test_list01(){list<int> first;for (int i = 0; i < 4; i++){first.push_back(i);}//ListIterator<int> it = first.begin();list<int>::iterator it = first.begin();while (it != first.end()){cout << *it << " ";++it;}cout << endl;for (auto e : first){cout << e << " ";}cout << endl;}struct pos{int _row;int _col;pos(int row = 0, int col = 0):_row(row), _col(col){}};void test_list02(){list<pos> It1;It1.push_back(pos(100, 200));It1.push_back(pos(300, 400));It1.push_back(pos(500, 600));list<pos>::iterator it = It1.begin();while (it != It1.end()){//cout << (*it)._row << ":" << (*it)._col << endl;// 为了可读性,省略了一个->//cout << it->_row << ":" << it->_col << endl;//cout << it->->_row << ":" << it->->_col << endl;cout << it.operator->()->_row << ":" << it.operator->()->_col << endl;++it;}cout << endl;}void Fun(const list<int>& lt){list<int>::const_Iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;}void test_list03(){list<int> It2;It2.push_back(1);It2.push_back(2);It2.push_back(3);Fun(It2);}void test_list04(){list<int> It3;It3.push_back(1);It3.push_back(2);It3.push_back(3);It3.insert(It3.begin(), 100);It3.push_back(1);It3.push_back(2);It3.push_back(3);It3.erase(++It3.begin());list<int>::iterator it = It3.begin();while (it != It3.end()){cout << *it << " ";++it;}cout << endl;It3.pop_back();list<int>::iterator it2 = It3.begin();while (it2 != It3.end()){cout << *it2 << " ";++it2;}cout << endl;It3.push_front(200);list<int>::iterator it3 = It3.begin();while (it3 != It3.end()){cout << *it3 << " ";++it3;}cout << endl;It3.pop_front();list<int>::iterator it4 = It3.begin();while (it4 != It3.end()){cout << *it4 << " ";++it4;}}
}

🚩总结

请添加图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/413751.html

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

相关文章

数据仓库系列 3:数据仓库的主要组成部分有哪些?

你是否曾经好奇过,当你在网上购物或使用手机应用时,背后的数据是如何被存储和分析的?答案就在数据仓库中。本文将为你揭开数据仓库的神秘面纱,深入探讨其核心组成部分,以及这些组件如何协同工作,将海量数据转化为有价值的商业洞察。 目录 引言:数据仓库的魔力1. 数据源和数据…

[Algorithm][综合训练][体育课测验(二)][合唱队形][宵暗的妖怪]详细讲解

目录 1.体育课测验(二)1.题目链接2.算法原理详解 && 代码实现 2.合唱队形1.题目链接2.算法原理详解 && 代码实现 3.宵暗的妖怪1.题目链接2.算法原理详解 && 代码实现 1.体育课测验(二) 1.题目链接 体育课测验(二) 2.算法原理详解 && 代码实现…

解决Selenium已安装,在pycharm导入时报错

搭建设selenium环境时&#xff0c;selenium已安装&#xff0c;但是在pycharm中使用“from selenium import webdriver”语句时红线报错 解决方案&#xff1a; 1.file->settings进入设置 2.点击加号&#xff0c;搜索‘selenium’安装 3&#xff0c;等待安装完成&#xff0…

项目技巧二

目录 java中Date和mysql数据库datetime数据类型 注意&#xff1a; 在yml文件中配置成员变量的值 1.写一个yml文件 2.写一个与yml相互映射的类来读取yml的属性信息 3.在其他子模块的配置类中开启此类&#xff0c;读取yml文件的内容信息 4.直接依赖注入&#xff08;因为已…

Java多进程调用dll程序和exe程序

&#x1f3af;导读&#xff1a;本文介绍了使用Java调用本地DLL及EXE程序的方法。针对DLL调用&#xff0c;文章提供了基于Java Native Access (JNA) 库的具体实现方案&#xff0c;包括定义Java接口以映射DLL中的函数&#xff0c;并展示了如何加载DLL及调用其中的方法。对于EXE程…

opencv之几何变换

文章目录 1 前言2 线性几何变换的主要类型2.1 平移 (Translation)&#xff1a;2.1.1 定义2.1.2代码 2.2 缩放 (Scaling)&#xff1a;2.2.1 定义2.2.2 代码 2.3 旋转 (Rotation)&#xff1a;2.3.1 定义2.3.2 代码 2.4 仿射变换 (Affine Transformation)&#xff1a;2.4.1 定义2.…

数据源10min自动断开连接导致查询抛异常(未获取可用连接)

由于个人能力有限&#xff0c;本文章仅仅代表本人想法&#xff0c;若有不对请即时指出&#xff0c;若有侵权&#xff0c;请联系本人。 1 背景 工作中引入druid来管理数据源连接&#xff0c;由于数据源每隔10分钟强制管理空闲超过10分钟的连接&#xff0c;导致每隔10分钟出现1…

3D打印透气钢与传统透气钢的差异

透气钢作为一种集金属强度与透气性能于一体的特殊材料&#xff0c;在注塑模具领域扮演着关键角色&#xff0c;通过有效排除模具内困气&#xff0c;显著提升制品成型质量与生产效率。当前&#xff0c;市场上主流的透气钢产品多源自日本、美国&#xff0c;其高昂成本与技术壁垒限…

Golang | Leetcode Golang题解之第388题文件的最长绝对路径

题目&#xff1a; 题解&#xff1a; func lengthLongestPath(input string) (ans int) {n : len(input)level : make([]int, n1)for i : 0; i < n; {// 检测当前文件的深度depth : 1for ; i < n && input[i] \t; i {depth}// 统计当前文件名的长度length, isFi…

生成艺术,作品鉴赏:物似主人形

2001年&#xff0c;当21岁的我&#xff0c;还在恒基伟业当高级工程师时。我有一个女同事&#xff0c;她有个特别大的杯子用来喝水&#xff0c;不夸张的说&#xff0c;是那种我从来没见过的大杯子&#xff0c;由于她是很大只的那种&#xff0c;她便自嘲说&#xff1a;「物似主人…

【Kubernetes部署篇】二进制搭建K8s高可用集群1.26.15版本(超详细,可跟做)

文章目录 一、服务器环境信息及部署规划1、K8S服务器信息及网段规划2、服务器部署架构规划3、组件版本信息4、实验架构图 二、初始化环境操作1、关闭防火墙2、配置本地域名解析3、配置服务器时间保持一致4、禁用swap交换分区(K8S强制要求禁用)5、配置主机之间无密码登录6、修改…

JVM2-JVM组成、字节码文件、类的生命周期、类加载器

Java虚拟机的组成 Java虚拟机主要分为以下几个组成部分&#xff1a; 类加载子系统&#xff1a;核心组件类加载器&#xff0c;负责将字节码文件中的内容加载到内存中运行时数据区&#xff1a;JVM管理的内存&#xff0c;创建出来的对象、类的信息等内容都会放在这块区域中执行引…

RelativeLayout相对布局

activity_relative_layout.xml <?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"150dp…

QT QGraphicsView实现预览图片显示缩略图功能

QT QGraphicsView实现预览图片显示缩略图功能QT creator Qt5.15.2 头文件&#xff1a; #ifndef TGRAPHICSVIEW_H #define TGRAPHICSVIEW_H#include <QGraphicsView> #include <QMainWindow> #include <QObject> #include <QWidget>class TGraphicsVie…

Oracle 客户端 PL/SQL Developer 15.0.4 安装与使用

目录 官网下载与安装 切换中文与注册 连接Oracle数据库 tnsnames.ora 文件使用 Oracle 客户端 PL/SQL Developer 12.0.7 安装、数据导出、Oracle 执行/解释计划、for update。 官网下载与安装 1、官网&#xff1a;https://www.allroundautomations.com/products/pl-sql-d…

P01-何谓Java方法

P01-何谓Java方法 一、System.out.println()分析 二、剖析方法 谈到方法&#xff0c;我就突然想到了c函数&#xff1a; 其实&#xff1a;Java 方法和 C 函数在许多方面确实有类似之处&#xff0c;但它们也存在一些显著的差异。下面是它们的一些共同点和不同点&#xff1a; 共同…

DORIS - DORIS简介

前言 本博文基于DORIS的2.1.5版本。apache-doris-2.1.5-bin-x64.tar.gz 是什么&#xff1f; DORIS官网 Apache Doris 是一款基于 MPP 架构的高性能、实时的分析型数据库&#xff0c;以高效、简单、统一的特点被人们所熟知&#xff0c;仅需亚秒级响应时间即可返回海量数据下的…

【第0004页 · 递归】生成括号对

【前言】本文以及之后的一些题解都会陆续整理到目录中&#xff0c;若想了解全部题解整理&#xff0c;请看这里&#xff1a; 第0004页 生成括号对 今天这题有点难绷&#xff0c;从某种程度上来说应该是第二次写这个问题了&#xff0c;但还是卡住了&#xff0c;现在我们来看一下…

安防视频汇聚平台EasyCVR启动后无法访问登录页面是什么原因?

安防视频监控/视频集中存储/云存储/磁盘阵列EasyCVR平台基于云边端一体化架构&#xff0c;兼容性强、支持多协议接入&#xff0c;包括国标GB/T28181协议、部标JT808、GA/T1400协议、RTMP、RTSP/Onvif协议、海康Ehome、海康SDK、大华SDK、华为SDK、宇视SDK、乐橙SDK、萤石云SDK等…

设计模式之适配器模式:软件世界的桥梁建筑师

一、什么是适配器模式 适配器模式&#xff08;Adapter Pattern&#xff09;是一种结构型设计模式&#xff08;Structural Pattern&#xff09;&#xff0c;通过将类的接口转换为客户期望的另一个接口&#xff0c;适配器可以让不兼容的两个类一起协同工作。其核心思想是通过一个…