C++——list类及其模拟实现

这篇具有很好参考价值的文章主要介绍了C++——list类及其模拟实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

前言:这篇文章我们继续进行C++容器类的分享——list也就是数据结构中的链表,而且是带头双向循环链表


一.基本框架

namespace Mylist
{
	template<class T>
	//定义节点
	struct ListNode
	{
		ListNode<T>* _next;
		ListNode<T>* _prev;
		T _data;

		ListNode(const <T>& x = T())
			:_next(nullptr)	
			,_prev(nullptr)
			,_data(x)
		{}
	};
	template<class T>
	class list
	{
		typedef ListNode<T> Node;
	public:
		//构造函数
		list()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
		}
		//析构函数
		~list()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
			delete _head;
			_head = nullptr;
		}
		//数据个数
		size_t size()
		{
			iterator it = begin();
			size_t Size = 0;
			while (it != end())
			{
				Size++;
				it++;
			}
			return Size;
		}
	private:
		Node* _head;
	};
}

由于要满足存储任意类型的数据,所以我们必须要使用模版来进行定义。 


迭代器

关于list类中的最难之处,就是迭代器了。

因为迭代器的原理即为指针,对于string和vector这种创建的对象的物理空间是连续的类来说,我们可以直接对迭代器进行“++”、“--”等数学运算

而对于本质为链表的list来说,由于每个节点的物理空间都是随机创建,各个节点的地址并不连续,所以我们没法直接进行迭代器的数学运算,而需要对迭代器的各种功能进行重新定义,所以我们创建一个专门为迭代器服务的类

	//迭代器
	template<class T>
	struct ListIterator
	{
		typedef ListNode<T> Node;
		typedef ListIterator<T> Self;

		ListIterator(Node* node)
			:_node(node)
		{}
		//解引用
		T& operator*()
		{
			return _node->_data;
		}
		//前置++
		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)
		{
			return _node != it._node;
		}
		//相等
		bool operator==(const Self& it)
		{
			return _node == it._node;
		}
		Node* _node;
	};

随后在list类中将该类名重定义为iterator,便可正常使用迭代器了

		typedef ListIterator<T> iterator;
		iterator begin()
		{
			return _head->_next;
		}
		iterator end()
		{
			return _head;
		}

 这里值得注意的是,因为是带头双向循环链表,所以链表的开始即哨兵位的下一个,而结尾就是哨兵位


但是现在的迭代器是存在问题的,它并不能实现对const修饰的数据的操作,所以我们还需要一个const迭代器。因为我们的普通迭代器就是用模版来实现的,所以这里可以直接通过模版来实现const迭代器

	//迭代器
	template<class T,class Ref>
	struct ListIterator
	{
		typedef ListNode<T> Node;
		typedef ListIterator<T,Ref> Self;
		//构造函数
		ListIterator(Node* node)
			:_node(node)
		{}
		//解引用
		Ref operator*()
		{
			return _node->_data;
		}
		//前置++
		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)
		{
			return _node != it._node;
		}
		//相等
		bool operator==(const Self& it)
		{
			return _node == it._node;
		}
		Node* _node;
	};
		typedef ListIterator<T,T&> iterator;
		typedef ListIterator<T,const T&> const_iterator;

这里有一个细节,因为T同时还要服务于Node类,所以不能直接对其进行修改,而是另用一个模版参数。 

 因为const对象与非const对象最大的不同之处在于对数据的访问,所以定义一个名为Ref(引用)的模版参数,来对解引用运算符重载函数进行改造


二.常用操作

1.插入

先来看任意位置的插入需要传入某个位置的指针pos

		//pos前插入
		void insert(iterator pos, const T& val)
		{
			Node* cur = pos._node;
			Node* newnode = new Node(val);
			Node* prev = cur->_prev;

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

 现在对于我们来说就是非常简单,测试如下:

C++——list类及其模拟实现,c++,list,开发语言

这里有一个小细节,如果我们插入的位置是第一个节点之前,由于it迭代器的指向并未改变,所以如果进行遍历,他就不会遍历出我们新插入的数据,所以需要更新一下it。


有了pos位置的插入之后,就可以用它来扩展头插和尾插

		//尾插
		void push_back(const T& x)
		{
			insert(end(), x);
		}
		//头插
		void push_front(const T& x)
		{
			insert(begin, x);
		}

2.删除

我们同样先写出pos位置的删除

		//pos删除
		iterator erase(iterator pos)
		{
			Node* cur = pos._node;
			Node* next = cur->_next;
			Node* prev = cur->_prev;

			next->_prev = prev;
			prev->_next = next;
			delete cur;
			return iterator(next);
		}

由于删除会导致迭代器成为野指针,所以我们要对其进行更新, 测试如下:

C++——list类及其模拟实现,c++,list,开发语言


同样由其扩展出头删和尾删

		//头删
		void pop_front()
		{
			erase(begin());
		}
		//尾删
		void pop_back()
		{
			erase(--end());
		}

3.拷贝

和string和vector一样,list的拷贝也需要使用深拷贝,那么它的拷贝构造函数该怎么写?

同样是要开辟新的空间,需要一个自己的头结点,随后按照被拷贝的链表的数据进行尾插即可:

		//拷贝构造
		list(const list<T>& lt)
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
			for (auto& e : lt)
			{
				push_back(e);
			}
		}

测试如下:

C++——list类及其模拟实现,c++,list,开发语言


此外,还有“=”运算符重载的方法:

		//交换
		void swap(list<T>& it)
		{
			std::swap(_head, it._head);
		}
		//=运算符重载
		list<T>& operator=(list<T> lt)
		{
			swap(lt);
			return *this;
		}

这里仍然是巧妙的运用swap函数,因为lt是一个临时拷贝,有自己的空间和地址,所以直接让两者进行交换,lt在退出函数时即被销毁,而拷贝者则继承了它的地址空间,测试如下:

C++——list类及其模拟实现,c++,list,开发语言


总结

关于list类的基本知识就分享到这里啦。

因为与string和vector都存在很多相似之处,所以建议将这三者放在一起学习。

喜欢本篇文章记得一键三连,下期再见!文章来源地址https://www.toymoban.com/news/detail-846938.html

到了这里,关于C++——list类及其模拟实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C++ list模拟实现

    源码中的list实现为 带头双向链表   list类的对象有两个成员:指向头结点的指针_head,统计数据个数的_size 在模拟实现list之前,需要先模拟实现 结点类,迭代器类 结点类:三个成员,_data _prev _next , 实现成struct (也是类,不过与class不同的是,它的成员都是公开的,都可以

    2024年02月11日
    浏览(43)
  • C++ list 模拟实现

      目录 1. 基本结构的实现 2.  list() 3. void push_back(const T val) 4. 非 const 迭代器 4.1 基本结构  4.2 构造函数  4.3 T operator*() 4.4  __list_iterator operator++() 4.5 bool operator!=(const __list_iterator it) 4.6 T* operator-() 5. const 迭代器  6. begin()  end() ​编辑 7. iterator insert(iterator pos, const T v

    2024年02月08日
    浏览(46)
  • 【C++】list模拟实现

    个人主页 : zxctscl 如有转载请先通知 在前面一篇博客中分享了list的相关介绍 【C++】list介绍,这次来模拟实现一下list。 成员变量: 无参构造: 插入: 在库里面定义节点需要全部公有时用到的就是struct: 这里我们也用相同方法自己定义出一个节点: 然后在写list类时候就要

    2024年04月11日
    浏览(33)
  • 《C++ list的模拟实现》

    本文主要介绍list容器的模拟实现 list示意图: 首先需要定义一个节点 的结构体 我们之前所理解的是:迭代器理解为像指针一样的东西,但是在list中有些不同 我们可以来观察一下STL源码中大佬是怎么封装的: 我们可以看到,只有一个成员,那就是一个结点的指针node,link_

    2024年02月07日
    浏览(41)
  • 【C++】list的模拟实现

    list为任意位置插入删除的容器,底层为带头双向循环链表 begin() 代表第一个结点,end()代表最后一个结点的下一个 1. list_node 类设计 C++中,Listnode作为类名,而next和prev都是类指针,指针引用成员时使用-,而对象引用成员时使用 . 通过显示实例化,将两个类指针指定类型为T

    2024年02月02日
    浏览(41)
  • [C++]:12:模拟实现list

    1.节点结构: 1.SGI下的节点通过两个结构体实现。 2.基础的链表节点只包括前驱指针和后继指针。 3.链表节点去继承基础链表节点,新增节点数据。 4.优化掉指针类型带模板参数。 2.节点构造函数: 1.节点本身在这个地方是没有构造函数的。 2.观察下面的链表的结构和链表的

    2024年01月22日
    浏览(41)
  • (C++) list底层模拟实现

     个人主页:Lei宝啊  愿所有美好如期而遇 首先,list底层是一个带头双向循环链表,再一个,我们还要解决一个问题,list的迭代器,vector和string的迭代器可以直接++,是因为他们的地址空间是连续的,而链表不是,所以链表的迭代器封装的不是原生指针,我们需要想办法解决

    2024年01月21日
    浏览(42)
  • [C++]string及其模拟实现

    目录 string及其模拟实现::                                        1.构造函数                                        2.拷贝构造函数                                        3.赋值运算符重载                                        4.析构函数        

    2024年02月07日
    浏览(69)
  • 【C++】list容器功能模拟实现

            上一次介绍了list队容器的迭代器模拟,这次模拟实现list的简单功能,尤其要注意 构造函数、析构函数、以及赋值运算符重载 的实现。         list容器需要接纳所有类型的数据,因此,结构设置与迭代器设置同理,需要引入结点,数据。     //结点结构     templ

    2024年01月24日
    浏览(55)
  • C++ list链表模拟实现

    目录 前言: 模拟实现: 迭代器的实现: list类功能函数实现:  初始化成空函数(empty_init): 构造函数:  拷贝构造函数: 尾插(push_back): 插入(insert): 删除(erase):  尾删(pop_back): 头插(push_front): 头删(pop_front):  清理(clear):  交换(swap): 赋值重载:

    2024年04月12日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包