当前位置：主页 > 查看内容

C++ list类的模拟实现

发布时间：2021-06-09 00:00| 有位朋友查看

简介：list类和string与vector不一样list类的底层是通过双向带头循环链表属性定义由于是带头的链表为了方便使用我们定义两个类一个是单独结点的类一个是属性只有头结点用于存放结点的List类。 //单独结点类 template class T struct ListNode { T _data ; //结……

list类和string与vector不一样，list类的底层是通过双向带头循环链表

属性定义

由于是带头的链表，为了方便使用我们定义两个类，一个是单独结点的类，一个是属性只有头结点，用于存放结点的List类。

//单独结点类
template <class T>
struct ListNode
{
	T _data; //结点数据
	ListNode<T>* _next; //该结点的下一个结点
	ListNode<T>* _prev; //该结点的上一个结点

	//默认构造函数
	ListNode(const T& val = T())
		:_data(val)
		, _next(nullptr)
		, _prev(nullptr)
	{}
};

//只有头结点存放结点的List类
template <class T>
class List
{
public:
	typedef ListNode<T> Node;
private :
	Node* _header;
};

构造函数

构造函数存在多种，但是每个构造函数在构造前，都必须先构建它的基本结构，也就是保证该链表是一个双向带头循环链表
在这里插入图片描述

第一种：无参构造函数

	List()
		:_header(new Node())
	{
		//确立循环结构
		_header->_next = _header->_prev = _header;
	}

第二种：创建n个结点，值为val (利用到尾插，后面有实现)

	List(int n, const T& val = T())
		:_header(new Node())
	{
		_header->_next = _header->_prev = _header;
		for (size_t i = 0; i < n; ++i)
		{
			//尾插
			pushBack(val);
		}
	}

测试用例：
在这里插入图片描述
第三种：通过迭代器构造list (利用到尾插，后面有实现)
使用新的迭代器的原因是使传入的迭代器可以是任意类型的，如果使用List的迭代器，那么传入的迭代器的类型只能和List的类型一样，这里拿string举例，创建一个char类型的List，但是传入的迭代器并不是char类型的，可以是字符数组的迭代器或者是string的迭代器。只要通过解引用是char类型就可以
通过传进来的两个迭代器，只要迭代器不相等，就将第一个迭代器的值进行尾插，再++，直到两个迭代器相等

	template<class inputIterator>
	List(inputIterator first, inputIterator last)
		:_header(new Node())
	{
		_header->_next = _header->_prev = _header;
		while (first != last)
		{
			pushBack(*first);
			++first;
		}
	}

测试用例：
在这里插入图片描述

pushBack()

按照一定顺序改变各结点的指向

最后一个节点的next等于新的结点
新的结点的prev等于最后一个节点
新的结点的next等于头结点
头结点的prev等于新的结点

	void pushBack(const T& val)
	{
		Node* tail = _header->_prev;//最后一个节点
		Node* newNode = new Node(val); //新结点

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

		newNode->_next = _header;
		_header->_prev = newNode;
	}

测试用例：
在这里插入图片描述

clean()

clean()的实现其实就是销毁链表，由于是带头的链表，我们不能和不带头的链表一样，利用判空条件去结束销毁。应该定义一个头结点的下一个结点cur，先保存cur结点的下一个结点next，再释放和置空cur，再更新cur为next，如此循环，直到cur为头结点

void clear()
	{
		if (_header != nullptr)
		{
			Node* cur = _header->_next;
			while (cur != _header)
			{
				Node* next = cur->_next;
				delete[] cur;
				cur = nullptr;
				cur = next;
			}
		}
	}

析构函数

先将头结点之外的所有结点都删除掉，最后再单独删除头结点。可以复用clear函数

~List()
	{
		clear();
		delete _header;
		_header = nullptr;
	}

size()

定义一个计数器，然后从头结点的下一个结点开始遍历，每遍历一个节点计数器就+1。当遇到头结点就结束遍历，返回计数器

	size_t size()const
	{
		int sz = 0;
		Node* cur = _header->_next;
		while (cur != _header)
		{
			++sz;
			cur = cur->_next;
		}
		return sz;
	}

list迭代器的实现

list底层是一个链表，底层并不像vector一样是通过原生态指针来实现的。如果是指针，对迭代器的++也就是地址的偏移。偏移量为list对象的大小，但是list底层是链表实现，也就是说在物理地址上并非是连续存储的，只是在逻辑上是连续的。偏移就并非能偏移到指定的位置，所以list的迭代器不能通过指针来实现。可不可以是结点指针类型的呢？假设它是结点指针类型的迭代器，通过++操作也并非能指向下一个节点，通过*操作也只是获得该结点，但是该结点的属性有好几个，并不能通过解引用来获得该结点的数据。

我们可以归纳一下，通过迭代器的操作，我们链表底层的实际操作对应的应该是哪些操作
迭代器的解引用* ---- node->data
迭代器的++ ---- node->next
所以我们只能通过对结点的封装才能实现该操作，也就是用自定义类型来封装结点。但是自定义类型也并不支持解引用和++的操作，那我们就必须在类内重载运算符，实现我们实际的操作。操作我们封装的结点，就是操作我们list中链表的结点。为了方便遍历，我们再重载一个!=的实现.

template<class T>
struct ListIterator
{
	//结点
	typedef ListNode<T> Node;
	typedef ListIterator<T> Self;
	Node* _node;
	
	//构造函数
	ListIterator(Node* node = nullptr)
		: _node(node)
	{}
	
	//重载*，返回的是该结点的数据
	T& operator*()
	{
		return _node->_data;
	}
	
	//重载前置++，返回的是该结点的下一个结点
	Self& operator++()
	{
		_node = _node->_next;
		return *this;
	}
	
	//两个节点的地址不同，就是不相同的结点
	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}
};

在List类中，应该要提供begin()和end()函数，它们的返回值应该就是本身的迭代器类型

typedef ListIterator<T> iterator;
	iterator begin()
	{
		//封装第一个结点
		return iterator(_header->_next);
	}

	iterator end()
	{
		//封装最后一个结点的下一个结点，也就是头结点
		return iterator(_header);
	}

测试结果：
在这里插入图片描述
接下来补全迭代器的基本操作

template<class T>
struct ListIterator
{
	typedef ListNode<T> Node;
	typedef ListIterator<T> Self;
	Node* _node;

	ListIterator(Node* node = nullptr)
		: _node(node)
	{}
	Self& operator++()
	{
		_node = _node->_next;
		return *this;
	}

	Self operator++(int)
	{
		Self tmp(_node);
		_node = _node->_next;
		return tmp;
	}

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

	T& operator*()
	{
		return _node->_data;
	}

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

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

以上的操作支持内置类型的基本操作，但是并不能满足当结点存储的内置类型的操作，当对对象解引用时，是返回的结点的_data，但是这个_data是一个对象，也就并非能得到内置类型的值。*it得到的是对象，再通过.来获得对象的属性值。

struct A
{
	int _a;
	A(int a = 0)
		:_a(a)
	{}
};

在这里插入图片描述
但是该操作并不方便，通过解引用再获取对象值。在STL库中的迭代器可以直接通过->_a来获取，迭代器是一个对象，怎么可以通过->来获取自定义类型的属性呢？我们就必须重载->来实现。就是it->获得自定义类型对象的地址，再通过->就可以获得自定义类型对象的指定的值it->->_a
只是在C++会进行优化，省略了其中的一个->。
一下是实现第一个->的代码

	//场景：T为自定义类型，且包含多个成员
	//it->T*->指定成员
	//it->指定成员 来访问成员变量
	T* operator->()
	{
		//返回自定义类型对象的地址
		return &(_node->_data);
	}

测试结果：
在这里插入图片描述
满足了内置类型和自定义类型的迭代器，我们就可以使用范围for来遍历list。

我们已经能够正常实现可读可写的迭代器了，现在我们来实现只能读的迭代器const_iterator。我们能不能按照之前迭代器的实现，在迭代器前加const关键字呢？我们在迭代器类中添加const的接口，但是添加const后的成员函数是不能改变成员变量的值，而++操作就涉及到了成员变量的改变_node=_node->next

//const修饰后不能改变当前类的成员
Self& operator++() const
{
	_node = _node ->next;//error
	return *this;
}

这样子的方法行不通，我们只能再创建一个自定义类型，专门处理只读迭代器的操作。能通过迭代器获取到对象的值只有两个成员函数，一个是解引用*操作，一个是->操作。所以我们在新的类中将这两个成员函数的返回值设置为const就可以了。其他代码不变。

template<class T>
struct ConstListIterator
{
	typedef ListNode<T> Node;
	typedef ConstListIterator<T> Self;
	Node* _node;

	ConstListIterator(Node* node = nullptr)
		: _node(node)
	{}

	ConstListIterator(const Self& s)
		: _node(s._node)
	{}

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

	Self operator++(int)
	{
		Self tmp(_node);
		_node = _node->_next;
		return tmp;
	}

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

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

	//返回值不能修改
	const T& operator*()
	{
		return _node->_data;
	}
	
	//返回值不能修改
	const T* operator->()
	{
		return &(_node->_data);
	}

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

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

List类中const迭代器代码：

typedef ConstListIterator<T> const_iterator;

	const_iterator cbegin() const
	{
		return const_iterator(_header->_next);
	}

	const_iterator cend() const
	{
		return const_iterator(_header);
	}

测试结果：
在这里插入图片描述

但是STL库中实现并不是这样子的，我们发现两个迭代器类型只是类中两个成员函数的返回值不一样而已。其他代码逻辑都是一样的，所以我们可以通过多加两个模板类型来解决这个问题，让他们成为一个类，只是类型有所差别。在原来的迭代器中将模板改为template<class T, class Ref, class Ptr> T为普通类型，Ref为引用类型，Ptr为指针类型。

	//Self别名中的类型也要对应起来
	typedef ListIterator<T, Ref, Ptr> Self;
	//const T& operator*()
	Ref operator*()
	{
		return _node->_data;
	}
	
	//const T* operator->()
	Ptr operator->()
	{
		return &(_node->_data);
	}

这时候在List中将只读迭代器的泛型类型都修饰成const，此时就返回的类型就都是带有const的了。调用只读迭代器，编译器会通过类型推出该类型为只读，不能修改

typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&, const T*> const_iterator;

erase()

获取pos迭代器的结点，保存该结点的下一个结点next和上一个结点prev
将这两个结点收尾相接
释放pos位置上的结点
返回next结点封装后的迭代器

	iterator erase(iterator pos)
	{
		if (pos != end())
		{
			Node* next = pos._node->_next;
			Node* prev = pos._node->_prev;

			prev->_next = next;
			next->_prev = prev;
			delete[] pos._node;
			return iterator(next);
		}
		return pos;
	}

测试结果：
在这里插入图片描述

insert()

创建一个值为v的结点newNode
获取当前位置pos的前一个节点prev
最后首尾相连即可

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

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

pushFront()

第一个结点前插入新的结点

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

popBack()

删除最后一个节点，end()指向的是头结点，–end()

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

popFront()

删掉第一个结点

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

拷贝构造函数

利用现代写法，利用构造函数创建一个临时对象tmp，

List(List<T>& l)
		:_header(new Node())
	{
		_header->_next = _header->_prev = _header;
		List<T> tmp(l.begin(), l.end());
		swap(tmp);
	}
	//交换两个对象的头结点
	void swap(List<T>& l)
	{
		Node* tmp = l._header;
		l._header = this->_header;
		this->_header = tmp;
	}

赋值运算符重载

利用了拷贝构造函数创建新空间，然后再交换他们的头结点，tmp离开函数就会自动释放了

	List<T>& operator=(List<T> tmp)
	{
		swap(tmp);
		return *this;
	}

运行结果：
在这里插入图片描述
整个List实现

template <class T>
struct ListNode
{
	T _data;
	ListNode<T>* _next;
	ListNode<T>* _prev;

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

template<class T, class Ref, class Ptr>
struct ListIterator
{
	typedef ListNode<T> Node;
	typedef ListIterator<T, Ref, Ptr> Self;
	Node* _node;

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

	ListIterator(const Self& s)
		: _node(s._node)
	{}

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

	Self operator++(int)
	{
		Self tmp(_node);
		_node = _node->_next;
		return tmp;
	}

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

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

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

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

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

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


template <class T>
class List
{
public:
	typedef ListNode<T> Node;
	typedef ListIterator<T, T&, T*> iterator;
	typedef ListIterator<T, const T&, const T*> const_iterator;

	iterator begin()
	{
		return iterator(_header->_next);
	}

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

	const_iterator cbegin() const
	{
		return const_iterator(_header->_next);
	}

	const_iterator cend() const
	{
		return const_iterator(_header);
	}

	List()
		:_header(new Node())
	{
		//循环结构
		_header->_next = _header->_prev = _header;
	}

	List(int n, const T& val = T())
		:_header(new Node())
	{
		_header->_next = _header->_prev = _header;
		for (size_t i = 0; i < n; ++i)
		{
			pushBack(val);
		}
	}

	template<class inputIterator>
	List(inputIterator first, inputIterator last)
		:_header(new Node())
	{
		_header->_next = _header->_prev = _header;
		while (first != last)
		{
			pushBack(*first);
			++first;
		}
	}

	List(List<T>& l)
		:_header(new Node())
	{
		_header->_next = _header->_prev = _header;
		List<T> tmp(l.begin(), l.end());
		swap(tmp);
	}

	List<T>& operator=(List<T> tmp)
	{
		swap(tmp);
		return *this;
	}

	void swap(List<T>& l)
	{
		Node* tmp = l._header;
		l._header = this->_header;
		this->_header = tmp;
	}

	void pushBack(const T& val)
	{
		/*Node* tail = _header->_prev;
		Node* newNode = new Node(val);

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

		newNode->_next = _header;
		_header->_prev = newNode;*/
		insert(end(), val);
	}

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

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

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

	T& font()
	{
		return _header->_next->_data;
	}

	const T& font()const 
	{
		return _header->_next->_data;
	}

	T& back()
	{
		return _header->_prev->_data;
	}

	const T& back()const
	{
		return _header->_prev->_data;
	}

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

	size_t size()const
	{
		int sz = 0;
		Node* cur = _header->_next;
		while (cur != _header)
		{
			++sz;
			cur = cur->_next;
		}
		return sz;
	}

	iterator erase(iterator pos)
	{
		if (pos != end())
		{
			Node* next = pos._node->_next;
			Node* prev = pos._node->_prev;

			prev->_next = next;
			next->_prev = prev;
			delete[] pos._node;
			return iterator(next);
		}
		return pos;
	}

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

	void clear()
	{
		if (_header != nullptr)
		{
			Node* cur = _header->_next;
			while (cur != _header)
			{
				Node* next = cur->_next;
				delete[] cur;
				cur = nullptr;
				cur = next;
			}
		}
	}

	~List()
	{
		clear();
		delete _header;
		_header = nullptr;
	}

private :
	Node* _header;
};

；原文链接：https://blog.csdn.net/qq_44443986/article/details/115431846
本站部分内容转载于网络，版权归原作者所有，转载之目的在于传播更多优秀技术内容，如有侵权请联系QQ/微信：153890879删除，谢谢！

上一篇：【排序算法】之lowb三人组（冒泡、插入、选择） 下一篇：没有了

随机推荐

QQ空间经典说说：太勉强自己的话，总有一

1．很多事情当你再回忆时会发现其实没什么。所以，不管当时你多么生气都告诉自己...
浅析Linux进程的内存管理

本文转载自微信公众号「人人都是极客」，作者布道师Peter。转载本文请联系人人都...
CNN特征提取结果可视化——hooks简单应用

本文代码地址https://github.com/njulhy/funny_code/blob/main/cnn_feature_visu...
Windows 10隐藏功能：不用任何软件就可实

投屏工具我也介绍了不少，所有的都是需要安装第三方软件的。不过，其实 Windows...
为什么我们要从MySQL迁移到TiDB？

【51CTO.com原创稿件】当一张百亿数据量的表放在你面前，你将面临着什么?加列?哭...
抛弃床的温暖，只为了它丨云库一款跑在鸿

想了解更多内容，请访问： 51CTO和华为官方战略合作共建的鸿蒙技术社区 https://...
一文统计IPFS凭什么这么硬气

1、阿里巴巴云布局IPFS 2、华为砸4亿布局IPFS 3、京东弯道超车布局IPFS 4、微软...
上手Pandas，带你玩转数据（4）-- 数据清

文章目录描述性方法注汇总数据 pandas处理文本数据检查缺失值判断行列中是...
Deepin20安装开发环境的超详细教程

Deepin安装开发环境系统环境配置挂载分区 1、挂载分区（需要先卸载分区）： de...
Canvas动画案例演示，含动画猫、变幻线、

Canvas动画案例演示含动画猫、变幻线、代码雨等内容介绍一、查看地址二、二维...

C++ list类的模拟实现

属性定义

构造函数

pushBack()

clean()

析构函数

size()

list迭代器的实现

erase()

insert()

pushFront()

popBack()

popFront()

拷贝构造函数

赋值运算符重载

推荐图文

如何让npm install速度更快

Discuz!NT 论坛整合ASP程序论坛教程

优秀官配：世界上人们很喜欢的数据库+很喜欢的语言

vue实现图书管理系统

Linux常用命令详解 xfs文件系统的备份与还原 xf

HTML里面Textarea换行问题总结

随机推荐

QQ空间经典说说：太勉强自己的话，总有一

浅析Linux进程的内存管理

CNN特征提取结果可视化——hooks简单应用

Windows 10隐藏功能：不用任何软件就可实

为什么我们要从MySQL迁移到TiDB？

抛弃床的温暖，只为了它丨云库一款跑在鸿

一文统计IPFS凭什么这么硬气

上手Pandas，带你玩转数据（4）-- 数据清

Deepin20安装开发环境的超详细教程

Canvas动画案例演示，含动画猫、变幻线、

关于我们