[ C++ ] STL---list的模拟实现

目录

结点类的模拟实现

迭代器类的模拟实现

构造函数

前置++与后置++

前置- -与后置 - -

== 与 !=运算符重载

* 运算符重载

-> 运算符重载

普通迭代器总体实现代码

list类的实现

list类的成员变量

构造函数

迭代器

insert(）

erase()

push_front/push_back/pop_front/pop_back

front/back

clear()

empty()

swap()

拷贝构造函数

赋值运算符重载

析构函数

结点类的模拟实现

list 的底层结构为带头双向循环链表，所以结点类里的成员变量：

T _data(数据)，ListNode<T>* _prev(前驱指针)，ListNode<T>* _next(后继指针)；

成员函数只需要构造函数即可(指针初始化为nullptr，数据以缺省参数的形式进行初始化)；

template<class T>
struct ListNode
{
	//结点中的成员变量
	T _data;//数据
	ListNode<T>* _prev;//前驱指针
	ListNode<T>* _next;//后继指针

	//结点类的构造函数
	ListNode(const T& val=T())
		: _data(val)
		, _prev(nullptr)
		, _next(nullptr)
	{}
};

迭代器类的模拟实现

迭代器并不关心容器底层的数据结构为顺序表、链表或者树型结构，提供统一的方式访问、修改容器中的数据并且遍历区间为左闭右开[begin,end)；

vector与string的模拟实现中，迭代器均为原生指针，是因为vector和string底层物理空间连续(顺序表)，那么list可否采用原生指针(结点指针)作为迭代器?

思考一：

若it为结点指针，it++，能否从链表的当前位置指向链表当前位置的下一位置?  (×)

思考二：

若it为结点指针，*it，能否得到链表结点中的数据_data?（×）

解决方案：

采用原生指针作为list的迭代器均不满足需求，运算符重载可以对已有的运算符重新进行定义，赋予其另一种功能，从而满足需求，但是运算符重载的前提为自定义类型，而指针本身为内置类型，只能将结点指针封装为自定义类型，从而使用运算符重载满足需求；

迭代器的成员变量 : Node* _node；（_node为指向结点的指针）
迭代器的成员函数 : 运算符重载函数；

template<class T>
//使用struct关键字封装结点指针,方便访问数据成员_node
//若使用class关键字封装节点指针,需要提供函数接口访问_node
struct __List_iterator
{
	typedef ListNode<T> Node;
	Node* _node;
};

构造函数

//__List_iterator it();
//需要结点指针对_node进行有参构造且不能给定缺省值为nullptr,
//否则解引用操作导致系统崩溃
//__List_iterator(Node* node=nullptr)(×)
//因此迭代器遍历链表时必须给定有效参数,参数为结点指针;
__List_iterator(Node* node)
   :_node(node)
	{}

思考：迭代器内部需要实现析构函数，拷贝构造函数吗？

      1. 提供链表的结点指针给迭代器，方便迭代器访问链表结点，并不需要释放结点；

          而且对于内置类型(指针)成员变量，编译器自动生成的析构函数不做任何处理；

      2. 将一个迭代器拷贝给另一个迭代器，只需要两个迭代器指向同一个链表结点，

          而编译器自动生成的拷贝构造函数实现了浅拷贝，所以不需要实现拷贝构造函数；

前置++与后置++

前置++，this指针出作用域销毁，但是this指针指向的对象在函数结束不会被销毁，以传引用的方式返回以提升效率；

//++it
__List_iterator<T>& operator++()
{
	_node = _node->_next;
	return *this;
}

返回类型太长，使用typedef重定义类型名；

typedef __List_iterator<T> self;
self& operator++()
{
	_node = _node->_next;
	return *this;
}

C++规定：

后置++重载时多增加一个int类型的参数，但调用函数时参数不需要传递，编译器自动传递；

后置++，tmp为临时拷贝对象，出作用域销毁，只能以传值的方式返回；

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

前置- -与后置 - -

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

== 与 !=运算符重载

==运算符重载比较两个迭代器对象的_node指针指向是否相同；

bool operator==(const self& s)
{
	return _node == s._node;
}

!=运算符重载比较两个迭代器对象的_node指针指向是否相同；

bool operator!=(const self& s)
{
	return _node != s._node;
}

* 运算符重载

重载 * 运算符的目的是为了得到迭代器对象的_node指针所指向的数据；

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

-> 运算符重载

struct Date
{
	int _year = 2024;
	int _month = 1;
	int _day = 1;
};
int main()
{
	//链表中的数据成员为自定义类型Date
	list<Date> lt;
	Date d1;
	lt.push_back(d1);

	//it为封装结点指针的迭代器类
	list<Date>::iterator it = lt.begin();

	//结点中的数据成员访问方式1: 结构体变量.结构体成员
	cout << (*it)._year << " " << (*it)._month << " " << (*it)._day << endl;
	cout << it.operator*()._year << " " << it.operator*()._month << " " << it.operator*()._day << endl;

	//结点中的数据成员访问方式2: 结构体指针->结构体成员

	//it->_year本应该为it->->_year,但由于->->可读性差,编译器优化为->;
	//第一个->去调用operator->重载函数返回Date*的指针，第二个->用来去访问自定义类型的成员变量;
	cout << it->_year << " " << it->_month << " " << it->_day << endl;
	cout << it.operator->()->_year << " " << it.operator->()->_month <<" " << it.operator->()->_day<< endl;
}

当迭代器内部重载了operator->()函数，且该函数返回结点中的数据成员的地址，便可以使用->访问自定义类型数据中的成员变量；

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

普通迭代器总体实现代码

template<class T>
struct __List_iterator
{
	typedef ListNode<T> Node;
	Node* _node;
	__List_iterator(Node* node)
		:_node(node)
	{}
	typedef __List_iterator<T> self;
	//++it
	self& operator++()
	{
		_node = _node->_next;
		return *this;
	}
	//it++
	self operator++(int)
	{
		self tmp(*this);
		_node = _node->_next;
		return tmp;
	}
	//--it
	self& operator--()
	{
		_node = _node->_prev;
		return *this;
	}
	//it--
	self operator--(int)
	{
		self tmp(*this);
		_node = _node->_prev;
		return tmp;
	}
	bool operator==(const self& s)
	{
		return _node == s._node;
	}
	bool operator!=(const self& s)
	{
		return _node != s._node;
	}
	T& operator*()
	{
		return _node->_data;
	}
	T* operator->()
	{
		return &_node->_data;
	}
};

无论是普通迭代器还是const迭代器，均需要迭代器遍历容器中的内容，因此迭代器本身可以被修改，区别仅在于迭代器指向的内容是否可以被修改，那么该如何实现const迭代器类呢？

由于const迭代器本质为保护迭代器指向的内容不允许被修改，若实现const迭代器类，只需要普通迭代器的operator*()与operator->()两个接口的返回值采用const修饰，便保护容器中的内容不会被修改，其余接口均保持不变；

template<class T>
struct __List_const_iterator
{
	typedef ListNode<T> Node;
	Node* _node;
	__List_const_iterator(Node* node)
		:_node(node)
	{}
	typedef __List_const_iterator<T> self;
	self& operator++();
	self operator++(int);
	self& operator--();
	self operator--(int);
	bool operator==(const self& s);
	bool operator!=(const self& s);
	const T& operator*()
	{
		return _node->_data;
	}
	const T* operator->()
	{
		return &_node->_data;
	}
};

上述实现方案，在同一份文件中存在普通迭代器类与const迭代器类，两者之间仅有两个接口的返回值不同，如此便造成了代码的冗余，导致可读性变差，那么该如何改进呢？

迭代器类增加两个模版参数，使用时便可实例化出普通迭代器与const迭代器；

//迭代器实现最终总体代码,只给出函数声明与普通迭代器代码相同
template<class T,class Ref,class Ptr>
struct __List_iterator
{
	typedef ListNode<T> Node;
	Node* _node;
	__List_iterator(Node* node)
		:_node(node)
	{}
	typedef __List_iterator<T> self;
	self& operator++();
	self operator++(int);
	self& operator--();
	self operator--(int);
	bool operator==(const self& s);
	bool operator!=(const self& s);
	Ref operator*()
	{
		return _node->_data;
	}
	Ptr operator->()
	{
		return &_node->_data;
	}
};

当在list类中定义两个迭代器类，普通迭代器类，const迭代器类(Ref为 T&/const T& 类型，Ptr为 T*/const T* 类型)

typedef __List_iterator<T,T&,T*> iterator;
typedef __List_iterator<T,const T&,const T*> const_iterator;

当使用普通迭代器对象时，实例化出普通迭代器类(iterator)，使用const迭代器对象时，实例化出const迭代器类(const_iterator) ；

list类的实现

list类的成员变量

list类的成员变量只需要一个头结点，便可通过迭代器访问其他节点元素；

template<class T>
class list
{
	typedef ListNode<T> Node;
public:
	typedef __List_iterator<T, T& , T*> iterator;//重命名普通迭代器
	typedef __List_iterator<T, const T&, const T*> const_iterator;//重命名const迭代器
private:
	Node* _head;
};

构造函数

list()
{
	_head = new Node; // 申请一个头结点
	_head->_next = _head; // 后继指针指向自己
	_head->_prev = _head; // 前驱指针指向自己
}

迭代器

begin() : 构造出指针指向第一个结点的迭代器对象；
end() :    构造出指针指向头结点的迭代器对象；

iterator begin()
{
	//return iterator(_head->_next);
	//单参数的构造函数支持类型转换__List_iterator(Node* node)
	//支持Node* 转换为 迭代器对象
	return _head->_next;
}

iterator end()
{
	return _head;
}

const_iterator begin() const
{
	return _head->_next;
}

const_iterator end() const
{
	return _head;
}

insert(）

  1. 新开辟一个结点newnode(值为val)，得到当前结点的指针，前驱结点的指针；
  2. 前驱结点的_next 指向 newnode，newnode的_prev指向前驱结点；
  3. newnode的_next 指向当前结点，当前结点的_prev指向newnode；
iterator insert(iterator pos, const T& x)
{
	Node* cur = pos._node;//当前结点指针
	Node* prev = cur->_prev;//前驱结点指针
	Node* newnode = new Node(x);//新开辟结点

	prev->_next = newnode;
	newnode->_prev = prev;
	newnode->_next = cur;
	cur->_prev = newnode;

	//return iterator(newnode);
	return newnode;
}

erase()

  1. 得到前驱结点和后继结点的指针；
  2. 前驱结点的_next 指向后继结点；
  3. 后继结点的_prev指向前驱结点；
  4. 删除当前结点，返回删除位置的下一个位置；
iterator erase(iterator pos)
{
	assert(pos != end());//不能删除空双向循环链表

	Node* cur = pos._node;//当前结点指针
	Node* prev = cur->_prev;//前驱结点指针
	Node* next = cur->_next;//后继结点指针
	prev->_next = next;
	next->_prev = prev;

	delete cur;

	return next;//返回删除位置的下一位置
}

push_front/push_back/pop_front/pop_back

push_back :  尾插即在头结点前插入一个结点；
pop_back   :  尾删，删除最后一个结点；
push_front  :  头插即在第一个结点前(非头结点)插入一个结点；
pop_front   :   头删，删除第一个结点（非头结点）；

void push_back(const T& x)
{
	insert(end(), x);
}

void push_front(const T& x)
{
	insert(begin(), x);
}

void pop_back()
{
	erase(--end());
}

void pop_front()
{
	erase(begin());
}

front/back

front() : 返回第一个结点数据的引用；
end()  :  返回最后一个结点数据的引用；

T& front()
{  
	//*begin-->T& operator*()
	return *begin();
}
const T& front()const
{
	return *begin();
}
T& back()
{
	return *(--end());
}
const T& back()const
{
	return *(--end());
}

clear()

双向循环链表只保留头结点，遍历链表时调用erase接口进行删除，注意调用erase后迭代器it已经失效，使用返回值接收，自动指向下一结点；

void clear()
{
	iterator it = begin();
	while (it != end())
	{
		it = erase(it);
	}
}

empty()

//判断容器是否非空
bool empty()const
{
	return begin() == end();
}

swap()

//交换容器的头指针
void swap(list<T>& tmp)
{
	std::swap(_head, tmp._head);
}

拷贝构造函数

  1. 申请一个头结点，构造空双向循环链表(新容器)；
  2. 将 lt 中的数据拷贝到新构造的容器中；
list(const list<T>& lt)
{
	_head = new Node; // 申请一个头结点
	_head->_next = _head; // 后继指针指向自己
	_head->_prev = _head; // 前驱指针指向自己
	for (const auto& e : lt) // 拷贝到新构造的容器中
	{
		push_back(e);
	}
}

赋值运算符重载

传统写法：

  1. 释放除了头结点以外的所有结点；
  2. 将 lt 中的数据拷贝到新构造的容器中；
list<T>& operator=(const list<T>& lt)
{
	// 防止自己给自己赋值
	if (this != &lt)
	{
		clear(); // 清空数据
		for (const auto& e : lt) // 拷贝到新构造的容器中
		{
			push_back(e);
		}
	}
	return *this; // 支持连续赋值
}

现代写法：

  1. 拷贝构造出 lt 对象；
  2. 交换 this 和 lt 的 _head 指针，出了作用域，lt 调用析构函数，释放掉原this的结点；
list<T>& operator=(list<T> lt) //拷贝构造lt对象
{
	std::swap(_head, lt._head); //交换指针
	return *this; //支持连续赋值
}

析构函数

  1. 使用 clear() 释放除了头结点以外的结点；
  2. 释放掉头结点；
~list()
{
	clear();

	delete _head;
	_head = nullptr;
}

欢迎大家批评指正，博主会持续输出优质内容，谢谢大家观看，码字不易，希望大家给个一键三连支持~ 你的支持是我创作的不竭动力~

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

C#探索之路基础篇(2)：接口Interface的概念、实现、应用范围

C#探索之路基础篇(2)：接口Interface的概念、实现、应用范围

文章目录 1 概念2 示例代码&#xff1a;2.1 简单接口的实现2.2 简单的使用接口2.3 使用接口呈现多态性2.4 通过接口实现一个数组迭代器2.5 通过接口来实现松耦合的关系2.6 使用接口实现可扩展、便利性 3 使用范围与时机4 注意事项 不知道大家在学习的过程中&#xff0c;有没有反…
阅读更多...
AI原生安全 亚信安全首个“人工智能安全实用手册”开放阅览

AI原生安全 亚信安全首个“人工智能安全实用手册”开放阅览

不断涌现的AI技术新应用和大模型技术革新&#xff0c;让我们感叹从没有像今天这样&#xff0c;离人工智能的未来如此之近。 追逐AI原生&#xff1f;企业组织基于并利用大模型技术探索和开发AI应用的无限可能&#xff0c;迎接生产与业务模式的全面的革新。 我们更应关心AI安全原…
阅读更多...
机器学习——决策树（四）后剪枝

机器学习——决策树（四）后剪枝

观前提示&#xff1a;这是本人决策树相关的第四篇博文&#xff0c;前3篇的内容如下&#xff1a; 1、建造训练集的决策树【完成结点类编写和建树过程】 2、用验证集评估模型、选出泛化较好的数据划分方式训练模型 3、预剪枝 读者可根据需要从上方《机器学习》专栏中查阅对应…
阅读更多...
【论文笔记】RobotGPT: Robot Manipulation Learning From ChatGPT

【论文笔记】RobotGPT: Robot Manipulation Learning From ChatGPT

【论文笔记】RobotGPT: Robot Manipulation Learning From ChatGPT 文章目录 【论文笔记】RobotGPT: Robot Manipulation Learning From ChatGPTAbstractI. INTRODUCTIONII. RELATED WORK1. LLMs for Robotics2. Robot Learning III. METHODOLOGY1. ChatGPT Prompts for Robot …
阅读更多...
基于Python3的数据结构与算法 - 16 链表

基于Python3的数据结构与算法 - 16 链表

目录 链表 1. 创建链表 2. 链表的插入和删除 3. 双链表 4. 链表总结 链表 链表是由一系列节点组成的元素集合。每个节点包含两部分&#xff0c;数据域item和指向下一个节点得指针next。通过节点之间的相互连接&#xff0c;最终串联成一个链表。 class Node:def __init…
阅读更多...
数据结构——循环队列的实现

数据结构——循环队列的实现

&#x1f49e;&#x1f49e; 前言 hello hello~ &#xff0c;这里是大耳朵土土垚~&#x1f496;&#x1f496; &#xff0c;欢迎大家点赞&#x1f973;&#x1f973;关注&#x1f4a5;&#x1f4a5;收藏&#x1f339;&#x1f339;&#x1f339; &#x1f4a5;个人主页&#x…
阅读更多...
Python 小而精Web开发框架Flask精通指南

Python 小而精Web开发框架Flask精通指南

文章目录 Flask 简介说明Flask 核心依赖Flask 常用扩展Flask 快速启动工作流程代码示例Flask 快速启动控制台Flask 快速启动效果 Flask 启动参数Flask 路由定义Flask 支持的 HTTP 请求方式&#xff1a;路由装饰器中的参数 Flask 路由参数Flask 路由蓝图路由蓝图的优点路由蓝图的…
阅读更多...
痛失offer的八股

痛失offer的八股

java面试八股 mysql篇&#xff1a; 事物的性质&#xff1a; 事物的性质有acid四特性。 a&#xff1a;automic&#xff0c;原子性&#xff0c;要么全部成功&#xff0c;要么全部失败&#xff0c;mysql的undolog&#xff0c;事物在执行的时候&#xff0c;mysql会进行一个快照读…
阅读更多...
获取KEGG通路的基因列表 做单细胞GSEA、GSVA分析

获取KEGG通路的基因列表 做单细胞GSEA、GSVA分析

使用KEGG通路的基因列表进行单细胞GSEA GSVA分析的过程&#xff0c;我们需要遵循以下步骤&#xff1a; 获取KEGG通路的基因列表&#xff1a;这通常涉及使用专门的R包&#xff0c;如KEGGREST或biomaRt&#xff0c;来查询KEGG数据库并检索特定通路的基因列表。 准备单细胞表达数…
阅读更多...
详解JS原型与原型链的关系

详解JS原型与原型链的关系

1、构造函数原型prototype (1)、构造函数通过原型分配的函数是所有对象所共享的&#xff1b; (2)、JavaScript规定&#xff0c;每一个构造函数都有一个prototype属性&#xff0c;指向另一个对象&#xff1b; (3)、注意这个prototype就是一个对象&#xff0c;这个对象的所有属性…
阅读更多...
Scikit-Learn逻辑回归(二)

Scikit-Learn逻辑回归(二)

Scikit-Learn逻辑回归二&#xff1a;多项式与正则化 1、多项式回归回顾1.1、逻辑回归为什么要使用多项式1.2、多项式回归及原理 2、逻辑回归与多项式 1、多项式回归回顾 本文接上篇&#xff1a;Scikit-Learn逻辑回归(一) 上篇中&#xff0c;我们详细介绍了逻辑回归的概念、原理…
阅读更多...
使用 React antd 的ProFormSelect组件 搜索查询 多选的写法

使用 React antd 的ProFormSelect组件 搜索查询 多选的写法

使用 React antd 的ProFormSelect组件 搜索查询 多选的写法 需求&#xff1a;需要一个搜索框&#xff0c;可以选择员工&#xff0c;&#xff08;员工人数多无法一次性获取&#xff0c;全部放入options中&#xff09;&#xff0c;所以需要使用搜索功能&#xff0c;而且是可以多…
阅读更多...
XR“黑话”

XR“黑话”

MTP&#xff08;Motion-To-Photon Latency&#xff09;&#xff1a;实际人体发生运动到图像显示到屏幕上的时间延迟。早期一些vr产生晕动症的主要原因。 ATW&#xff08;Asynchronous Timewarp&#xff09;&#xff1a;主要解决两个问题&#xff0c;一是延迟&#xff0c;二是补…
阅读更多...
CSS弹性盒模型（学习笔记）

CSS弹性盒模型（学习笔记）

一、厂商前缀 1.1 作用 解决浏览器对C3新特性的兼容&#xff0c;不同的浏览器厂商&#xff0c;定义了自己的厂商前缀 1.2 语法 浏览器 厂商前缀内核(渲染引擎)&#xff1a;解析htmlcssjs谷歌 -webkit-blink苹果-webkit-webkit欧朋-o-blink火狐 -moz-geckoIE-ms- trid…
阅读更多...
OpenCV4.9.0开源计算机视觉库安装教程

OpenCV4.9.0开源计算机视觉库安装教程

返回&#xff1a;OpenCV系列文章目录&#xff08;持续更新中......&#xff09; 引言&#xff1a;OpenCV系列文章中的安装部分今天全部完成了&#xff0c;为了读者更方便阅读&#xff0c;大家可以按下列索引前往&#xff0c;成文较为仓促有错漏在所难免&#xff0c;欢迎大家指正…
阅读更多...
服务器运行一段时间后

服务器运行一段时间后

自己记录一下。 一、查看目录占用情况 df -h 命令查看磁盘空间 du -ah --max-depth=1 / 查看根目录下各个文件占用情况 二、mysql日志清空 这个日志是可以清空的 echo > /usr/local/mysql/data/syzl-db2.log #将文件清空 说明： 这个文件这么大是因为，开启 …
阅读更多...
将OpenCV与gdb驱动的IDE结合使用

将OpenCV与gdb驱动的IDE结合使用

返回&#xff1a;OpenCV系列文章目录&#xff08;持续更新中......&#xff09; 上一篇&#xff1a;OpenCV4.9.0开源计算机视觉库在 Linux 中安装 下一篇&#xff1a;将OpenCV与gcc和CMake结合使用 ​ 能力 这个漂亮的打印机可以显示元素类型、、标志is_continuous和is_subm…
阅读更多...
微信小程序分销返佣模式--小程序1-3级分销插件--小程序分销--

微信小程序分销返佣模式--小程序1-3级分销插件--小程序分销--

团购小程序是一种基于社区团购模式的电商平台&#xff0c;主要面向社区居民用户。 如果你想要开发一款分销团购小程序可以参考以下功能需求进行开发制作。 1、用户注册和登录 提供用户注册和登录功能&#xff0c;使用户能够创建和管理他们的账户。 2、会员管理 包括会员注…
阅读更多...
springboot网站开发-诡异的static/images读取故障

springboot网站开发-诡异的static/images读取故障

springboot网站开发-诡异的static/images读取故障!我在本地环境测试代码&#xff0c;一切正常。可以读取到该路径下的图片模板&#xff0c;正常生成图片存储在本地D盘下面的文件夹。但是改成服务器linux环境后就不行了。打包发布后&#xff0c;死活读取不到图片模板。 这个故障…
阅读更多...
HTML（一）

HTML（一）

一、网页 1.1 什么是网页 网站是指在因特网上根据一定的规则&#xff0c;使用 HTML 等制作的用于展示特定内容相关的网页集合。 网页是网站中的一“页”&#xff0c;通常是 HTML 格式的文件&#xff0c;它要通过浏览器来阅读。 网页是构成网站的基本元素&#xff0c;它通常由…
阅读更多...
最新文章

Copyright @ 2022~2023