当前位置： 首页 > article >正文

C++容器list底层迭代器的实现逻辑~list相关函数模拟实现

article 2024/11/15 10:55:55

目录

1.两个基本的结构体搭建

2.实现push_back函数

3.关于list现状的分析（对于我们如何实现这个迭代器很重要）

3.1和string,vector的比较

3.2对于list的分析

3.3总结

4.迭代器类的封装

5.list容器里面其他函数的实现

6.个人总结

7.代码附录

1.两个基本的结构体搭建

首先就是我们的这个list结构体，这个里面包含了我们的基本的函数的实现，以便于我们后期的测试；

这个里面的成员变量就是现在的这个_head即我们的哨兵位节点，这个节点是我们链表的第一个节点，但是是没有实际含义的，他的下一个节点才是我们的链表里面的真正的第一个节点；

因为我们的这个list表示的就是一个双向的链表，因此这个里面的每一个元素都是我们的节点，我们的节点里面又包含了数据域和指针域，因此这个需要我们重新定义一个node的结构体，方便我们在这个list里面进行使用；

其中这个里面的list_node结构体里面包含的内容就是我们的data元素和next指针变量；

  • 这个下面的list_node就是一个模版类，list_node<T>表示的就是模版类的类型，其中这个里面的T可以是任意的数据类型，例如这个T就是我们熟悉的int类型，这个时候的，list_node<int>表示的就是这个类里面的数据就是int类型的数据，这个前驱指针和后继指针就是int*类型的；
  • _naxt表示的就是后继指针，_prev就是前驱指针，都是英文的缩写；

  • 这个里面为了简答起见，我们对于这个list_node进行重定义为Node，这样我们后面使用的时候就会方便一些；
  • 这个里面是对于 list链表进行初始化的工作，list()就是一个构造函数，首先我们使用new开辟新的节点，这个时候这个节点就是我们的链表里面的唯一的节点；
  • 所以这个_haed头结点的前驱指针和后继指针指向的都是自己；

2.实现push_back函数

为什么首先实现这个push_back函数，这个函数实现的就是向这个链表里面插入数据，我们想要使用迭代器进行遍历首先这个链表里面需要有数据，因此我们使用这个push_back函数向这个链表里面添加数据；

代码解读

  • 首先使用new开辟一个新的节点（第一行代码），让原来的tai的next指针l指向这个新的节点（第三行代码）；
  • 我们的tail这个时候就是_haed这个头结点的前驱指针（第二行代码），因为我们的这个链表是一个双向的链表，第一个头结点和最后一个尾结点之间有联系；
  • newnode的前后建立联系，前面是我们的这个原来的tail节点，后面的后继指针指向的就是我们的头结点（第4,5行代码）；
  • 最后一行表示的是这个_head头结点的前驱节点就是我们的这个新开辟的newnode节点；

此外，我们可以实现一些基本的函数供我们使用，这个包括了size函数计算这个链表里面的节点的个数，以及使用这个_size成员变量进行判断我们的这个链表是不是空的；

3.关于list现状的分析（对于我们如何实现这个迭代器很重要）

3.1和string,vector的比较

我们的迭代器就是对于这个容器里面的元素进行遍历的，我们的之前介绍的string和vector都是支持这个迭代器的，这个list也支持，但是没有那么随意；

什么是随意，就是我们的这个string vector因为自身的这个连续性，因为string就是相当于我们学过的这个字符串，vector就是类似于我们学习的这个数组，他们的这个空间都是连续的，我们可以使用这个++，--运算符对于这个迭代器的指针进行移动，进而对于这个容器里面的元素进行遍历；

而且我们对上面的两个string,vector使用这个迭代器解引用就可以直接拿到这个对应位置的数据，这些都是我们list链表无法直接做到的；

3.2对于list的分析

因为我们的list里面的节点通过指针进行连接，这个里面的指针分为前驱指针和后继指针，其中这个指针里面存放了下一个元素的地址；

这个时候我们无法使用++，--直接拿到相邻位置的元素，因为我们的++，--只是拿到的物理上连续空间的地址，但是这个list节点之间的物理地址不是连续的；

但是我们可以通过一定的手段去拿到，因为我们知道下一个元素的地址；

同理，我们通过解引用也没有办法得到这个位置的数据，因为我们拿到的是节点，这个里面有数据域和指针域，而我们想要实现的效果就是通过解引用直接得到这个数据；

但是我们可以通过一定的方法，例如使用这个运算符的重载，把这个解引用操作符重载成为直接拿到这个节点对应的数据的操作符；

3.3总结

因此，我们需要封装一个类，实现这个operator*和operator++的重载，进而可以让我们达到我们想要的效果；

4.迭代器类的封装

这个里面封装了我们的operator*和operator++两个运算符，都是我们经过上面的这个对于list容器的现状的分析之后得到的结论：我们应该使用这个*运算符的重载直接得到这个节点对应位置的数据，使用这个++运算符直接找到这个链表里面的下一个节点；

当我们在进行遍历的时候，我们的两个迭代器不相等就需要接着进行遍历，当相等的时候就需要停止这个便利的过程，因此我们还重载了这个里面的operator!=运算符方便我们对于这个遍历的过程进行控制；

其中在这个++运算符的重载里面，我们就是直接把下一个节点的指针赋值给当前的这个节点，返回值就是赋值之后的这个新的节点，这样就实现了这个++运算符的重载；

我们的list里面也是对于这个list_iterator进行重定义，这个名字和上面的这个self的意义是一样的，就是这个表达上不相同罢了，因为我们实际上进行遍历还是使用的这个iterator迭代器，这个重命名就是为了我们使用方便；

我们的这个begin函数返回值是一个迭代器，但是我们return的就是一个指针，但是我们的list_iterator里面是一个单参数的构造函数，因此这个是可以支持隐式类型转换的；

完整代码：写到这个地方，我们基本的这个逻辑就已经实现了，这个时候就可以使用这个迭代器对于这个list容器里面的元素进行遍历了；

//#define _CRT_SECURE_NO_WARNINGS 1
//list.h文件

#pragma once
#include<iostream>
using namespace std;

namespace bite
{
	template<class T>

	//对于节点定义一个类
	struct list_node
	{
		T _data;
		list_node<T>* _next;
		list_node<T>* _prev;

		list_node(const T& data = T())
			:_data(data)
			, _prev(nullptr)
			, _next(nullptr)
		{

		}
	};
	template<class T>
	
	struct list_iterator
	{
		typedef list_node<T> Node;

		typedef list_iterator<T>  self;
		Node* _node;

		list_iterator(Node* node)
			:_node(node)
		{

		}

		//使用引用是因为我们可以修改这个里面的数据
		T& operator*()
		{
			return _node->_data;
		}

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

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


	template<class T>

	class list
	{
		typedef list_node<T> Node;
	public:
		typedef list_iterator<T>  iterator;

		//返回的是一个节点，接受的是迭代器，但是这个是单参数构造函数支持隐式类型转换
		iterator begin()
		{
			//iterator it(_head->next);

			return _head->_next;
		}

		iterator end()
		{
			//最后一个元素的下一个位置
			return _head;
		}
		list()
		{
			_head = new Node(T());
			_head->_next = _head;
			_head->_prev = _head;
		}

		void push_back(const T& x)
		{
			Node* newnode = new Node(x);
			Node* tail = _head->_prev;

			tail->_next = newnode;
			newnode->_prev = tail;
			newnode->_next = _head;
			_head->_prev = newnode;
		}

		size_t size() const
		{
			return _size;
		}

		bool empty() const
		{
			return _size == 0;
		}
	private:
		Node* _head;
		size_t _size;
	};

	void test_list1()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);

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

}
#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
//#include<algorithm>
//#include<list>
//#include<vector>
//using namespace std;

#include"list.h"

int main()
{
	bite::test_list1();
	return 0;
}

 这个时候，我们对于这个迭代器进行测试，发现这个迭代器就可以正常的跑起来了；

5.list容器里面其他函数的实现

首先就是这个insert和erase，即链表里面的数据的插入和删除；

插入数据的话，就是新建一个节点，在这个节点的前后和这个节点建立联系，因为是双向的，就是指针之间的相互指向的确定（4行代码）；

erase就是把这个节点的前面和后面的节点确定，让前后两个节点相互指向，然后把这个节点释放掉，这个节点就被删除掉了；

实现了上面的这个insert和erase之后，我们想要在这个指定的位置进行数据的插入和删除就比较容易了，我们只需要调用上面的函数即可；

push_back不需要之前写的那么复杂，直接在这个end()前面插入数据即可；

push_front就是在这个begin()前面插入数据（这个里面的begin指向的是第一个有实际意义的节点，不是我们的哨兵位头结点，这个一定要注意！！！！！！！！！！！！！）

pop_front就是删除这个头结点的数据，直接调用这个erase把这个begin()传递进去即可；

pop_back函数就是删除这个最后的数据，因为我们的end指向的是最后一个数据的下一个位置，因此这个地方我们进行传参的时候进行了--操作；

6.个人总结

在实现这个迭代器的时候，我们需要搞清楚这个架构，实际上就是三个结构体，一个是节点的，一个是链表的，一个就是我们自己封装的这个迭代器，其中这个节点的结构体就是为了方便使用；

其次这个不断地进行typedef对于初学者也是一个挑战，不是因为它很难，而是在这个重命名之后，我们需要这个结构重命名之前是什么，这个结构的里面有哪些内容，例如pos._node我就理解了很久，就是因为重命名之后对于这个结构里面的内容不清楚导致的；

实际上，这个pos就是我们的参数iterator，本质上就是迭代器，这个list_iterator结构体里面就有我们的这个_node成员，因此这个pos._node就不难理解了，实际上这个struct使用就是因为我们的struct默认的就是公有的，符合我们的使用要求，使用class也是可以的，但是要加上这个public表示我们的权限，因此class里面的内容默认是私有的，使用class之后，我们这个代码风格里面的pos._node就应该相应的修改；

另外，我们的这个迭代器使用的时候看似和其他的这个string .vector没有区别，就是进行遍历，但是实际上我们是封装了一个类的，为了封装这个类，我们定义了其他的两个类，这些都是我们在调用时候看不到的，我们只看到了这个迭代器可以进行遍历，但是实际上这个背后的功夫确是我们无法估量的，如果你认为很简单，自己独立实现一下就知道这个过程的难度了；

这个就好比我们普通的孩子和生来就条件好的孩子，生来条件就好的孩子好比string,vector人家就是可以直接调用这个*找到这个位置的数值，使用这个++进行这个循环的控制，但是我们普通人家的孩子就是list，我们没有他们的优势，但是我们可以通过自己的努力，实现一个类的封装，我们也可以实现相同的效果，就看肯不肯去克服实现这个类的路上的困难了；

看似就是一个list，却让我们从中看到了大部分人的影子，因为我们大部分都是list，没有先天的优势，但是只要我们肯付出努力，就可以实现相同的遍历的效果，因此，努力吧少年~我命由我不由天，努力奋进改尘寰~~我们要相信自己的努力，就是这个迭代器封装的类，我们最后也是会实现相同的效果的，list就是证明~~

7.代码附录

//#define _CRT_SECURE_NO_WARNINGS 1
//list.h文件，包含迭代器和一些常用的函数

#pragma once
#include<iostream>
using namespace std;

namespace bite
{
	template<class T>

	//对于节点定义一个类
	struct list_node
	{
		T _data;
		list_node<T>* _next;
		list_node<T>* _prev;

		//内置类型：0，0.0，空指针
		//自定义类型：调用默认构造，调用自己的模版
		list_node(const T& data = T())//第一次修改，-------给默认构造
			:_data(data)
			, _prev(nullptr)
			, _next(nullptr)
		{

		}
	};
	template<class T>
	
	struct list_iterator
	{
		typedef list_node<T> Node;

		typedef list_iterator<T>  self;
		Node* _node;

		list_iterator(Node* node)
			:_node(node)
		{

		}

		//使用引用是因为我们可以修改这个里面的数据
		T& operator*()
		{
			return _node->_data;
		}

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

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

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

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


	template<class T>

	class list
	{
		typedef list_node<T> Node;
	public:
		typedef list_iterator<T>  iterator;

		//返回的是一个节点，接受的是迭代器，但是这个是单参数构造函数支持隐式类型转换
		iterator begin()
		{
			//iterator it(_head->next);

			return _head->_next;
		}

		iterator end()
		{
			//最后一个元素的下一个位置
			return _head;
		}
		list()
		{
			_head = new Node(T());//这个是第一次报错的原因，---------------修改的地方
			//第一次报错是因为没有写这个地方的node的构造函数
			//new Node(x);需要我们传递匿名对象
			_head->_next = _head;
			_head->_prev = _head;
		}

		void push_back(const T& x)
		{
			/*Node* newnode = new Node(x);
			Node* tail = _head->_prev;

			tail->_next = newnode;
			newnode->_prev = tail;
			newnode->_next = _head;
			_head->_prev = newnode;*/
			insert(end(), x);
		}

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

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

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

		void insert(iterator pos, const T& x)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;

			Node* newnode = new Node(x);

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

			++_size;
		}

		void erase(iterator pos)
		{
			assert(pos != end());

			Node* prev = pos._node->_prev;
			Node* next = pos._node->_next;

			prev->_next = next;
			next->_prev = prev;
			delete pos._node;

			--_size;
		}

		size_t size() const
		{
			return _size;
		}

		bool empty() const
		{
			return _size == 0;
		}
	private:
		Node* _head;
		size_t _size;
	};

	void test_list1()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);

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

}
#define _CRT_SECURE_NO_WARNINGS 1
//test.cpp测试文件，验证我们的迭代器的功能，是否可以正常的遍历链表
#include<iostream>
//#include<algorithm>
//#include<list>
//#include<vector>
//using namespace std;

#include"list.h"

int main()
{
	bite::test_list1();
	return 0;
}


http://www.kler.cn/a/316957.html

相关文章：

  • git没有识别出大写字母改成小写重命名的文件目录
  • EXCEL延迟退休公式
  • arcgis做buffer
  • C++ 编程基础（6）作用域 | 6.3、类作用域
  • Springboot配置全局异常通用返回
  • Spring Boot中的自动装配机制
  • 安卓LiveData与MutableLiveData的使用
  • 游戏淡入淡出效果
  • 消息中间件---Kafka
  • 频率增强通道注意力机制（FECAM）学习总结
  • LLMs之Qwen：Qwen2.5的简介、安装和使用方法、案例应用之详细攻略
  • Redisson 总结
  • 二叉树---java---黑马
  • 吴恩达深度学习笔记：卷积神经网络（Foundations of Convolutional Neural Networks）2.1-2.2
  • 【IPV6从入门到起飞】5-5 IPV6+Home Assistant(HACS商店安装)docker版本安装
  • Leetcode3289. 数字小镇中的捣蛋鬼
  • vue中高德地图使用 Marker 标点 - 标点数据快到 1000 时页面卡顿问题解决（已解决 - 多方面原因）+ 海量点功能实现解决
  • 南昌大学-计算机科学与技术专业-预推免-专业课（408）复试面试准备
  • 通信工程学习：什么是MANO管理编排
  • 蓝桥杯嵌入式的学习总结
  • 18 基于51单片机的心率体温监测报警系统(包括程序、仿真、原理图、流程图)
  • helm安装promethues
  • MySQL的缓存策略
  • 数据结构二
  • 影刀RPA实战：网页爬虫之携程酒店数据
  • 文件（打开关闭读写） C语言