C++第二十五弹---从零开始模拟STL中的list(下)

2024-06-08 1864阅读

✨个人主页：熬夜学编程的小林

💗系列专栏：【C语言详解】【数据结构详解】【C++详解】

1、函数补充

2、迭代器完善

3、const迭代器

总结

1、函数补充

拷贝构造

思路：

先构造一个头结点，然后将 lt 类中的元素依次尾插到新的结点上。

void empty_init()
{
	_head = new Node;
	_head->_next = _head;
	_head->_prev = _head;
	_size = 0;
}
list(const list& lt)
{
	empty_init();//构造一个头结点
	for (auto& x : lt)
	{
		push_back(x);
	}
}

{}初始化构造

思路：

先构造一个头结点，然后将 il 类中的元素依次尾插到新的结点上。

list(initializer_list il)
{
	empty_init();
	for (auto& x : il)
	{
		push_back(x);
	}
}

赋值操作符重载

void swap(list& lt)
{
	std::swap(_head, lt._head);
	std::swap(_size, lt._size);
}
list& operator=(list lt)
{
	swap(lt);
	return *this;
}

大小相关函数

size_t size()
{
	return _size;
}
bool empty()
{
	return _size == 0;
}

clear()

清空list的内容，保留头结点。

//清空数据
void clear()
{
	iterator it = begin();
	while (it != end())
	{
		it = erase(it);//更新迭代器
	}
}

~list()

析构函数，清空list的内容并释放头结点。

~list()
{
	clear();//清空内容函数
	delete _head;//释放头结点
	_head = nullptr;//置空
}

2、迭代器完善

前面我们处理的都是内置类型的情况，如果我们出现自定义类型，如何解决？

自定义类型举例：

struct A
{
	int _a1;
	int _a2;
	A(int a1 = 0, int a2 = 0)
		:_a1(a1)
		, _a2(a2)
	{}
};

首先我们先看看几种自定义类型的尾插方式:

void test_list3()
{
	list lt;
	A aa1(1, 1);//实例化对象
	A aa2{ 2,2 };//多参数的隐式类型转换，C++11
	lt.push_back(aa1);//有名对象实例化
	lt.push_back(aa2);
	lt.push_back(A(3, 3));//匿名对象
	lt.push_back({ 4,4 });//多参数的隐式类型转换，C++11
}

对自定义类型进行遍历：

list::iterator it = lt.begin();
while (it != lt.end())
{
	cout 访问元素 
cout _a1 运算符时，C++ 会自动和透明地调用重载的 operator-> 并继续 “链式” 访问成员，而不需要程序员显示地添加多余的箭头。  
 
3、const迭代器 
 我们上一弹写的普通迭代器对于const对象是无法编译成功的，const不能调用非const成员函数(权限放大)。 
下面我们则实现一个const迭代器的类。 
 
与普通迭代器类似，我们需要先在list类中重命名一个const迭代器 
typedef ListConstIterator const_iterator;//const迭代器类
const_iterator begin() const
{
	return const_iterator(_head->_next);//匿名对象
	//return _head->_next;//单参数类型转换
}
const_iterator end() const
{
	return const_iterator(_head);
} 
注意： 
const迭代器名字不能写成 const iterator，因为const迭代器的本质是迭代器指向的内容不能修改，而不是迭代器本身不能修改，const_iterator这样定义是迭代器不能修改，内容还是可以修改的 
 
实现const_iterator类有两种方式，如下： 
方式一(单独实现一个新的类，修改普通迭代器的部分地方)： 
template
struct ListConstIterator
{
	typedef ListConstIterator Self;//对迭代器类重定义
	typedef ListNode Node;
	Node* _node;
	//构造
	ListConstIterator(Node* node)
		:_node(node)
	{}
	const T& operator*()//只能访问，不能修改值
	{
		return _node->_data;
	}
	const T* operator->()
	{
		return &_node->_data;//返回指针
	}
	//前置++ 
	Self& operator++()
	{
		_node = _node->_next;
		return *this;
	}
	//后置++
	Self operator++(int)
	{
		Self tmp(*this);
		_node = _node->_next;
		return *this;
	}
	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;
	}
}; 
 
我们可以看到，const迭代器与普通迭代器的区间只在operator*与operator->的返回的类型上，那么我们是不是可以将两个类封装成一个模板类呢？？？ 
 
//普通迭代器和const迭代器只有两个返回值不同，因此我们使用模板封装
template//reference引用 point指针
struct ListIterator
{
	typedef ListIterator Self;//对迭代器类重定义
	typedef ListNode Node;
	Node* _node;
	//构造
	ListIterator(Node* node)
		:_node(node)
	{}
	//T& operator*()//遍历及修改
	Ref operator*()
	{
		return _node->_data;
	}
	//T* operator->()
	Ptr 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;
	}
}; 
合并之后的三个类模板参数：

T：链表结点存储_data值的数据类型
Ref：通过迭代器访问数据时的返回类型，可以是T&或者const T&。

Ptr：通过迭代器访问数据的指针类型，可以是T*或者const T*。

链表实例化如下：

typedef ListIterator iterator;//普通迭代器类
typedef ListIterator const_iterator;//const迭代器类

list实现全部代码

namespace lin
{
	//链表基本结构
	template
	struct ListNode
	{
		ListNode* _prev;
		ListNode* _next;
		T _data;
		ListNode(const T& val = T())//初始化值构造
			:_prev(nullptr)
			,_next(nullptr)
			,_data(val)
		{}
	};
	//原版普通迭代器
	//迭代器操作类 方法都要被访问，使用struct
	//template
	//struct ListIterator
	//{
	//	typedef ListIterator Self;//对迭代器类重定义
	//	typedef ListNode Node;
	//	Node* _node;
	//	//构造
	//	ListIterator(Node* node)
	//		:_node(node)
	//	{}
	//	T& operator*()//遍历及修改
	//	{
	//		return _node->_data;
	//	}
	//	T* operator->()
	//	{
	//		return &_node->_data;//返回指针
	//	}
	//	//前置++ 
	//	Self& operator++()
	//	{
	//		_node = _node->_next;
	//		return *this;
	//	}
	//	//后置++
	//	Self operator++(int)
	//	{
	//		Self tmp(*this);
	//		_node = _node->_next;
	//		return *this;
	//	}
	//	bool operator!=(const Self& it)
	//	{
	//		return _node != it._node;
	//	}
	//	bool operator==(const Self& it)
	//	{
	//		return _node == it._node;
	//	}
	//};
	//原版const迭代器
	//template
	//struct ListConstIterator
	//{
	//	typedef ListConstIterator Self;//对迭代器类重定义
	//	typedef ListNode Node;
	//	Node* _node;
	//	//构造
	//	ListConstIterator(Node* node)
	//		:_node(node)
	//	{}
	//	const T& operator*()//只能访问，不能修改值
	//	{
	//		return _node->_data;
	//	}
	//	const T* operator->()
	//	{
	//		return &_node->_data;//返回指针
	//	}
	//	//前置++ 
	//	Self& operator++()
	//	{
	//		_node = _node->_next;
	//		return *this;
	//	}
	//	//后置++
	//	Self operator++(int)
	//	{
	//		Self tmp(*this);
	//		_node = _node->_next;
	//		return *this;
	//	}
	//	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;
	//	}
	//};
	//普通迭代器和const迭代器只有两个返回值不同，因此我们使用模板封装
	template//reference引用 point指针
	struct ListIterator
	{
		typedef ListIterator Self;//对迭代器类重定义
		typedef ListNode Node;
		Node* _node;
		//构造
		ListIterator(Node* node)
			:_node(node)
		{}
		//T& operator*()//遍历及修改
		Ref operator*()
		{
			return _node->_data;
		}
		//T* operator->()
		Ptr 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;
		}
	};
	
	template
	class list
	{
		typedef ListNode Node;//将链表结构重命名
	public:
		//普通版本
		//typedef ListIterator iterator;//需要被访问，放在public内
		//typedef ListConstIterator const_iterator;//const迭代器类
		//类模板
		typedef ListIterator iterator;//需要被访问，放在public内
		typedef ListIterator const_iterator;//const迭代器类
		//构造哨兵结点
		void empty_init()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
		}
		list()//默认构造
		{
			empty_init();//创建哨兵头结点
		}
		size_t size()
		{
			return _size;
		}
		void clear()//清空数据，不销毁哨兵头结点
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}
		~list()//析构函数
		{
			clear();
			delete _head;
			_head = nullptr;
		}
		list(const list& lt)//拷贝构造
		{
			empty_init();//创建头结点，然后进行尾插
			for (auto& x : lt)
			{
				push_back(x);
			}
		}
		void swap(list& lt)
		{
			std::swap(_head, lt._head);
			std::swap(_size, lt._size);
		}
		list& operator=(list lt)
		{
			swap(lt);
			return *this;
		}
		iterator begin() 
		{
			return iterator(_head->_next);//匿名对象
			//return _head->_next;//单参数类型转换
		}
		iterator end() 
		{
			return iterator(_head);
		}
		//解决打印修改值问题
		const_iterator begin() const
		{
			return const_iterator(_head->_next);//匿名对象
			//return _head->_next;//单参数类型转换
		}
		const_iterator end() const
		{
			return const_iterator(_head);
		}
		//单独实现的尾插
		//void push_back(const T& val)
		//{
		//	//tail 
		//	Node* newnode = new Node(val);
		//	Node* tail = _head->_prev;
		//	tail->_next = newnode;
		//	newnode->_prev = tail;
		//	newnode->_next = _head;
		//	_head->_prev = newnode;
		//}
		
		void insert(iterator pos, const T& val)//在pos位置前插入val
		{
			Node* cur = pos._node;
			Node* newnode = new Node(val);
			Node* prev = cur->_prev;
			//prev newnode cur
			newnode->_next = cur;
			cur->_prev = newnode;
			prev->_next = newnode;
			newnode->_prev = prev;
			_size++;
		}
		iterator erase(iterator pos)//删除pos位置，防止迭代器失效，返回迭代器后一个位置
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;
			//prev next
			prev->_next = next;
			next->_prev = prev;
			delete cur;
			_size--;
			return iterator(next);
		}
		//调用insert函数
		void push_back(const T& val)
		{
			//insert(--begin(),val);//不能使用+n，在--begin前面插入
			insert(end(), val);//end()前面
		}
		void push_front(const T& val)
		{
			insert(begin(), val);//begin()前面插入
		}
		void pop_back()
		{
			erase(--end());//end()前面删除
		}
		void pop_front()
		{
			erase(begin());//begin()位置删除
		}
	private:
		Node* _head;//链表成员变量
		size_t _size;//链表大小
	};
}

总结

本篇博客就结束啦，谢谢大家的观看，如果公主少年们有好的建议可以留言喔，谢谢大家啦！

VPS购买请点击我

免责声明：我们致力于保护作者版权，注重分享，被刊用文章因无法核实真实出处，未能及时与作者取得联系，或有版权异议的，请联系管理员，我们会立即处理! 部分文章是来自自研大数据AI进行生成,内容摘自(百度百科,百度知道,头条百科,中国民法典,刑法,牛津词典,新华词典,汉语词典,国家院校,科普平台)等数据,内容仅供学习参考,不准确地方联系删除处理! 图片声明：本站部分配图来自人工智能系统AI生成,觅知网授权图片,PxHere摄影无版权图库和百度，360，搜狗等多加搜索引擎自动关键词搜索配图，如有侵权的图片，请第一时间联系我们，邮箱：ciyunidc@ciyunshuju.com。本站只作为美观性配图使用,无任何非法侵犯第三方意图,一切解释权归图片著作权方,本站不承担任何责任。如有恶意碰瓷者,必当奉陪到底严惩不贷!

C++第二十五弹---从零开始模拟STL中的list(下)

1、函数补充

2、迭代器完善

总结

相关阅读

怎么把织梦的模板替换?

dedecms怎么调用特定的栏目文档?

怎么抓包一个网页?

wap怎么封装app?

目录[+]