资讯专栏INFORMATION COLUMN

C++list类模拟实现

894974231 / 1756人阅读

摘要:类模拟实现类的基本结构结点类成员变量成员函数迭代器类成员函数解引用运算符重载箭头运算符重载迭代器前置迭代器后置迭代器的比较链表类成员变量成员函数构造函数拷贝构造赋值重载析构函数其他小型接口类的基本结构中是一个双向带头循环链表。

list类的基本结构

xxxxSTL中list是一个双向带头循环链表。除了头结点不存储有效信息外,其余node结点存储有效信息。同时,为了防止代码冗余,对于存储信息类型不同的问题,将采用模板的方式解决。
xxxxlist需要创建3个类:结点类、迭代器类和链表类。

结点类

成员变量

xxxx就像C语言中链表的创建,C++的链表也需要构建一个类(类似于C的结构体)包含节点中数据信息、下一节点地址和上一节点的地址三部分信息。
结点类成员变量如下:

template<class T>struct _list_node_{	T _val;					//存储数据	_list_node_<T>* _next;	_list_node_<T>* _prev;};

成员函数

xxxx分析我们需要写的成员函数:发现只有构造函数需要写,因为在new新的结点时,会自动调用它的构造函数,如果不写就会产生随机值。但是结点不会拷贝构造,不会赋值。并且节点的释放是list控制。所以不需要写拷贝构造、赋值运算法重载和析构函数。
结点类完整代码如下:

解释:由于结点类的成员变量需要被其他类直接访问,所以要将成员变量设置成公有,所以直接用struct(默认内容为公有public)。下面迭代器类同理

迭代器类

xxxx不同于string、vector两种容器,list的迭代器并不是原生的指针,而是封装结点指针成了一个类。
迭代器类代码如下:

	template<class T, class Ref, class Ptr>	struct _list_iterator_					//迭代器就是需要浅拷贝,不需要重新写拷贝构造或者复制	{										//析构函数:迭代器只是存一下指针,指针指向的结点由链表管理,不需要迭代器去释放空间		typedef _list_node_<T> node;		typedef _list_iterator_<T, Ref, Ptr> self;		_list_iterator_(node* pnode = nullptr)			:_pnode(pnode)		{}		Ref operator*()				//不加引用就是返回一个临时变量,不可更改具有常属性		{			return _pnode->_val;		}		Ptr operator->()		{			return &_pnode->_val;				//it->->_year   it->获得T*,T*->获得T类中的内容		}		bool operator==(const self& s) const		{			return _pnode == s._pnode;		}		bool operator!=(const self& s) const		{			return _pnode != s._pnode;			}		self& operator++()		{			_pnode = _pnode->_next;			return *this;		}		self operator++(int)			//返回的是临时对象,所以不返回引用		{			self tmp(*this);			_pnode = _pnode->_next;			return tmp;		}		self& operator--()		{			_pnode = _pnode->_prev;			return *this;		}		self operator--(int)			//返回的是临时对象,所以不返回引用		{			self tmp(*this);			_pnode = _pnode->_prev;			return tmp;		}		//成员变量		node* _pnode;	};

xxxx问题一:为什么要这样做呢?因为由于list并不是序列型容器,而是一个一个结点通过地址连接起来的。而为了保证所有容器迭代器使用方法的统一性,都要有对迭代器++/–/*等操作。++/–会直接访问上一个结点或者下一个结点的数据;解引用操作则会直接访问当前结点存储的数据。如果我们使用原生指针(结点的指针),则无法达到迭代器所要求的结果。因此,我们需要将结点的指针包装成类,通过运算符重载改变它的行为。达到这样的目的。
xxxx问题二:为什么迭代器类不写拷贝构造、赋值重载和析构函数呢?因为迭代器在拷贝构造和赋值的时候,就是希望做到浅拷贝,就是将值进行拷贝,让他们指向同一块空间,而不是将指向的内容进行深拷贝。因此编译器自动生成的浅拷贝就够了。其次,由于迭代器并没有自己开辟空间,因此无空间的释放,所以不需要析构函数。结点的释放是链表的任务
xxxx问题三:迭代器的模板中,为何需要三个模板参数?三个模板参数分别代表什么意思?。我们都知道,list的迭代器不同于string和vector的原生指针类型的迭代器,他是一个类。对于原生指针来说。被const修饰和不被const修饰的两种指针就是两种类型。因此对于正常的思维来说,迭代器就应该实现成两种类,一个是iterator,一个是const_iterator,两种分开写。因为如果还是想string、vector一样单纯把const和非const两种迭代器看作一种,在list类里typedef成const和非const类型的迭代器。这样就会导致const无效,还是可以更改内容。因为,迭代器仍然是非const,你只是把迭代器的类型名改成了const_iterator,并没有改变迭代器的实质。所以当调用解引用的操作符重载时,还是会返回T&,还是可以更改。所以第一种解决方法就是将iterator和const_iterator两种迭代器类型分成两个类来写,这样const修饰的链表就会去调用const_iterator的类,非const链表就会调用iterator的类。但是这样就会造成大量代码的冗余。
xxxx于是,就出现了利用模板的方法,来区分两种迭代器。
xxxx第一个参数模板class T:代表的是数据的类型。
xxxx第二个参数模板class Ref:代表的是结点中数据的引用。
xxxx第三个参数模板class Ptr:代表的是结点中数据的指针。
具体如下图:

如果还是有不理解可以通过下面成员函数的解析再次加深理解。

成员函数

1、解引用运算符重载

Ref operator*()				//不加引用就是返回一个临时变量,不可更改具有常属性{	return _pnode->_val;}

xxxx对于string、vector迭代器是原生指针的容器来说。他们的迭代器就是数据的地址,因此解引用可以直接拿到数据。而list并不是,所以需要运算符重载来改变它的行为。可以通过对迭代器解引用直接获取数据。所以return _pnode->val
xxxx同时,对于返回值,我们需要返回的是一个引用,否则,返回的就是一个临时变量,具有常属性,不可改变。并且,如果迭代器是const_iterator所以它的Ref就是const T&就不能对数据进行写,只能读。const类型迭代器返回的是T&,就可读可写了。

2、箭头运算符重载

Ptr operator->(){	return &_pnode->val;}

xxxx若迭代器为原生指针,则it->就可以直接获取it的内容,但是list的迭代器不可以,所以就需要运算符重载改变行为。
xxxx值得注意的是

3、迭代器前置++

typedef _list_iterator_<class T, class Ref, class Ptr> selfself& operator++(){	_pnode = _pnode->_next;	return *this;}

xxxxself是一个类型,返回的就是迭代器自己。self是typedef出来的。前置–类似就是将_next换成_prev。

4、迭代器后置++

self operator++(int){	self tmp(*this);	_pnode = _pnode->_next;	return tmp;}

xxxx因为返回的是tmp,是临时变量,所以不能返回引用。因为返回的值是改变之前的值,所以要报错原来的值,返回再将*this改变。后置–类似,就是将_next换成_prev。

5、迭代器的比较

xxxx迭代器的比较比较简单,所以就不细说了。

链表类

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;	list()	{		_head = (node*)malloc(sizeof(node));		_head->_next = _head;		_head->_prev = _head;	}	list(const list<T>& lt)	{		_head = new node;		_head->_next = _head;		_head->_prev = _head;		for (const T& e:lt)		{			push_back(e);		}	}			list<T>& operator=(list<T> lt)		//现代写法	{		swap(_head, lt._head);		return *this;	}	~list()	{		clear();		delete _head;		_head = nullptr;	}				void clear()	{		iterator it = begin();		while (it != end())		{			it = erase(it);		}	}	iterator begin()	{		return _head->_next;	}	const_iterator begin() const	{		return _head->_next;	}	iterator end()	{		return _head;	}	const_iterator end() const	{		return _head;	}	void push_back(const T& x)	{		node* tail = _head->_prev;		node* newnode = new node(x);		//调用node的构造函数		tail->_next = newnode;		newnode->_next = _head;		_head->_prev = newnode;		newnode->_prev = tail;	}	void insert(iterator pos, const T& x)	{		assert(pos._pnode);		node* cur = pos._pnode;		node* prev = cur->_prev;		node* newnode = new node(x);		prev->_next = newnode;		newnode->_next = cur;		cur->_prev = newnode;		newnode->_prev = prev;	}	iterator erase(iterator pos)	{		assert(pos._pnode);		assert(pos != end());		node* prev = pos._pnode->_prev;		node* next = pos._pnode->_next;		delete pos._pnode;				prev->_next = next;		next->_prev = prev;		return iterator(next);	}	size_t size()	{		size_t sz = 0;		iterator it = begin();		while (it != end())		{			it++;			sz++;		}		return sz;	}	bool empty()	{		return begin() == end();	}private:	node* _head;};

成员变量

xxxx成员变量就是一个头结点。同时还需要typedef出结点、const_iterator和iterator

成员函数

1、构造函数

list(){	_head = (node*)malloc(sizeof(node));	_head->_next = _head;	_head->_prev = _head;}

xxxx注意_head需要使用malloc来开辟空间,因为头结点不需要存储数据,所以不需要初始化。如果用new的话存在一个问题,就是如果出现数据类型T也是list,那么用new开辟头结点空间时,就会自动迪调用构造函数初始化,初始化就要调用构造函数,调用构造函数就要new并且初始化,就会出现一个无限循环。所以就需要malloc来开辟空间。
xxxx对于空链表来说,应该是头结点的next和prev都指向自己。

2、拷贝构造

list(const list<T>& lt){	_head = (node*)malloc(sizeof(node));	_head->_next = _head;	_head->_prev = _head;	for(const auto& e : lt)	{		push_back(e);	}}

xxxx可以复用代码,使用push_back。但是push_back之前,必须是规范的空链表,必须初始化。

3、赋值重载

list<T>& operator=(const list<T> lt){	swap(_head, lt._head);	return *this;}

xxxx这是一种现代写法,很简单,先利用拷贝构造,构造出一个完全相同的,这样把*this的_head与拷贝构造出来的_head一换,这样就直接把拷贝构造出来的内容的给了this

4、析构函数

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

xxxx同样的道理,也是复用,先用clear,将链表置空(所有的结点都被释放掉),然后再释放掉头结点。

5、clear

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

xxxx挨个释放所有结点就是复用erase,同时,因为释放结点后,就无法找到该结点后的结点,所以it要接受erase的返回值(即:被释放结点后结点的迭代器)

6、begin()、end()

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

7、insert

void insert(iterator pos, const T&x){	assert(pos._pnode);	node* cur = pos._pnode;	node* prev = cur->_prev;	node* newnode = new node(x);	prev->_next = newnode;	newnode->_next = cur;	cur->_prev = newnode;	newnode->_prev = prev;}

xxxxprev、cur、next三个结点的链接关系搞清楚即可,由于是带头双向循环,所以,不需要考虑结点之间连接的顺序,也不需要考虑多种情况。需要考虑的就是pos除是否为空,空的位置不能操作,断言一下。提高安全性。

8、erase

iterator erase(iterator pos){	assert(pos._pnode);	assert(pos != end());	node* prev = pos._pnode->_prev;	node* next = pos._pnode->_next;	delete pos._pnode;	prev->_next = next;	next->_prev = prev;	return iterator(next);}

xxxx删除后,为了防止迭代器失效,所以要把下一位置的的迭代器当做返回值返回。这是STL中容器的普遍做法。

其他小型接口

xxxx其余的接口都比较比较简单,直接看代码就能明白,代码在上面的list类完整版部分。

xxxx
xxxx
xxxx
xxxx
xxxx如果读者还有任何疑问,可以评论留言,或者私信我,我们一起探讨,一起进步

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/118802.html

相关文章

  • [C/C++ -STL]list模拟实现list迭代器底层刨析

    摘要:对类采用三个模板来实现迭代器。楷体类中和模板定义分别对应迭代器中模板定义的楷体采用向上传值的方式,传入不同值来采用不同迭代器。首先是迭代器的,分为前置和后置。迭代器的和都是获取迭代器所对应的值。唯一的差别就是就是用到了迭代器。 ...

    不知名网友 评论0 收藏0
  • 1、Map接口 2、模拟斗地主洗牌发牌

    摘要:中的集合称为单列集合,中的集合称为双列集合。洗牌通过数字完成洗牌发牌发牌将每个人以及底牌设计为将最后张牌直接存放于底牌,剩余牌通过对取模依次发牌。存放的过程中要求数字大小与斗地主规则的大小对应。 01Map集合概述 A:Map集合概述: 我们通过查看Map接口描述,发现Map接口下的集合与Collection接口下的集合,它们存储数据的形式不同  a:Collection中的集...

    付伦 评论0 收藏0
  • Java编程基础17——集合(List集合)

    1_(去除ArrayList中重复字符串元素方式)* A:案例演示 需求:ArrayList去除集合中字符串的重复值(字符串的内容相同) 思路:创建新集合方式 import java.util.ArrayList; import java.util.Iterator; public class ArrayList_1_demo { /* 创建新集合将重复元素去掉 * 1.明...

    scola666 评论0 收藏0
  • 模拟可取消任务的股票交易处理程序(百万订单)(FutureTask

    摘要:并且线程可被中断,那么在订单处理过程中接收的取消请求会结束剩余的处理流程。演示可取消任务的股票交易处理程序交易订单创建数量为的线程池来执行订单。邪恶线程邪恶线程,随机的取消某些订单。判断是否取消成功,在每两个请求之间让邪恶线程睡一会。 FutureTask类 重点是那个股票交易处理程序的例子,认真看三遍。本文花了三个小时。 GitHub代码欢迎star。 小白认为学习语言最好的方式就是...

    TigerChain 评论0 收藏0
  • [C/C++]详解STL容器3--list的功能和模拟实现(迭代器失效问题)

    摘要:本文介绍了的常用接口的使用,并对其进行了模拟实现,包括迭代器的实现。与为反向迭代器,对迭代器执行操作,迭代器向前移动。 本文介绍了list的常用接口的使用,并对其进行了模拟实现,包括list迭代器的实现。 目录 一、list的介绍 二、list的常用接口的使用 1. list的构造 2. l...

    amc 评论0 收藏0

发表评论

0条评论

894974231

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<