【C++从青铜到王者】第十一篇:STL之list类的初识

阳光穿透心脏的1/2处 2023-01-23 04:51 25阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center]

# 系列文章目录 #

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

### 文章目录 ###

*  系列文章目录
 *  前言
 *  一、 list的介绍及使用
 *   *   *  1.list的介绍
         *  2.list的使用
         *   *  1.list的构造
             *  2.list iterator的使用
             *  3.list capacity的使用
             *  4.list element access的使用
             *  5.list modifiers的使用
             *  6.list modifiers的迭代器失效
 *  总结

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

# 前言 #

![在这里插入图片描述][20210712234453517.png_pic_left]

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

# 一、 list的介绍及使用 #

![在这里插入图片描述][20210712232744772.png]

### 1.list的介绍 ###

[list文档介绍][list]

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

### 2.list的使用 ###

#### 1.list的构造 ####

**list中的接口比较多，此处类似，只需要掌握如何正确的使用，然后再去深入研究背后的原理，已达到可扩展的能力。以下为list中一些常见的重要接口。**

<table> 
 <thead> 
  <tr> 
   <th>构造函数</th> 
   <th>接口说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>list()</td> 
   <td>构造空的list</td> 
  </tr> 
  <tr> 
   <td>list (size_type n, const value_type&amp; val = value_type())</td> 
   <td>构造的list中包含n个值为val的元素</td> 
  </tr> 
  <tr> 
   <td>list (const list&amp; x)</td> 
   <td>拷贝构造函数</td> 
  </tr> 
  <tr> 
   <td>list (InputIterator first, InputIterator last)</td> 
   <td>用[first, last)区间中的元素构造list</td> 
  </tr> 
 </tbody> 
</table>

void testlist2()
    { 
    	list<int>lt1;
    	lt1.push_back(1);
    	lt1.push_back(2);
    	lt1.push_back(3);
    	lt1.push_back(4);
    	lt1.push_front(10);
    	lt1.push_front(20);
    
    	list<int>lt2(lt1);                   //拷贝构造 
    	list<int>::iterator it = lt2.begin();
    	while (it != lt2.end())
    	{ 
    		cout << *it << " ";
    		it++;
    	}
    	cout << endl;
    	print_list(lt2);
    
    	list<int> lt3;
    	lt3 = lt2;                         //赋值运算符重载
    	print_list(lt3);  
    	for (auto e : lt3)                 //支持迭代器就支持范围for,范围for就是标准的begin，end演化而来
    	{ 
    		cout << e << " ";
    	}
    	cout << endl;
    
    	list<int>::reverse_iterator rit = lt3.rbegin();
    	while (rit != lt3.rend())
    	{ 
    		cout << *rit << " ";
    		rit++;
    	}
    	cout << endl;

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 1]

#### 2.list iterator的使用 ####

**此处，大家可暂时将迭代器理解成一个指针，该指针指向list中的某个节点。**

<table> 
 <thead> 
  <tr> 
   <th>函数声明</th> 
   <th>接口说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>begin()+end()</td> 
   <td>返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器</td> 
  </tr> 
  <tr> 
   <td>rbegin()+rend()</td> 
   <td>返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的reverse_iterator,即begin位置</td> 
  </tr> 
 </tbody> 
</table>

void testlist1()
    { 
    	//带头双向循环链表
    	list<int> l;
    	l.push_back(1);
    	l.push_back(2);
    	l.push_back(3);
    	l.push_back(4);
    	l.push_front(10);
    	l.push_front(20);
    	l.pop_back();
    	l.pop_front();
    	list<int>::iterator it = l.begin();
    	while (it != l.end())
    	{ 
    		*it += 1;
    		cout << *it << " ";
    		it++;
    	}
    	cout << endl;
    	list<int>::reverse_iterator  vit = l.rbegin();
    	while (vit != l.rend())
    	{ 
    		cout << *vit << " ";
    		vit++;
    	}
    	cout << endl;
    
    	//const list<int>l;
    	list<int>::const_iterator cit = l.begin();
    	while (cit != l.end())
    	{ 
    		//*cit += 1;
    		cout << *cit << " ";
    		cit++;
    	}
    	cout << endl;
    }
    void print_list(const list<int>& lt)//传引用，提高效率，减少拷贝,const迭代器只可以读
    { 
    	list<int>::const_iterator it = lt.begin();
    	while (it != lt.end())
    	{ 
    		cout << *it << " ";
    		it++;
    	}
    	cout << endl;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 2]

#### 3.list capacity的使用 ####

<table> 
 <thead> 
  <tr> 
   <th>函数声明</th> 
   <th>接口声明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>size()</td> 
   <td>检测list是否为空，是返回true，否则返回false</td> 
  </tr> 
  <tr> 
   <td>empty()</td> 
   <td>返回list中有效节点的个数</td> 
  </tr> 
 </tbody> 
</table>

void testlist3()
    { 
    	list<int>lt1;
    	lt1.push_back(1);
    	lt1.push_back(2);
    	lt1.push_back(3);
    	lt1.push_back(4);
    	lt1.push_front(10);
    	lt1.push_front(20);
    	cout << lt1.size() << endl;
    	cout << lt1.empty() << endl;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 3]

#### 4.list element access的使用 ####

<table> 
 <thead> 
  <tr> 
   <th>函数声明</th> 
   <th>接口说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>front</td> 
   <td>返回list的第一个节点中值的引用</td> 
  </tr> 
  <tr> 
   <td>back</td> 
   <td>返回list的最后一个节点中值的引用</td> 
  </tr> 
 </tbody> 
</table>

#### 5.list modifiers的使用 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 5]

void testlist4()
    { 
    	list<int>lt1;
    	lt1.push_back(1);
    	lt1.push_back(2);
    	lt1.push_front(10);
    	lt1.push_front(20);
    	print_list(lt1);
    
    	lt1.pop_back();
    	lt1.pop_front();
    	print_list(lt1);
    
    	lt1.insert(lt1.begin(), 10);
    	lt1.insert(lt1.end(), 20);
    	print_list(lt1);
    
    	list<int>::iterator pos = find(lt1.begin(), lt1.end(), 1);   //查找算法，双向迭代器list不支持下标访问
    	if (pos != lt1.end())
    	{ 
    		lt1.insert(pos, 100);  //insert在pos位置的前面插入
    	}
    	print_list(lt1);
    	
    	lt1.erase(pos);
    	print_list(lt1);
    
    	lt1.erase(lt1.begin(), lt1.end());
    	print_list(lt1);
    
    	lt1.clear();
    	print_list(lt1);
    
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 6]

void testlist5()
    { 
    	list<int>lt1;
    	lt1.push_back(20);
    	lt1.push_back(10);
    	lt1.push_back(30);
    	lt1.push_front(40);
    	print_list(lt1);
    
    	lt1.sort();
    	print_list(lt1);
    
    	lt1.reverse();
    	for (auto e : lt1)
    	{ 
    		cout << e << " ";
    	}
    	cout << endl;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 7]

#### 6.list modifiers的迭代器失效 ####

**前面说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 8]

void testlist6()
    { 
    	list<int>lt1;
    	lt1.push_back(1);
    	lt1.push_back(2);
    	lt1.push_front(10);
    	lt1.push_front(20);
    	print_list(lt1);
    	
    	//list<int>::iterator it = lt1.begin(); //list不能erase，会造成迭代器失效问题
    	//while (it != lt1.end())
    	//{ 
    	// if (*it % 2 == 0)
    	// { 
    	// lt1.erase(it);
    	// }
    	// it++;
    	//}
    	//print_list(lt1);
    
    	list<int>::iterator it = lt1.begin();   //list不能erase，会造成迭代器失效问题,解决方法对迭代器重新赋值
    	while (it != lt1.end())
    	{ 
    		if (*it % 2 == 0)
    		{ 
    			it = lt1.erase(it);
    		}
    		else
    		{ 
    			it++;
    		}
    	}
    	print_list(lt1);
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 9]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 10]

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

# 总结 #

以上就是今天要讲的内容，本文简单介绍了list类的介绍和用法，而list类提供了大量能使我们快速便捷地处理数据的函数和方法，非常的便捷，所以我们务必掌握。另外如果上述有任何问题，请懂哥指教，不过没关系，主要是自己能坚持，更希望有一起学习的同学可以帮我指正，但是如果可以请温柔一点跟我讲，爱与和平是永远的主题，爱各位了。  
![在这里插入图片描述][20210712232154179.jpg_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221004/4bcfb1a47b114064a7c4c1b7eaf3c8a4.png
[20210712234453517.png_pic_left]: /images/20221004/ca683d049a6848d49d69391a79a1fe58.png
[20210712232744772.png]: /images/20221004/5f9627fc0206460786e1167e0b81e129.png
[list]: http://www.cplusplus.com/reference/list/list/?kw=list
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70]: /images/20221004/7489af43f2cd437f81198dfaf7d679c9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 1]: /images/20221004/316a88d687cb4a6e844df371fc79e839.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 2]: /images/20221004/c7268448b5504856a6ff5465447e561e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 3]: /images/20221004/7226a0f20afd43298f317bc4412023ee.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 4]: /images/20221004/872937957295496fa02cfc2ea0cfe733.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 5]: /images/20221004/71b1b88c44f147e3828154b7c10e15cf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 6]: /images/20221004/3319d5f8907f490d85e5b4c9004d47de.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 7]: /images/20221004/999cce07ac9c4409b401fac370adc955.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 8]: /images/20221004/c96cdd25cbe2419d9e6c3735f5bab20d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 9]: /images/20221004/0b85df3dba19485fb7ff17931fac012b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 10]: /images/20221004/cae603ffc5d642f3a311bcf5147d761b.png
[20210712232154179.jpg_pic_center]: /images/20221004/dac4f6e3dc2b4f3c8ba09b20130d88b5.png