STL中list的基本用法以及模拟实现

￡神魔★判官ぃ 2023-09-28 14:50 119阅读 0赞

### STL中list的基本用法以及模拟实现 ###

*  一、list的介绍以及使用
 *   *  1、list的介绍
     *  2、list的使用
     *   *  2.1 list的构造
         *  2.2 list iterator的使用
         *  2.3 list 容量函数
         *  2.4 list 的元素获取
         *  2.5 list 的修改
         *  2.6 list 的迭代器失效
 *  二、list的模拟实现
 *   *  1、模拟实现list的迭代器类以及结点类
     *  2、list的模拟实现代码
 *  三、list与vector的比较

# 一、list的介绍以及使用 #

## 1、list的介绍 ##

[list文档阅读][list]

1.  list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
2.  list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
3.  list与forward\_list非常相似：最主要的不同在于forward\_list是单链表，只能朝前迭代，已让其更简单高效。
4.  与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
5.  与其他序列式容器相比，list和forward\_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)

图示：  
![98d76484383f46338c86eabf6464bb00.png][]

## 2、list的使用 ##

### 2.1 list的构造 ###

<table> 
 <thead> 
  <tr> 
   <th align="left"><a href="https://cplusplus.com/reference/list/list/list/" rel="nofollow">构造函数</a></th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left">list()</td> 
   <td>构造空的list</td> 
  </tr> 
  <tr> 
   <td align="left">list (size_type n, const value_type&amp; val = value_type())</td> 
   <td>构造的list中包含n个值为val的元素</td> 
  </tr> 
  <tr> 
   <td align="left">list (const list&amp; x)</td> 
   <td>拷贝构造函数</td> 
  </tr> 
  <tr> 
   <td align="left">list (InputIterator first, InputIterator last)</td> 
   <td>用[first, last)区间中的元素构造list</td> 
  </tr> 
 </tbody> 
</table>

#include <iostream>
    #include <list>
    int main ()
    {
        
    	std::list<int> l1; // 构造空的l1
    	std::list<int> l2 (4,100); // l2中放4个值为100的元素
    	std::list<int> l3 (l2.begin(), l2.end()); // 用l2的[begin(), end()）左闭右开的区间构造l3
    	std::list<int> l4 (l3); // 用l3拷贝构造l4
    	// 以数组为迭代器区间构造l5
    	int array[] = {
        16,2,77,29};
    	std::list<int> l5 (array, array + sizeof(array) / sizeof(int) );
    	// 用迭代器方式打印l5中的元素
    	for(std::list<int>::iterator it = l5.begin(); it != l5.end(); it++)
    		std::cout << *it << " ";
    	std::cout<<endl;
    	// C++11范围for的方式遍历
    	for(auto& e : l5)
    		std::cout<< e << " ";
    	std::cout<<endl;
    	return 0;
    }

### 2.2 list iterator的使用 ###

<table> 
 <thead> 
  <tr> 
   <th align="left">函数声明</th> 
   <th>接口说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left"><a href="https://cplusplus.com/reference/list/list/begin/" rel="nofollow">begin</a> +<a href="https://cplusplus.com/reference/list/list/end/" rel="nofollow">end</a></td> 
   <td>返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器</td> 
  </tr> 
  <tr> 
   <td align="left"><a href="https://cplusplus.com/reference/list/list/rbegin/" rel="nofollow">rbegin</a> + <a href="https://cplusplus.com/reference/list/list/rend/" rel="nofollow">rend</a></td> 
   <td>返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的reverse_iterator,即begin位置</td> 
  </tr> 
 </tbody> 
</table>

图示：  
![45b2ecdbe6c648c4bf59dad59c957ca5.png][]

【注意】

1.  begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
2.  rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动

#include <iostream>
    using namespace std;
    #include <list>
    void print_list(const list<int>& l)
    {
        
    // 注意这里调用的是list的 begin() const，返回list的const_iterator对象
    for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it)
    {
        
    cout << *it << " ";
    // *it = 10; 编译不通过
    }
    cout << endl;
    }
    int main()
    {
        
    	int array[] = {
         1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    	list<int> l(array, array + sizeof(array) / sizeof(array[0]));
    	// 使用正向迭代器正向list中的元素
    	for (list<int>::iterator it = l.begin(); it != l.end(); ++it)
    		cout << *it << " ";
    	cout << endl;
    	// 使用反向迭代器逆向打印list中的元素
    	for (list<int>::reverse_iterator it = l.rbegin(); it != l.rend(); ++it)
    		cout << *it << " ";
    	cout << endl;
    	return 0;
    }

### 2.3 list 容量函数 ###

<table> 
 <thead> 
  <tr> 
   <th align="left">函数声明</th> 
   <th>接口说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left"><a href="https://cplusplus.com/reference/list/list/empty/" rel="nofollow">empty</a></td> 
   <td>检测list是否为空，是返回true，否则返回false</td> 
  </tr> 
  <tr> 
   <td align="left"><a href="https://cplusplus.com/reference/list/list/size/" rel="nofollow">size</a></td> 
   <td>返回list中有效节点的个数</td> 
  </tr> 
 </tbody> 
</table>

### 2.4 list 的元素获取 ###

<table> 
 <thead> 
  <tr> 
   <th align="left">函数声明</th> 
   <th>接口说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left"><a href="https://cplusplus.com/reference/list/list/front/" rel="nofollow">front</a></td> 
   <td>返回list的第一个节点中值的引用</td> 
  </tr> 
  <tr> 
   <td align="left"><a href="https://cplusplus.com/reference/list/list/back/" rel="nofollow">back</a></td> 
   <td>返回list的最后一个节点中值的引用</td> 
  </tr> 
 </tbody> 
</table>

### 2.5 list 的修改 ###

<table> 
 <thead> 
  <tr> 
   <th align="left">函数声明</th> 
   <th>接口说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left"><a href="https://cplusplus.com/reference/list/list/push_front/" rel="nofollow">push_front</a></td> 
   <td>在list首元素前插入值为val的元素</td> 
  </tr> 
  <tr> 
   <td align="left"><a href="https://cplusplus.com/reference/list/list/pop_front/" rel="nofollow">pop_front</a></td> 
   <td>删除list中第一个元素</td> 
  </tr> 
  <tr> 
   <td align="left"><a href="https://cplusplus.com/reference/list/list/push_back/" rel="nofollow">push_back</a></td> 
   <td>在list尾部插入值为val的元素</td> 
  </tr> 
  <tr> 
   <td align="left"><a href="https://cplusplus.com/reference/list/list/pop_back/" rel="nofollow">pop_back</a></td> 
   <td>删除list中最后一个元素</td> 
  </tr> 
  <tr> 
   <td align="left"><a href="https://cplusplus.com/reference/list/list/insert/" rel="nofollow">insert</a></td> 
   <td>在list position 位置中插入值为val的元素</td> 
  </tr> 
  <tr> 
   <td align="left"><a href="https://cplusplus.com/reference/list/list/erase/" rel="nofollow">erase</a></td> 
   <td>删除list position位置的元素</td> 
  </tr> 
  <tr> 
   <td align="left"><a href="https://cplusplus.com/reference/list/list/swap/" rel="nofollow">swap</a></td> 
   <td>交换两个list中的元素</td> 
  </tr> 
  <tr> 
   <td align="left"><a href="https://cplusplus.com/reference/list/list/clear/" rel="nofollow">clear</a></td> 
   <td>清空list中的有效元素</td> 
  </tr> 
 </tbody> 
</table>

测试代码：

#include <list>
    void PrintList(list<int>& l)
    {
        
    	for (auto& e : l)
    	cout << e << " ";
    	cout << endl;
    }
    //=========================================================================================
    // push_back/pop_back/push_front/pop_front
    void TestList1()
    {
        
    	int array[] = {
         1, 2, 3 };
    	list<int> L(array, array+sizeof(array)/sizeof(array[0]));
    	// 在list的尾部插入4，头部插入0
    	L.push_back(4);
    	L.push_front(0);
    	PrintList(L);
    	// 删除list尾部节点和头部节点
    	L.pop_back();
    	L.pop_front();
    	PrintList(L);
    }
    //=========================================================================================
    // insert /erase
    void TestList3()
    {
        
    	int array1[] = {
         1, 2, 3 };
    	list<int> L(array1, array1+sizeof(array1)/sizeof(array1[0]));
    	// 获取链表中第二个节点
    	auto pos = ++L.begin();
    	cout << *pos << endl;
    	// 在pos前插入值为4的元素
    	L.insert(pos, 4);
    	PrintList(L);
    	// 在pos前插入5个值为5的元素
    	L.insert(pos, 5, 5);
    	PrintList(L);
    	// 在pos前插入[v.begin(), v.end)区间中的元素
    	vector<int> v{
         7, 8, 9 };
    	L.insert(pos, v.begin(), v.end());
    	PrintList(L);
    	// 删除pos位置上的元素
    	L.erase(pos);
    	PrintList(L);
    	// 删除list中[begin, end)区间中的元素，即删除list中的所有元素
    	L.erase(L.begin(), L.end());
    	PrintList(L);
    }
    //=========================================================================================
    // resize/swap/clear
    void TestList4()
    {
        
    	// 用数组来构造list
    	int array1[] = {
         1, 2, 3 };
    	list<int> l1(array1, array1+sizeof(array1)/sizeof(array1[0]));
    	PrintList(l1);
    	// 交换l1和l2中的元素
    	l1.swap(l2);
    	PrintList(l1);
    	PrintList(l2);
    	// 将l2中的元素清空
    	l2.clear();
    	cout<<l2.size()<<endl;
    }

### 2.6 list 的迭代器失效 ###

迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。**因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。**

例如：

void TestListIterator1()
    {
        
    	int array[] = {
         1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    	list<int> l(array, array+sizeof(array)/sizeof(array[0]));
    	auto it = l.begin();
    	while (it != l.end())
    	{
        
    		// erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给其赋值
    		l.erase(it);
    		++it;
    	}
    }
    // 改正
    void TestListIterator()
    {
        
    	int array[] = {
         1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    	list<int> l(array, array+sizeof(array)/sizeof(array[0]));
    	auto it = l.begin();
    	while (it != l.end())
    	{
        
    		l.erase(it++); // it = l.erase(it);
    	}
    }

# 二、list的模拟实现 #

## 1、模拟实现list的迭代器类以及结点类 ##

结点类：

template<class T>
    	struct list_node
    	{
        
    		list_node<T>* _next;
    		list_node<T>* _prev;
    		T _data;
    
    		list_node(const T& val = T())
    			:_next(nullptr)
    			,_prev(nullptr)
    			,_data(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*()
    		{
        
    			return _node->_data;
    		}
    
    		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;
    		}
    	};

## 2、list的模拟实现代码 ##

#pragma once
    #include<assert.h>
    #include<iostream>
    
    
    namespace my_list
    {
        
    	template<class T>
    	struct list_node
    	{
        
    		list_node<T>* _next;
    		list_node<T>* _prev;
    		T _data;
    
    		list_node(const T& val = T())
    			:_next(nullptr)
    			,_prev(nullptr)
    			,_data(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*()
    		{
        
    			return _node->_data;
    		}
    
    		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 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_iterator begin()const 
    		{
        
    			return const_iterator(_head->_next);
    			//return _head->_next;
    		}
    
    		const_iterator end()const
    		{
        
    			return const_iterator(_head);
    		}
    
    		iterator begin()
    		{
        
    			return iterator(_head->_next);
    			//return _head->_next;
    		}
    
    		iterator end()
    		{
        
    			return iterator(_head);
    		}
    
    		void swap(list<T>& lt)
    		{
        
    			std::swap(_head, lt._head);
    		}
    
    		void empty_init()
    		{
        
    			_head = new Node();
    			_head->_next = _head;
    			_head->_prev = _head;
    		}
    
    
    		list()
    		{
        
    			empty_init();
    		}
    		
    		template<class InputIterator>
    		list(InputIterator first, InputIterator last)
    		{
        
    			empty_init();
    
    			while (first != last)
    			{
        
    				push_back(*first);
    				++first;
    			}
    		}
    
    		list(const list<T>& lt)
    		{
        
    			empty_init();
    			list<T> tmp(lt.begin(), lt.end());
    			swap(tmp);
    		}
    
    		list<T>& operator=(list<T> lt)
    		{
        
    			swap(lt);
    			return *this;
    		}
    
    		~list()
    		{
        
    			clear();
    			delete _head;
    			_head = nullptr;
    		}
    
    		void clear()
    		{
        
    			iterator it = begin();
    			while (it != end())
    			{
        
    				it = erase(it);
    			}
    		}
    
    		void push_back(const T& x)
    		{
        
    			//Node* tail = _head->_prev;
    			//Node* newnode = new Node(x);
    
    			//tail->_next = newnode;
    			//newnode->_next = tail;
    			//newnode->_next = _head;
    			//_head->_prev = newnode;
    
    			insert(end(), x);
    		}
    
    		void push_front(const T& x)
    		{
        
    			insert(begin(), x);
    		}
    
    		void pop_back()
    		{
        
    			erase(--end());
    		}
    
    		void pop_front()
    		{
        
    			erase(begin());
    		}
    
    		//pos前插入x
    		iterator insert(iterator pos, const T& x)
    		{
        
    			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;
    
    			return iterator(newnode);
    		}
    
    		iterator erase(iterator pos)
    		{
        
    			assert(pos != end());
    
    			Node* cur = pos._node;
    			Node* next = cur->_next;
    			Node* prev = cur->_prev;
    
    			prev->_next = next;
    			next->_prev = prev;
    			delete cur;
    
    			return iterator(next);
    		}
    
    	private:
    		Node* _head;
    	};
    }

# 三、list与vector的比较 #

vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不同，其主要不同如下：

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th align="left">vector</th> 
   <th align="left">list</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>底层结构</td> 
   <td align="left">动态顺序表，一段连续空间</td> 
   <td align="left">带头结点的双向循环列表</td> 
  </tr> 
  <tr> 
   <td>随机访问</td> 
   <td align="left">支持随机访问，访问某个元素的效率为O(1)</td> 
   <td align="left">不支持随机访问，访问某个元素的时间效率为O(N)</td> 
  </tr> 
  <tr> 
   <td>插入和删除</td> 
   <td align="left">任意位置插入和删除效率低，需要挪动数据，时间复杂度为O(N)，插入时可能需要增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低</td> 
   <td align="left">任意位置插入和删除效率高，不需要挪动数据，时间复杂度为O(1)</td> 
  </tr> 
  <tr> 
   <td>空间利用率</td> 
   <td align="left">底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高</td> 
   <td align="left">底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低</td> 
  </tr> 
  <tr> 
   <td>迭代器</td> 
   <td align="left">原生态指针</td> 
   <td align="left">对原生态指针(节点指针)进行封装</td> 
  </tr> 
  <tr> 
   <td>迭代器失效</td> 
   <td align="left">在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效</td> 
   <td align="left">插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响</td> 
  </tr> 
  <tr> 
   <td>使用场景</td> 
   <td align="left">需要高效存储，支持随机访问，不关心插入删除效率</td> 
   <td align="left">大量插入和删除操作，不关心随机访问</td> 
  </tr> 
 </tbody> 
</table>

[list]: https://cplusplus.com/reference/list/list/?kw=list
[98d76484383f46338c86eabf6464bb00.png]: https://img-blog.csdnimg.cn/98d76484383f46338c86eabf6464bb00.png
[45b2ecdbe6c648c4bf59dad59c957ca5.png]: https://img-blog.csdnimg.cn/45b2ecdbe6c648c4bf59dad59c957ca5.png