首页 > 其他分享 >list类的模拟实现

list类的模拟实现

时间：2023-08-22 18:37:51浏览次数：44  
标签：node const iterator 迭代 实现 list next 模拟

一、list的介绍

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、list的构造

构造函数（constructor）

接口说明

list（size_type n,const value_type& val=value_type()）

构造的list中包含n个值为val的元素

list()

构造空的

list

list(cosnt list& x)

拷贝构造函数

list(InputIterator frist,InputIterator last)

用迭代器区间中的元素构造list

2、list iterator的使用

函数声明

接口说明

begin+end

返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器

rbegin+rend

返回第一个元素的reverse_iterator，即end位置，返回最后一个元素的下一个位置的reverse_iterator，即begin位置

list类的模拟实现_list

注意：

  • begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动。
  • rbegin与rend为反向迭代器，对迭代器执行++操作，迭代器向前移动。

3、list capacity

函数声明

接口说明

empty

检测list是否为空

size

返回list中有效节点的个数

4、list element access

函数声明

接口说明

front

返回list的第一个节点中值的引用

back

返回list的最后一个节点中值的引用

5、list modiflers

函数声明

接口说明

push_front

在list首元素前插入值为val的元素

pop_front

删除list中第一个元素

push_back

在list尾部插入值为val的元素

pop_back

删除list中最后一个元素

insert

在list pos位置中插入值为val的元素

erase

删除list pos位置的元素

swap

交换两个list中的元素

clear

清空list中的有效元素

三、list的迭代器失效

迭代器失效即迭代器所指向的节点无效，及该节点被删除了。因为list的底层结构为带头双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的。只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

void Test11()
{
	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
	list<int> l(array, array + sizeof(array) / sizeof(array[0]));
	auto it = l.begin();
	while (it != l.end())
	{
		// erase()函数执行后，it所指向的节点已被删除，因此it无效，
		//在下一次使用it时，必须先给其赋值
		l.erase(it);
		++it;
	}
}
//改正
void Test12()
{
	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
	list<int> l(array, array + sizeof(array) / sizeof(array[0]));
	auto it = l.begin();
	while (it != l.end())
	{
		l.erase(it++); // it = l.erase(it);
	}
}

四、list类的模拟实现

1、节点结构

template<class T>
struct list_node//节点结构
{
	list_node<T>* _prev;//指向前一个节点
	list_node<T>* _next;//指向后一个节点
	T _val;//存储数据
	list_node(const T& x = T())//初始化
		: _prev(nullptr)
		, _next(nullptr)
		, _val(x)
	{}
};

2、迭代器结构

因为list是链表，它的节点空间是不连续的，没办法用原生指针直接实现迭代器，我们需要专门写一个结构体来定义迭代器。

//用模板可以同时实现const_iterator和iterator
	template <class T, class Ref, class Ptr>//迭代器
	struct list_iterator
	{
		typedef list_node<T> Node;
		typedef list_iterator<T,Ref,Ptr> Self;
		Node* _node;//指向数据
		
    //需要传指向节点的指针，对迭代器的操作，实际上就是对这个指针进行操作
		list_iterator(Node* node)
			:_node(node)
		{}

		//运算符重载
		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;
		}
        //如果这里的Ref是const T&类型的，那返回的内容就是无法修改
        //如果这里的Ref是T&类型的，那返回的内容就可以修改
		Ref operator*()//*迭代器
		{
			return _node->_val;
		}
        //如果这里的Ref是const T*类型的，那返回的内容就是无法修改
        //如果这里的Ref是T*类型的，那返回的内容就可以修改
		Ptr operator->()//迭代器->
		{
			return &_node->_val;
		}
		bool operator==(const Self& s)const//迭代器==迭代器
		{
			return _node == s._node;
		}
		bool operator!=(const Self& s)const//迭代器！=迭代器
		{
			return _node != s._node;
		}
	};

3、list的成员变量

template<class T>
class list//链表结构
{
public:
	typedef list_node<T> Node;//节点
	typedef list_iterator<T, T&, T*> iterator;//迭代器
	typedef list_iterator<T, const T&, const T*> const_iterator;//const迭代器
	//注意：const iterator并不是我们想要的const迭代器，这样写，是迭代器无法移动
	//我们希望const迭代器可以移动，但是const迭代器指向的节点不能修改
private:
	Node* _phead;//节点
	size_t _size;//个数
};

4、空初始化与构造函数

void empty_init()//空初始化
{
	_phead = new Node;
	_size = 0;
	_phead->_prev = _phead->_next = _phead;
}
list()//构造函数
{
	empty_init();
}
list(const list<T>& l)//拷贝构造
{
	empty_init();
	for (auto a : l)
	{
		push_back(a);
	}
}

5、swap函数与赋值重载函数

void swap(list<T>& l)//交换
{
	std::swap(_phead, l._phead);
	std::swap(_size, l._size);
}

list<T>& operator=(const list<T>& l)//赋值重载
{
	list<T> tmp(l);
	swap(tmp);
	return *this;
}

6、迭代器

//迭代器
iterator begin()
{
	iterator ret(_phead->_next);
	return ret;
}
const_iterator begin()const
{
	const_iterator ret(_phead->_next);
	return ret;
}
iterator end()
{
	iterator ret(_phead);
	return ret;
}
const_iterator end()const
{
	const_iterator ret(_phead);
	return ret;
}

7、erase函数与pop_back函数与pop_front函数

iterator erase(iterator pos)//删除
{
	assert(pos != end());
	//记录前后节点
	Node* cur = pos._node;
	Node* prev = cur->_prev;
	Node* next = cur->_next;
  //释放当前节点
	delete cur;
	//连接前后节点
	prev->_next = next;
	next->_prev = prev;
	--_size;
	return next;
}
void pop_back()//尾删
{
	erase(--end());
}
void pop_front()//头删
{
	erase(begin());
}

8、clear函数与析构函数

void clear()//清空
{
	auto cur = begin();
	while (cur != end())//删除除了头结点以外的所以节点
	{
		cur = erase(cur);
	}
}

~list()//析构函数
{
	clear();//清空
	delete _phead;//把头结点也处理了
	_phead = nullptr;
	_size = 0;
}

9、insert函数与push_back函数与push_front函数

iterator insert(iterator pos, const T& x = T())//插入
{
	Node* newnode = new Node(x);//开新节点
	//记录前后节点
	Node* next = pos._node;
	Node* prev = next->_prev;
	//连接节点
	newnode->_next = next;
	newnode->_prev = prev;
	prev->_next = newnode;
	next->_prev = newnode;
	++_size;
	return newnode;
}
void push_back(const T& x)//尾插
{
	insert(end(), x);
}
void push_front(const T& x)//头插
{
	insert(begin(), x);
}

10、empty函数与size函数

bool empty()//判空
{
	return _size == 0;
}
size_t size()//返回size
{
	return _size;
}

11、其他的构造函数

list(int n, const T& x = T())//n个x构造
{
  empty_init();
	assert(n >= 0);
	while (n--)
	{
		push_back(x);
	}
}
template<class Iterator>
list(Iterator frist, Iterator last)//迭代器区间构造
{
	empty_init();
	while (frist != last)
	{
		push_back(*frist);
		++frist;
  }
}

12、完整代码

#include<iostream>
#include<assert.h>
using namespace std;
namespace lsx
{
	template<class T>
	struct list_node//节点结构
	{
		list_node<T>* _prev;//指向前一个节点
		list_node<T>* _next;//指向后一个节点
		T _val;//存储数据
		list_node(const T& x = T())
			: _prev(nullptr)
			, _next(nullptr)
			, _val(x)
		{
		}
	};

	//用模板可以同时实现const_iterator和iterator
	template <class T, class Ref, class Ptr>//迭代器
	struct list_iterator
	{
		typedef list_node<T> Node;
		typedef list_iterator<T,Ref,Ptr> Self;
		Node* _node;//指向数据
		
		list_iterator(Node* node)//需要传指向节点的柱子很
			:_node(node)
		{}

		//运算符重载
		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;
		}
		Ref operator*()//*迭代器
		{
			return _node->_val;
		}
		Ptr operator->()//迭代器->
		{
			return &_node->_val;
		}
		bool operator==(const Self& s)const//迭代器==迭代器
		{
			return _node == s._node;
		}
		bool operator!=(const Self& s)const//迭代器！=迭代器
		{
			return _node != s._node;
		}
	};

	template<class T>
	class list//链表结构
	{
	public:
		typedef list_node<T> Node;//节点
		typedef list_iterator<T, T&, T*> iterator;//迭代器
		typedef list_iterator<T, const T&, const T*> const_iterator;//const迭代器
		//注意：const iterator并不是我们想要的const迭代器，这样写，是迭代器无法移动
		//我们希望const迭代器可以移动，但是const迭代器指向的节点不能修改

		void empty_init()//空初始化
		{
			_phead = new Node;
			_size = 0;
			_phead->_prev = _phead->_next = _phead;
		}
		list()//构造函数
		{
			empty_init();
		}
		list(int n, const T& x = T())//n个x构造
		{
			empty_init();
			assert(n >= 0);
			while (n--)
			{
				push_back(x);
			}
		}
		template<class Iterator>
		list(Iterator frist, Iterator last)//迭代器区间构造
		{
			empty_init();
			while (frist != last)
			{
				push_back(*frist);
				++frist;
			}
		}
		list(const list<T>& l)//拷贝构造
		{
			empty_init();
			for (auto a : l)
			{
				push_back(a);
			}
		}
		list<T>& operator=(const list<T>& l)//赋值重载
		{
			list<T> tmp(l);
			swap(tmp);
			return *this;
		}
		~list()//析构函数
		{
			clear();
			delete _phead;
			_phead = nullptr;
			_size = 0;
		}

		//迭代器
		iterator begin()
		{
			iterator ret(_phead->_next);
			return ret;
		}
		const_iterator begin()const
		{
			const_iterator ret(_phead->_next);
			return ret;
		}
		iterator end()
		{
			iterator ret(_phead);
			return ret;
		}
		const_iterator end()const
		{
			const_iterator ret(_phead);
			return ret;
		}

		void clear()//清空
		{
			auto cur = begin();
			while (cur != end())//删除除了头结点以外的所以节点
			{
				cur = erase(cur);
			}
		}
		iterator erase(iterator pos)//删除
		{
			assert(pos != end());
			//记录前后节点
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;
			//释放当前节点
			delete cur;
			//连接前后节点
			prev->_next = next;
			next->_prev = prev;
			--_size;
			return next;
		}
		void pop_back()//尾删
		{
			erase(--end());
		}
		void pop_front()//头删
		{
			erase(begin());
		}
		iterator insert(iterator pos, const T& x = T())//插入
		{
			Node* newnode = new Node(x);//开新节点
			//记录前后节点
			Node* next = pos._node;
			Node* prev = next->_prev;
			//连接节点
			newnode->_next = next;
			newnode->_prev = prev;
			prev->_next = newnode;
			next->_prev = newnode;
			++_size;
			return newnode;
		}
		void push_back(const T& x)//尾插
		{
			insert(end(), x);
		}
		void push_front(const T& x)//头插
		{
			insert(begin(), x);
		}

		void swap(list<T>& l)
		{
			std::swap(_phead, l._phead);
			std::swap(_size, l._size);
		}
		bool empty()//判空
		{
			return _size == 0;
		}
		size_t size()//返回size
		{
			return _size;
		}
	private:
		Node* _phead;//节点
		size_t _size;//个数
	};

}



如有错误，欢迎指正，谢谢。


完结。。。。

标签：node,const,iterator,迭代,实现,list,next,模拟
From： https://blog.51cto.com/u_15855358/7191858

相关文章

  • 使用Apache IoTDB进行IoT相关开发的架构设计与功能实现(3)
    使用ApacheIoTDB进行IoT相关开发的架构设计与功能实现(3)接下来我给大家继续介绍一下ApacheIoTDB的数据类型和相关用法在显示时间戳时，IoTDB可以支持长类型和日期时间显示类型。日期时间显示类型可以支持用户定义的时间格式。自定义时间格式的语法如下表所示:**自定义时间格式的语......
  • springboot~kafka中延时消息的实现
    应用场景用户下单5分钟后,给他发短信用户下单30分钟后，如果用户不付款就自动取消订单kafka无死信队列kafka本身没有这种延时队列的机制，像rabbitmq有自己的死信队列，当一些消息在一定时间不消费时会发到死信队列，由死信队列来处理它们，上面的两个需求如果是rabbitmq可以通过死信......
  • 在vue中实现一个插件
    1、使用情景通过app.component()和app.directive()注册一到多个全局组件或自定义指令。通过app.provide()使一个资源可被注入进整个应用。向app.config.globalProperties中添加一些全局实例属性或方法一个可能上述三种都包含了的功能库(例如vue-router)。2、使用......
  • 13.Linux中fork函数详解（附图解与代码实现）
    13.Linux中fork函数详解（附图解与代码实现）我们先来看个代码，判断一下这个代码的输出结果会是什么样的，先不要去看运行结果，判断好后再去看看是否和你的预期结果一致。#include<stdio.h>#include<unistd.h>#include<stdlib.h>#include<string.h>intmain(void){ pid_tpid; ......
  • Android 恢复出厂设置、跳过开机向导、wifi扫描界面筛选显示 的代码实现
    恢复出厂设置：//APK侧Log.d(TAG,"exeRecovery");StringtimeStamp=DateFormat.format("yyyy-MM-ddTHH:mm:ssZ",System.currentTimeMillis()).toString();StringlocaleArg="--locale="+Locale.getDefault().toLa......
  • Centos使用nginx实现挂载本地yum源
    前言：生产环境中由于一些安全问题，无法使用外网，只能在内网运行，无法访问外部yum源，这时候对于一些环境的安装及其不方便，故使用内部挂载yum源方式解决。1、环境操作系统版本2、关闭selinux和防火墙#关闭selinuxsed-ri's/SELINUX=enforcing/SELINUX=disabled/'/etc/selinux/co......
  • 微信开发之一键修改群聊备注的技术实现
    修改群备注 修改群名备注后，如看到群备注未更改，是手机缓存问题，可以连续点击进入其他群，在点击进入修改的群，再返回即可看到修改后的群备注名，群名称的备注仅自己可见请求URL：http://域名地址/modifyGroupRemark请求方式：POST请求头Headers：Content-Type：application/json......
  • 普及模拟3
    普及模拟3\(T1\)最大生成树\(100pts\)简化题意：给定一个\(n(1\len\le1\times10^5）\)个点的完全图，给定各点的点权\(a_i(1\lei\len)\)，两点间的边权为\(|a_i-a_j|\)，求该图的最大生成树。正解：贪心，考虑到一个点对答案产生的贡献为\(\max(a_i-\min\limits_{j=1}^{......
  • java实现大文件上传技术
    ​ 1，项目调研因为需要研究下断点上传的问题。找了很久终于找到一个比较好的项目。 在GoogleCode上面，代码弄下来超级不方便，还是配置hosts才好，把代码重新上传到了github上面。 https://github.com/freewebsys/java-large-file-uploader-demo 效果： 上传中，显示进度，时间......
  • 使用EasyPlayer.js，通过设置解码器参数实现H.265音频解码
    EasyPlayer是一款稳定且流畅的流媒体播放器，它能够支持H.264和H.265视频播放。该播放器能够处理各种视频流格式，包括RTSP、RTMP、HLS、FLV和WebRTC等。EasyPlayer具备多个版本，例如EasyPlayer-RTSP、EasyPlayer.js和EasyPlayerPro，以满足不同用户在不同场景下的需求。此外，EasyPlayer还......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99