咨询热线 ：
028-86922220
×
01
关于我们

公司简介

发展历程

02
服务项目

高端网站建设

微信开发

APP开发

网络营销服务

电商网站定制

生物医药网站建设

外贸网站建设

教育培训网站建设

03
小程序开发

小程序开发

功能应用

客户案例

04
案例展示

网站建设案例

小程序案例

电商平台案例

APP案例

系统平台案例

05
建站动态

网站建设

网站设计

网站营销

小程序

06
联系我们

公司地址

人才招聘

地址：成都市太升南路288号锦天国际A幢1002号

电话：028-86922220

028-86922220

大橙子网站建设，新征程启航

为企业提供网站建设、域名注册、服务器等服务

【C++】list类模拟实现-创新互联

list
  • 一、list类实现准备
    • 1.1 list的节点类
    • 1.2 list类的成员变量
  • 二、迭代器实现❗️❗️
    • 2.1 正向迭代器
    • 2.2 反向迭代器
  • 三、list类接口的实现
    • 3.1 构造函数
    • 3.2 begin()和end()
    • 3.3 插入
    • 3.4 头插和尾插
    • 3.5 删除
    • 3.6 头删和尾删
    • 3.7 clear()和析构
    • 3.8 拷贝构造
      • 3.8.1 现代写法
    • 3.9 赋值拷贝
      • 3.9.1 现代写法
    • 3.10 初始化冲突问题

在郑州等地区，都构建了全面的区域性战略布局，加强发展的系统性、市场前瞻性、产品创新能力，以专注、极致的服务理念，为客户提供做网站、网站建设 网站设计制作按需设计网站,公司网站建设,企业网站建设,高端网站设计,营销型网站,成都外贸网站制作,郑州网站建设费用合理。一、list类实现准备

首先要知道list就是一个带头循环双向链表，在博主以前的文章有过详细讲解顺序表和链表超详细大总结
现在我们首先就要实现每个节点的类：

1.1 list的节点类
templatestruct ListNode
	{ListNode(const T& val = T())
			: _prev(nullptr)
			, _next(nullptr)
			, _val(val)
		{}
		ListNode* _prev;
		ListNode* _next;
		T _val;
	};
1.2 list类的成员变量

list的成员变量只需要头节点

typedef ListNodeNode;
private:
		Node* _head;
二、迭代器实现❗️❗️ 2.1 正向迭代器

按照以前的思路写迭代器如下：

templatestruct _list_iterator
	{typedef ListNodeNode;
		_list_iterator(Node* p)
		{	_p = p;
		}

		T& operator*()
		{	return _p->_val;
		}

		_list_iterator& operator++()
		{	_p = _p->_next;
			return *this;
		}

		_list_iterator& operator++(int)
		{	_list_iteratortmp(*this);
			_p = _p->_next;
			return tmp;
		}

		_list_iterator& operator--()
		{	_p = _p->_prev;
			return *this;
		}

		_list_iterator& operator--(int)
		{	_list_iteratortmp(*this);
			_p = _p->_prev;
			return tmp;
		}

		//end() 返回临时变量具有常属性 
		bool operator!=(const _list_iterator& it) const
		{	return _p != it._p;
		}

		bool operator!=(const _list_iterator& it) const
		{	return _p == it._p;
		}

		Node* _p;
	};

我们还有个迭代器叫做const迭代器，就是可以++，--，*，就是用的时候不能修改。也就是不能返回T&而是const T&
有人可能想实现一个const版本的重载：

const T& operator*() const
		{	return _p->_val;
		}

但现在我们的容器是const，传的迭代器没有变，想要修改还是可以。
为了解决这个问题，第一个方法是拷贝一份迭代器，换个名字，在使用上面的const版本*重载即可。但这样就会造成代码冗余。

所以我们可以这样修改：

typedef _list_iteratoriterator;
typedef _list_iteratorconst_iterator;

传入两个模板参数，迭代器模板使用template
再把*重载改成：

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

双模板参数迭代器实现如下：

templatestruct _list_iterator
	{typedef ListNodeNode;
		typedef _list_iteratoriterator;
		_list_iterator(Node* p)
		{	_p = p;
		}

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

		iterator& operator++()
		{	_p = _p->_next;
			return *this;
		}

		iterator& operator++(int)
		{	_list_iteratortmp(*this);
			_p = _p->_next;
			return tmp;
		}

		iterator& operator--()
		{	_p = _p->_prev;
			return *this;
		}

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

		//end() 返回临时变量具有常属性 
		bool operator!=(const iterator& it) const
		{	return _p != it._p;
		}

		bool operator==(const iterator& it) const
		{	return _p == it._p;
		}

		Node* _p;
	};

但是我们可以发现还有一个问题：*重载如果是原生类型好说，但是对于自定义类型我们需要取出每一个对象就需要重载->。
例如我们想要打印日期类的年月日，直接*取出的是节点。所以我们可以重载一个->拿到节点。

T* operator->()
	{return &_p->_val;
	}

打印年月日就可以这么写：

list::iterator it = lt.begin();
while (it != lt.end())
{cout<< it->year<< it->month<< it->day<< endl;
	++it;
}

其实这里应该写成it->->year，为了可读性编译器优化省略了一个->。而且所有类型只要想重载->都会这样省略。而重载->又会涉及到是否能修改的问题。所以再传一个模板参数。

typedef _list_iteratoriterator;
typedef _list_iteratorconst_iterator;

对于迭代器：

Ptr operator->()
		{	return &_p->_val;
		}
2.2 反向迭代器

其实正向迭代器就是对Node* 指针的封装，而反向迭代器就是正向迭代器的封装。

反向迭代器的--就是正向迭代器的++。
而比较大的区别时反向迭代器的*重载取得不是当前位置，而是前一个位置的值。
在这里插入图片描述
正向迭代器的开始就是反向迭代器的结束，正向迭代器的结束就是反向迭代器的开始。
代码如下：

namespace yyh
{templatestruct reverse_iterator
	{typedef reverse_iteratoriterator;
		// 封装正向迭代器
		reverse_iterator(Iterator it)
			: _it(it)
		{}

		Ref operator*()
		{	Iterator tmp = _it;
			return *--tmp;
		}

		Ptr operator->()
		{	Iterator tmp = _it;
			return &--tmp;
		}

		iterator& operator++()
		{	--_it;
			return *this;
		}

		iterator& operator++(int)
		{	iterator tmp(*this);
			--_it;
			return tmp;
		}

		iterator& operator--()
		{	++_it;
			return *this;
		}

		iterator& operator--(int)
		{	iterator tmp(*this);
			++_it;
			return tmp;
		}

		bool operator==(const iterator& it) const
		{	return _it == it._it;
		}

		bool operator!=(const iterator& it) const
		{	return _it != it._it;
		}

		Iterator _it;
	};
}
三、list类接口的实现 3.1 构造函数
_list_iterator(Node* p)
		{	_p = p;
		}
3.2 begin()和end()
iterator begin()
		{	return iterator(_head->_next);
		}

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

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

		const const_iterator end() const
		{	return const_iterator(_head);
		}
3.3 插入
iterator insert(iterator pos, const T& val)
		{	Node* cur = pos._p;
			Node* prev = cur->_prev;
			Node* newnode = new Node(val);
			cur->_prev = newnode;
			newnode->_next = cur;
			prev->_next = newnode;
			newnode->_prev = prev;
			return iterator(newnode);
		}
3.4 头插和尾插
void push_back(const T& val)
		{	insert(end(), val);
		}

		void push_front(const T& val)
		{	insert(begin(), val);
		}
3.5 删除
iterator erase(iterator pos)
		{	assert(pos != end());
			Node* prev = pos._p->_prev;
			Node* next = prev->_next->_next;
			delete pos._p;
			prev->_next = next;
			next->_prev = prev;
			return iterator(next);
		}
3.6 头删和尾删
void pop_back()
		{	erase(--end());
		}

		void pop_front()
		{	erase(begin());
		}
3.7 clear()和析构
~list()
		{	clear();
			delete _head;
			_head = nullptr;
		}

		void clear()
		{	iterator it = begin();
			while (it != end())
			{		it = erase(it);
			}
		}
3.8 拷贝构造
list(const list& lt)
		{	// 先创建头节点
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
			const_iterator it = lt.begin();
			while (it != lt.end())
			{		push_back(*it);
				++it;
			}
		}

这里要注意先创建头节点，再插入数据。

3.8.1 现代写法
// 迭代器区间初始化
		templatelist(InputIterator first, InputIterator last)
		{	// 先创建头节点
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
			while (first != last)
			{		push_back(*first);
				++first;
			}
		}

		list(const list& lt)
		{	_head = new Node;// _head不能为nullptr,析构会解用
			_head->_next = _head;
			_head->_prev = _head;
			listtmp(lt.begin(), lt.end());
			swap(_head, tmp._head);
		}

这里如果给_head赋值为nullptr，后边调用clear()会用到return iterator(_head->_next);，程序崩溃。

3.9 赋值拷贝
list& operator=(const list& lt)
		{	if (this != <)
			{		clear();
				for (auto& e : lt)
				{push_back(e);
				}
			}
			return *this;
		}
3.9.1 现代写法
list& operator=(listlt)
		{	_head->_next = _head;
			_head->_prev = _head;
			swap(_head, lt._head);
			return *this;
		}
3.10 初始化冲突问题

当我们想用n个val初始化的时候：

list(size_t n, const T& val = T())
		{	_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
			for (size_t i = 0; i< n; i++)
			{		push_back(val);
			}
		}

但是我们前面使用迭代器初始化：

templatelist(InputIterator first, InputIterator last)
		{	// 先创建头节点
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
			while (first != last)
			{		push_back(*first);
				++first;
			}
		}

当我们使用listlt(5, 1)时，此时我们就会传到迭代器区间初始化，造成寻址错误。
解决方法：
重载一个int 类型的初始化函数：

list(size_t n, const T& val = T())
		{	_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
			for (size_t i = 0; i< n; i++)
			{		push_back(val);
			}
		}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧


网页标题：【C++】list类模拟实现-创新互联
链接地址：http://dzwzjz.com/article/jcgpg.html

其他资讯

分享至：
关于我们
公司简介 发展历程
服务项目
高端网站建设 小程序开发 APP开发 网络营销
建站知识
行业新闻 建站学堂 常见问题
联系我们
公司地址 人才招聘
成都 达州
电话：028-86922220
地址：成都市太升南路288号锦天国际A幢1002号
电话：028-86922220
地址：达州市南岸区弹子石腾龙大道58号2栋21-6
友情链接： 上海除甲醛   成都网站建设   网站推广公司   成都网站制作公司   成都SEO公司   百度推广公司   四川正泰动物   装饰公司网站建设方案   服务器机柜   专业LED亮化工程   
版权所有：青羊区大橙子信息咨询工作室 蜀ICP备2022028542号-14
在线咨询
服务热线
服务热线：028-86922220
TOP