C++模拟实现list:list、list类的初始化和尾插、list的迭代器的基本实现、list的完整实现、测试、整个list类等的介绍

文章目录

  • 前言
  • 一、list
  • 二、list类的初始化和尾插
  • 三、list的迭代器的基本实现
  • 四、list的完整实现
  • 五、测试
  • 六、整个list类
  • 总结


前言

C++模拟实现list:list、list类的初始化和尾插、list的迭代器的基本实现、list的完整实现、测试、整个list类等的介绍


一、list

list本质上是一个双向带头循环链表。
实现list类,需要节点类(clase list_node)、迭代器(class __list_iterator);
节点类(clase list_node): 定义每个节点的结构;
迭代器(class __list_iterator): 使用节点的指针封装出一个类,可以使用运算符重载的形式更好的访问链表;

二、list类的初始化和尾插

namespace hhb
{

	// 节点
	template <class T>
	struct list_node
	{
		list_node(const T& val = T())
			: _next(nullptr)
			, _prev(nullptr)
			, _val(val)
		{}

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


	// 链表
	 template<class T> 
	class list
	{
		typedef list_node<T> Node;
	public:
		list()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
		}

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

			newNode->_next = _head;
			newNode->_prev = tail;

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

	private:
		Node* _head;
	};
}

在这里插入图片描述

三、list的迭代器的基本实现

  • 使用链表节点的指针封装出一个类,是list链表的访问可以向vector一样使用++等操作访问
  • vector和list的使用,虽然在形式上一样,但是他们的底层是不一样的
  • (*)vector迭代器是对指针的解引用
  • (*)list迭代器是调用operator(解引用操作符)函数重载,本质是不一样的

对于const迭代器,是operator(*)和 operator(->)的运算符重载函数的返回值不一样,因此需要增加两个模板参数

  • 即: (T& 和 T*)
// 迭代器
template <class T, class Ref, class Ptr>
struct __list_iterator
{
	typedef list_node<T> Node;
	typedef __list_iterator<T, Ref, Ptr> self;
public:
	__list_iterator(Node* node)
		:_node(node)
	{}

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

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

	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& it) const
	{
		return _node != it._node;
	}
	bool operator==(const self& it) const
	{
		return _node == it._node;
	}

	Node* _node;
};
  • operator->运算符重载编译器会进行优化, 如下:
struct A
{
public:
	A(int a1 = 0, int a2 = 0)
		: _a1(a1)
		, _a2(a2)
	{}
	int _a1;
	int _a2;
};
void test_list02()
{
	hhb::list<A> lt;

	lt.push_back(A(1, 1));
	lt.push_back(A(2, 2));
	lt.push_back(A(3, 3));
	lt.push_back(A(4, 4));
	lt.push_back(A(5, 5));

	hhb::list<A>::iterator it = lt.begin();

	while (it != lt.end())
	{
		//cout << (*it)._a1 << " " << (*it)._a2 << " " << endl;
		cout << it->_a1 << " " << it->_a2 << " " << endl;
		// 此处编译器进行了优化, it->返回的是T* 也就是 A*, 如果要访问A的成员
		// 按道理来讲,应该是 (it->)->_a1 / (it->)->_a2 来进行访问
		++it;
	}
	cout << endl;

}

在这里插入图片描述

四、list的完整实现

  • list需要有size()的接口,所以需要对链表节点个数进行计数,增加一个成员变量_size.
  • 实现insert()和erase()接口后,push_back()和push_front()、pop_back()和pop_front()接口都可以复用接口。
  • clear()只清除(不包含哨兵位的头节点)数据,不销毁链表
  • 析构函数调用clear()后,释放_head节点(哨兵位的头节点)
  • 拷贝构造函数在拷贝之前,一定要先自己初始化(创建哨兵位的头节点)
  • 赋值(=)运算符重载使用现代写法,拷贝构造加交换函数加自动调用析构函数。
	// 链表
	 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 emptyInit()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;

			_size = 0;
		}


		list()
		{
			emptyInit();
		}

		list(const list<T>& lt)
		{
			emptyInit();

			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;

			_size = 0;
		}

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

			//newNode->_next = _head;
			//newNode->_prev = tail;

			//tail->_next = newNode;
			//_head->_prev = newNode;


			insert(end(), x);
		}

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

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

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

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

			newNode->_next = cur;
			newNode->_prev = prev;

			cur->_prev = newNode;
			prev->_next = newNode;

			++_size;
			return 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;
			cur = nullptr;

			--_size;

			return next;
		}

		//size_t size()
		//{
		//	int sz = 0;
		//	iterator it = begin();
		//	while (it != end())
		//	{
		//		sz++;
		//		++it;
		//	}
		//	
		//	return sz;
		//}

		size_t size()
		{
			return _size;
		}


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

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

五、测试

  • 测试push_back, pop_back可以顺便测试insert, erase函数, 所以不单独测试insert和erase函数
void test_list03()
{
	hhb::list<int> lt;

	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_front(5);
	lt.push_front(6);
	lt.push_front(7);
	lt.push_front(8);

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

	lt.pop_back();
	lt.pos_front();

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


	lt.clear();

	lt.push_back(10);
	lt.push_back(20);
	lt.push_back(30);
	lt.push_back(40);
	lt.push_back(50);


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

	cout << lt.size() << endl;


}

在这里插入图片描述

  • 测试拷贝构造和赋值运算符重载
void test_list04()
{
	hhb::list<int> lt;

	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);

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

	hhb::list<int> lt1(lt);

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

	hhb::list<int> lt2;
	lt2.push_back(10);
	lt2.push_back(20);
	lt2.push_back(30);
	lt2.push_back(40);

	lt1 = lt2;

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

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


}

在这里插入图片描述

六、整个list类

// list.h
#pragma once

#include <assert.h>
namespace hhb
{

	// 节点
	template <class T>
	struct list_node
	{
		list_node(const T& val = T())
			: _next(nullptr)
			, _prev(nullptr)
			, _val(val)
		{}

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

	// 迭代器
	template <class T, class Ref, class Ptr>
	struct __list_iterator
	{
		typedef list_node<T> Node;
		typedef __list_iterator<T, Ref, Ptr> self;
	public:
		__list_iterator(Node* node)
			:_node(node)
		{}

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

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

		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& it) const
		{
			return _node != it._node;
		}
		bool operator==(const self& it) const
		{
			return _node == it._node;
		}

		Node* _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 emptyInit()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;

			_size = 0;
		}


		list()
		{
			emptyInit();
		}

		list(const list<T>& lt)
		{
			emptyInit();

			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;

			_size = 0;
		}

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

			//newNode->_next = _head;
			//newNode->_prev = tail;

			//tail->_next = newNode;
			//_head->_prev = newNode;


			insert(end(), x);
		}

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

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

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

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

			newNode->_next = cur;
			newNode->_prev = prev;

			cur->_prev = newNode;
			prev->_next = newNode;

			++_size;
			return 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;
			cur = nullptr;

			--_size;

			return next;
		}

		//size_t size()
		//{
		//	int sz = 0;
		//	iterator it = begin();
		//	while (it != end())
		//	{
		//		sz++;
		//		++it;
		//	}
		//	
		//	return sz;
		//}

		size_t size()
		{
			return _size;
		}


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

			_size = 0;
		}
	
	private:
		Node* _head;
		size_t _size;
	};
}
  • 整个测试
#define  _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <list>
using namespace std;
#include "list.h"


void print1(const hhb::list<int>& lt)
{
	hhb::list<int>::const_iterator it = lt.begin();
	while (it != lt.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
}

void test_list01()
{
	hhb::list<int> lt;

	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(5);

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


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


	print1(lt);
}

struct A
{
public:
	A(int a1 = 0, int a2 = 0)
		: _a1(a1)
		, _a2(a2)
	{}
	int _a1;
	int _a2;
};



void test_list02()
{
	hhb::list<A> lt;

	lt.push_back(A(1, 1));
	lt.push_back(A(2, 2));
	lt.push_back(A(3, 3));
	lt.push_back(A(4, 4));
	lt.push_back(A(5, 5));

	hhb::list<A>::iterator it = lt.begin();

	while (it != lt.end())
	{
		//cout << (*it)._a1 << " " << (*it)._a2 << " " << endl;
		cout << it->_a1 << " " << it->_a2 << " " << endl;
		// 此处编译器进行了优化, it->返回的是T* 也就是 A*, 如果要访问A的成员
		// 按道理来讲,应该是 (it->)->_a1 / (it->)->_a2 来进行访问
		++it;
	}
	cout << endl;

}

void test_list03()
{
	hhb::list<int> lt;

	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_front(5);
	lt.push_front(6);
	lt.push_front(7);
	lt.push_front(8);

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

	lt.pop_back();
	lt.pos_front();

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


	lt.clear();

	lt.push_back(10);
	lt.push_back(20);
	lt.push_back(30);
	lt.push_back(40);
	lt.push_back(50);


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

	cout << lt.size() << endl;


}


void test_list04()
{
	hhb::list<int> lt;

	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);

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

	hhb::list<int> lt1(lt);

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

	hhb::list<int> lt2;
	lt2.push_back(10);
	lt2.push_back(20);
	lt2.push_back(30);
	lt2.push_back(40);

	lt1 = lt2;

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

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


}


int main()
{

	//test_list01();

	test_list02();

	//test_list03();

	//test_list04();

	return 0;
}

总结

C++模拟实现list:list、list类的初始化和尾插、list的迭代器的基本实现、list的完整实现、测试、整个list类等的介绍

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

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

相关文章

计算机网络34——Windows内存管理

1、计算机体系结构 2、内存管理 分为连续分配管理和非连续分配管理 在块内存在的未使用空间叫内部碎片&#xff0c;在块外存在的未使用空间叫外部碎片 固定分区分配可能出现内部碎片&#xff0c;动态分区分配可能出现外部碎片 3、逻辑地址和实际地址的互相转换 4、缺页中断 …

k8s中,pod生命周期,初始化容器,容器探针,事件处理函数,理解其设计思路及作用

k8s中&#xff0c;为什么要设计pod 平台直接管理容器不是挺好的吗 为什么要以pod为单位进行管理&#xff0c; 然后把容器放在pod里面 那么有pod和没pod的区别是什么 也就是pod提供了什么作用 这个可以考虑从pod生命周期管理的角度去思考 如图&#xff0c;pod主容器在运行…

JAVA并发编程系列(10)Condition条件队列-并发协作者

一线大厂面试真题&#xff0c;模拟消费者-生产者场景。 同样今天的分享&#xff0c;我们不纸上谈兵&#xff0c;也不空谈八股文。以实际面经、工作实战经验进行开题&#xff0c;然后再剖析核心源码原理。 按常见面经要求&#xff0c;生产者生产完指定数量产品后&#xff0c;才能…

文档矫正算法:DocTr++

文档弯曲矫正&#xff08;Document Image Rectification&#xff09;的主要作用是在图像处理领域中&#xff0c;对由于拍摄、扫描或打印过程中产生的弯曲、扭曲文档进行校正&#xff0c;使其恢复为平整、易读的形态。 一. 论文和代码 论文地址&#xff1a;https://arxiv.org/…

LDRA Testbed(TBrun)软件单元测试_常见问题及处理

系列文章目录 LDRA Testbed软件静态分析_操作指南 LDRA Testbed软件静态分析_自动提取静态分析数据生成文档 LDRA Testbed软件静态分析_Jenkins持续集成&#xff08;自动静态分析并用邮件自动发送分析结果&#xff09; LDRA Testbed软件静态分析_软件质量度量 LDRA Testbed软件…

POI操作EXCEL增加下拉框

文章目录 POI操作EXCEL增加下拉框 POI操作EXCEL增加下拉框 有时候通过excel将数据批量导入到系统&#xff0c;而业务操作人员对于一些列不想手动输入&#xff0c;而是采用下拉框的方式来进行选择 采用隐藏sheet页的方式来进行操作 String sheetName "supplier_hidden_s…

Python记录

1.冒泡排序 时间复杂度O&#xff08;n^2) 选择、插入都是 def bubble(data, reverse):for i in range(len(data)-1):for j in range(len(data)-i-1):if data[j] > data[j1]:data[j], data[j1] data[j1], data[j]if reverse:data.reverse()return data 2.快速排序 时间…

基于深度学习的文本情感原因提取研究综述——论文阅读

前言 既然要学习情感分析&#xff0c;那么肯定还要了解情感原因对抽取的发展历程&#xff0c;所以我又搜了一篇研究综述&#xff0c;虽然是2023年发表的&#xff0c;但是里面提及到的历程仅停留到2022年。这篇综述发布在TASLP期刊&#xff0c;是音频、声学、语言信号处理的顶级…

【Verilog学习日常】—牛客网刷题—Verilog快速入门—VL21

根据状态转移表实现时序电路 描述 某同步时序电路转换表如下&#xff0c;请使用D触发器和必要的逻辑门实现此同步时序电路&#xff0c;用Verilog语言描述。 电路的接口如下图所示。 输入描述&#xff1a; input A , input clk , …

结构设计模式 -装饰器设计模式 - JAVA

装饰器设计模式 一. 介绍二. 代码示例2.1 抽象构件&#xff08;Component&#xff09;角色2.2 具体构件&#xff08;Concrete Component&#xff09;角色2.3 装饰&#xff08;Decorator&#xff09;角色2.4 具体装饰&#xff08;Concrete Decorator&#xff09;角色2.5 测试 结…

【HTML5】html5开篇基础(1)

1.❤️❤️前言~&#x1f973;&#x1f389;&#x1f389;&#x1f389; Hello, Hello~ 亲爱的朋友们&#x1f44b;&#x1f44b;&#xff0c;这里是E绵绵呀✍️✍️。 如果你喜欢这篇文章&#xff0c;请别吝啬你的点赞❤️❤️和收藏&#x1f4d6;&#x1f4d6;。如果你对我的…

【优选算法之前缀和】No.6--- 经典前缀和算法

文章目录 前言一、前缀和例题模板&#xff1a;1.1 【模板】前缀和1.2 【模板】⼆维前缀和1.3 寻找数组的中⼼下标1.4 除⾃⾝以外数组的乘积1.5 和为 K 的⼦数组1.6 和可被 K 整除的⼦数组1.7 连续数组1.8 矩阵区域和 前言 &#x1f467;个人主页&#xff1a;小沈YO. &#x1f6…

Python酷玩之旅_mysql-connector

前言 Python作为数据科学、机器学习等领域的必选武器&#xff0c;备受各界人士的喜爱。当你面对不同类型、存储于各类介质的数据时&#xff0c;第一时间是不是要让它亮个相&#xff1f;做个统计&#xff0c;画个图表&#xff0c;搞个报表… 等等。 正如Java中的JdbcDriver一样…

亲测好用,ChatGPT 3.5/4.0新手使用手册,最好论文指令手册~

本以为遥遥领先的GPT早就普及了&#xff0c;但小伙伴寻找使用的热度一直高居不下&#xff0c;其实现在很简单了&#xff01; 国产大模型快200家了&#xff0c;还有很多成熟的国内AI产品&#xff0c;跟官网一样使用&#xff0c;还更加好用~ ① 3.5 大多数场景是够用的&#xff…

OpenCV特征检测(12)检测图像中的潜在角点函数preCornerDetect()的使用

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 计算用于角点检测的特征图。 该函数计算源图像的基于复杂空间导数的函数 dst ( D x src ) 2 ⋅ D y y src ( D y src ) 2 ⋅ D x x src − 2 …

【Linux】解锁管道通信和共享内存通信,探索进程间通信的海洋

目录 引言&#xff1a; 1、进程间通信基础介绍 1.1为什么需要在进程之间通信&#xff1f; 1.2进程间通信是什么&#xff1f; 1.3我们具体如何进行进程间的通信呢&#xff1f; a.一般规律&#xff1a; b.具体做法 2.管道 2.1什么是管道 2.2匿名管道&#xff1a; 创建…

Zotero进阶指南:7个插件让文献管理变得前所未有的简单

还在为海量文献管理头疼吗?还在为找不到合适的插件犯愁吗?别急,今天我就要带你解锁Zotero的终极武器 - 那些让你爱不释手的必备插件! 作为一个从小白到文献管理达人的过来人,我可以负责任地说:没有这些插件,你的Zotero只能发挥一半功力!安装了这些插件,你的效率绝对能飙升! …

计算机毕业设计之:基于微信小程序的电费缴费系统(源码+文档+讲解)

博主介绍&#xff1a; ✌我是阿龙&#xff0c;一名专注于Java技术领域的程序员&#xff0c;全网拥有10W粉丝。作为CSDN特邀作者、博客专家、新星计划导师&#xff0c;我在计算机毕业设计开发方面积累了丰富的经验。同时&#xff0c;我也是掘金、华为云、阿里云、InfoQ等平台…

关于LLC知识18(公式的理解)

公式中有三个未知数&#xff1a;x,k,Q 1、其中&#xff0c;x为归一化频率&#xff0c;开关频率f与谐振频率fr的比值&#xff1b; k&#xff1a;励磁电感和谐振电感的比值Lm/Lr Q&#xff1a;第一谐振频率点的感抗与Rac的比值2fL/Rac 2、KLm/Lr&#xff0c;其中fr11/2&#…

Qt/C++ 多线程同步机制详解及应用

在多线程编程中&#xff0c;线程之间共享资源可能会导致数据竞争和不一致的问题。因此&#xff0c;采用同步机制确保线程安全至关重要。在Qt/C中&#xff0c;常见的同步机制有&#xff1a;互斥锁&#xff08;QMutex、std::mutex&#xff09;、信号量&#xff08;QSemaphore&…