list(介绍与实现)

目录

1. list的介绍及使用

1.1 list的介绍

1.2 list的使用

1.2.1 list的构造

1.2.2 list iterator的使用

 1.2.3 list capacity

1.2.4 list element access

 1.2.5 list modififiers

1.2.6 list的迭代器失效

2. list的模拟实现

2.1 模拟实现list

2.2 list的反向迭代器


1. list的介绍及使用

1.1 list的介绍

1. list 是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。
2. list 的底层是双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向其前一个元素和后一个元素。
3. list forward_list 非常相似:最主要的不同在于 forward_list 是单链表,只能朝前迭代,已让其更简单高效。
4. 与其他的序列式容器相比 (array vector deque) list 通常在任意位置进行插入、移除元素的执行效率更好。
5. 与其他序列式容器相比, list forward_list 最大的缺陷是不支持任意位置的随机访问,比如:要访问 list的第6 个元素,必须从已知的位置 ( 比如头部或者尾部 ) 迭代到该位置,在这段位置上迭代需要线性的时间开销;list 还需要一些额外的空间,以保存每个节点的相关联信息 ( 对于存储类型较小元素的大 list 来说这可能是一个重要的因素)

 

1.2 list的使用

list 中的接口比较多,此处类似,只需要掌握如何正确的使用,然后再去深入研究背后的原理,已达到可扩展的能力。以下为list 中一些 常见的重要接口

1.2.1 list的构造

构造函数(
(constructor)
接口说明
list (size_type n, const value_type& val = value_type())
构造的 list 中包含 n 个值为 val 的元素
list()
构造空的 list
list (const list& x)
拷贝构造函数
list (InputIterator fifirst, InputIterator last)
[fifirst, last) 区间中的元素构造 list

1.2.2 list iterator的使用

此处,大家可暂时 将迭代器理解成一个指针,该指针指向 list 中的某个节点

 

 

【注意】
1. begin end 为正向迭代器,对迭代器执行 ++ 操作,迭代器向后移动
2. rbegin(end) rend(begin) 为反向迭代器,对迭代器执行 ++ 操作,迭代器向前移动

 1.2.3 list capacity

1.2.4 list element access

 

 1.2.5 list modififiers

函数声明
接口说明
push_front
list 首元素前插入值为 val 的元素
pop_front
删除 list 中第一个元素
push_back
list 尾部插入值为 val 的元素
pop_back
删除 list 中最后一个元素
insert
list position 位置中插入值为 val 的元素
erase
删除 list position 位置的元素
swap
交换两个 list 中的元素
clear
清空 list 中的有效元素

1.2.6 list的迭代器失效

前面说过,此处大家可将迭代器暂时理解成类似于指针, 迭代器失效即迭代器所指向的节点的无效,即该节 点被删除了 。因为 list 的底层结构为带头结点的双向循环链表 ,因此 list 中进行插入时是不会导致 list 的迭代 器失效的,只有在删除时才会失效,并且失效的只是指向被删除节点的迭代器,其他迭代器不会受到影响

2. list的模拟实现

2.1 模拟实现list

要模拟实现 list ,必须要熟悉 list 的底层结构以及其接口的含义,通过上面的学习,这些内容已基本掌握,现在我们来模拟实现list
#pragma once

#include <iostream>
using namespace std;
#include <assert.h>

namespace bite
{
	// List的节点类
	template<class T>
	struct ListNode
	{
		ListNode(const T& val = T())
			: _prev(nullptr)
			, _next(nullptr)
			, _val(val)
		{}

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

	/*
	List 的迭代器
	迭代器有两种实现方式,具体应根据容器底层数据结构实现:
	  1. 原生态指针,比如:vector
	  2. 将原生态指针进行封装,因迭代器使用形式与指针完全相同,因此在自定义的类中必须实现以下方法:
		 1. 指针可以解引用,迭代器的类中必须重载operator*()
		 2. 指针可以通过->访问其所指空间成员,迭代器类中必须重载oprator->()
		 3. 指针可以++向后移动,迭代器类中必须重载operator++()与operator++(int)
			至于operator--()/operator--(int)释放需要重载,根据具体的结构来抉择,双向链表可以向前             移动,所以需要重载,如果是forward_list就不需要重载--
		 4. 迭代器需要进行是否相等的比较,因此还需要重载operator==()与operator!=()
	*/
	template<class T, class Ref, class Ptr>
	class ListIterator
	{
		typedef ListNode<T> Node;
		typedef ListIterator<T, Ref, Ptr> Self;

		// Ref 和 Ptr 类型需要重定义下,实现反向迭代器时需要用到
	public:
		typedef Ref Ref;
		typedef Ptr Ptr;
	public:
		//
		// 构造
		ListIterator(Node* node = nullptr)
			: _node(node)
		{}

		//
		// 具有指针类似行为
		Ref operator*() 
		{ 
			return _node->_val;
		}

		Ptr operator->() 
		{ 
			return &(operator*()); 
		}

		//
		// 迭代器支持移动
		Self& operator++()
		{
			_node = _node->_next;
			return *this;
		}

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

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

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

		//
		// 迭代器支持比较
		bool operator!=(const Self& l)const
		{ 
			return _node != l._node;
		}

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

		Node* _node;
	};

	template<class Iterator>
	class ReverseListIterator
	{
		// 注意:此处typename的作用是明确告诉编译器,Ref是Iterator类中的一个类型,而不是静态成员变量
		// 否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员变量
		// 因为静态成员变量也是按照 类名::静态成员变量名 的方式访问的
	public:
		typedef typename Iterator::Ref Ref;
		typedef typename Iterator::Ptr Ptr;
		typedef ReverseListIterator<Iterator> Self;
	public:
		//
		// 构造
		ReverseListIterator(Iterator it)
			: _it(it)
		{}

		//
		// 具有指针类似行为
		Ref operator*()
		{
			Iterator temp(_it);
			--temp;
			return *temp;
		}

		Ptr operator->()
		{
			return &(operator*());
		}

		//
		// 迭代器支持移动
		Self& operator++()
		{
			--_it;
			return *this;
		}

		Self operator++(int)
		{
			Self temp(*this);
			--_it;
			return temp;
		}

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

		Self operator--(int)
		{
			Self temp(*this);
			++_it;
			return temp;
		}

		//
		// 迭代器支持比较
		bool operator!=(const Self& l)const
		{
			return _it != l._it;
		}

		bool operator==(const Self& l)const
		{
			return _it != l._it;
		}

		Iterator _it;
	};

	template<class T>
	class list
	{
		typedef ListNode<T> Node;

	public:
		// 正向迭代器
		typedef ListIterator<T, T&, T*> iterator;
		typedef ListIterator<T, const T&, const T&> const_iterator;

		// 反向迭代器
		typedef ReverseListIterator<iterator> reverse_iterator;
		typedef ReverseListIterator<const_iterator> const_reverse_iterator;
	public:
		///
		// List的构造
		list()
		{
			CreateHead();
		}

		list(int n, const T& value = T())
		{
			CreateHead();
			for (int i = 0; i < n; ++i)
				push_back(value);
		}

		template <class Iterator>
		list(Iterator first, Iterator last)
		{
			CreateHead();
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

		list(const list<T>& l)
		{
			CreateHead();

			// 用l中的元素构造临时的temp,然后与当前对象交换
			list<T> temp(l.begin(), l.end());
			this->swap(temp);
		}

		list<T>& operator=(list<T> l)
		{
			this->swap(l);
			return *this;
		}

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

		///
		// List的迭代器
		iterator begin() 
		{ 
			return iterator(_head->_next); 
		}

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

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

		const_iterator end()const
		{ 
			return const_iterator(_head); 
		}

		reverse_iterator rbegin()
		{
			return reverse_iterator(end());
		}

		reverse_iterator rend()
		{
			return reverse_iterator(begin());
		}

		const_reverse_iterator rbegin()const
		{
			return const_reverse_iterator(end());
		}

		const_reverse_iterator rend()const
		{
			return const_reverse_iterator(begin());
		}

		///
		// List的容量相关
		size_t size()const
		{
			Node* cur = _head->_next;
			size_t count = 0;
			while (cur != _head)
			{
				count++;
				cur = cur->_next;
			}

			return count;
		}

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

		void resize(size_t newsize, const T& data = T())
		{
			size_t oldsize = size();
			if (newsize <= oldsize)
			{
				// 有效元素个数减少到newsize
				while (newsize < oldsize)
				{
					pop_back();
					oldsize--;
				}
			}
			else
			{
				while (oldsize < newsize)
				{
					push_back(data);
					oldsize++;
				}
			}
		}
		
		// List的元素访问操作
		// 注意:List不支持operator[]
		T& front()
		{
			return _head->_next->_val;
		}

		const T& front()const
		{
			return _head->_next->_val;
		}

		T& back()
		{
			return _head->_prev->_val;
		}

		const T& back()const
		{
			return _head->_prev->_val;
		}

		
		// List的插入和删除
		void push_back(const T& val) 
		{ 
			insert(end(), val); 
		}

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

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

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

		// 在pos位置前插入值为val的节点
		iterator insert(iterator pos, const T& val)
		{
			Node* pNewNode = new Node(val);
			Node* pCur = pos._node;
			// 先将新节点插入
			pNewNode->_prev = pCur->_prev;
			pNewNode->_next = pCur;
			pNewNode->_prev->_next = pNewNode;
			pCur->_prev = pNewNode;
			return iterator(pNewNode);
		}

		// 删除pos位置的节点,返回该节点的下一个位置
		iterator erase(iterator pos)
		{
			// 找到待删除的节点
			Node* pDel = pos._node;
			Node* pRet = pDel->_next;

			// 将该节点从链表中拆下来并删除
			pDel->_prev->_next = pDel->_next;
			pDel->_next->_prev = pDel->_prev;
			delete pDel;

			return iterator(pRet);
		}

		void clear()
		{
			Node* cur = _head->_next;
			
			// 采用头删除删除
			while (cur != _head)
			{
				_head->_next = cur->_next;
				delete cur;
				cur = _head->_next;
			}

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

		void swap(bite::list<T>& l)
		{
			std::swap(_head, l._head);
		}

	private:
		void CreateHead()
		{
			_head = new Node;
			_head->_prev = _head;
			_head->_next = _head;
		}
	private:
		Node* _head;
	};
}


///
// 对模拟实现的list进行测试
// 正向打印链表
template<class T>
void PrintList(const bite::list<T>& l)
{
	auto it = l.begin();
	while (it != l.end())
	{
		cout << *it << " ";
		++it;
	}

	cout << endl;
}

// 测试List的构造
void TestBiteList1()
{
	bite::list<int> l1;
	bite::list<int> l2(10, 5);
	PrintList(l2);

	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
	bite::list<int> l3(array, array + sizeof(array) / sizeof(array[0]));
	PrintList(l3);

	bite::list<int> l4(l3);
	PrintList(l4);

	l1 = l4;
	PrintList(l1);
}

// PushBack()/PopBack()/PushFront()/PopFront()
void TestBiteList2()
{
	// 测试PushBack与PopBack
	bite::list<int> l;
	l.push_back(1);
	l.push_back(2);
	l.push_back(3);
	PrintList(l);

	l.pop_back();
	l.pop_back();
	PrintList(l);

	l.pop_back();
	cout << l.size() << endl;

	// 测试PushFront与PopFront
	l.push_front(1);
	l.push_front(2);
	l.push_front(3);
	PrintList(l);

	l.pop_front();
	l.pop_front();
	PrintList(l);

	l.pop_front();
	cout << l.size() << endl;
}

// 测试insert和erase
void TestBiteList3()
{
	int array[] = { 1, 2, 3, 4, 5 };
	bite::list<int> l(array, array + sizeof(array) / sizeof(array[0]));

	auto pos = l.begin();
	l.insert(l.begin(), 0);
	PrintList(l);

	++pos;
	l.insert(pos, 2);
	PrintList(l);

	l.erase(l.begin());
	l.erase(pos);
	PrintList(l);

	// pos指向的节点已经被删除,pos迭代器失效
	cout << *pos << endl;

	auto it = l.begin();
	while (it != l.end())
	{
		it = l.erase(it);
	}
	cout << l.size() << endl;
}

// 测试反向迭代器
void TestBiteList4()
{
	int array[] = { 1, 2, 3, 4, 5 };
	bite::list<int> l(array, array + sizeof(array) / sizeof(array[0]));

	auto rit = l.rbegin();
	while (rit != l.rend())
	{
		cout << *rit << " ";
		++rit;
	}
	cout << endl;

	const bite::list<int> cl(l);
	auto crit = l.rbegin();
	while (crit != l.rend())
	{
		cout << *crit << " ";
		++crit;
	}
	cout << endl;
}

2.2 list的反向迭代器

通过前面例子知道,反向迭代器的 ++ 就是正向迭代器的 -- ,反向迭代器的 -- 就是正向迭代器的 ++ ,因此反向迭代器的实现可以借助正向迭代器,即:反向迭代器内部可以包含一个正向迭代器,对正向迭代器的接口进行包装即可。
template<class Iterator>
class ReverseListIterator
{
 // 注意:此处typename的作用是明确告诉编译器,Ref是Iterator类中的类型,而不是静态成员变量
 // 否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员变量
 // 因为静态成员变量也是按照 类名::静态成员变量名 的方式访问的
public:
 typedef typename Iterator::Ref Ref;
 typedef typename Iterator::Ptr Ptr;
 typedef ReverseListIterator<Iterator> Self;
public:
 //
 // 构造
 ReverseListIterator(Iterator it): _it(it){}
 //
 // 具有指针类似行为
 Ref operator*(){
 Iterator temp(_it);
 --temp;
 return *temp;
 }
 Ptr operator->(){ return &(operator*());}
 //
 // 迭代器支持移动
 Self& operator++(){
--_it;
 return *this;
 }
 Self operator++(int){
 Self temp(*this);
 --_it;
 return temp;
 }
 Self& operator--(){
 ++_it;
 return *this;
 }
 Self operator--(int)
 {
 Self temp(*this);
 ++_it;
 return temp;
 }
 //
 // 迭代器支持比较
 bool operator!=(const Self& l)const{ return _it != l._it;}
 bool operator==(const Self& l)const{ return _it != l._it;}
 Iterator _it;
};

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

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

相关文章

C语言_分支和循环语句(3)

文章目录 前言一、猜数字游戏1.1.电脑随机生成一个数&#xff08;1~100&#xff09;&#xff1b;1.2.猜数字&#xff1a;1.3.玩完一把不过瘾&#xff0c;可以继续玩&#xff0c;不用退出程序。1.4.rand 和 srand 之间的联系5.猜数字游戏源码 二、go to 语句2.1.例如&#xff1a…

阿里云配置MySQL-server 8.0远程登录

Ubuntu 22.04 LTS 安装MySQL-Server 8.0 # apt search mysql-server # apt install mysql-server重建服务 # service mysql stop # vi /etc/mysql/mysql.conf.d/mysqld.cnf ... bind-address 0.0.0.0 ... # service mysql start # lsof -i:3306 COMMAND PID USER FD …

vant2 van-calendar组件增加清除按钮和确定按钮

利用自定义插槽增加一个清除按钮 <van-calendar ref"fTime1" select"selectTimePicker" confirm"changeTimePicker" :default-date"null" :show-confirm"false" v-model"timePickerShow" type"range&quo…

基于swing的中国象棋java小游戏jsp源代码Mysql

本项目为前几天收费帮学妹做的一个项目&#xff0c;Java EE JSP项目&#xff0c;在工作环境中基本使用不到&#xff0c;但是很多学校把这个当作编程入门的项目来做&#xff0c;故分享出本项目供初学者参考。 一、主要功能 可以实现双人下棋&#xff0c;可以悔棋&#xff0c;可…

新员工入职培训选修课《提高时间的效能》考试答案

中电金信新员工入职培训选修课《提高时间的效能》考试答案 z

铁威马教程丨铁威马NAS如何使用安全顾问工具

在使用NAS的过程中&#xff0c;我们时常可能忽略了一些小细节&#xff0c;久而久之可能造成一定的风险&#xff0c;影响着我们NAS的健康。而使用铁威马NAS的安全顾问工具&#xff0c;可以快速地帮我们扫描系统设置是否安全&#xff0c;让我们更放心更安心地使用NAS。 安全顾问…

【JUC系列-03】熟练掌握Atomic原子系列基本使用

JUC系列整体栏目 内容链接地址【一】深入理解JMM内存模型的底层实现原理https://zhenghuisheng.blog.csdn.net/article/details/132400429【二】深入理解CAS底层原理和基本使用https://blog.csdn.net/zhenghuishengq/article/details/132478786【三】熟练掌握Atomic原子系列基本…

cookie和session区别

一.Cookie详解 &#xff08;1&#xff09;Cookie是什么 &#xff1f; Cookie&#xff0c;有时也用其复数形式Cookies。类型为“小型文本文件”&#xff0c;是某些网站为了辨别用户身份&#xff0c;进行Session跟踪而储存在用户本地终端上的数据&#xff08;通常经过加密&#…

北斗星耀,导航天下:中国北斗卫星导航系统的发展历程与应用现状

听到“北斗”这个词&#xff0c;你会想到什么&#xff1f; 若是在古代&#xff0c;人们会想到闪耀在夜空的北斗七星。 而在现代&#xff0c;很多人会脱口而出“北斗卫星”。我国蓬勃发展的现代航天事业&#xff0c;为“北斗”赋予了一层新的含义。 北斗卫星导航系统&#xff08…

C#调用barTender打印标签示例

使用的电脑需要先安装BarTender 我封装成一个类 using System; using System.Windows.Forms;namespace FT_Tools {public class SysContext{public static BarTender.Application btapp new BarTender.Application();public static BarTender.Format btFormat;public void Q…

Python中的迭代器和生成器介绍

一、迭代器&#xff08;Iterators&#xff09; 迭代器是Python中用于遍历数据集合的一种机制。它是一个实现了迭代协议的对象&#xff0c;可以通过iter()函数来获得迭代器。迭代器需要实现两个方法&#xff1a;__iter__()和__next__()。其中&#xff0c;__iter__()返回迭代器自…

探秘二叉树后序遍历:从叶子到根的深度之旅

本篇博客会讲解力扣“145. 二叉树的后序遍历”的解题思路&#xff0c;这是题目链接。 本题的思路是&#xff1a; 先创建一个数组&#xff0c;用来存储二叉树后序遍历的结果。数组的大小跟树的结点个数有关。树的结点个数可以使用递归实现&#xff0c;即总个数左子树结点个数右…

【C++】多态学习

多态 多态的概念与定义多态的概念构成多态的两个条件虚函数与重写重写的两个特例 final 和 override重载、重写(覆盖)、重定义(隐藏)的对比抽象类多态的原理静态绑定与动态绑定 单继承与多继承关系下的虚函数表(派生类)单继承中的虚函数表查看多继承中的虚函数表查看 菱形继承与…

Unity3d:GameFramework解析:实体,对象池,资源管理,获取计数,引用计数,自动释放

基本概念 1.GF万物基于引用池IReference 2.ObjectBase : IReference类的m_Target持有unity中Mono&#xff0c;资源&#xff0c;GameObejct 3.AssetObject : ObjectBase类m_Target持有Assetbundle中的Asset&#xff0c;具有获取&#xff0c;引用两个计数管理释放 4.ResourceObj…

sql:SQL优化知识点记录(三)

&#xff08;1&#xff09;explain之select_type和table介绍 简单的查询类型是&#xff1a;simple 外层 primary&#xff0c;括号里subquery 用到了临时表&#xff1a;derived &#xff08;2&#xff09;explain之type介绍 trpe反映的结果与我们sql是否优化过&#xff0c;是否…

从零起步:学习数据结构的完整路径

文章目录 1. 基础概念和前置知识2. 线性数据结构3. 栈和队列4. 树结构5. 图结构6. 散列表和哈希表7. 高级数据结构8. 复杂性分析和算法设计9. 实践和项目10. 继续学习和深入11. 学习资源12. 练习和实践 &#x1f389;欢迎来到数据结构学习专栏~从零起步&#xff1a;学习数据结构…

电气特征分析(ESA)技术是什么及有何应用场景

在现代工业领域&#xff0c;电机扮演着不可或缺的角色&#xff0c;驱动着生产设备的正常运行。然而&#xff0c;电机的故障可能会导致生产中断、计划外停机以及高昂的经济损失。为了保障生产的连续性和效率&#xff0c;预测性维护变得至关重要。在这个背景下&#xff0c;电气特…

HTML基础--标签

目录 列表标签 有序列表 type属性 有序列表嵌套 无序列表 type属性 无序列表嵌套 常见应用场景 表格标签 表格展示效果 表格属性 表格单元格合并 单元格合并属性 列表标签 HTL作为构建网页内容的标记语言&#xff0c;提供了多种列表标签&#xff0c;用于在网页中展…

如何使用CSS实现一个3D旋转效果?

聚沙成塔每天进步一点点 ⭐ 专栏简介⭐ 3D效果实现⭐ 写在最后 ⭐ 专栏简介 前端入门之旅&#xff1a;探索Web开发的奇妙世界 记得点击上方或者右侧链接订阅本专栏哦 几何带你启航前端之旅 欢迎来到前端入门之旅&#xff01;这个专栏是为那些对Web开发感兴趣、刚刚踏入前端领域…

实战教学:农产品小程序商城的搭建与运营

随着移动设备的普及和互联网技术的发展&#xff0c;小程序商城已经成为农产品销售的一种新兴渠道。本文将以乔拓云网为平台&#xff0c;详细介绍如何搭建和运营农产品小程序商城。 步骤一&#xff1a;登录乔拓云网后台 首先&#xff0c;进入乔拓云网站后台&#xff0c;找到并点…