C++_list

news/2024/7/24 13:10:24 标签: c++, 开发语言

目录

一、模拟实现list

1、list的基本结构

2、迭代器封装

2.1 正向迭代器

2.2 反向迭代器 

3、指定位置插入

4、指定位置删除

5、结语

前言：

        list是STL(标准模板库)中的八大容器之一，而STL属于C++标准库的一部分，因此在C++中可以直接使用list容器存储数据。list实质上是一个带头双向循环链表，这也使得他能够在常数的时间复杂度范围内插入和删除数据，缺点是不能像数组那样进行元素下标的随机访问。

一、模拟实现list

        在C++中可以直接调用库里的list，并且使用起来非常的简便，和使用vector、string相差无几，但是为了能够更好的了解list和其底层原理，下文会对lsit的常用接口进行模拟实现，以便对list有更深入的理解，并且list的底层实现逻辑完美的表现了面向对象的思想。

1、list的基本结构

        与实现vector和string不一样，list可以分成两个整体：链表本身、节点本身，因此需要两个类（链表类、节点类）完成list的基本实现，并且把节点类看作是一个普通的节点，而实现链表的具体功能函数都放在链表类中。

        list基本功能代码如下：

#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
using namespace std;

namespace ZH
{
	template <class T>
	struct list_node//节点类
	{
		list_node<T>* prev;
		list_node<T>* next;
		T val;

		list_node(const T& t)
			:prev(nullptr)
			, next(nullptr)
			, val(t)
		{}
	};

	template <class T>
	class list//链表类
	{
	public:
		typedef list_node<T> node;//让节点类看起来像一个普通的节点

		list()//构造函数、目的是创建哨兵位头节点
			:_node(new node(-1))
		{
			_node->next = _node;
			_node->prev = _node;
		}

		void push_front(const T& t)//头插
		{
			node* newnode = new node(t);
			node* cur = _node->next;

			_node->next = newnode;
			newnode->prev = _node;
			newnode->next = cur;
			cur->prev = newnode;
		}

		void Print()//打印数据
		{
			node* cur = _node->next;
			while (cur != _node)
			{
				cout << cur->val << " ";
				cur = cur->next;
			}
		}

		~list()//析构
		{
			node* cur = _node->next;
			node* dest = cur->next;
			while (cur != _node)
			{
				delete cur;
				cur = dest;
				dest = dest->next;
			}
			delete _node;
			_node = nullptr;
		}

	private:
		node* _node;

	};
}

int main()
{
	ZH::list<int> lt;
	lt.push_front(1);
	lt.push_front(2);
	lt.push_front(3);
	lt.push_front(4);
	lt.Print();
	return 0;
}

        运行结果：

        从上面的代码可以发现， list的底层实现和之前c语言中实现双向循环链表的逻辑一模一样，只不过用C++的方式将其进行了封装。

        这里节点类里的成员变量要放在公有域（struct定义类默认为公有域），因为在list中会改变节点前后指针的指向，因此节点的指针要设为外部可见。

2、迭代器封装

2.1 正向迭代器

        在调用库里面的list，会发现库里面list的迭代器用起来像是一个指针，因为可以对迭代器进行解引用操作以及++操作。所以在模拟实现迭代器时，我们也用一个指针来模拟迭代器的行为，不同的是指针进行++操作时，会指向该地址的下一个地址，而我们期望的迭代器++可以指向下一个节点。

        示意图如下：

        因此，如果单单的把指针看成迭代器则无法实现遍历链表的功能，所以要实现迭代器必须对指针进行又一层的封装，也就是把迭代器写成一个类，但是该类的底层还是一个节点指针，只是对该指针的操作有了新的规定。

        正向迭代器代码实现如下：

#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
using namespace std;

namespace ZH
{
	template <class T>
	struct list_node//节点类
	{
		list_node<T>* prev;
		list_node<T>* next;
		T val;

		list_node(const T& t)
			:prev(nullptr)
			, next(nullptr)
			, val(t)
		{}
	};

	template<class T>
	struct list_iterator//迭代器类
	{
		typedef list_node<T> node;
		typedef list_iterator<T> self;

		node* _node;// 成员变量

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

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

		self& operator++()//重载前置++
		{
			_node = _node->next;
			return *this;
		}

		T& operator*()//重载解引用
		{
			return _node->val;
		}

	};

	template <class T>
	class list//链表类
	{
	public:
		typedef list_node<T> node;//让节点类看起来像一个普通的节点
		typedef list_iterator<T> iterator;//让迭代器类看起来像一个迭代器

		list()//构造函数、目的是创建哨兵位头节点
			:_node(new node(-1))
		{
			_node->next = _node;
			_node->prev = _node;
		}

		void push_front(const T& t)//头插
		{
			node* newnode = new node(t);
			node* cur = _node->next;

			_node->next = newnode;
			newnode->prev = _node;
			newnode->next = cur;
			cur->prev = newnode;
		}

		iterator begin()
		{
			//begin返回的是一个指向头节点的下一个节点的迭代器对象
			return iterator(_node->next);//匿名对象创建并返回
		}

		iterator end()
		{
			//begin返回的是一个指向头节点的迭代器对象
			return iterator(_node);//匿名对象创建并返回
		}

		~list()//析构
		{
			node* cur = _node->next;
			node* dest = cur->next;
			while (cur != _node)
			{
				delete cur;
				cur = dest;
				dest = dest->next;
			}
			delete _node;
			_node = nullptr;
		}

	private:
		node* _node;//指向哨兵位的头节点

	};
}

int main()
{
	ZH::list<int> lt;
	lt.push_front(1);
	lt.push_front(2);
	lt.push_front(3);
	lt.push_front(4);
	ZH::list<int>::iterator it = lt.begin();
	while (it!=lt.end())
	{
		cout << *it << " ";
		++it;
	}
	return 0;
}

        运行结果：

        注意，这里的it要看成是一个对象，他的类型是 list<int>::iterator。ZH::list<int>::iterator it = lt.begin();这句代码实际上是调用了拷贝构造，用begin（）的返回对象构造了一个新的对象it。

2.2 反向迭代器 

        反向迭代器与正向迭代器的区别在于，反向迭代器是从链表的最后一个节点开始往前遍历的，并且他的逻辑和正向迭代器的逻辑是相反的，可以确定的一点是反向迭代器也是通过一个类来实现的。

        反向迭代器实现代码如下：

#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
using namespace std;

namespace ZH
{
	template <class T>
	struct list_node//节点类
	{
		list_node<T>* prev;
		list_node<T>* next;
		T val;

		list_node(const T& t)
			:prev(nullptr)
			, next(nullptr)
			, val(t)
		{}
	};

	template<class T>
	struct list_iterator//迭代器类
	{
		typedef list_node<T> node;
		typedef list_iterator<T> self;

		node* _node;// 成员变量

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

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

		self& operator++()//重载前置++
		{
			_node = _node->next;
			return *this;
		}

		self& operator--()//重载前置--
		{
			_node = _node->prev;
			return *this;
		}

		T& operator*()//重载解引用
		{
			return _node->val;
		}

	};

	template<class T>
	class list_reverse_iterator
	{
	public:
		typedef list_iterator<T> iterator;
		typedef list_reverse_iterator<T> rself;

		list_reverse_iterator(iterator it)
				:rit(it)
		{}

		bool operator!=(const rself& s)//重载！=
		{
			return rit!= s.rit;//复用正向迭代器的！=重载
		}

		rself& operator++()//重载前置++
		{
			--rit;//复用正向迭代器的++
			return *this;
		}

		T& operator*()//重载解引用
		{
			return *rit;//复用正向迭代器的解引用
		}

	private:
		iterator rit;
	};

	template <class T>
	class list//链表类
	{
	public:
		typedef list_node<T> node;//让节点类看起来像一个普通的节点
		typedef list_iterator<T> iterator;//让迭代器类看起来像一个迭代器
		typedef list_reverse_iterator<T> reverse_iterator;

		list()//构造函数、目的是创建哨兵位头节点
			:_node(new node(-1))
		{
			_node->next = _node;
			_node->prev = _node;
		}

		void push_front(const T& t)//头插
		{
			node* newnode = new node(t);
			node* cur = _node->next;

			_node->next = newnode;
			newnode->prev = _node;
			newnode->next = cur;
			cur->prev = newnode;
		}

		reverse_iterator rbegin()
		{
			return reverse_iterator(iterator(_node->prev));//返回最后一个节点
		}

		reverse_iterator rend()
		{
			return reverse_iterator(iterator(_node));//返回头节点
		}

		~list()//析构
		{
			node* cur = _node->next;
			node* dest = cur->next;
			while (cur != _node)
			{
				delete cur;
				cur = dest;
				dest = dest->next;
			}
			delete _node;
			_node = nullptr;
		}

	private:
		node* _node;//指向哨兵位的头节点

	};
}

int main()
{
	ZH::list<int> lt;
	lt.push_front(1);
	lt.push_front(2);
	lt.push_front(3);
	lt.push_front(4);
	ZH::list<int>::reverse_iterator rit = lt.rbegin();
	while (rit != lt.rend())
	{
		cout << *rit << " ";
		++rit;
	}
	return 0;
}

        运行结果：

        从上述代码中可以发现，反向迭代器是复用正向迭代器的成员函数达到实现的，只不过在反向迭代器类里进行又一层包装。

3、指定位置插入

        有了迭代器，就可以实现从指定位置插入了，指定位置插入代码如下：

void Insert(iterator pos, const T& val)//插入
		{
			node* newnode = new node(val);
			node* cur = pos._node;
			node* prev = cur->prev;

			prev->next = newnode;
			newnode->prev = prev;
			newnode->next = cur;
			cur->prev = newnode;
		}

         值得注意的是，list的插入不会导致迭代器失效，因为即使在该迭代器指向节点的前面插入一个数据，则该迭代器还是指向该节点的。

4、指定位置删除

        指定位置删除代码如下：

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

        删除逻辑示意图：

        删除与插入不同在于，删除之后迭代器会失效，因为此时it指向的是一块被回收的区域，不能直接访问it所指向的区域，会导致野指针问题。 

5、结语

        以上就是关于list如何实现的讲解，list的模拟实现完全体现了面向对象的思想，链表本身、节点以及迭代器都被封装成一个类，从用户的角度看，是在对象的层面上直接进行操作的，但是底层却是各种复用，依旧是通过操作内置类型来实现上层的对象之间的操作。

        最后希望本文可以给你带来更多的收获，如果本文对你起到了帮助，希望可以动动小指头帮忙点赞👍+关注😎+收藏👌！如果有遗漏或者有误的地方欢迎大家在评论区补充，谢谢大家！！


http://www.niftyadmin.cn/n/5354023.html

相关文章

【游戏服务器部署】幻兽帕鲁服务器一键部署保姆级教程，游戏私服还是自己搭建的香

【游戏服务器部署】幻兽帕鲁服务器一键部署保姆级教程，游戏私服还是自己搭建的香

在帕鲁的世界&#xff0c;你可以选择与神奇的生物「帕鲁」一同享受悠闲的生活&#xff0c;也可以投身于与偷猎者进行生死搏斗的冒险。帕鲁可以进行战斗、繁殖、协助你做农活&#xff0c;也可以为你在工厂工作。你也可以将它们进行售卖&#xff0c;或肢解后食用。—幻兽帕鲁 想要…
阅读更多...
伦敦银交易时遇到横盘震荡行情怎么办？

伦敦银交易时遇到横盘震荡行情怎么办？

做伦敦银的投资者很怕碰到震荡行情&#xff0c;因为我们做伦敦银交易&#xff0c;一般会去寻找高概率入场的机会&#xff0c;而发现高概率机会的方法多数是建立在顺势交易的基础上。什么方法对应什么样的行情&#xff0c;那应对横盘震荡&#xff0c;我们该怎么办呢&#xff1f;…
阅读更多...
Chrome 121 释出

Chrome 121 释出

Chrome 121 释出 有趣的是2024年1月23日Mozilla Firefox&#xff0c;释放了122的版本。Mozilla Firefox 的版本号现在超过了 Google Chrome。 Google 释出 Chrome 121&#xff0c;修正了 17 个安全漏洞&#xff0c;其中 3 个高危。 其它变化包括&#xff1a; 新的标签组织 A…
阅读更多...
sklearn 计算 tfidf 得到每个词分数

sklearn 计算 tfidf 得到每个词分数

from sklearn.feature_extraction.text import TfidfVectorizer# 语料库 可以换为其它同样形式的单词 corpus [list(range(-5, 5)),list(range(-6,4)),list(range(12)),list(range(13))]# corpus [ # [Two, wrongs, don\t, make, a, right, .], # [The, pen, is, might…
阅读更多...
【每日一题】YACS 473：栈的判断

【每日一题】YACS 473：栈的判断

这是上海计算机学会竞赛 P 473 P473 P473&#xff1a;栈的判断&#xff08; 2021 2021 2021年 8 8 8月月赛 丙组 T 4 T4 T4&#xff09;标签&#xff1a;栈题意&#xff1a;给定 n n n个数字&#xff0c;已知这些数字的入栈顺序为 1 , 2 , 3... , n 1,2,3...,n 1,2,3...,n&…
阅读更多...
CTF CRYPTO 密码学-7

CTF CRYPTO 密码学-7

题目名称&#xff1a;敲击 题目描述&#xff1a; 让我们回到最开始的地方 0110011001101100011000010110011101111011011000110110010100110011011001010011010100110000001100100110001100101101001101000011100001100011001110010010110100110100011001000011010100110000…
阅读更多...
【C语言/数据结构】排序（归并排序|计数排序|排序算法复杂度）

【C语言/数据结构】排序（归并排序|计数排序|排序算法复杂度）

&#x1f308;个人主页&#xff1a;秦jh__https://blog.csdn.net/qinjh_?spm1010.2135.3001.5343&#x1f525; 系列专栏&#xff1a;《数据结构》https://blog.csdn.net/qinjh_/category_12536791.html?spm1001.2014.3001.5482 ​​​​ 目录 归并排序 代码实现&#xf…
阅读更多...
【MyBatis】快速入门MyBatis（保姆式教学），你值得一看

【MyBatis】快速入门MyBatis（保姆式教学），你值得一看

文章目录 &#x1f4c4;前言一. Mybatis简介✈️1. 什么是Mybatis&#x1f680;2. 为什么使用Mybatis 二. Mybatis快速入门&#x1f346;1. mybatis使用前准备1.1 创建springboot项目并引入相关依赖1.2 在 application.ym中进行数据源的配置1.3 创建数据表&#xff0c;准备表数…
阅读更多...
最新文章

Copyright @ 2022~2023