C++ list模拟实现

list模拟实现代码：

namespace djx
{
	template<class T>
	struct list_node
	{
		T _data;
		list_node<T>* _prev;
		list_node<T>* _next;

		list_node(const T& x = T())
			:_data(x)
			,_prev(nullptr)
			,_next(nullptr)
		{}
	};

	template<class T,class Ref,class Ptr>
	struct __list_iterator
	{
		typedef list_node<T> Node;
		typedef __list_iterator<T, Ref, Ptr> self;

		Node* _node;

		__list_iterator(Node* node)
			:_node(node)
		{}

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

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

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

		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;
		}

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

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

	template<class T>
	class list
	{
		typedef list_node<T> Node;
	public:
		typedef __list_iterator<T, T&, T*> iterator;
		typedef __list_iterator<T, const T&, const T*> const_iterator;
		
		iterator begin()
		{
			return _head->_next;
		}

		iterator end()
		{
			return _head;
		}

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

		const_iterator end()const
		{
			return _head;
		}

		void empty_init()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
			_size = 0;
		}

		list()
		{
			empty_init();
		}

		list(const list<T>& lt)
		{
			empty_init();
			for (auto e : lt)
			{
				push_back(e);
			}
		}

		void swap(list<T>& lt)
		{
			std::swap(_head, lt._head);
			std::swap(_size, lt._size);
		}

		list<T>& operator=(list<T> lt)
		{
			swap(lt);
			return *this;
		}

		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}

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

		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());
		}

		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;
			_size++;
			return newnode;
		}

		iterator erase(iterator pos)
		{
			Node* cur = pos._node;
			Node* next = cur->_next;
			Node* prev = cur->_prev;

			delete cur;
			prev->_next = next;
			next->_prev = prev;
			_size--;
			return next;
		}
		
		size_t size()
		{
			return _size;
		}

	private:
		Node* _head;
		size_t _size;
	};
}

源码中的list实现为带头双向链表

 

list类的对象有两个成员：指向头结点的指针_head，统计数据个数的_size

在模拟实现list之前，需要先模拟实现结点类，迭代器类

结点类：三个成员，_data _prev _next，实现成struct（也是类，不过与class不同的是，它的成员都是公开的，都可以在类外访问），因为这三个成员，在迭代器类中都要使用访问，设it是迭代器，*it就会返回结点中值(_data)的引用，it++（要访问结点中的_next) ， it--（要访问结点中的_prev)

    template<class T>
	struct list_node
	{
		T _data;
		list_node<T>* _prev;
		list_node<T>* _next;

		list_node(const T& x = T())//x是匿名对象的引用，const延长了匿名对象的生命周期，x销毁，匿名对象才销毁，匿名对象会调用它的构造函数，完成初始化
			:_data(x)
			,_prev(nullptr)
			,_next(nullptr)
		{}
	};

要写构造函数：list类中的push_back插入数据时，需要new一个结点，并传数值

                         调用构造函数时，若是直接使用编译器生成的默认构造函数，则无法传参

构造函数的参数设计成缺省参数：有传实参过来就使用此值，没有传参过来就用匿名对象去拷贝构造_data，使用匿名对象去拷贝构造_data的情形：list类中的无参构造函数-->让list中的成员变量_head指向一个new出来的头结点，头结点中不存储任何有效数据，故而new时无需传参

迭代器类：一个成员 _node（结点的指针）

设计成struct：在list类中设计insert和erase时，传参给它们的是iterator迭代器，我们要使用迭代器中的成员变量（结点的指针）即要访问迭代器中的成员，那么设计成struct会比设计成class类方便不少

list的迭代器与vector,string类不同，在模拟实现vector和string的迭代器时，它们可以用原生指针来实现，因为完美契合原生指针的行为，但是模拟实现list的迭代器时，它必须设计成一个类，是对原生指针的封装，原因：

若是list的迭代器就用原生指针来实现，那么*it（it是一个迭代器）得到的不是数据，而是结点

it++ 不能走向下一个数据，故而需要对原生指针进行封装，让*it得到数据，it++，走向下一个数据

template<class T,class Ref,class Ptr>
	struct __list_iterator
	{
		typedef list_node<T> Node;
		typedef __list_iterator<T, Ref, Ptr> self;

		Node* _node;

		__list_iterator(Node* node)//要写带参的构造，因为在list类中实现begin()时，返回值的类型是迭代器，但是我们返回的可以是结点的指针，单参数的构造函数支持隐式类型转换，也可以是迭代器，但是此迭代器中的成员变量（结点的指针）需要和第一个结点的指针一样
			:_node(node)
		{}

		Ref operator*()//Ref可以是T&（普通迭代器） const T& （const迭代器）
		{
			return _node->_data;
		}

		Ptr operator->()Ptr可以是T* (普通迭代器） const T* (const迭代器）
		{
			return &_node->_data;
		}

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

		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;
		}

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

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

迭代器有非const对象调用的，也有const对象调用的，二者的区别仅仅是能否修改的问题，*迭代器返回的是数据的引用，const对象调用的迭代器返回的也是数据的引用，但是const修饰的

迭代器-> 返回的是数据的地址，const对象调用的迭代器返回的是const修饰的数据地址

(迭代器可以看作是模拟原生指针的行为，若是数据为自定义类型，那么迭代器->就可以访问到自定义类型对象中的成员，实际上看成是原生指针的迭代器-> 无法做到，但是对原生指针封装而出现的迭代器可以做到，只要迭代器->返回的是数据的指针，那么有了自定义类型对象指针，不就可以访问它里面的成员了吗）

综上来看，我们只需要写一份迭代器类的模板，根据实例化参数的不同，生成不同的迭代器

迭代器需要三个模板参数：T（迭代器类中的成员变量是结点的指针，结点实例化需要）

模板参数 Ref  : 迭代器类中重载*运算符所用，重载*运算符的函数要返回数据的引用，而若是const对象的迭代器解引用，就要用const去修饰返回值

模板参数Ptr ：迭代器类中重载->运算符所用，重载->运算符的函数返回数据的指针，而若是const对象的迭代器->，也要用const去修饰返回值

那么在list类中，设计普通迭代器，const对象调用的迭代器时，就可以用迭代器类的模板，实例化参数不同就会是完全不同的类型，普通迭代器用迭代器类的模板实例化，传参 T   T&   T*

const对象调用的迭代器用迭代器类的模板实例化，传参 T  const T&   const T*

构造函数：

1 无参的构造

    让list对象中的成员变量_head指向一个头指针（双向循环）

    参照源码list的实现：

 

        void empty_init()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
			_size = 0;
		}

		list()
		{
			empty_init();
		}

2 拷贝构造（深拷贝）

        list(const list<T>& lt)
		{
			empty_init();
			for (auto e : lt)
			{
				push_back(e);
			}
		}

析构函数：

        ~list()
		{
			clear();
			delete _head;//释放头结点
			_head = nullptr;
		}

		void clear()//清除数据
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}

赋值重载：

        void swap(list<T>& lt)
		{
			std::swap(_head, lt._head);
			std::swap(_size, lt._size);
		}

		list<T>& operator=(list<T> lt)///lt是实参的深拷贝，lt销毁会释放掉原本由*this申请的空间
		{
			swap(lt);//交换*this和lt
			return *this;
		}

迭代器：

        typedef __list_iterator<T, T&, T*> iterator;
		typedef __list_iterator<T, const T&, const T*> const_iterator;
		
		iterator begin()
		{
			return _head->_next;
		}

		iterator end()
		{
			return _head;
		}

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

		const_iterator end()const
		{
			return _head;
		}

测试1：

void test1()
{
	djx::list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(5);

	djx::list<int>:: iterator it = lt.begin();
	while (it != lt.end())
	{
		*it += 20;
		cout << *it << " ";
		it++;
	}
	cout << endl;

	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
}

测试2：

void test2()
{
	djx::list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(5);

	djx::list<int> lt1(lt);//拷贝构造

	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;

	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;

	djx::list<int> lt2;
	lt2.push_back(100);
	lt2.push_back(200);
	lt2.push_back(300);
	lt2.push_back(400);
	lt2.push_back(500);

	lt1 = lt2;//赋值重载

	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;

	for (auto e : lt2)
	{
		cout << e << " ";
	}
	cout << endl;

}

 

 

插入：

 1 push_back

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

2 push_front

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

3 insert

        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;
			_size++;
			return newnode;//单参数的构造函数支持隐式类型转换
                           //或者写成：iterator(newnode)
		}

删除：

1 pop_back

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

2 pop_front

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

3 erase

        iterator erase(iterator pos)
		{
			Node* cur = pos._node;
			Node* next = cur->_next;
			Node* prev = cur->_prev;

			delete cur;
			prev->_next = next;
			next->_prev = prev;
			_size--;
			return next;//返回下一个数据的地址
		}

测试3：

struct AA
{
	AA(int a1 = 0, int a2 = 0)
		:_a1(a1)
		, _a2(a2)
	{}

	int _a1;
	int _a2;
};

void test3()
{
	djx::list<AA> lt;
	lt.push_back(AA(1, 1));
	lt.push_back(AA(2, 2));
	lt.push_back(AA(3, 3));

	djx::list<AA>::iterator it = lt.begin();
	while (it != lt.end())
	{
		//cout << (*it)._a1 << " "<<(*it)._a2<<endl;
		cout << it->_a1 << " " << it->_a2 << endl;
		it++;
	}
	cout << endl;
}

题外：

 设计一个打印函数，打印任意list对象

template<typename T>//不可以用class
void print_list(const djx:: list<T>& lt)
{
    //list<T>未实例化的类模板，编译器不能去它里面去找
    //编译器就无法list<T>::const_iterator是内嵌类型，还是静态成员变量
    //前面加一个typename就是告诉编译器，这里是一个类型，等list<T>实例化，再去类里面找
	typename djx::list<T>::const_iterator it = lt.begin();
	while (it != lt.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
}

打印任意容器

template<typename Container>
void print_container(const Container& con)
{
	typename Container::const_iterator it = con.begin();
	while (it != con.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
}

测试4：

void test4()
{
	djx::list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	print_list(lt);
}

测试5：

void test5()
{
	djx::list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	print_container(lt);

	djx::list<string> lt1;
	lt1.push_back("1111111111111");
	lt1.push_back("1111111111111");
	lt1.push_back("1111111111111");
	lt1.push_back("1111111111111");
	lt1.push_back("1111111111111");
	//print_list(lt1);
	print_container(lt1);

	vector<string> v;
	v.push_back("222222222222222222222");
	v.push_back("222222222222222222222");
	v.push_back("222222222222222222222");
	v.push_back("222222222222222222222");
	print_container(v);

}

 

 

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

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

相关文章

ctfshow-红包题第二弹

ctfshow-红包题第二弹

0x00 前言 CTF 加解密合集CTF Web合集 0x01 题目 0x02 Write Up 同样&#xff0c;先看一下有没有注释的内容&#xff0c;可以看到有一个cmd的入参 执行之后可以看到文件代码&#xff0c;可以看到也是eval&#xff0c;但是中间对大部分的字符串都进行了过滤&#xff0c;留下了…
阅读更多...
纸贵科技连续三年蝉联IDC中国 FinTech 50榜单

纸贵科技连续三年蝉联IDC中国 FinTech 50榜单

近日&#xff0c;国际权威市场研究机构IDC公布了“2023 IDC中国FinTech 50榜单”。作为领先的区块链技术和解决方案服务商&#xff0c;纸贵科技凭借过硬的区块链技术和丰富的金融科技创新成果&#xff0c;连续第三年荣登IDC中国FinTech 50榜单。 IDC中国FinTech 50榜单是金融科…
阅读更多...
【leetcode 力扣刷题】双指针///原地扩充线性表

【leetcode 力扣刷题】双指针///原地扩充线性表

双指针///原地扩充线性表 剑指 Offer 05. 替换空格定义一个新字符串扩充字符串&#xff0c;原地替换思考 剑指 Offer 05. 替换空格 题目链接&#xff1a;剑指 Offer 05. 替换空格 题目内容&#xff1a; 这是一道简单题&#xff0c;理解题意&#xff0c;就是将字符串s中的空格…
阅读更多...
很干的 Nginx

很干的 Nginx

&#x1f3a8; 前言 本篇文章有些概念性的东西&#xff0c;是结合自己的理解表达出来的&#xff0c;可能有些理解不到位的地方。希望多多指教&#xff0c;谢谢大家。 红包献上 &#x1f9e7;&#x1f9e7;&#x1f9e7;&#x1f9e7;&#x1f9e7;&#x1f9e7;&#x1f9e7;…
阅读更多...
【c语言】文件操作 万字详解

【c语言】文件操作 万字详解

目录 一&#xff0c;为什么使用文件 二&#xff0c;什么是文件 1&#xff0c;程序文件 2&#xff0c;数据文件 3&#xff0c;文件名 三&#xff0c;文件的打开和关闭 1&#xff0c;文件指针 2&#xff0c;文件的打开和关闭 四&#xff0c; 文件的顺序读写 1&#xff0c;顺序…
阅读更多...
ethers.js2：provider提供商

ethers.js2：provider提供商

1、Provider类 Provider类是对以太坊网络连接的抽象&#xff0c;为标准以太坊节点功能提供简洁、一致的接口。在ethers中&#xff0c;Provider不接触用户私钥&#xff0c;只能读取链上信息&#xff0c;不能写入&#xff0c;这一点比web3.js要安全。 除了之前介绍的默认提供者d…
阅读更多...
如何编译打包OpenSSH 9.4并实现批量升级

如何编译打包OpenSSH 9.4并实现批量升级

1 介绍 openssh 9.4版本已于8月10号发布&#xff0c;安全团队又催着要赶紧升级环境里的ssh版本&#xff0c;本文主要介绍Centos5、Centos6、Centos7下openssh 9.4源码编译rpm包以及批量升级服务器openssh版本的方法。关注公众号后台回复ssh可获取本文相关源码文件。 https://w…
阅读更多...
使用Tampermonkey（篡改猴）向页面注入js脚本

使用Tampermonkey（篡改猴）向页面注入js脚本

一、Tampermonkey 简单介绍 Tampermonkey是一款浏览器插件&#xff0c;适用于Chrome、Microsoft Edge、Safari、Opera Next 和 Firefox。他允许我们自定义javascript给指定网页添加功能&#xff0c;或修改现有功能。也可以用来辅助调试&#xff0c;或去除网页广告等。 官网地…
阅读更多...
深度学习-4-二维目标检测-YOLOv3理论模型

深度学习-4-二维目标检测-YOLOv3理论模型

单阶段目标检测模型YOLOv3 R-CNN系列算法需要先产生候选区域&#xff0c;再对候选区域做分类和位置坐标的预测&#xff0c;这类算法被称为两阶段目标检测算法。近几年&#xff0c;很多研究人员相继提出一系列单阶段的检测算法&#xff0c;只需要一个网络即可同时产生候选区域并…
阅读更多...
Redis.conf详解

Redis.conf详解

Redis.conf详解 配置文件unit单位对大小写不敏感 包含 网络 bind 127.0.0.1 # 绑定的ip protected-mode yes # 保护模式 port 6379 # 端口设置通用 GENERAL daemonize yes # 以守护进程的方式运行 默认为no pidfile /var/run/redis_6379.pid #如果以后台的方式运行&#xff…
阅读更多...
bash: conda: command not found

bash: conda: command not found

问题描述&#xff1a; 在Pycharm上用SSH远程连接到服务器&#xff0c;打开Terminal准备查看用 conda 创建的虚拟环境时&#xff0c;却发现调用 conda 指令时出现以下报错&#xff1a; -bash: conda: command not found如果使用Xshell 利用端口号直接连接该 docker 容器&#…
阅读更多...
CTF-XXE(持续更新，欢迎分享更多相关知识点的题目)

CTF-XXE(持续更新，欢迎分享更多相关知识点的题目)

知识 实例 BUU [PHP]XXE 进来看到 然后一起看 Write BUU XXE COURSE 1 进来看到 一起看 write NSS [NCTF2019]Fake XML cookbook 反正是XXE 直接整 write [NCTF 2019]True XML cookbook 不整花里胡哨&#xff0c;解题在最下面 write 与博主不同&#xff0c;我通过…
阅读更多...
SQL中ON筛选和Where筛选的区别

SQL中ON筛选和Where筛选的区别

转载&#xff1a;sql连接查询中on筛选与where筛选的区别https://zhuanlan.zhihu.com/p/26420938 结论:on后面接上连接条件&#xff0c;where后面接上过滤条件
阅读更多...
裸露土堆识别算法

裸露土堆识别算法

裸露土堆识别算法首先利用图像处理技术&#xff0c;提取出图像中的土堆区域。裸露土堆识别算法首通过计算土堆中被绿色防尘网覆盖的比例&#xff0c;判断土堆是否裸露。若超过40%的土堆没有被绿色防尘网覆盖&#xff0c;则视为裸露土堆。当我们谈起计算机视觉时&#xff0c;首先…
阅读更多...
删除流氓360首页

删除流氓360首页

不管你使用什么浏览器都很容易中招360给你自动设置的流氓首页&#xff0c;流氓厂石锤了。 你在浏览器设置新的首页一样无效&#xff0c;比如 完全没有卵用&#xff0c;以前这样是可以生效的&#xff0c;最近几天突然不行了&#xff0c;这简直流氓的不行&#xff0c;而且 细心…
阅读更多...
合宙Air724UG LuatOS-Air LVGL API控件--进度条 (Bar)

合宙Air724UG LuatOS-Air LVGL API控件--进度条 (Bar)

进度条 (Bar) Bar 是进度条&#xff0c;可以用来显示数值&#xff0c;加载进度。 示例代码 – 创建进度条 bar lvgl.bar_create(lvgl.scr_act(), nil) – 设置尺寸 lvgl.obj_set_size(bar, 200, 20); – 设置位置居中 lvgl.obj_align(bar, NULL, lvgl.ALIGN_CENTER, 0, 0) …
阅读更多...
LLMs参数高效微调（PEFT） Parameter efficient fine-tuning (PEFT)

LLMs参数高效微调（PEFT） Parameter efficient fine-tuning (PEFT)

正如你在课程的第一周所看到的&#xff0c;训练LLMs需要大量的计算资源。完整的微调不仅需要内存来存储模型&#xff0c;还需要在训练过程中使用的各种其他参数。 即使你的计算机可以容纳模型权重&#xff0c;最大模型的权重现在已经达到几百GB&#xff0c;你还必须能够为优化…
阅读更多...
ThinkPHP 多应用配置，及不同域名访问不同应用的配置【详解】

ThinkPHP 多应用配置，及不同域名访问不同应用的配置【详解】

ThinkPHP 多应用配置&#xff0c;及不同域名访问不同应用的配置【详解】 一、安装多应用扩展二、删除项目的中默认的controller文件夹三、创建多应用四、修改config/app.php文件五、测试并且访问多应用六、配置小皮&#xff0c;不同域名访问不同的应用七、小结 一、安装多应用扩…
阅读更多...
在CSS中，盒模型中的padding、border、margin是什么意思？

在CSS中，盒模型中的padding、border、margin是什么意思？

在CSS中&#xff0c;盒模型&#xff08;Box Model&#xff09;是用来描述和布局HTML元素的基本概念。它将每个HTML元素看作是一个矩形的盒子&#xff0c;这个盒子包括了内容&#xff08;content&#xff09;、内边距&#xff08;padding&#xff09;、边框&#xff08;border&a…
阅读更多...
时空数据挖掘精选23篇论文解析【AAAI 2023】

时空数据挖掘精选23篇论文解析【AAAI 2023】

今天和大家分享时空数据挖掘方向的资料。 时空数据挖掘是人工智能技术的重要分支&#xff0c;是一种采用人工智能和大数据技术对城市时空数据进行分析与挖掘的方法&#xff0c;旨在挖掘时空数据&#xff0c;理解城市本质&#xff0c;解决城市问题。 目前&#xff0c;时空数据…
阅读更多...
最新文章

Copyright @ 2022~2023