C++_STL——list模拟实现-Toy模板网

这篇具有很好参考价值的文章主要介绍了C++_STL——list模拟实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

list作为一个容器组件，有着其重要的价值，其实在底层这是一个带头双向循环的链表数据结构，可以在任意位置进行插入和删除的序列式容器，并且该容器可以前后进行遍历。

那么同样作为序列式容器，list和vector相比又有哪些优缺点呢？

优点:对于在任意位置进行插入、删除操作，list的效率相对于vector是高很多的(这是由于vector在进行这些操作时需要移动数据进行覆盖)

缺点:list不支持任意位置的随机访问,这是由于list内部数据的存储方式并不是连续的，随机访问所需的代价较高，并且对缓存的利用率较低

因此，同样作为序列式容器，vector和list是优势互补，不可替代的，并且list在实际中的使用频率也很高，所以，为了更好的使用list，我们需要进行模拟实现。

list使用文档

在进行模拟实现之前，我们首先需要直到STL的list的各种使用接口以及其功能，然后才能高效的使用和模拟，下面是stl_list的使用文档及其说明：
list使用文档

模拟实现

节点struct

首先，我们直到对于带头双向循环链表来说，每个数据是存在一个节点中的，这个节点还要包括指向前一个节点和后一个节点的指针，所以我们需要用一个结构体来封装这些信息。

	template<typename T>
	struct list_node
	{
		list_node* next;
		list_node* prev;
		T val;
	};

类成员

在将要模拟实现的类中，我们想要找到所有的数据，只需要保存头节点即可，并且为了更简单的获得类的成员数量，可以在加一个size_t的_size成员标式数量。

	template<typename T>
	class list
	{
	private:
	    //这里为了方便，仿照源代码使用了typedef
	    //并且使用了c++11的缺省参数语法
		typedef list_node<T> link_node;
		link_node* _head = nullptr;
		size_t _size = 0;
	}

默认构造函数

带头双向循环链表的构造函数要求创建一个头节点，并且让其头节点的next和prev都指向自身。

		list()
			:_head(new link_node)
		{
			_head->next = _head;
			_head->prev = _head;
			_head->val = T();
		}

list的迭代器实现

我们知道，迭代器实现了stl容器和算法的分离，对于vector来说，迭代器使用原生的指针进行typedef来即可，但这是由于vector内部数据在物理空间上是连续的，但是对于list来说其数据在物理空间上并不是连续的，所以对于list来说，他的迭代器就不能是指针，而是一个类，通过重载运算符的方式，做到其使用方法能够和指针相同（对迭代器++使得指针指向next，–使得指针指向prev）下面是实现：

template<class T>
	struct __list_iterator
	{
		typedef list_node<T> Node;
		Node* _node;

		__list_iterator(Node* node)
			:_node(node)
		{}

		T& operator*()
		{
			return _node->_val;
		}
		
		T* operator->()
		{
			return &_node->_val;
		}

		__list_iterator<T>& operator++()
		{
			_node = _node->_next;
			return *this;
		}

		__list_iterator<T> operator++(int)
		{
			__list_iterator<T> tmp(*this);

			_node = _node->_next;

			return tmp;
		}

		bool operator!=(const __list_iterator<T>& it)
		{
			return _node != it._node;
		}

		bool operator==(const __list_iterator<T>& it)
		{
			return _node == it._node;
		}
	};

这里，有人可能会不知道operator->()函数有什么用，那么可以看下面的代码：

	lzz::list<pair<int, int>> lt;
	lt.push_back({ 1,1 });
	lt.push_back({ 2,2 });
	lt.push_back({ 3,3 });
	lt.push_back({ 4,4 });
	lt.push_back({ 5,5 });
	auto it = lt.begin();
	while (it != lt.end())
	{
		//这里其实应该是it->->first(it.operator->()->first)
		//c++为了代码观赏性，对其进行了优化
		cout << it->first << " " << it->second << endl;
		it++;
	}

对于结构体，为了使得使用方式和指针一样，所以重载了该运算符。并且由于list的数据结构进行随机访问是极为低效的**o(n)**的复杂度，所以list的迭代器并没有支持+功能。

那么又该如何设计const_iterator呢？通过分析我们会发现，对于const_iterator类，只有operator*()和operator->()函数需要修改返回值，其他则不需要变，如果重新写一个类命名为const_iterator，就过于冗余了，那么有什么更好的解决方法呢？
这里参考了库里的巧妙的实现方式，通过巧用模板完美的解决了这个问题，看下面代码：

//这里传输三个引用是为了让const引用和const指针能够不用重复设计
	template<typename T, typename Ref, typename Ptr>
	//为了便于在list里面使用迭代器，用struct而不是类
	struct __list_iterator
	{
		typedef list_node<T> Node;
		typedef __list_iterator<T, Ref, Ptr> self;
		/*迭代器成员*/
		Node* _node;
		//构造函数
		__list_iterator(Node* x = nullptr)
			:_node(x)
		{}
		//析构函数
		//不需要析构函数，根据需求，iterator消失并不代表数据消失
		Ref operator*() { return _node->val; }
		self& operator++()
		{
			_node = _node->next;
			//返回的都是iterator
			return *this;
		}
		//这里比较直接用const防止权限放大问题
		bool operator!=(const __list_iterator& it) { return _node != it._node; }
		Ptr operator->() { return &(_node->val); }
		self operator++(int)
		{
			self tmp(*this);
			_node = _node->next;
			return tmp;
		}
		bool operator==(const self& it) { return _node == it._node; }
		self& operator--()
		{
			_node = _node->prev;
			return *this;
		}
		self operator--(int)
		{
			self tmp(*this);
			_node = _node->prev;
			return tmp;
		}
	};

上面代码多传入了两个模板参数，分别是Ref和Ptr,并且分别用其替代了operator*()和operator->()的返回值，然后通过控制模板参数就可以控制返回值的类型了！
在类中可以使用typedef来进行使用，如下：

class list
{
	typedef __list_iterator<T, T&, T*> iterator;
	//错误的设计，类比vector<const int>
	//typedef __list_iterator<const T> const_iterator;
	//如果使用const T类型，就表示了内部指针不能够进行改变，那如何修改他指向下一个或上一个指针？
	typedef __list_iterator<T, const T&, const T*> const_iterator;
}

需要啥传啥，就能够进行更好的控制了！

begin(),end()

**begin()😗*直接返回头节点的下一个指针(第一个位置指向的指针)，利用隐式类型转换自动构造迭代器
**end()😗*直接返回头节点，利用隐式类型转换构造迭代器

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

list的增删查改等操作

insert，erase

对于链表来说，insert和erase操作都是在修改数据之间的链接关系罢了，大家可以画图理解，但是要注意链接前后关系

		iterator insert(const iterator& pos, const T& val)
		{
			link_node* tmp = new link_node;
			tmp->val = val;
			tmp->next = pos._node;
			tmp->prev = pos._node->prev;
			pos._node->prev->next = tmp;
			pos._node->prev = tmp;
			//记得维护_size
			++_size;
			return tmp;
		}
		iterator erase(iterator pos)
		{
			//不能删去头节点
			assert(pos != end());
			link_node* tmp = pos._node;
			tmp->prev->next = tmp->next;
			tmp->next->prev = tmp->prev;
			//别忘了释放空间
			++pos;
			delete tmp;
			--_size;
			return pos;
		}

头尾删插

对于这部分，可以直接复用insert和erase即可,这也是先实现insert和erase的原因

		void push_back(const T& val) { insert(end(), val); }
		void pop_back()
		{
			assert(!empty());
			erase(--end());
		}
		void push_front(const T& val) { insert(begin(), val); }
		void pop_front()
		{ 
			assert(!empty());
			erase(begin());
		}

同样由于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; }
size_t size() { return _size; }

clear()清空数据以及析构函数

在通过遍历一个个delete节点时，要记得先保存下一个节点，否则析构之后再使用当前节点就出现了野指针问题。

		void clear()
		{
			//不删除头节点
			link_node* del = _head->next;
			while (del != _head)
			{
				link_node* ne = del->next;
				delete del;
				del = ne;
			}
			_size = 0;
		}

析构与clear()的主要区别就是析构需要释放头节点，而clear()函数不需要清空，所以析构可以先调用clear()函数，然后再释放头节点即可。

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

完整模拟实现代码

#pragma once
#include<assert.h>
namespace lzz
{
	template<typename T>
	struct list_node
	{
		list_node* next;
		list_node* prev;
		T val;
	};

	//这里传输三个引用是为了让const引用和const指针能够不用重复设计
	template<typename T, typename Ref, typename Ptr>
	//为了便于在list里面使用迭代器，用struct而不是类
	struct __list_iterator
	{
		typedef list_node<T> Node;
		typedef __list_iterator<T, Ref, Ptr> self;
		/*迭代器成员*/
		Node* _node;
		//构造函数
		__list_iterator(Node* x = nullptr)
			:_node(x)
		{}
		//析构函数
		//不需要析构函数，根据需求，iterator消失并不代表数据消失
		Ref operator*() { return _node->val; }
		self& operator++()
		{
			_node = _node->next;
			//返回的都是iterator
			return *this;
		}
		//这里比较直接用const防止权限放大问题
		bool operator!=(const __list_iterator& it) { return _node != it._node; }
		Ptr operator->() { return &(_node->val); }
		self operator++(int)
		{
			self tmp(*this);
			_node = _node->next;
			return tmp;
		}
		bool operator==(const self& it) { return _node == it._node; }
		self& operator--()
		{
			_node = _node->prev;
			return *this;
		}
		self operator--(int)
		{
			self tmp(*this);
			_node = _node->prev;
			return tmp;
		}
	};

	template<typename T>
	class list
	{
	public:
		typedef __list_iterator<T, T&, T*> iterator;
		//错误的设计，类比vector<const int>
		//typedef __list_iterator<const T> const_iterator;
		typedef __list_iterator<T, const T&, const T*> const_iterator;
		typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;
		typedef Reverse_iterator <const_iterator, const T&, const T*> constReverseIterator;
	private:
		typedef list_node<T> link_node;
		link_node* _head = nullptr;
		size_t _size = 0;
	public:
		//void empty_init()
		//带头双向循环链表初始化
		list()
			:_head(new link_node)
		{
			_head->next = _head;
			_head->prev = _head;
			_head->val = T();
		}
		//这里用int是为了防止和之后的迭代器区间初始化产生冲突
		list(int n, const T& val = T())
			:list()
		{
			for (; _size < n;)
				push_back(val);
		}
		//深拷贝
		list(const list<T>& lt)
			:list()
		{
			for (auto& e : lt)
				push_back(e);
		}
		template<typename InputIterator>
		list(InputIterator first, InputIterator last)
			:list()
		{
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}
		void swap(list<T>& lt)
		{
			std::swap(_head, lt._head);
			std::swap(_size, lt._size);
		}
		list<T>& operator=(list<T> lt)
		{
			swap(lt);
			return *this;
		}
		//经典写法
		/*void push_back(const T& val)
		{
			link_node* tmp = new link_node;
			tmp->val = val;
			tmp->next = _head;
			_head->prev->next = tmp;
			tmp->prev = _head->prev;
			_head->prev = tmp;
		}*/
		bool empty() { return !_size; }
		//复用写法
		void push_back(const T& val) { insert(end(), val); }
		void pop_back()
		{
			assert(!empty());
			erase(--end());
		}
		void push_front(const T& val) { insert(begin(), val); }
		void pop_front()
		{ 
			assert(!empty());
			erase(begin());
		}

		iterator begin() { return _head->next; }
		iterator end() { return _head; }
		const_iterator begin() const { return const_iterator(_head->next); }
		const_iterator end() const { return const_iterator(_head); }
		iterator insert(const iterator& pos, const T& val)
		{
			link_node* tmp = new link_node;
			tmp->val = val;
			tmp->next = pos._node;
			tmp->prev = pos._node->prev;
			pos._node->prev->next = tmp;
			pos._node->prev = tmp;
			++_size;
			return tmp;
		}
		iterator erase(iterator pos)
		{
			//不能删去头节点
			assert(pos != end());
			link_node* tmp = pos._node;
			tmp->prev->next = tmp->next;
			tmp->next->prev = tmp->prev;
			//别忘了释放空间
			++pos;
			delete tmp;
			--_size;
			return pos;
		}
		size_t size() { return _size; }
		void clear()
		{
			//不删除头节点
			link_node* del = _head->next;
			while (del != _head)
			{
				link_node* ne = del->next;
				delete del;
				del = ne;
			}
			_size = 0;
		}
		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()
		{
			clear();
			delete _head;
			_head = nullptr;
		}
	};
}

总结

对于list底层和vector，string的底层模拟来说，最大的难点就时list的迭代器需要自己写一个类封装起来，而另两个由于数据存储空间连续直接使用原生指针即可，但是能使用指针的情况也就只有这两种，stl的其他容器的迭代器基本都是用类封装的，但这种设计思路大体时相同的，这也是stl设计的强大之处了！大家在以后学习其他stl容器时，会越来越体会到这种容器的巧妙的！
以上就是本篇博客模拟实现list的全部内容，如果还有不懂的或者作者写的有问题的地方，欢迎在评论区提出！文章来源地址https://www.toymoban.com/news/detail-604157.html

到了这里，关于C++_STL——list模拟实现的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！