C++第十二弹 -- STL之list模拟实现

文章索引

  • 前言
  • 模拟实现list
    • 1. ListNode节点类
    • 2. list的迭代器封装
    • 3. 反向迭代器
    • 4. list类的模拟实现
    • 测试代码
  • list的反向迭代器
  • 总结

前言

通过模拟实现可以让我们更加深刻的理解C++底层STL的实现逻辑, 本篇就对list的底层进行模拟实现.

博客主页: 酷酷学!!! 点击关注 共同进步!!!

正文开始

模拟实现list

要模拟实现list, 必须要熟悉list的底层结构以及其接口的含义, 通过上一篇的学习, 这些内容基本掌握之后, 现在我们来模拟实现list.

1. ListNode节点类

#pragma once
#include<iostream>
using namespace std;
#include<assert.h>

namespace my
{
	//list的节点类
	template<class T>
	struct ListNode
	{

		ListNode(const T& val = T())
			: _prev(nullptr)
			, _next(nullptr)
			, _val(val)
		{}

		ListNode<T>* _prev;
		ListNode<T>* _next;
		T _val;
	};

2. list的迭代器封装

list的迭代器
迭代器有两种实现方式, 具体应根据容器底层数据结构的实现:
1.原生态指针, 比如:vector
2.将原生态指针进行封装, 因迭代器使用形式与指针完全相同,
因此在自定义的类中必须实现以下方法:
	1.指针可以解引用,迭代器的类中必须重载operator*()
	2.指针可以通过->访问其所指空间成员,迭代器类中必须重载operator->()
	3.指针可以++向后移动,迭代器类中必须重载operator++()与operator++(int)
	  至于operator--()/operator--(int)释放需要重载,根据具体的结构来抉择,
	  双向链表可以向前或者向后移动,所以需要重载,如果是forward_list就不需要重载--
	4.迭代器需要进行是否相等的比较,因此还需要重载operator==()与operator!=()

	template<class T,class Ref,class Ptr>
	class ListIterator
	{
		typedef ListNode<T> Node;
		typedef ListIterator<T, Ref, Ptr> Self;
		//Ref 和 Ptr类型需要重新定义下,实现反向迭代器时需要用到
	public:
		typedef Ref Ref;
		typedef Ptr Ptr;

		//构造
		ListIterator(Node* node = nullptr)
			: _node(node)
		{}

		//具有指针类似行为
		Ref operator*()
		{
			return _node->_val;
		}

		Ptr operator->()
		{
			return &(operator*());
		}

		//迭代器支持移动
		Self& operator++()
		{
			_node = _node->_next;
			return *this;
		}

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

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

		Self operator--(int)
		{
			Self temp(*this);
			_node = _node->_prev;
			return temp;
		}

		//迭代器支持比较
		bool operator!=(const Self& l) const
		{
			return _node != l._node;
		}

		bool operator==(const Self & l) const
		{
			return _node == l._node;
		}

		Node* _node;
	};

3. 反向迭代器

	//反向迭代器,迭代器复用
	template<class Iterator>
	class ReverseListIterator
	{
		//注意:此处typename的作用是明确的告诉编译器,Ref是Iterator类中的一个类型,
		//而不是静态成员变量,否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员
		//变量,因为静态成员变量也是按照 类名::静态成员变量名 的方式访问的
	public:
		typedef typename Iterator::Ref Ref;
		typedef typename Iterator::Ptr Ptr;
		typedef ReverseListIterator<Iterator> Self;

		//构造
		ReverseListIterator(Iterator it)
			: _it(it)
		{}

		//具有指针类似行为
		Ref operator*()
		{
			Iterator temp(_it);
			--temp;
			return *temp;
		}

		Ptr operator->()
		{
			return &(operator*());
		}

		//迭代器支持移动
		Self& operator++()
		{
			--_it;
			return *this;
		}

		Self& operator++(int)
		{
			Self temp(*this);
			--_it;
			return *this;
		}

		Self& operator--()
		{
			++_it;
			return *this;
		}

		Self& operator--(int)
		{
			Self temp(*this);
			++_it;
			return temp;
		}

		//迭代器支持比较
		bool operator!=(const Self& l) const
		{
			return _it != l._it;
		}

		bool operator==(const Self& l) const
		{
			return _it == l._it;
		}
		Iterator _it;
	};

4. list类的模拟实现

	template<class T>
	class list
	{
		typedef ListNode<T> Node;

	public:

		//正向迭代器
		typedef ListIterator<T, T&, T*> iterator;
		typedef ListIterator<T, const T&, T*> const_iterator;

		//反向迭代器
		typedef ReverseListIterator<iterator> reverse_iterator;
		typedef ReverseListIterator<const_iterator> const_reverse_iterator;
		
		//List的构造
		list()
		{
			CreateHead();
		}

		list(int n, const T& value = T())
		{
			CreateHead();
			for (int i = 0; i < n; ++i)
			{
				push_back(value);
			}
		}

		template<class Iterator>
		list(Iterator first, Iterator last)
		{
			CreateHead();
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}
		
		list(const list<T>& l)
		{
			CreateHead();
			//用l中的元素构造临时的temp,然后与当前对象交换
			list<T> temp(l.begin(), l.end());
			this->swap(temp);
		}

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

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


		//list的迭代器
		iterator begin()
		{
			return iterator(_head->_next);
		}

		iterator end()
		{
			return iterator(_head);
		}

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

		const_iterator end() const
		{
			return const_iterator(_head);
		}

		reverse_iterator rbegin()
		{
			return reverse_iterator(end());
		}

		reverse_iterator rend()
		{
			return reverse_iterator(begin());
		}

		const_reverse_iterator rbegin() const
		{
			return const_reverse_iterator(end());
		}

		const_reverse_iterator rend() const
		{
			return const_reverse_iterator(begin());
		}

		//List的容器相关
		size_t size() const
		{
			Node* cur = _head->_next;
			size_t count = 0;
			while (cur != _head)
			{
				++count;
				cur = cur->_next;
			}
			return count;
		}

		bool empty() const
		{
			return _head->_next = _head;
		}

		void resize(size_t newsize, const T* data = T())
		{
			size_t oldsize = size();
			if (newsize <= oldsize)
			{
				//将有效元素减少到newsize
				while (newsize < oldsize)
				{
					pop_back();
					--oldsize;
				}
			}
			else
			{
				while (oldsize < newsize)
				{
					push_back(data);
					++oldsize;
				}
			}
		}

		//list的元素访问操作
		//注意:List不支持operator[]
		T& front()
		{
			return _head->_next->_val;
		}

		const T& front() const
		{
			return _head->_next->_val;
		}

		T& back()
		{
			return _head->_prev->_val;
		}

		const T& back() const 
		{
			return _head->_prev->_val;
		}


		//list的插入和删除
		void push_back(const T& val)
		{
			insert(end(), val);
		}

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

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

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

		//在pos位置前插入值为val的节点
		iterator insert(iterator pos, const T& val)
		{
			Node* pNewNode = new Node(val);
			Node* pCur = pos._node;
			//先将新节点插入
			pNewNode->_prev = pCur->_prev;
			pNewNode->_next = pCur;
			pNewNode->_prev->_next = pNewNode;
			pCur->_prev = pNewNode;
			return iterator(pNewNode);
		}

		//删除pos位置的节点,返回该节点的下一个位置
		iterator erase(iterator pos)
		{
			//找到待删除的节点
			Node* pDel = pos._node;
			Node* pRet = pDel->_next;

			//将该节点从链表中拆下来并删除
			pDel->_prev->_next = pDel->_next;
			pDel->_next->_prev = pDel->_prev;
			delete pDel;

			return iterator(pRet);
		}

		void clear()
		{
			Node* cur = _head->_next;
			//采用头删除删除
			while (cur != _head)
			{
				Node* next = cur->_next;
				delete cur;
				cur = next;
			}
			_head->_next = _head->_prev = _head;
		}
		
		void swap(my::list<T>& l)
		{
			std::swap(_head, l._head);
		}

	private:
		void CreateHead()
		{
			_head = new Node;
			_head->_prev = _head;
			_head->_next = _head;
		}
		Node* _head;
	};	
}

测试代码

对构造函数进行测试

//对模拟实现的list进行测试
//正向打印链表
template<class T>
void PrintList(const my::list<T>& l)
{
	auto it = l.begin();
	while (it != l.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
}

//测试list的构造
void Testmylist1()
{
	my::list<int> l1;
	my::list<int> l2(10, 5);
	PrintList(l2);

	int array[] = { 1,2,3,4,5,6,7,8,9,0 };
	my::list<int> l3(array, array + sizeof(array) / sizeof(array[0]));
	PrintList(l3);

	my::list<int> l4(l3);
	PrintList(l4);

	l1 = l4;
	PrintList(l1);
}

在这里插入图片描述

对头/尾插入删除进行测试

//PushBack()/PopBack()/PushFront()/PopFront()
void Testmylist2()
{
	//测试pushBack和PopBack
	my::list<int> l;
	l.push_back(1);
	l.push_back(2);
	l.push_back(3);
	PrintList(l);

	l.pop_back();
	l.pop_back();
	PrintList(l);

	l.pop_back();
	cout << l.size() << endl;

	//测试pushFront与popFront
	l.push_front(1);
	l.push_front(2);
	l.push_front(3);
	PrintList(l);

	l.pop_front();
	l.pop_front();
	PrintList(l);

	l.pop_front();
	cout << l.size() << endl;
}

在这里插入图片描述

测试指定位置插入删除

//测试insert和erase
void Testmylist3()
{
	int array[] = { 1,2,3,4,5 };
	my::list<int> l(array, array + sizeof(array) / sizeof(array[0]));
	auto pos = l.begin();
	l.insert(l.begin(), 0);
	PrintList(l);

	++pos;
	l.insert(pos, 2);
	PrintList(l);

	l.erase(l.begin());
	l.erase(pos);
	PrintList(l);

	//pos指向的节点已经被删除,pos迭代器失效
	cout << *pos << endl;
	auto it = l.begin();
	while (it != l.end())
	{
		it = l.erase(it);
	}
	cout << l.size() << endl;
}

在这里插入图片描述

测试反向迭代器

//测试反向迭代器
void Testmylist4()
{
	int array[] = { 1,2,3,4,5 };
	my::list<int> l(array, array + sizeof(array) / sizeof(array[0]));
	
	auto rit = l.rbegin();
	while (rit != l.rend())
	{
		cout << *rit << " ";
		++rit;
	}
	cout << endl;

	const my::list<int> cl(l);
	auto crit = l.rbegin();
	while (crit != l.rend())
	{
		cout << *crit <<" ";
		++crit;
	}
	cout << endl;
}

在这里插入图片描述

list的反向迭代器

我们知道, 反向迭代器的++就是正向迭代器的- -, 反向迭代器的- -就是正向迭代器的++, 因此反向迭代器的实现可以借助正向迭代器, 即: 返现迭代器内部可以包含一个正向迭代器, 对正向迭代器的接口进行包装即可.

	//反向迭代器,迭代器复用
	template<class Iterator>
	class ReverseListIterator
	{
		//注意:此处typename的作用是明确的告诉编译器,Ref是Iterator类中的一个类型,
		//而不是静态成员变量,否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员
		//变量,因为静态成员变量也是按照 类名::静态成员变量名 的方式访问的
	public:
		typedef typename Iterator::Ref Ref;
		typedef typename Iterator::Ptr Ptr;
		typedef ReverseListIterator<Iterator> Self;

		//构造
		ReverseListIterator(Iterator it)
			: _it(it)
		{}

		//具有指针类似行为
		Ref operator*()
		{
			Iterator temp(_it);
			--temp;
			return *temp;
		}

		Ptr operator->()
		{
			return &(operator*());
		}

		//迭代器支持移动
		Self& operator++()
		{
			--_it;
			return *this;
		}

		Self& operator++(int)
		{
			Self temp(*this);
			--_it;
			return *this;
		}

		Self& operator--()
		{
			++_it;
			return *this;
		}

		Self& operator--(int)
		{
			Self temp(*this);
			++_it;
			return temp;
		}

		//迭代器支持比较
		bool operator!=(const Self& l) const
		{
			return _it != l._it;
		}

		bool operator==(const Self& l) const
		{
			return _it == l._it;
		}
		Iterator _it;
	};

完

总结

通过以上的实现，可以模拟出一个类似于list的数据结构，并且可以对其中的元素进行添加、删除、查找、等操作。这样就可以在不使用C++内置的list时，使用自己实现的List类来进行相同的操作。

感谢您的点赞与收藏!!!

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

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

相关文章

详解语义安全（semantically secure）

详解语义安全（semantically secure）

目录 一. 引入 二. 密文与明文 2.1 通俗性理解 2.2 定理 2.3 定理理解 三. 语义安全的第一个版本 3.1 基本理解 3.2 定理 3.3 定理理解 四. 语义安全的第二个版本 4.1 直观解释 4.2 小结 一. 引入 密码学中安全加密要求&#xff1a;敌手&#xff08;adversary&…
阅读更多...
Git使用方法(三)---简洁版上传git代码

Git使用方法(三)---简洁版上传git代码

1 默认已经装了sshWindows下安装SSH详细介绍-CSDN博客 2 配置链接github的SSH秘钥 1 我的.ssh路径 2 进入路径cd .ssh 文件 3 生成密钥对 ssh-keygen -t rsa -b 4096 (-t 秘钥类型 -b 生成大小) 输入完会出现 Enter file in which to save the key (/c/Users/Administrator/…
阅读更多...
【Android】adb devices 出现devices offline的问题

【Android】adb devices 出现devices offline的问题

1 问题 adb devices 出现devices offline 2 解决方法 adb kill-serveradb start-server 然后&#xff0c;adb devices查看。 adb devices 问题解决啦。。。&#x1f49b; &#x1f499; &#x1f49c; ❤️ &#x1f49a; &#x1f49b; &#x1f499; &#x1f49c; ❤️…
阅读更多...
雨云美国二区E5v2服务器测评（非广告）

雨云美国二区E5v2服务器测评（非广告）

注&#xff1a;本文非广告&#xff0c;非推广 本文长期更新地址&#xff1a; 雨云美国二区E5v2服务器测评&#xff08;非广告&#xff09;-星零岁的博客https://blog.0xwl.com/13594.html 今天来测评一下雨云美国二区v2服务器。我测试的这台配置是4-8&#xff0c; 35 M上传&a…
阅读更多...
《机器学习》周志华-CH1（绪论）

《机器学习》周志华-CH1（绪论）

1.1引言 机器学习&#xff08;Matchine-Learning&#xff09;所研究的主要内容是关于在计算机上从数据中产生“模型”&#xff08;model&#xff09;的算法&#xff0c;即“学习算法”&#xff08;learning algorithm&#xff09;。可以说机器学习&#xff08;Matchine-Learni…
阅读更多...
智能菜谱推荐系统_ct3p7

智能菜谱推荐系统_ct3p7

TOC springboot575智能菜谱推荐系统_ct3p7--论文 第一章 概述 1.1 研究背景 近些年&#xff0c;随着中国经济发展&#xff0c;人民的生活质量逐渐提高&#xff0c;对网络的依赖性越来越高&#xff0c;通过网络处理的事务越来越多。随着智能菜谱推荐管理的常态化&#xff0c…
阅读更多...
PYQT实现上传图片，保存图片

PYQT实现上传图片，保存图片

代码如下 from PyQt5.QtWidgets import * from PyQt5.QtGui import * from PyQt5.QtCore import * import sysclass MyWindow(QMainWindow):def __init__(self):super(MyWindow, self).__init__()self.setWindowTitle("图片处理")self.setGeometry(200, 200, 500, …
阅读更多...
最全海外广告库大合集，建议收藏！

最全海外广告库大合集，建议收藏！

在当今数字营销的世界中&#xff0c;广告投放的精准性和创意性变得越来越重要。而“海外广告库”作为一种强大的工具&#xff0c;正在被越来越多的广告主和营销专家所使用。本文将深入探讨几大主流的海外广告库&#xff0c;并探讨如何利用它们来提升广告效果。 什么是海外广告…
阅读更多...
推荐一个开源的kafka可视化客户端GUI工具（Kafka King）

推荐一个开源的kafka可视化客户端GUI工具（Kafka King）

大佬的博客地址&#xff1a; https://blog.ysboke.cn/posts/tools/kafka-king Github地址&#xff1a; https://github.com/Bronya0/Kafka-King Kafka-King功能清单 查看集群节点列表&#xff08;完成&#xff09;支持PLAINTEXT、SASL PLAINTEXT用户名密码认证&#xff08;完…
阅读更多...
[C语言]-基础知识点梳理-文件管理

[C语言]-基础知识点梳理-文件管理

前言 各位师傅们好&#xff0c;我是qmx_07&#xff0c;今天给大家讲解文件管理的相关知识&#xff0c;也就是常见的 读取&#xff0c;删除一类的操作 文件 为什么要使用文件&#xff1f; 程序的数据是存储在电脑的内存中&#xff0c;如果程序退出&#xff0c;内存回收&…
阅读更多...
[Leetcode 61][Medium]-旋转链表

[Leetcode 61][Medium]-旋转链表

目录 一、题目描述 二、整体思路 三、代码 一、题目描述 原题链接 二、整体思路 首先发现这样的规律&#xff1a;当k大于等于链表中节点总数n时&#xff0c;会发现此时旋转后的链表和kk%n时的旋转后的链表一样。同时对于特殊情况n0和n1时&#xff0c;无论k的值为多少都可以…
阅读更多...
认识Mongodb及其Java的连接

认识Mongodb及其Java的连接

什么是Mongodb&#xff1f; MongoDB是一个介于关系数据库和非关系数据库(nosql)之间的产品&#xff0c;是非关系数据库当中功能最丰富&#xff0c;最像关系数据库的。 优点 1.MongoDB的提供了一个面向文档存储&#xff0c;操作起来比较简单和容易。 2.如果负载的增加&#x…
阅读更多...
Python中matplotlib使用4

Python中matplotlib使用4

在matplotlib中&#xff0c;可以通过绘制“饼图”来展示各类别在总体中所占的比例。 1 绘制基本“饼图” 通过matplotlib中的pie()函数绘制饼图&#xff0c;代码如图1所示。 图1 绘制基本“饼图”的代码 从图1中可以看出&#xff0c;pie()函数的参数y即为要绘制的数据&#…
阅读更多...
使用SSMS连接和查询 SQL Server 实例

使用SSMS连接和查询 SQL Server 实例

简介 SQL Server Management Studio 是用于管理SQL Server基础架构的集成环境。Management Studio提供用于配置、监视和管理SQL Server实例的工具。 此外&#xff0c;它还提供了用于部署、监视和升级数据层组件(如应用程序使用的数据库和数据仓库)的工具以生成查询和脚本。 官方…
阅读更多...
现代RTK测量设备的高速发展及其应用前景

现代RTK测量设备的高速发展及其应用前景

RTK&#xff08;实时动态定位&#xff0c;Real-Time Kinematic&#xff09;测量设备是利用GNSS&#xff08;全球导航卫星系统&#xff0c;Global Navigation Satellite System&#xff09;技术&#xff0c;通过引用基准站与移动站的数据传输机制&#xff0c;实现高精度的位置信…
阅读更多...
基于spring boot的小型诊疗预约平台的设计与开发

基于spring boot的小型诊疗预约平台的设计与开发

TOC springboot262基于spring boot的小型诊疗预约平台的设计与开发 绪论 1.1 研究背景 当前社会各行业领域竞争压力非常大&#xff0c;随着当前时代的信息化&#xff0c;科学化发展&#xff0c;让社会各行业领域都争相使用新的信息技术&#xff0c;对行业内的各种相关数据进…
阅读更多...
打靶记录12——Fawkes

打靶记录12——Fawkes

靶机&#xff1a; https://download.vulnhub.com/harrypotter/Fawkes.ova这是个哈利波特系列的靶机&#xff0c;作者和本人都非常喜欢这个系列&#xff0c;因为它的漏洞和利用点都设计得很巧妙。 难度&#xff1a; 高 目标&#xff1a; 取得2个root权限 3 个flag 涉及攻…
阅读更多...
Linux中的exec族函数

Linux中的exec族函数

exec 系列函数用于替换当前进程的用户空间代码和数据&#xff0c;从而执行一个新的程序。调用 exec 系列函数不会创建新的进程&#xff0c;但会用新程序的代码和数据替换当前进程&#xff0c;因此调用 exec 后&#xff0c;进程的 ID 保持不变&#xff0c;但进程的行为变为执行新…
阅读更多...
前端基础4

前端基础4

本节内容&#xff1a; 1.CSS的弹性布局&#xff0c;也称Flex布局 2.Vue2的生命周期 一、Flex布局 弹性布局是前端页面布局最常用的方式之一&#xff0c;通常使用四个属性。 1.创建盒子 先创建一个盒子并为其添加一些样式可以更直观的体验弹性布局&#xff0c;代码如下&#…
阅读更多...
keepalived保活nginx1，nginx2

keepalived保活nginx1，nginx2

1 下载两个小玩意 yum -y install keepalived yum install psmisc -y 2 配置nginx1&#xff0c;2自启脚本 vim /root/shell/check-nginx.sh 我的脚本放在root/shell里 #!/bin/bash #获取nginx正在运行的进程数 npsnumps -C nginx --no-header | wc -lif [ $n…
阅读更多...
最新文章

Copyright @ 2022~2023