list类模板与vetcor有何不同

分手后的思念是犯贱 2022-10-22 04:14 249阅读 0赞

**在谈及二者不同之前，首先要先熟悉二者内部实现，二者内部如何实现将有助于我们进一步理解，对比优缺点**

**前期介绍了vector类模板的实现[vector类模板][vector]**

**接下来介绍list类模板模拟实现**

### list类模板 ###

list类实现基于带头双向循环链表，基于此结构完成基础结构搭建，定义模板类，其私有成员变量为\_head 头指针，不存储数据

private:
    	ListNode<T>* _head;

根据带头双向循环链表结构特点，头结点的下一个节点才开始存储数据，作为有效节点，对此需要定义Node节点结构体

template<class T>
    
    struct ListNode
    {
    	T _data;
    	ListNode<T>* _next;
    	ListNode<T>* _prev;
    
    	ListNode(const T& val = T())
    		:_data(val)
    		,_next(nullptr)
    		,_prev(nullptr)
    	{}
    };

**每一个Node节点包括三部分，一部分存放数据，一个指向前一个节点，一个指向下一节点**

**根据这个ListNode结构体，在list类中重命名ListNode结构体为Node，并将结构体指针重命名为PNode**

typedef ListNode<T> Node;
    	typedef Node* pNode;

*  ### 构造函数 ###

定义无参构造函数，但必须保证其带头双向循环链表的结构，对此

list()
    		:_head(new Node())
    	{
    		//构造循环结构
    		_head->_next = _head->_prev = _head;
    	}

保证头节点的下一节点以及前一节点指向均为头结点本身，具体的结构如果难以理解可以参考[带头双向循环链表][Link 1]

定义带参构造函数

list(size_t n,const T& val=T())
    		:_head(new Node())
    	{
    		//构造循环结构
    		_head->_next = _head->_prev = _head;
    		for (size_t i = 0; i < n; i++)
    		{
    			push_back(val);
    		}
    	}
    
    	void push_back(const T& val)
    	{
    		Node* newnode = new Node(val);
    		Node* tail = _head->_prev;
    
    		tail->_next = newnode;
    		newnode->_prev = tail;
    
    		newnode->_next = _head;
    		_head->_prev = newnode;
    	}

构造函数中传入的第一个参数为节点个数，第二个参数为节点值

在构造函数中依然需要维护带头双向循环链表结构，之后依次尾插新节点，通过带头双向循环链表结构可知，插入过程中不需要考虑仅存在一个头结点的情况，只有删除的情况才会考虑

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70][]

**测试结果如下：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 1][]

测试push\_back 依次插入数据，接下来依次观察其 next指向和prev指向，符合双向循环链表的结构

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 2][]

参数为迭代器的构造函数 通过类模板来实现 这样做的好处是具有泛型 传入参数可以不限制迭代器类型 但注意此时依然需要维持双向循环链表结构

template<class inputiterator>
    	list(inputiterator first, inputiterator last)
            :_head(new Node())
    	{
            //构造循环结构
    		_head->_next = _head->_prev = _head;
    		while (first != last)
    		{
    			push_back(*first);
    			first++;
    		}
    	}

**测试结果如下：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 3][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 4][]

插入字符类型 结尾字符为c 其next的指向为\_head ,值为；‘\\0’,满足双向循环链表结构

*  ### 析构函数 ###

~list()
    	{
    		//遍历  逐个释放资源
    		if (_head)
    		{
    			Node* cur = _head->_next;//从头的下一个开始
    			while (cur != _head)//由于循环结构 判断遍历一遍结束的标志  再次找到头结束
    			{
    				Node* next = cur->_next;
    				free(cur);
    				cur = next;
    			}
    			delete _head;//最后释放头结点
    			_head = nullptr;
    		}
    	}

类似于带头双向循环链表资源释放步骤，需要依次遍历到每一个节点进行资源释放，最后释放头结点

测试结果如下：

率先析构lst1，其中存储数据‘a’，‘b’，‘c’，依次析构，释放资源，最后释放头结点

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 5][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 6][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 7][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 8][]

未完待续。。。

[vector]: https://blog.csdn.net/qq_36131611/article/details/115329733
[Link 1]: https://blog.csdn.net/qq_36131611/article/details/111475641
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70]: /images/20221022/8ff2dabb22164729b554e8e38f01ccca.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 1]: /images/20221022/baa5d2291f0542a28cef8dd7088c4631.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 2]: /images/20221022/05577806103147bcb523f5682142edac.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 3]: /images/20221022/6b5592d600834af4866528a87b965661.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 4]: /images/20221022/aa3f936a9246429e9dcda0590f74c6d2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 5]: /images/20221022/99248ffad5d34059bac06d91ae604524.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 6]: /images/20221022/42f2a25bb719424ba651140fe16e2d26.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 7]: /images/20221022/9e5f4eef36304864932f1d562df29b6d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 8]: /images/20221022/cac52e50fd8c4dc9ae874ff1db2a85f4.png