[C++] 模拟实现list（二）

标题：[C++] 模拟实现list（二）

@水墨不写bug

目录

（一）回顾

（二）迭代器类的封装设计

（1）成员函数简要分析

 （2）const迭代器类的设计

（3）list类的封装设计

（4）反向迭代器类的设计

（三）实现list类

正文开始：

（一）回顾

        本篇文章接续《[C++] 模拟实现list（二）》继续讲解STL实现list的逻辑和思考，最终提供实现的list的最终版本。

        [C++] 模拟实现list（二）中，我们定义了三个类：

template<typename T>
struct ListNode;

template<typename T>
struct ListIterator;

template<class T>
class list;

        ListNode即是list的一个节点；ListIterator即对节点的指针的封装的一个类，也就是迭代器；list即是链表的类；

         我们一般通过指针来维护链表，但是如果直接拿指针这个内置类型作为迭代器，迭代器的行为不符合我们的要求，所以我们将这个指针封装为一个类，这样就可以通过类的成员函数重载运算符来使得迭代器的行为符合我们的要求。

（二）迭代器类的封装设计

（1）成员函数简要分析

        我们实现迭代器类ListIterator，本质就是通过封装节点的指针，来实现要求的功能。这个迭代器类，看似是一个自定义类，其实我们可以把它的行为等效的看为一个指针类型：

        指针的前置++，就是节点指针先向后移动再使用。

        指针的前置--，就是节点指针的先向前移动，再使用。

        指针的后置++，后置--，先使用，再移动。

        指针的解引用，就得到了数据——然而对于封装的类，我们把它的行为定义为返回节点指针的数据。

        变量引用返回，得到这个变量本身——对于ListIterator类，我们返回数据T的引用；

        以及对==和 != 的重载，只需要比较节点指针内的数据是否一致即可。

 （2）const迭代器类的设计

        有普通的迭代器，就会有const迭代器，我们根据上面的分析，可以实现的普通迭代器如下：

template<typename T>
struct ListIterator
{
	typedef ListNode<T> Node;
	typedef ListIterator<T> Self;
	ListIterator(Node* node = nullptr)
		:_node(node)
	{}
	Self& operator++()
	{
		_node = _node->_next;
		return *this;
	}
	Self& operator--()
	{
		_node = _node->_prev;
		return *this;
	}
	Self& operator++(int)
	{
		Self tem(*this);
		_node = _node->_next;
		return tem;
	}
	Self& operator--(int)
	{
		Self tem(*this);
		_node = _node->_prev;
		return *this;
	}
	T& operator*()
	{
		return _node->_data;
	}
	T* operator->()
	{
		return &(_node->_data);
	}
	bool operator==(const Self& ltt)
	{
		return _node == ltt._node;
	}
	bool operator!=(const Self& ltt)
	{
		return !(*this == ltt);
	}
	 Node* _node;
};

        如果第一次思考，你可能会想到直接在实例化的时候在普通迭代器前面加上const，但是这是错误的做法：如果直接在普通迭代器前面加上const，这就表明const修饰迭代器本身（类本身，也就是类对象本身不能修改：由于类内部只有一个节点的指针类型，所以这个指针本身不能修改，这是一个与事实相悖的结果：指针不能移动了！）

        想要解决上述问题，我们只有再定义一个类ConstListIterator，在类内部我们发现其实现与普通迭代器相比，只有两个不同的地方：

        这两个地方自然是涉及对象内数据的成员函数重载，他们是：

operator*()

operator->()

         如果我们执意要实现ConstListIterator类，可以实现如下：

template<typename T>
struct ListIterator
{
	typedef ListNode<T> Node;
	typedef ListIterator<T> Self;
	ListIterator(Node* node = nullptr)
		:_node(node)
	{}
	Self& operator++()
	{
		_node = _node->_next;
		return *this;
	}
	Self& operator--()
	{
		_node = _node->_prev;
		return *this;
	}
	Self& operator++(int)
	{
		Self tem(*this);
		_node = _node->_next;
		return tem;
	}
	Self& operator--(int)
	{
		Self tem(*this);
		_node = _node->_prev;
		return *this;
	}
	const T& operator*()
	{
		return _node->_data;
	}
	const T* operator->()
	{
		return &(_node->_data);
	}
	bool operator==(const Self& ltt)
	{
		return _node == ltt._node;
	}
	bool operator!=(const Self& ltt)
	{
		return !(*this == ltt);
	}
	 Node* _node;
};

通过比较两个类，我们发现只有他们的返回值不同而已，这两个类的大部分代码都是重复的。那么有没有一种方法可以缩减代码量，减少我们的工作量呢？

        我们可以通过额外多传入两个参数Ptr，Ref来解决这个问题：

template<typename T,class Ref,class Ptr>
struct ListIterator
{
	typedef ListNode<T> Node;
	typedef ListIterator<T, Ref, Ptr> Self;
	ListIterator(Node* node = nullptr)
		:_node(node)
	{}
	Self& operator++()
	{
		_node = _node->_next;
		return *this;
	}
	Self& operator--()
	{
		_node = _node->_prev;
		return *this;
	}
	Self& operator++(int)
	{
		Self tem(*this);
		_node = _node->_next;
		return tem;
	}
	Self& operator--(int)
	{
		Self tem(*this);
		_node = _node->_prev;
		return *this;
	}
	T& operator*()
	{
		return _node->_data;
	}
	Ref operator*() const
	{
		return _node->_data;
	}
	T* operator->()
	{
		return &(_node->_data);
	}
	Ptr operator->() const
	{
		return &(_node->_data);
	}
	bool operator==(const Self& ltt)
	{
		return _node == ltt._node;
	}
	bool operator!=(const Self& ltt)
	{
		return !(*this == ltt);
	}

	 Node* _node;
};

        由于const迭代器与普通迭代器的大部分行为都是类似的，只有上述两个重载函数的返回值不同，这意味着const迭代器的*和->的返回值不能修改，是一个常量，这于事实相符。

        所以我们的第一个模板参数相同。都是T，而第二与第三个模板参数则根据迭代器类型的不同而不同：如果实例化的对象是const迭代器，则传入的Ref接受的是const T&，Ptr接受的是const T* ，我们这样就通过一个类模板就可以实现ListIterator和ConstListIterator两种迭代器类型。

（3）list类的封装设计

        由于我们在设计迭代器类的时候，把整个类设置为了struct，可以公开访问，这意味着我们可以在list类中使用迭代器ListIterator，这是我们现前就考虑的。但是在STL中，整个容器的设计按照迭代器模式设计，将迭代器类统称为iterator，所以与STL保持一致，同时与我们的迭代器类相互嵌合，所以我们先typedef出迭代器和const迭代器；接下来对于list的实现，就是我们的老面孔了——实现双向带头循环链表，你可以参考我的这篇文章：《实现双向链表》——里面有非常详细的讲解。

        所以，在这里我们不再赘述实现双向链表的过程。

（4）反向迭代器类的设计

        反向迭代器与普通迭代器的实现基本一致，只是在++改为节点前移动；--改为节点后移动。

反向迭代器类实现如下：

template<typename T, class Ref, class Ptr>
struct ReverseListIterator
{
	typedef ListNode<T> Node;
	typedef ReverseListIterator<T, Ref, Ptr> Self;
	ReverseListIterator(Node* node = nullptr)
		:_node(node)
	{}
	Self& operator++()
	{
		_node = _node->_prev;
		return *this;
	}
	Self& operator--()
	{
		_node = _node->_next;
		return *this;
	}
	Self& operator++(int)
	{
		Self tem(*this);
		_node = _node->_prev;
		return tem;
	}
	Self& operator--(int)
	{
		Self tem(*this);
		_node = _node->_next;
		return *this;
	}
	T& operator*()
	{
		return _node->_data;
	}
	Ref operator*() const
	{
		return _node->_data;
	}
	T* operator->()
	{
		return &(_node->_data);
	}
	Ptr operator->() const
	{
		return &(_node->_data);
	}
	bool operator==(const Self& ltt)
	{
		return _node == ltt._node;
	}
	bool operator!=(const Self& ltt)
	{
		return !(*this == ltt);
	}

	Node* _node;
};

        需要注意的是，反向迭代器也有const类型，所以采用了和普通迭代器同样的处理方法：设置三个模板参数：<T，Ref，Ptr>

（三）实现list类

        源代码如下：

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

namespace ddsm
{
	template<typename T>
	struct ListNode
	{
		ListNode<T>* _prev;
		ListNode<T>* _next;
		T _data;

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


	template<typename T,class Ref,class Ptr>
	struct ListIterator
	{
		typedef ListNode<T> Node;
		typedef ListIterator<T, Ref, Ptr> Self;
		ListIterator(Node* node = nullptr)
			:_node(node)
		{}
		Self& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		Self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}
		Self& operator++(int)
		{
			Self tem(*this);
			_node = _node->_next;
			return tem;
		}
		Self& operator--(int)
		{
			Self tem(*this);
			_node = _node->_prev;
			return *this;
		}
		T& operator*()
		{
			return _node->_data;
		}
		Ref operator*() const
		{
			return _node->_data;
		}
		T* operator->()
		{
			return &(_node->_data);
		}
		Ptr operator->() const
		{
			return &(_node->_data);
		}
		bool operator==(const Self& ltt)
		{
			return _node == ltt._node;
		}
		bool operator!=(const Self& ltt)
		{
			return !(*this == ltt);
		}

		 Node* _node;
	};
	template<typename T, class Ref, class Ptr>
	struct ReverseListIterator
	{
		typedef ListNode<T> Node;
		typedef ReverseListIterator<T, Ref, Ptr> Self;
		ReverseListIterator(Node* node = nullptr)
			:_node(node)
		{}
		Self& operator++()
		{
			_node = _node->_prev;
			return *this;
		}
		Self& operator--()
		{
			_node = _node->_next;
			return *this;
		}
		Self& operator++(int)
		{
			Self tem(*this);
			_node = _node->_prev;
			return tem;
		}
		Self& operator--(int)
		{
			Self tem(*this);
			_node = _node->_next;
			return *this;
		}
		T& operator*()
		{
			return _node->_data;
		}
		Ref operator*() const
		{
			return _node->_data;
		}
		T* operator->()
		{
			return &(_node->_data);
		}
		Ptr operator->() const
		{
			return &(_node->_data);
		}
		bool operator==(const Self& ltt)
		{
			return _node == ltt._node;
		}
		bool operator!=(const Self& ltt)
		{
			return !(*this == ltt);
		}

		Node* _node;
	};


	template<class T>
	class list
	{
		typedef ListNode<T> Node;
	public:
		typedef ListIterator<T, T&, T*> iterator;
		typedef ListIterator<T, const T&, const T*> const_iterator;
		typedef ReverseListIterator<T, T&, T*> reverse_iterator;
		typedef ReverseListIterator<T, const T&, const T*> const_reverse_iterator;
	public:
		//对于空链表的初始化（只创建一个头节点）
		void init_empty()
		{
			_pHead = new Node;
			_pHead->_next = _pHead;
			_pHead->_prev = _pHead;
		}
		//默认构造
		list()
		{
			init_empty();
		}
		// n 个值初始化
		list(int n, const T& value = T())
		{
			init_empty();
			for (size_t i = 0; i < n; i++)
			{
				push_back(value);
			}
		}
		//拷贝构造,深拷贝
		//list<int> l1(l2)
		list(const list<T>& lt)
		{
			init_empty();
			for (const auto& e : lt)
			{
				push_back(e);
			}
		}

		//赋值重载现代写法
		//复用拷贝构造
		void operator=(list<T> lt)
		{
			std::swap(_pHead,lt._pHead);
		}

		//初始化列表，初始化
		list(std::initializer_list<T> init)
		{
			init_empty();
			for (const auto& e : init)
			{
				push_back(e);
			}
		}


		void clear()
		{
			auto pos = begin();
			while (pos != end())
			{
				pos = erase(pos);//迭代器更新防止失效
			}
		}

		~list()
		{
			clear();
			delete _pHead;
			_pHead = nullptr;
		}
		/*void push_back(const T& value = T()) const
		{
			Node* newnode = new Node(value);

			newnode->_next = _pHead;
			newnode->_prev = _pHead->_prev;
			_pHead->_prev->_next = newnode;
			_pHead->_prev = newnode;
		}*/
		/*void push_back(const T& value)
		{
			Node* newnode = new Node(value);

			newnode->_next = _pHead;
			newnode->_prev = _pHead->_prev;
			_pHead->_prev->_next = newnode;
			_pHead->_prev = newnode;
		}*/

		reverse_iterator rbegin()
		{
			return reverse_iterator(_pHead->_prev);
		}
		const_reverse_iterator rbegin() const
		{
			return const_reverse_iterator(_pHead->_prev);
		}
		reverse_iterator rend()
		{
			return reverse_iterator(_pHead);
		}
		const_reverse_iterator rend() const
		{
			return const_reverse_iterator(_pHead);
		}
		iterator begin()
		{
			return iterator(_pHead->_next);
		}
		const_iterator begin() const
		{
			return const_iterator(_pHead->_next);
		}
		iterator end()
		{
			return iterator(_pHead);
		}
		const_iterator end() const
		{
			return const_iterator(_pHead);
		}
		//在指定位置之前插入
		iterator insert(iterator pos,const T& val = T())
		{
			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;

			return iterator(newnode);
		}
		//删除指定位置的节点
		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 iterator(next);
		}
		void push_front(const T& value)
		{
			insert(begin(), value);
		}
		void push_back(const T& value)
		{
			insert(end(), value);
		}
		void pop_front()
		{
			erase(begin());
		}
		void pop_back()
		{
			erase(--end());
		}
		T& front()
		{
			return begin()._node->_data;
		}
		const T& front()const
		{
			return begin()._node->_data;
		}
		T& back()
		{
			return (--end())._node->_data;
		}
		const T& back()const
		{
			return (--end())._node->_data;
		}
		size_t size()const
		{
			int count = 0;
			for (const auto& e : *this)
			{
				count++;
			}
			return count;
		}
		bool empty()const
		{
			return size() == 0;
		}
	private:
		Node* _pHead;
	};

}

完~

未经作者同意禁止转载

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

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

相关文章

Nginx上配置多个网站

Nginx上配置多个网站

一、需求描述 我们只有一台安装了Nginx的服务器，但是我们需要实现在这台服务器上部署多个网站，用以对外提供服务。 二、Nginx上配置多个网站分析 一般网站的格式为：【http://ip地址:端口号/URI】(比如：http://192.168.3.201:80)，IP地址也可用域名表示；那么要实现在Nginx…
阅读更多...
在Linux上搭建服务器之综合实验(web,dns,防火墙，SELinux)

在Linux上搭建服务器之综合实验(web,dns,防火墙，SELinux)

其实验简图如下&#xff1a; 解读&#xff1a; 本实验需要完成4部分内容&#xff0c;web服务器的搭建&#xff0c;主从dns服务器的搭建&#xff0c;防火墙的开启&#xff0c;以及SELinux设置为强制模式。 首先dns主服务器上配置web服务&#xff08;其中我本机的IP为192.168.5.…
阅读更多...
docker安装及部署本地项目命令示例-【window及linux通用安装】

docker安装及部署本地项目命令示例-【window及linux通用安装】

文章目录 安装部署本地项目的相关命令(本地项目可以是大模型&#xff0c;算法&#xff0c;软件开发等)其他相关命令 安装 windows教程 注&#xff1a;上面链接中&#xff0c;安装docker可以默认C盘等。登录docker destop即使报错也可使用cmd命令窗口 linux教程 注&#xff1a;…
阅读更多...
第三方配件也能适配苹果了，iOS 18与iPadOS 18将支持快速配对

第三方配件也能适配苹果了，iOS 18与iPadOS 18将支持快速配对

苹果公司以其对用户体验的不懈追求和对创新技术的不断探索而闻名。随着iOS 18和iPadOS 18的发布&#xff0c;苹果再次证明了其在移动操作系统领域的领先地位。 最新系统版本中的一项引人注目的功能&#xff0c;便是对蓝牙和Wi-Fi配件的配对方式进行了重大改进&#xff0c;不仅…
阅读更多...
OS_同步与互斥

OS_同步与互斥

2024-07-04&#xff1a;操作系统同步与互斥学习笔记 第9节 同步与互斥 9.1 同步互斥的基本概念9.1.1 同步关系9.1.2 互斥关系9.1.3 临界资源9.1.4 临界区9.1.5 同步机制应遵循规则 9.2 软件同步机制9.2.1 单标志法9.2.2 双标志先检查法9.2.3 双标志后检查法9.2.4 peterson算法 …
阅读更多...
Rust代码优化的九大技巧

Rust代码优化的九大技巧

一.使用 Cargo 内置的性能分析工具 描述&#xff1a;Cargo 是 Rust 的包管理器&#xff0c;带有内置工具来分析代码性能&#xff0c;以识别性能瓶颈。 解释&#xff1a; 发布模式&#xff1a;在发布模式下编译启用优化&#xff0c;可以显著提高性能。 cargo build --release基…
阅读更多...
匠芯创汽车电子方案应用

匠芯创汽车电子方案应用

汽车电子是指应用于汽车中的各种电子技术、电子设备和电子控制系统。它覆盖了车辆的信息娱乐系统、车辆控制系统、车辆通讯系统等多个方面。汽车电子通过增强车辆的性能、安全和乘坐体验&#xff0c;成为现代汽车设计和制造中不可或缺的一部分。 匠芯创ArtInChip应用芯片&#…
阅读更多...
什么是敏捷本地化

什么是敏捷本地化

快速、敏捷的多语言产品和服务交付正逐渐成为众多行业的常态。在这种情况下&#xff0c;重点从传统的期望&#xff08;即在合理的时间框架内翻译大量内容&#xff09;转变为翻译工作量非常大的小片段&#xff0c;通常在2-3到12-24小时之间&#xff0c;通常在周末或假期。 Logr…
阅读更多...
海狐外卖O2O商城系统：技术架构与运营模式的深度解析

海狐外卖O2O商城系统：技术架构与运营模式的深度解析

摘要&#xff1a; 本文深入探讨了海狐外卖O2O商城系统的技术架构、功能特性以及运营模式。海狐外卖作为一款专注于细分市场领域的外卖餐饮解决方案&#xff0c;不仅拥有先进的技术栈支持&#xff0c;还通过丰富的系统插件和灵活的运营模式&#xff0c;为商户和用户提供高效、便…
阅读更多...
构建未来对话：从零开始实现基于Vue 3的AI聊天页面

构建未来对话：从零开始实现基于Vue 3的AI聊天页面

大家好&#xff0c;今天我们将一起探索如何从零开始&#xff0c;使用Vue 3构建一个AI对话页面。这个过程不仅会让我们了解Vue 3的新特性&#xff0c;还会让我们对构建交互式Web应用有一个全新的认识。如果你是编程新手&#xff0c;别担心&#xff0c;我会用通俗易懂的语言&…
阅读更多...
AI大模型API：开启智能应用的新纪元

AI大模型API：开启智能应用的新纪元

AI大模型API是当今技术领域的重要突破&#xff0c;它们以其卓越的性能和强大的计算能力引领着人工智能的发展。这些API不仅仅是一种技术工具&#xff0c;更是推动智能化时代的核心驱动力。通过AI大模型类API&#xff0c;我们可以利用先进的算法和深度学习模型&#xff0c;实现各…
阅读更多...
LeetCode之最长回文子串

LeetCode之最长回文子串

1.题目链接 5. 最长回文子串 - 力扣&#xff08;LeetCode&#xff09;https://leetcode.cn/problems/longest-palindromic-substring/description/ 2.题目解析 对于这道题目我们可以使用动态规划的思路来求解&#xff0c;具体思路是&#xff0c;对于一个长度大于2的子串&…
阅读更多...
Python爬虫教程第5篇-使用BeautifulSoup查找html元素几种常用方法

Python爬虫教程第5篇-使用BeautifulSoup查找html元素几种常用方法

文章目录 简介find()和find_all()字符串通过id查找通过属性查找通过.方式查找通过CSS选择器查找通过xpath查找正则表达自定义方法总结 简介 上一篇详细的介绍了如何使用Beautiful Soup的使用方法&#xff0c;但是最常用的还是如何解析html元素&#xff0c;这里再汇总介绍下查询…
阅读更多...
Sprint Boot 2 核心功能（一）

Sprint Boot 2 核心功能（一）

核心功能 1、配置文件 application.properties 同基础入门篇的application.properties用法一样 Spring Boot 2 入门基础 application.yaml&#xff08;或application.yml&#xff09; 基本语法 key: value&#xff1b;kv之间有空格大小写敏感使用缩进表示层级关系缩进不允…
阅读更多...
Doze和AppStandby白名单配置方法和说明

Doze和AppStandby白名单配置方法和说明

机制 配置路径 配置案例 说明 影响机制 调试命令 Doze /platform/frameworks/base /data/etc/platform.xml allow-in-power-save 【系统应用Doze白名单配置】 Doze\Job\AppStandby\Alarm\WakeLock\Sync 查看Doze白名单:adb shell dumpsys deviceidle 添加Doze白名单…
阅读更多...
系统服务综合实验

系统服务综合实验

实验需求&#xff1a; 现有主机 node01 和 node02&#xff0c;完成如下需求&#xff1a; 在 node01 主机上提供 DNS 和 WEB 服务dns 服务提供本实验所有主机名解析web服务提供 www.rhce.com 虚拟主机该虚拟主机的documentroot目录在 /nfs/rhce 目录该目录由 node02 主机提供的…
阅读更多...
Mocreak：一键自动化部署Microsoft Office，高效办公必备

Mocreak：一键自动化部署Microsoft Office，高效办公必备

Mocreak是一款用于自动化下载、安装和部署 Microsoft Office 的办公增强工具。这款软件完全免费、无GG、绿色、无毒&#xff0c;并且具备简约、高效和安全的特点。它支持一键快速下载、安装和部署最新版的 Microsoft Office 软件&#xff0c;并提供了一个简约且可自定义的图形界…
阅读更多...
xcode项目添加README.md文件并进行编辑

xcode项目添加README.md文件并进行编辑

想要给xcode项目添加README.md文件其实还是比较简单的&#xff0c;但是对于不熟悉xcode这个工具的人来讲&#xff0c;还是有些陌生&#xff0c;下面简单给大家讲一下流程。 选择“文件”>“新建”>“文件”&#xff0c;在其他&#xff08;滚动到工作表底部&#xff09;下…
阅读更多...
2022 RoboCom省赛题目解析

2022 RoboCom省赛题目解析

题目解析&#xff1a;这就是一题很简单的模拟&#xff0c;直接上代码&#xff1b; #include<iostream> using namespace std; const int N 10010; int arr[N]; int main() {int n , m;cin >> n >> m;int sum 0;int res 0;for(int i 0; i < n;i ) cin…
阅读更多...
【计算机组成原理 | 第一篇】计算机硬件的发展

【计算机组成原理 | 第一篇】计算机硬件的发展

前言&#xff1a; 在信息时代&#xff0c;计算机已经成为我们生活和工作中不可或缺的工具。它们以各种形态存在&#xff0c;从个人电脑到智能手机&#xff0c;再到庞大的数据中心&#xff0c;计算机的应用无处不在。然而&#xff0c;无论计算机的形态如何变化&#xff0c;它们的…
阅读更多...
最新文章

Copyright @ 2022~2023