分类导航

程序笔记发布时间：2022-07-13 发布网站：大佬教程 code.js-code.com

大佬教程收集整理的这篇文章主要介绍了list模拟实现，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

文章目录

一. list接口函数总览
二.结点类的模拟实现
三. 迭代器类模拟实现
- 构造函数
- 前置++和后置++
- 前置- -和后置- -
- ==/!=运算符重载
- * 运算符重载
- -> 运算符重载
list模拟实现
- 构造函数
- 拷贝构造函数
- 赋值运算符重载
- 析构函数
- begin和end
- front/BACk
- insert
- erase
- push_BACk/pop_BACk/push_front/pop_front
- size
- clear
- empty
- swap
- resize

一. list接口函数总览

namespace lyp
{
	//模拟实现list当中的结点类
	template<class T>
	struct _list_node
	{
		//成员函数
		_list_node(const T& val = T()); //构造函数

		//成员变量
		T _val;                 //数据域
		_list_node<T>* _next;   //后继指针
		_list_node<T>* _prev;   //前驱指针
	};

	//模拟实现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);  //构造函数

		//各种运算符重载函数
		self operator++();
		self operator++(int);
		self operator--();
		self operator--(int);
		bool operator==(const self& s) const;
		bool operator!=(const self& s) const;
		Ref operator*();
		Ptr operator->();

		//成员变量
		node* _pnode; //一个指向结点的指针
	};

	//模拟实现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;

		//默认成员函数
		list();
		list(const list<T>& lt);
		list<T>& operator=(const list<T>& lt);
		~list();

		//迭代器相关函数
		iterator begin();
		iterator end();
		const_iterator begin() const;
		const_iterator end() const;

		//访问容器相关函数
		T& front();
		T& BACk();
		const T& front() const;
		const T& BACk() const;

		//插入、删除函数
		void insert(iterator pos, const T& x);
		iterator erase(iterator pos);
		void push_BACk(const T& x);
		void pop_BACk();
		void push_front(const T& x);
		void pop_front();

		//其他函数
		size_t size() const;
		void resize(size_t n, const T& val = T());
		void clear();
		bool empty() const;
		void swap(list<T>& lt);

	private:
		node* _head; //指向链表头结点的指针
	};
}

二.结点类的模拟实现

list 的底层结构为带头双向循环链表࿰c;所以结点类里的成员变量有 T _val(数据)࿰c;_list_node< T >* _prev(前驱指针)࿰c;_list_node< T >* _next(后继指针)࿰c;成员函数只需要构造函数即可(初始化数据࿰c;初始化指针为nullptr)

list模拟实现

template<class T>
struct _list_node
{
  _list_node(const T& val = T())
  	:_val(val)
  	,_prev(nullptr)
  	,_next(nullptr)
  {}
	T _val;                // 数据
	_list_node<T>* _prev;  // 前驱指针
	_list_node<T>* _next; // 后继指针
}

三. 迭代器类模拟实现

前面的博客已经介绍过 vector 和 String 类的模拟实现࿰c;在 vector 和 String 中࿰c;迭代器均为原生指针࿰c;是因为vector和String底层实现均为数组࿰c;在使用迭代器进行遍历时可以支持 != 判断是否到末尾࿰c;++ 移动到下一数据࿰c;但list为带头双向循环链表࿰c;若迭代器采用原生指针࿰c;不支持 != 操作࿰c;且++后不能移动到下一数据(底层是链表࿰c;空间不连续)࿰c;因此需要用一个类来封装指针࿰c;对上述操作的运算符进行重载࿰c;使list能够像vector/String一样使用同样的方式去进行遍历

迭代器的成员变量 : node* _pnode; //一个指向结点的指针迭代器的成员函数 : 运算符的重载

可能有读者对模板参数比较疑惑࿰c;为什么会有三个模板参数呢?

template<class T,class Ref,class Ptr>

因为我们在list类中定义了两个迭代器类࿰c;普通迭代器类࿰c;const迭代器类(Ref为 T&/const T& 类型࿰c;Ptr为 T*/const T* 类型)

typedef _list_iterator<T,T&,T*> iterator;
typedef _list_iterator<T,const T&,const T*> const_iterator;

当我们使用普通迭代器对象时࿰c;实例化出普通迭代器类(iterator)࿰c;使用COnst迭代器对象时࿰c;实例化出const迭代器类(const_iterator)

构造函数

对封装的指针进行初始化即可

_list_iterator(node* pnode)
	:_pnode(pnode)
{}

前置++和后置++

前置++/后置++都是将指针指向下一个数据࿰c;即 _pnode = _pnode->_next࿰c;前置++返回++之后的值࿰c;后置++返回原先的值࿰c;为了区分前置++和后置++,后置++比前置++多一个int参数

self 为当前迭代器类型

typedef _list_iterator<T,Ref,Ptr> self

// 前置++
self& operator++()
{
	_pnode = _pnode->_next;
	return *this;
}

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

前置- -和后置- -

前置- -/后置- -都是将指针指向前一个数据࿰c;即 _pnode = _pnode->_prev࿰c;前置- -返回- -之后的值࿰c;后置- -返回原先的值࿰c;为了区分前置- -和后置- -,后置- -比前置- -多一个int参数

self 为当前迭代器类型

// 前置- -
self& operator--()
{
	_pnode = _pnode->_prev;
	return *this;
}

// 后置- -
self& operator--(int)
{
	self tmp(*this);
	_pnode = _pnode->_prev;
	return tmp;
}

==/!=运算符重载

==运算符重载比较两个迭代器对象的_pnode指针指向是否相同

// ==运算符重载
bool operator==(const self& s)const
{
	return _pnode == s._pnode;
}

!=运算符重载比较两个迭代器对象的_pnode指针指向是否不同

// !=运算符重载
bool operator!=(const self& s)const
{
	return _pnode != s._pnode;
}

* 运算符重载

重载 * 运算符的目的是为了得到迭代器对象的_pnode指针所指向的数据

// * 运算符重载
Ref operator*()
{
	return _pnode->_val;
}

-> 运算符重载

重载 -> 运算符的目的是当list中的数据是自定义类型时࿰c;我们可以通过 -> 来访问自定义类型的成员变量

// -> 运算符重载
Ptr operator->()
{
	return &_pnode->_val;
}

使用案例

class Date
{
public:
	int _year = @H_468_1262@0;
	int _month = @H_468_1262@1;
	int _day = @H_468_1262@1;
}
int @H_886_101@main()
{
	lt<Date> lt;
	lt.push_BACk(Date());
	list<Date>::iterator it = lt.begin();
	cout<<it->_year<<" "<<it->_month<<" "<<it->_day<<endl;
}

在这里编译器做了一些优化 it->_year 本来应该是 it->->_year ࿰c;第一个->去调用operator->重载函数返回T*的指针࿰c;第二个->用来去访问自定义类型的成员变量࿰c;但是两个箭头程序的可读性较差࿰c;所以编译器做了优化࿰c;省略了一个箭头

list模拟实现

构造函数

list是一个带头双向循环链表࿰c;构造函数的目的是创建一个头结点࿰c;_next 和 _prev都指向自己

list()
{
	_head = new node; // 申请一个头结点
	_head->_next = _head; // 后继指针指向自己
	_head->_prev = _head; // 前驱指针指向自己
}

拷贝构造函数

1). 申请一个头结点࿰c;_next 和 _prev都指向自己 2). 将 lt 中的数据拷贝到新构造的容器中

list(const list<T>& lt)
{
	_head = new node; // 申请一个头结点
	_head->_next = _head; // 后继指针指向自己
	_head->_prev = _head; // 前驱指针指向自己
	for(const auto& e : lt) // 拷贝到新构造的容器中
	{
		push_BACk(e);
	}
}

赋值运算符重载

传统写法 : 1). 释放除了头结点以外的结点 2). 将 lt 中的数据拷贝到新构造的容器中

list<T>& operator=(const list<T>& lt)
{
  // 防止自己给自己赋值
	if(this != &lt)
	{
		clear(); // 清空数据
		for(const auto& e : lt) // 拷贝到新构造的容器中
		{
			push_BACk(e);
		}
	}
	return *this; // 支持连续赋值
}

现代写法 : 1). 拷贝构造出 lt 对象 2). 交换 this 和 lt 的 _head 指针࿰c;出了作用域࿰c;lt 调用析构函数࿰c;释放掉原this的结点

list<T>& operator=(list<T> lt) // 拷贝构造
{
	std::swap(_head,lt._head); // 交换指针
	return *this; // 支持连续赋值
}

析构函数

1). 使用 clear() 释放除了头结点以外的结点 2). 释放掉头结点

~list()
{
	clear(); // 释放除了头结点以外的结点
	delete _head; // 释放掉头结点
	_head = nullptr; // 置空头指针
}

begin和end

begin() : 构造出指针指向第一个结点的迭代器对象 end() : 构造出指针指向头结点的迭代器对象

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

front/BACk

front() : 返回第一个结点数据的引用 end() : 返回最后一个结点数据的引用

T& front()
{
	return *begin(); 
}
const T& front()const
{
	return *begin(); 
}
T& end()
{
	return *(--end()); 
}
const T& end()const
{
	return *(--end()); 
}

insert

1). 新开辟一个结点newnode(值为val)࿰c;得到当前结点的指针࿰c;前驱结点的指针 2). 前驱结点的_next 指向 newnode࿰c;newnode的_prev指向前驱结点 3). newnode的_next 指向当前结点࿰c;当前结点的_prev指向newnode

void insert(iterator pos,const T& val)
{
		assert(pos._pnode); // 断言指针不为空
		node* cur = pos._pnode; // 当前结点指针
		node* prev = pos._pnode->_prev; // 前驱结点指针
		node* newnode = new node(val); // 新开辟结点

		prev->_next = newnode; // 前驱结点的_next 指向 newnode
		newnode->_prev = prev; // newnode的_prev指向前驱结点
		newnode->_next = cur;  // newnode的_next 指向当前结点
		cur->_prev = newnode;  // 当前结点的_prev指向newnode
}

erase

1). 得到前驱结点和后继结点的指针 2). 前驱结点的_next 指向后继结点 3). 后继结点的_prev指向前驱结点 4). 删除当前结点࿰c;返回删除位置的下一个位置

iterator erase(iterator pos)
{
	assert(!empty()); // 链表不为空
	assert(pos._pnode != _head); // 不能删头结点
	node* prev = pos._pnode->_prev; // 前驱结点指针
	node* next = pos._pnode->_next; // 后继结点指针
	prev->_next = next; // 前驱结点的_next 指向后继结点
	next->_prev = prev; // 后继结点的_prev指向前驱结点
	delete pos._pnode;  // 删除当前结点
	return iterator(next); // 返回删除位置的下一个位置
}

push_BACk/pop_BACk/push_front/pop_front

这四个函数都可以复用 insert 和 erase 函数

push_BACk : 尾插即在头结点前插入一个结点 pop_BACk : 尾删࿰c;删除最后一个结点 push_front : 头插即在第一个结点前插入一个结点 pop_front : 头删࿰c;删除第一个结点

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());
}

size

获取链表中有效结点的个数࿰c;遍历一次链表即可得到࿰c;但这是O(n)的时间复杂度࿰c;如果要频繁的使用size接口࿰c;可以在list类中加入_size成员变量

size_t size() const
{
	size_t sz = @H_468_1262@0; //统计有效数据个数
	const_iterator it = begin(); //获取第一个有效数据的迭代器
	while (it != end()) //通过遍历统计有效数据个数
	{
		sz++;
		it++;
	}
	return sz; //返回有效数据个数
}

clear

只保留头结点࿰c;遍历链表调用erase接口进行删除࿰c;注意调用erase后 it 迭代器就已经失效了

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

empty

判断容器是否为空

bool empty()const
{
	return begin() == end();
}

swap

交换容器的头指针即可

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

resize

1). 若n大于当前容器的size࿰c;则尾插结点࿰c;直到size等于n为止。 2). 若n小于当前容器的size࿰c;则只保留前n个结点。

void resize(size_t n, const T& val = T())
{
		size_t len = size();
		if (n < len)
		{
			size_t count = len - n;
			while (count--)
			{
				pop_BACk();
			}
		}
		// n > len
		else
		{
			size_t count = n - len;
			while (count--)
			{
				push_BACk(val);
			}
		}
}

大佬总结

以上是大佬教程为你收集整理的list模拟实现全部内容，希望文章能够帮你解决list模拟实现所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。

标签：cap list php while 优化参数程序员遍历

上一篇: 数据结构顺序表/ 链表oj 曲四下一篇:数据结构之排序算法（python）

猜你在找的程序笔记相关文章

You can't specify target table 'xxx' for update in FROM clause的解决 2022-07-21
【UNIAPP】上传视频，进度条的前台与后端 2022-07-21
十款代码表白特效，一个比一个浪漫！ 2022-07-04
作业3 2022-07-06
linux系统下部署项目访问报404错误的解决方法 2022-05-30
C++带有指针成员的类处理方式详解 2022-06-07
Linux——（1）基本命令 2022-07-21
JavaScript之正则表达式学习笔记 2019-11-07
Redux源码学习笔记 2019-11-07
Webpack学习笔记 2019-11-07