资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划，从策略到执行的一站式服务

网站建设 >

查看其它板块

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

目录
  • 前言
  • 一、list和vector的区别
  • 二、节点的定义
  • 三、list类定义
  • 四、push_back函数
  • 五、push_front函数
  • 六、迭代器
  • 七、begin和end函数
  • 八、迭代器区间初始化
  • 九、迭代器的操作符重载
    • 操作符++重载
    • 操作符- -重载
    • 操作符！=重载
    • 操作符==重载
    • 操作符*重载
  • 十、insert函数
  • 十一、erase函数
  • 十二、pop_back函数
  • 十三、pop_front
  • 十四、析构函数
  • 十五、拷贝构造函数
  • 十六、赋值操作符重载
  • 十七、迭代器优化
  • 十七、反向迭代器
  • 总结:

在永清等地区，都构建了全面的区域性战略布局，加强发展的系统性、市场前瞻性、产品创新能力，以专注、极致的服务理念，为客户提供做网站、成都网站建设 网站设计制作按需策划,公司网站建设,企业网站建设,成都品牌网站建设,网络营销推广,外贸网站建设,永清网站建设费用合理。前言

上次模拟实现了一个vector容器，那么我们这次来实现一个list(链表)容器，链表在实际的开发中并不常见。但是也是一种很重要的数据结构，下面给大家介绍一下链表(list) 和 vector(顺序表)的区别。

一、list和vector的区别

list 和 vector 一样，是一个存储容器。不同的是vector在内存中是连续存储的，而list每个节点所在的内存区域是不连续的。那我们用vector还是用list呢？vector和list的优劣势有以下几点。
vector优点:
1.支持下标随机访问。
2.cpu命中缓存率高
vector缺点:
1.存在一定的程度的空间浪费。
2.扩容代价大。
3.中间和前面元素的删除与插入，代价大。

list优点:
1.按需申请空间，不存在空间浪费。
2.任意位置的插入与删除，时间复杂度都是O(1)。
list缺点:
1.不支持随机访问，以至于查找，排序等操作代价太大。
2.cpu命中缓存率低。

综上所述，我们可以看到list和vector是完全互补的两个容器。vector的优点就是list的缺点，vector的缺点就是list的优点。所以，如果查找多，用vector，如果增删操作多，用list，了解了list之后，接下来我们就可以模拟实现一下它。

二、节点的定义

我们要实现的是一个带头双向循环的链表。
在这里插入图片描述
所以节点有三个参数，一个的prve指向前一个节点，一个是date存储数据，还有一个是next指向下一个节点。当然，我们还需要有个构造函数，来给date赋值。

代码:

//节点结构体
	templatestruct ListNode
	{typedef ListNodeNode;
		Node* _prve;
		Node* _next;
		T _data;

		//构造函数
		ListNode():_prve(nullptr),_next(nullptr),_data(0){}
		
		ListNode(const T& val)
			:_prve(nullptr)
			,_next(nullptr)
		{	_data = val;
		}
	};
三、list类定义

list定义很简单，因为要存任意类型的参数，我们用模板即可。
而私有成员只有一个，那就是头节点。

代码:

templateclass list
	{typedef ListNodeNode;
	public:
		//构造函数
		list()
		{	//开辟空间
			_head = new Node;
			//自己指向自己
			_head->_prve = _head;
			_head->_next = _head;
		}
	private:
		Node* _head;
	};
四、push_back函数

push_back函数也就是尾部插入，我们可以通过头节点的prev找到最后一个节点，随后链接即可。

代码:

void push_back(const T& val)
		{	//创建一个新节点
			Node* newNode = new Node(val);
			//找到尾节点
			Node* tail = _head->_prve;
			//尾节点和创建的节点链接
			tail->_next = newNode;
			newNode->_prve = tail;
			_head->_prve = newNode;
			newNode->_next = _head;
		}
五、push_front函数

就是头插，很简单，直接保存节点的下一个节点，然后创建一个新节点。把这俩节点链接起来。

代码:

void push_front(const T& val)
		{	//创建一个新节点
			Node* newNode = new Node(val);
			//保存头节点的下一个节点
			Node* next = _head->_next;
			//链接
			_head->_next = newNode;
			newNode->_prve = _head;
			next->_prve = newNode;
			newNode->_next = next;
		}
六、迭代器

因为是链表容器，链表在内存中的存储不是连续的，所以迭代器+1是无法找到下一个节点的。所以我们要单独弄一个结构体来封装list的迭代器。

代码:

templatestruct_list_iterator
	{Node* _it;
		typedef ListNodeNode;
		// 构造函数
		_list_iterator(Node* node)
			:_it(node)
		{		}

	};
七、begin和end函数

我们的链表是带头的，也就是头节点是不存放有效值的，所以头节点的_next指向的节点就是链表的第一个节点。而最后一个节点的下一个节点又恰好是头节点。所以迭代器开始位置是在头节点的下一个位置，结束位置是头节点。不过再此之前，我们需要把迭代器typedef一下。

代码:

//迭代器
		typedef _list_iteratoriterator;
		typedef _list_iteratorconst_iterator;
		//迭代器获取
		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);
		}
八、迭代器区间初始化

有了迭代器之后，我们可以用迭代器区间来进行初始化。

代码:

templatelist(InputIterator first, InputIterator last)
		{	//创建头节点
			_head = new Node();
			_head->_prve = _head;
			_head->_next = _head;

			while (first != last)
			{		pusb_back(*first);
				++first;
			}
		}
九、迭代器的操作符重载

接下来我们来完善迭代器的一些操作。

操作符++重载

迭代器++，就是指向下一个元素。

typedef _list_iteratorself;
		//前置++重载
		self& operator++()
		{	_it = _it->_next;
			return *this;
		}
		//后置++重载
		self operator++(int)
		{	self tmp(*this);
			_it = _it->_next;
			return tmp;
		}
操作符- -重载

和++类似，不过- -是到前一个节点。

//前置--重载
		self& operator--()
		{	_it = _it->_prve;
			return *this;
		}

		//后置--重载
		self operator--(int)
		{	self tmp(*this);
			_it = _it->_prve;
			return tmp;
		}
操作符！=重载

直接比较地址即可。

// !=重载
		bool operator!=(const self& it)const
		{	return _it != it._it;
		}
操作符==重载

直接比较地址即可。

// ==重载
		bool operator==(const self& it)const
		{	return _it == it._it;
		}
操作符*重载

*就是解引用，所以我们返回节点的值即可。

T& operator*()
		{	return _it->_data;
		}

但是这个代码有个缺陷，那就是当容器是const的时候，依旧可以解引用修改它的值，这也就意味着const迭代器根本就不具有常属性，要想const迭代具备常属性，我们必须增加模板参数。
在这里插入图片描述
当容器是const的时候，返回的const迭代器必须具有常属性。所以我们要加一个模板参数作为返回值。
在这里插入图片描述

然后list里面typedef的类型也修改一下。
在这里插入图片描述
然后我们解引用时，返回Ref这个模板参数
在这里插入图片描述
这样，我们就让const的迭代器具备了常属性
在这里插入图片描述
迭代器结构体的所有代码:

//迭代器
	templatestruct _list_iterator
	{		typedef ListNodeNode;
		typedef _list_iteratorself;
		Node* _it;
		// 构造函数
		_list_iterator(Node* node)
			:_it(node){}
		//前置++重载
		self& operator++()
		{	_it = _it->_next;
			return *this;
		}

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

		//前置--重载
		self& operator--()
		{	_it = _it->_prve;
			return *this;
		}

		//后置--重载
		self operator--(int)
		{	self tmp(*this);
			_it = _it->_prve;
			return tmp;
		}
		// *重载
		Ref operator*()
		{	return _it->_data;
		}
		// !=重载
		bool operator!=(const self& it)const
		{	return _it != it._it;
		}
		// ==重载
		bool operator==(const self& it)const
		{	return _it == it._it;
		}

	};
十、insert函数

insert函数是在指定位置插入一个节点，那么我们可以用迭代器来接收这个要插入的位置。

//插入节点
		iterator insert(iterator pos, const T& val)
		{	assert(pos._it);
			//保存pos的前一个位置
			Node* cru = pos._it;
			Node* prve = cru->_prve;
			//创建节点
			Node* newNode = new Node(val);
			//链接
			prve->_next = newNode;
			newNode->_prve = prve;
			newNode->_next = cru;
			cru->_prve = newNode;

			return pos;
		}
十一、erase函数

指定位置删除节点，删除节点会影响迭代器失效，所以要返回一个有效的迭代器。删除操作也十分简单，保存前一个节点的地址和后一个地址的节点，然后链接这2个节点，之后释放pos节点。

iterator erase(iterator pos)
		{	assert(pos._it);
			Node* cru = pos._it;
			Node* prve = cru->_prve;
			Node* next = cru->_next;
			//链接
			prve->_next = next;
			next->_prve = prve;
			//释放cru
			delete cru;
			return next;
		}
十二、pop_back函数

就是尾删，我们可以直接复用erase

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

当然，push_back也可以复用inset

十三、pop_front

就是头删，还是复用erase。头插也可以复用insert

void pop_front()
		{	erase(begin());
		}
十四、析构函数

链表的基本功能已经实现完了，但是当我们链表不用的时候，申请的空间必须销毁。而自带的析构函数不会销毁动态申请的空间，需要我们自己写析构函数销毁。

代码:

//析构函数
		~list()
		{	//清空链表
			clear();
			//释放头节点
			delete _head;
			_head = nullptr;
		}

		void clear()
		{	//除了头节点外，其他都释放。
			iterator it = begin();
			while (it != end())
			{		//保存下一个位置的地址
				iterator next = it++;
				delete next._it;
			}
			//释放完之后，头节点指向的是个野指针，所以我们让它指向自己
			_head->_next = _head;
			_head->_prve = _head;
		}
十五、拷贝构造函数

那么我们想拷贝链表呢？我们可以直接用迭代器区间去创建一个新的对象，然后把新对象的头节点成员和旧对象进行交换。出了函数创建的对象会自动调用析构函数释放空间。

//拷贝构造
		list(const list& l1)
		{	//创建头节点
			_head = new Node();
			_head->_prve = _head;
			_head->_next = _head;
			//创建新对象，利用迭代器区间
			listtmp(l1.begin(), l1.end());
			//随后交换新对象和旧对象的成员
			swap(_head, tmp._head);
		}
十六、赋值操作符重载

我们可以利用拷贝构造创建一个新对象，然后交换头节点。函数结束，创建的对象自动析构。

代码:

list& operator=(const list& l1)
		{	listtmp(l1);
			swap(_head, tmp._head);
			return *this;
		}
十七、迭代器优化

我们的迭代器还不够完美，因为如果list装的是自定义类型的话，我们还需要让迭代器支持 ->访问。期望它返回一个对象的指针回来，然后该对象的指针可以->直接访问成员。所以我们还需要增加模板参数。

增加一个指针参数
在这里插入图片描述
链表里的迭代器调整。
在这里插入图片描述
然后重载 迭代器的->操作符

Ptr operator->()
		{	//返回对象的指针
			return &(_it->_data);
		}

可以直接支持->访问
在这里插入图片描述

十七、反向迭代器

之前在vector实现的时候，我们实现过反向迭代器。vector实现链接。所以我们可以复用这个反向迭代器。

首先，包上反向迭代器的头文件名。
在这里插入图片描述
其次，我们typedef 2个反向迭代器
在这里插入图片描述

随后用rbegin函数和rend函数获取迭代器的开始和结束位置。
begin返回的是从头节点的下一个节点，所以rend就是返回头节点的下一个位置。
end返回的是头节点，所以rbegin返回头节点。

代码:

//反向迭代器获取
		reverse_iterator rbegin()
		{	return reverse_iterator(end());
		}

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

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

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

全部代码:
list.h代码

#pragma once
#include "reverse_iterator.h"

namespace wyl
{//节点结构体
	templatestruct ListNode
	{typedef ListNodeNode;
		Node* _prve;
		Node* _next;
		T _data;

		//构造函数
		ListNode():_prve(nullptr),_next(nullptr),_data(0){}

		ListNode(const T& val)
			:_prve(nullptr)
			,_next(nullptr)
		{	_data = val;
		}
	};

	//迭代器
	templatestruct _list_iterator
	{		typedef ListNodeNode;
		typedef _list_iteratorself;
		Node* _it;
		// 构造函数
		_list_iterator(Node* node)
			:_it(node){}
		//前置++重载
		self& operator++()
		{	_it = _it->_next;
			return *this;
		}

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

		//前置--重载
		self& operator--()
		{	_it = _it->_prve;
			return *this;
		}

		//后置--重载
		self operator--(int)
		{	self tmp(*this);
			_it = _it->_prve;
			return tmp;
		}
		// *重载
		Ref operator*()
		{	return _it->_data;
		}
		// !=重载
		bool operator!=(const self& it)const
		{	return _it != it._it;
		}
		// ==重载
		bool operator==(const self& it)const
		{	return _it == it._it;
		}

		Ptr operator->()
		{	//返回对象的指针
			return &(_it->_data);
		}

	};

	templateclass list
	{typedef ListNodeNode;
		
	public:
		//迭代器
		typedef _list_iteratoriterator;
		typedef _list_iteratorconst_iterator;
		//反向迭代器
		typedef _reverse_iteratorreverse_iterator;
		typedef _reverse_iteratorconst_reverse_iterator;

		//构造函数
		list()
		{	//开辟空间
			_head = new Node();
			//自己指向自己
			_head->_prve = _head;
			_head->_next = _head;
		}
		//迭代器区间初始化
		templatelist(InputIterator first, InputIterator last)
		{	//创建头节点
			_head = new Node();
			_head->_prve = _head;
			_head->_next = _head;

			while (first != last)
			{		push_back(*first);
				++first;
			}
		}
		//拷贝构造
		list(const list& l1)
		{	//创建头节点
			_head = new Node();
			_head->_prve = _head;
			_head->_next = _head;
			//创建新对象，利用迭代器区间
			listtmp(l1.begin(), l1.end());
			//随后交换新对象和旧对象的成员
			swap(_head, tmp._head);
		}
		list& operator=(const list& l1)
		{	listtmp(l1);
			swap(_head, tmp._head);
			return *this;
		}

		//析构函数
		~list()
		{	//清空链表
			clear();
			//释放头节点
			delete _head;
			_head = nullptr;
		}

		void clear()
		{	//除了头节点外，其他都释放。
			iterator it = begin();
			while (it != end())
			{		//保存下一个位置的地址
				iterator next = it++;
				delete next._it;
			}
			//释放完之后，头节点指向的是个野指针，所以我们让它指向自己
			_head->_next = _head;
			_head->_prve = _head;
		}

		void push_back(const T& val)
		{	//创建一个新节点
			Node* newNode = new Node(val);
			//找到尾节点
			Node* tail = _head->_prve;
			//尾节点和创建的节点链接
			tail->_next = newNode;
			newNode->_prve = tail;
			_head->_prve = newNode;
			newNode->_next = _head;
		}

		void push_front(const T& val)
		{	//创建一个新节点
			Node* newNode = new Node(val);
			//保存头节点的下一个节点
			Node* next = _head->_next;
			//链接
			_head->_next = newNode;
			newNode->_prve = _head;
			next->_prve = newNode;
			newNode->_next = next;
		}



		//迭代器获取
		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);
		}

		//反向迭代器获取
		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());
		}


		//插入节点
		iterator insert(iterator pos, const T& val)
		{	assert(pos._it);
			//保存pos的前一个位置
			Node* cru = pos._it;
			Node* prve = cru->_prve;
			//创建节点
			Node* newNode = new Node(val);
			//链接
			prve->_next = newNode;
			newNode->_prve = prve;
			newNode->_next = cru;
			cru->_prve = newNode;

			return pos;
		}

		iterator erase(iterator pos)
		{	assert(pos._it);
			Node* cru = pos._it;
			Node* prve = cru->_prve;
			Node* next = cru->_next;
			//链接
			prve->_next = next;
			next->_prve = prve;
			//释放cru
			delete cru;
			return next;
		}
		
		void pop_back()
		{	erase(end());
		}

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

	private:
		Node* _head;
	};


	//--------------------------------------------------------------------------------------------
	//以下是测试内容

	void listTest1()
	{listl;
		l.push_back(1);
		l.push_back(2);
		l.push_back(3);
		l.push_front(30);
		l.push_front(20);
		l.push_front(10);
	}

	void a(const list& l)
	{list::const_iterator it = l.begin();
		while (it != l.end())
		{	//*it = 5;
			cout<< *it<< " ";
			it++;
		}
	}

	void listTest2()
	{listl;
		l.push_back(1);
		l.push_back(2);
		l.push_back(3);
		list::iterator it = l.begin();
		while (it != l.end())
		{	*it = 55;
			cout<< *it<< " ";
			++it;
		}
		//a(l);
	}

	void listTest3()
	{listl;
		l.push_back(1);
		l.push_back(2);
		l.push_back(4);
		l.push_back(5);
		l.insert(l.begin(),100);
		l.insert(l.end(), 10);

		list::iterator it = l.begin();
		while (it != l.end())
		{	if (*it % 2 == 0)
			{		it = l.erase(it);
			}
			else
				++it;
		}
		it = l.begin();
		while (it != l.end())
		{	cout<< *it<< " ";
			++it;
		}
	}

	void listTest4()
	{listl;
		l.push_back(1);
		l.push_back(2);
		l.push_back(4);
		l.push_back(5);
		l.clear();
		l.push_back(1);
		l.push_back(2);
		l.push_back(4); 
		l.push_back(5);
		listl2 = l;
		list::iterator it = l2.begin();
		while (it != l2.end())
		{	cout<< *it<< " ";
			++it;
		}
	}


	void listTest5()
	{listl;
		l.push_back(Date(2022, 1, 3));
		l.push_back(Date(2022, 1, 4));
		l.push_back(Date(2022, 1, 5));

		list::iterator it = l.begin();
		while (it != l.end())
		{	cout<< it->_year<< "/"<_month<<"/"<_day<listl;
		l.push_back(Date(2022, 1, 3));
		l.push_back(Date(2022, 1, 4));
		l.push_back(Date(2022, 1, 5));

		list::reverse_iterator it = l.rbegin();
		while (it != l.rend())
		{	cout<< it->_year<< "/"<< it->_month<< "/"<< it->_day<< endl;
			++it;
		}

	}

}

反向迭代器代码:
reverse_iterator.h

#pragma once

templateclass _reverse_iterator
{typedef _reverse_iteratorself;
public:	
	_reverse_iterator(iterator it)
		:_it(it)
	{}
	//前置++
	self& operator++()
	{--_it;
		return *this;
	}
	//后置++
	self operator++(int)
	{self tmp(*this);
		--_it;
		return tmp;
	}

	//前置--
	self& operator--()
	{++_it;
		return *this;
	}
	//后置--
	self operator--(int)
	{self tmp(*this);
		++_it;
		return tmp;
	}

	Ref operator*()
	{iterator tmp = (*this)._it;
		return *(--tmp);
	}

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

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

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

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

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


private:
	iterator _it;
};

主程序代码:

#include"list.h"
void listTest()
{//wyl::listTest2();
	//wyl::listTest3();
	//wyl::listTest4();
	//wyl::listTest5();
	wyl::listTest6();

}

int main()
{listTest();

}
总结:

list的实现，其实最主要的部分还是迭代器。list的迭代器是比较特殊的，因为list在内存中不是连续存储的。以上代码都是我边打，边测试，没问题了才会发出来。如果有什么没测试到的错误，欢迎大家指出。以后会持续为大家更新STL的内容，以及数据结构，C语言，linux等方面的内容。感谢大家的支持，如果感觉写的还不错，麻烦给个三连嘛。我会多多努力的！

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


网站标题：【C++】STL---list的模拟实现-创新互联
标题路径：http://cdkjz.cn/article/jccpd.html
返回首页 了解更多建站资讯

相关资讯

多年建站经验

多一份参考，总有益处

联系快上网，免费获得专属《策划方案》及报价

咨询相关问题或预约面谈，可以通过以下方式与我们联系

大客户专线   成都：13518219792   座机：028-86922220

在线咨询 提交需求
友情链接 交换友情链接
成都网站建设建站公司成都网站优化重庆app软件开发一带一路网上商城管理系统成都广告设计成都网站建设手机网站制作网站优化公司

成都网站建设公司地址：成都市青羊区太升南路288号锦天国际A座10层 建设咨询028-86922220

成都快上网科技有限公司-四川网站建设设计公司 | 蜀ICP备19037934号 Copyright 2020,ALL Rights Reserved cdkjz.cn | 成都网站建设 | © Copyright 2020版权所有.

专家团队为您提供成都网站建设,成都网站设计,成都品牌网站设计,成都营销型网站制作等服务,成都建网站就找快上网！ | 成都网站建设哪家好？ | 网站建设地图