【C++初阶】list的模拟实现附源码

た入场券 2024-04-22 12:12 83阅读 0赞

## 一.list介绍 ##

> list底层是一个双向带头循环链表，这个我们以前用C语言模拟实现过，->[双向带头循环链表][Link 1]

> 下面是list的文档介绍： [list文档介绍][list]
> 
> 我们会根据 list 的文档来模拟实现 list 的增删查改及其它接口。

![d5fb2210ec4149acac8da623b465904a.png][]

--------------------

## 二.list模拟实现思路 ##

> 既然是用C++模拟实现的，那么一定要封装在类里。
> 
> 为了适合各种类型的数据，会使用模板。

### 节点 Node ###

> 了解双向循环带头链表的都知道，我们需要一个节点 （Node），之前用C语言实现的时候，我们写了一个叫做 BuynewNode 的函数来获取节点，而在C++里我们用类封装一个，注意这个用 struct 封装比较好，因为 struct 默认是公有的，这样方便我们访问，所以可以写一个类：
> 
> **struct list\_node**

### 迭代器 iterator ###

> 我们知道，C++提供了一种统一的方式来访问容器，这就是迭代器，string 和 vector 的迭代器模拟实现很简单，因为 string 和 vector 底层是用数组实现的，数组是一段连续的物理空间，支持随机访问，所以它是天然的迭代器；
> 
> 但是链表不一样，它不是一段连续的物理空间，不支持随机访问，所以想让 list 的迭代器在表面上和 string，vector 的迭代器用起来没有区别，我们在底层上就需要用类封装迭代器，然后再迭代器类的内部，重载 ++ -- \* -> != == 这些迭代器会用到的运算符；
> 
> 所以创建一个迭代器类：
> 
> struct list\_iterator

### const 迭代器 const\_iterator ###

> 实现的普通的迭代器，还有 const 迭代器，const 迭代器的意思是让指针指向的内容不变，而指针本身可以改变，例如指针++，指针-- 这种操作，所以 const 迭代器与普通迭代器的不同只有 重载 \* 运算符的返回值不同，它是 const T& （T是模板参数），重写一个const 迭代器类又显得太冗余，代码的可读性就降低了；
> 
> 前面在学习模板时，我们知道不同的模板参数，编译器会生成不同的函数，所以我们选择加一个模板参数 ：Ref 。这样只要在显示实例化模板参数时：
> 
> 普通迭代器就传 T&；
> 
> const 迭代器就传 const T&；

### \-> 运算符重载 ###

看下面这段代码：

using namespace std;
    
    struct A
    {
    	A(int a1,int a2)
    		:_a1(a1)
    		,_a2(a2)
    	{}
    
    	int _a1;
    	int _a2;
    };
    
    void test_list()
    {
    	list<A> lt;   //实例化自定义类型
    	lt.push_back(A(1, 1));
    	lt.push_back(A(2, 2));
    	lt.push_back(A(3, 3));
    	lt.push_back(A(4, 4));
    
    	list<A>::iterator it = lt.begin();
    
    	while (it != lt.end())
    	{
    		cout << it->_a1 << " " << it->_a2 << endl;  //像指针一样访问自定义类型里的成员变量
    		it++;
    	}	
    }
    
    int main()
    {
    	test_list();
    
    	return 0;
    }

> 有时候，实例化的模板参数是自定义类型，我们想要像指针一样访问访问自定义类型力的成员变量，这样显得更通俗易懂，所以就要重载 -> 运算符，它的返回值是 T\* ，但是正常来说这里应该是这样访问的： it -> -> \_a1
> 
> 因为迭代器指向的是 整个自定义类型，要想再访问其内部成员应该再使用一次 -> （这个->就不是重载的 -> ，就是普通的 -> ），但是上面的代码为什么就写了一个 -> ，这个是C++语法把这里特殊化了。

> 那该怎么在迭代器类里重载 -> 运算符呢？
> 
> 和const 迭代器一样，只需要再加一个模板参数 ：Ptr
> 
> 显示实例化的时候传 T\* 就行了。

### 迭代器类 模拟实现源码： struct list\_iterator ###

> 以上的都算 list 模拟实现的难点，其他的像 重载 ++ 什么的，对于学过数据结构的小伙伴们是非常简单的，就不赘述了，没学过的可以看看这篇文章：[双向带头循环链表][Link 1]

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)
    		{}
    
    		//重载 * ++ -- != == ->
    		Ref operator*() const
    		{
    			return _node->_val;
    		}
    
    		Ptr operator->() const
    		{
    			return &_node->_val;
    		}
    
    		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& lt) const
    		{
    			return _node != lt._node;
    		}
    
    		bool operator==(const self& lt) const
    		{
    			return _node == lt._node;
    		}
    
    	};

### list ###

> 我们在用C语言实现双向带头循环链表时，会先初始化链表的头（head），即让它的 前驱指针（prev）和后继指针（next）都指向自己；
> 
> 在C++的模拟实现 list 中，我们会创建一个类 list 来管理链表的节点并实现增删查改及其它接口，所以 list 的构建函数就是初始化 头（head）节点。

--------------------

## 三.源码 ##

### list.h ###

### ![8ee880f210f14b6e9d631e620ccf56b8.png][] ###

![1d1920295f2b49c19fe8c32db384abc0.png][]

![2f9f4fd4e27341e59f4106ef47f10920.png][]

> 我们可以模拟实现以上接口，具体函数的逻辑可以查阅文档，实现起来都是很简单的。

namespace nagi   //把模拟实现list的类都放在一个命名空间里封装起来
    {
    	template<class T>
    	struct list_node   //创建节点
    	{
    		list_node<T>* _prev;
    		list_node<T>* _next;
    		T _val;
    
    		list_node(const T& val = T())  //构造函数，初始化节点
    			:_prev(nullptr)
    			,_next(nullptr)
    			,_val(val)
    		{}
    
    	};
    
    	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)
    		{}
    
    		//重载 * ++ -- != == ->
    		Ref operator*() const
    		{
    			return _node->_val;
    		}
    
    		Ptr operator->() const
    		{
    			return &_node->_val;
    		}
    
    		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& lt) const
    		{
    			return _node != lt._node;
    		}
    
    		bool operator==(const self& lt) const
    		{
    			return _node == lt._node;
    		}
    
    	};
    
    	template<class T>
    	class list
    	{
    		typedef list_node<T> Node;
    	public:
    		typedef list_iterator<T, T&, T*> iterator;  //重命名普通迭代器
    		typedef list_iterator<T, const T&, const T*> const_iterator;  //重命名const迭代器
    
    		void empty_init()  //因为构造函数和拷贝构造都会初始化头节点，所以就写成一个函数了
    		{
    			_head = new Node;
    			_head->_prev = _head;
    			_head->_next = _head;
    			_sz = 0;
    		}
    
    		list()  //构造函数
    		{
    			empty_init();
    		}
    		//普通迭代器
    		iterator begin()
    		{
    			return _head->_next;
    		}
    
    		iterator end()
    		{
    			return _head;
    		}
    		//const迭代器
    		const_iterator begin() const
    		{
    			return _head->_next;
    		}
    
    		const_iterator end() const
    		{
    			return _head;
    		}
    
    		iterator insert(iterator pos, const T& x)  //在pos之前插入
    		{
    			Node* newnode = new Node(x);
    			Node* cur = pos._node;
    			Node* prev = cur->_prev;
    			prev->_next = newnode;
    			newnode->_prev = prev;
    			newnode->_next = cur;
    			cur->_prev = newnode;
    			_sz++;
    
    			return newnode;
    		}
    
    		iterator erase(iterator pos)   //删除pos位置，注意删除的时候不能把头节点也删了，所以要做pos检查
    		{
    			assert(pos != end());
    
    			Node* cur = pos._node;
    			Node* prev = cur->_prev;
    			Node* next = cur->_next;
    
    			prev->_next = next;
    			next->_prev = prev;
    
    			delete cur;
    			_sz--;
    
    			return next;   //库里规定返回删除节点的下一个节点
    		}
    
    		void push_back(const T& x)  //尾插
    		{
    			insert(end(), x);
    		}
    
    		void push_front(const T& x)  //头插
    		{
    			insert(begin(), x);
    		}
    
    		void pop_back()  //尾删
    		{
    			erase(--end());
    		}
    
    		void pop_front()  //头删
    		{
    			erase(begin());
    		}
    
    		void clear()  //清楚除了头节点以外的所有节点
    		{
    			iterator it = begin();
    			while (it != end())
    			{
    				it=erase(it);
    				
    			}
    			_sz = 0;
    		}
    
    		~list()  //析构函数
    		{
    			clear();
    
    			delete _head;
    			_head = nullptr;
    		}
    
    		list(const list<T>& lt)   //拷贝构造
    		{
    			empty_init();
    
    			for (auto& e : lt)
    			{
    				push_back(e);
    			}
    			
    		}
    
    		void swap(list<T>& lt)
    		{
    			std::swap(_head, lt._head);
    			std::swap(_sz, lt._sz);
    		}
    
    		list<T>& operator=(list<T> lt)  //赋值重载
    		{
    			swap(lt);
    
    			return *this;
    		}
    
    	private:
    		Node* _head;  //头节点
    		size_t _sz;   //记录链表的长度
    	};
    
    }

--------------------

> **??本篇文章到此就结束了， 若有错误或是建议的话，欢迎小伙伴们指出；?️?**
> 
> **??希望小伙伴们能支持支持博主啊，你们的支持对我很重要哦；??**
> 
> **??谢谢你的阅读。??**

[Link 1]: http://t.csdn.cn/egQQA
[list]: https://legacy.cplusplus.com/reference/list/list/?kw=list
[d5fb2210ec4149acac8da623b465904a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/482c125574cb4c029fcd8ab0ef9c973d.png
[8ee880f210f14b6e9d631e620ccf56b8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/79b9e2ab24434e28a74e7af4696a728b.png
[1d1920295f2b49c19fe8c32db384abc0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/efb76e0b08c74333a5a662094180bc86.png
[2f9f4fd4e27341e59f4106ef47f10920.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/75e32b7cf66c4b82b75e1377d6a01aec.png