• ＜list＞——《C++初阶》

    目录

    1. list的介绍及使用

    1.1 list的介绍

    1.2 list的使用

     1.2.1 list的构造

     1.2.2 list iterator的使用

     1.2.3 list capacity

     1.2.4 list element access

     1.2.5 list modififiers

     1.2.6 list的迭代器失效

    后记：●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！                                                                  ——By 作者：新晓·故知

    1. list的介绍及使用

    1.1 list的介绍

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

     

    1.2 list的使用

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

    1.2.1 list的构造

    构造函数（ (constructor)）
    接口说明
    list()
    构造空的list
    list (size_type n, const value_type& val = value_type())
    构造的list中包含n个值为val的元素
    list (const list& x)  
    		拷贝构造函数
    list (InputIterator fifirst, InputIterator last)
    用[fifirst, last)区间中的元素构造list 

    1. // constructing lists
    2. #include 
    3. #include 
    4. using namespace std;
    5. int main()
    6. {
    7. 	std::list<int> l1; // 构造空的l1
    8. 	std::list<int> l2(4, 100); // l2中放4个值为100的元素
    9. 	std::list<int> l3(l2.begin(), l2.end()); // 用l2的[begin(), end()）左闭右开的区间构造l3
    10. 	std::list<int> l4(l3); // 用l3拷贝构造l4
    11. 	// 以数组为迭代器区间构造l5
    12. 	int array[] = { 16,2,77,29 };
    13. 	std::list<int> l5(array, array + sizeof(array) / sizeof(int));
    14. 	// 用迭代器方式打印l5中的元素
    15. 	for (std::list<int>::iterator it = l5.begin(); it != l5.end(); it++)
    16. 		std::cout << *it << " ";
    17. 	std::cout << endl;
    18.  
    19. 	// C++11范围for的方式遍历
    20. 	for (auto& e : l5)
    21. 		std::cout << e << " ";
    22.  
    23. 	std::cout << endl;
    24. 	return 0;
    25. }

     1.2.2 list iterator的使用

    此处，大家可暂时将迭代器理解成一个指针，该指针指向list中的某个节点
    函数声明
    接口说明
    begin + end
    返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器
    rbegin + rend
    返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的reverse_iterator,即begin位置

     

    【注意】
    1. begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
    2. rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动 
    1. #include 
    2. using namespace std;
    3. #include 
    4. void print_list(const list<int>& l)
    5. {
    6. 	// 注意这里调用的是list的 begin() const，返回list的const_iterator对象
    7. 	for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it)
    8. 	{
    9. 		cout << *it << " ";
    10. 		// *it = 10; 编译不通过
    11. 	}
    12.  
    13. 	cout << endl;
    14. }
    15. int main()
    16. {
    17. 	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    18. 	list<int> l(array, array + sizeof(array) / sizeof(array[0]));
    19. 	// 使用正向迭代器正向list中的元素
    20. 	for (list<int>::iterator it = l.begin(); it != l.end(); ++it)
    21. 		cout << *it << " ";
    22. 	cout << endl;
    23. 	// 使用反向迭代器逆向打印list中的元素
    24. 	for (list<int>::reverse_iterator it = l.rbegin(); it != l.rend(); ++it)
    25. 		cout << *it << " ";
    26. 	cout << endl;
    27. 	return 0;
    28. }

    实现结构的角度，迭代器分为三类：

    1.单向迭代器：支持++                         例：forward_list、unordered_map、unordered_set

    2.双向迭代器：支持++、--                   例：list、map、set

    3.随机迭代器：支持++、--、+、-         例：vector、string、deque

     1.2.3 list capacity

    函数声明
    接口说明
    empty
    检测list是否为空，是返回true，否则返回false
    size
    返回list中有效节点的个数

    1.2.4 list element access

    函数声明
    接口说明
    front
    返回list的第一个节点中值的引用
    back
    回list的最后一个节点中值的引用

     1.2.5 list modififiers

     

    1. #include 
    2. void PrintList(list<int>& l)
    3. {
    4. 	for (auto& e : l)
    5. 		cout << e << " ";
    6. 	cout << endl;
    7. }
    8. //=========================================================================================
    9. // push_back/pop_back/push_front/pop_front
    10. void TestList1()
    11. {
    12. 	int array[] = { 1, 2, 3 };
    13. 	list<int> L(array, array + sizeof(array) / sizeof(array[0]));
    14. 	// 在list的尾部插入4，头部插入0
    15. 	L.push_back(4);
    16. 	L.push_front(0);
    17. 	PrintList(L);
    18. 	// 删除list尾部节点和头部节点
    19. 	L.pop_back();
    20. 	L.pop_front();
    21. 	PrintList(L);
    22. }
    23. //=========================================================================================
    24. // insert /erase 
    25. void TestList3()
    26. {
    27. 	int array1[] = { 1, 2, 3 };
    28. 	list<int> L(array1, array1 + sizeof(array1) / sizeof(array1[0]));
    29. 	// 获取链表中第二个节点
    30. 	auto pos = ++L.begin();
    31. 	cout << *pos << endl;
    32. 	// 在pos前插入值为4的元素
    33. 	L.insert(pos, 4);
    34. 	PrintList(L);
    35. 	// 在pos前插入5个值为5的元素
    36. 	L.insert(pos, 5, 5);
    37. 	PrintList(L);
    38. 	// 在pos前插入[v.begin(), v.end)区间中的元素
    39. 	vector<int> v{ 7, 8, 9 };
    40. 	L.insert(pos, v.begin(), v.end());
    41. 	PrintList(L);
    42. 	// 删除pos位置上的元素
    43. 	L.erase(pos);
    44. 	PrintList(L);
    45. 	// 删除list中[begin, end)区间中的元素，即删除list中的所有元素
    46. 	L.erase(L.begin(), L.end());
    47. 	PrintList(L);
    48. }
    49. // resize/swap/clear
    50. void TestList4()
    51. {
    52. 	// 用数组来构造list
    53. 	int array1[] = { 1, 2, 3 };
    54. 	list<int> l1(array1, array1 + sizeof(array1) / sizeof(array1[0]));
    55. 	PrintList(l1);
    56. 	// 交换l1和l2中的元素
    57. 	l1.swap(l2);
    58. 	PrintList(l1);
    59. 	PrintList(l2);
    60. 	// 将l2中的元素清空
    61. 	l2.clear();
    62. 	cout << l2.size() << endl;
    63. }

    list中还有一些操作，需要用到时大家可参阅list的文档说明。

     1.2.6 list的迭代器失效

    前面说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节 点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代 器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响 。 
    1. void TestListIterator1()
    2. {
    3. 	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    4. 	list<int> l(array, array + sizeof(array) / sizeof(array[0]));
    5. 	auto it = l.begin();
    6. 	while (it != l.end())
    7. 	{
    8. 		// erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给
    9. 		其赋值
    10. 			l.erase(it);
    11. 		++it;
    12. 	}
    13. }
    14. // 改正
    15. void TestListIterator()
    16. {
    17. 	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    18. 	list<int> l(array, array + sizeof(array) / sizeof(array[0]));
    19. 	auto it = l.begin();
    20. 	while (it != l.end())
    21. 	{
    22. 		l.erase(it++); // it = l.erase(it);
    23. 	}
    24. }

    常用接口测试：

    1. #include
    2. #include
    3. using namespace std;
    4.  
    5. void TestList1()
    6. {
    7. 	list<int> lt;
    8. 	lt.push_back(1);
    9. 	lt.push_back(2);
    10. 	lt.push_back(3);
    11. 	lt.push_back(4);
    12. 	/*for (auto e : lt)
    13. 	{
    14. 		cout << e << " ";
    15. 	}
    16. 	cout << endl;*/
    17. 	list<int>::iterator it = lt.begin();  //正向迭代器
    18. 	while (it != lt.end())
    19. 	{
    20. 		cout << *it << " ";
    21. 		++it;
    22. 	}
    23. 	cout << endl;
    24. }
    25. void TestList2()
    26. {
    27. 	list<int> lt;
    28. 	lt.push_back(1);
    29. 	lt.push_back(2);
    30. 	lt.push_back(3);
    31. 	lt.push_back(4);
    32. 	list<int>::reverse_iterator rit = lt.rbegin(); //反向迭代器
    33. 	while (rit != lt.rend())
    34. 	{
    35. 		cout << *rit << " ";
    36. 		++rit;
    37. 	}
    38. 	cout << endl;
    39.  
    40. }
    41. void TestList3()
    42. {
    43. 	list<int> lt;
    44. 	lt.push_back(1);
    45. 	lt.push_back(2);
    46. 	lt.push_back(3);
    47. 	lt.push_back(4);
    48. 	for (auto e : lt)
    49. 	{
    50. 		cout << e << " ";
    51. 	}
    52. 	cout << endl;
    53. 	lt.push_front(5);
    54. 	lt.push_front(6);
    55. 	lt.push_front(7);
    56. 	for (auto e : lt)
    57. 	{
    58. 		cout << e << " ";
    59. 	}
    60. 	cout << endl;
    61. 	lt.pop_back();
    62. 	lt.pop_back();
    63. 	for (auto e : lt)
    64. 	{
    65. 		cout << e << " ";
    66. 	}
    67. 	cout << endl;
    68. 	lt.pop_front();
    69. 	lt.pop_front();
    70. 	for (auto e : lt)
    71. 	{
    72. 		cout << e << " ";
    73. 	}
    74. 	cout << endl;
    75. }
    76. void TestList4()
    77. {
    78. 	list<int> lt;
    79. 	lt.push_back(6);
    80. 	lt.push_back(2);
    81. 	lt.push_back(8);
    82. 	lt.push_back(4);
    83. 	for (auto e : lt)
    84. 	{
    85. 		cout << e << " ";
    86. 	}
    87. 	cout << endl;
    88. 	lt.sort();
    89. 	for (auto e : lt)
    90. 	{
    91. 		cout << e << " ";
    92. 	}
    93. }
    94. void TestList5()
    95. {
    96. 	list<int> lt;
    97. 	lt.push_back(6);
    98. 	lt.push_back(4);
    99. 	lt.push_back(2);
    100. 	lt.push_back(8);
    101. 	lt.push_back(4);
    102. 	lt.push_back(4);
    103. 	for (auto e : lt)
    104. 	{
    105. 		cout << e << " ";
    106. 	}
    107. 	cout << endl;
    108. 	lt.sort(); //排序
    109. 	for (auto e : lt)
    110. 	{
    111. 		cout << e << " ";
    112. 	
    113. 	}
    114. 	cout << endl;
    115. 	lt.unique(); //需先排序，再去重
    116. 	for (auto e : lt)
    117. 	{
    118. 		cout << e << " ";
    119. 	}
    120. 	cout << endl;
    121.  
    122. }
    123.  
    124. int main()
    125. {
    126. 	//TestList1();
    127. 	//TestList2();
    128. 	//TestList3();
    129. 	//TestList4();
    130. 	TestList5();
    131. 	return 0;
    132. }

    后记：
    ●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！
                                                                      ——By 作者：新晓·故知

  • 相关阅读:
    【Docker】常用命令总结
    独立站活动怎么复盘，做独立站需要掌握哪些？-站斧浏览器
    【ChatGPT-应用篇】基于chatGPT覆盖测试过程的初步探索
    智慧在线拜佛上供品花供果祈福求愿公众号开发
    腾讯云-对象存储服务（COS）的使用总结-JavaScript篇
    单例模式。
    langchain pdf链检索，提问式表单（实体命名识别）
    项目设计集合（人工智能方向）：助力新人快速实战掌握技能、自主完成项目设计升级，提升自身的硬实力（不仅限NLP、知识图谱、计算机视觉等领域）
    Navicat Premium 修改表注释
    专用神经网络处理器芯片,神经网络芯片的单片机
  • 原文地址：https://blog.csdn.net/m0_57859086/article/details/126179675