• 初识《list》及手搓模拟《list》

    目录

    前言：

    1. list的介绍及使用

    list的介绍：

    list的使用：

    1、list的构造​编辑

    2、list iterator的使用

    3、list capacity

    4、list element access

    5、list modifiers

    2.list的模拟实现

    1、关于迭代器：

    2、迭代器类的封装：

     3、模板为类的时候：

    4、关于const迭代器：

    一：而额外封装一个const迭代器。const_iterator

    二：利用模板

    3.vector与list的区别：

    总结：

    前言：

    现阶段我们已经逐渐熟悉了各个STL库中的容器，对于他们的各个接口都大差不差，在我们学习完vector之后我们就可以陆陆续续接触一些算法题。我们的《好题分析》这一专栏也会不断的进行更新！下面我们先来熟悉以下list这个容器。

    1. 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来说这可能是一个重要的因素)


    list的使用：

    1、list的构造

    2、list iterator的使用

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

     

    注意！！

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

    3、list capacity

    4、list element access

    5、list modifiers

     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. // 改正
    16. void TestListIterator()
    17. {
    18. 	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    19. 	list<int> l(array, array + sizeof(array) / sizeof(array[0]));
    20. 	auto it = l.begin();
    21. 	while (it != l.end())
    22. 	{
    23. 		l.erase(it++); // it = l.erase(it);
    24. 	}
    25. }

    2.list的模拟实现

    1、关于迭代器：

    我们对list的迭代器的理解与我们之前对于string 和 vector中的iterator的理解有十分大的区别。string和vector的迭代器我们可以替换理解为指针，在我们遍历vector或者string时，仅需要对++运算符进行重载，我们就可以拿到下一个位置的值，而operator++()也很好理解，就是指针+1指向下一个下标的位置。

    但是这次我们的list就大有不同，我们都知道list是一个带头的双向链表，而想要获得下一个结点的数据，应当是node = node -> next; 如果我们将运算符++重载为这个代码，那对于其它的代码想要运用++操作符，就纯粹扯淡。

    这个时候的唯一解决方法就是————————封装一个类！！！

    2、迭代器类的封装：

    1. // 一个结点的结构！！！
    2. template<class T>
    3. struct ListNode
    4. {
    5. 	T _data;
    6. 	ListNode* _next;
    7. 	ListNode* _prev;
    8.  
    9. 	ListNode(const T& x = T())
    10. 		:_next(nullptr)
    11. 		, _prev(nullptr)
    12. 		, _data(x)
    13. 	{}
    14. };
    15.  
    16. // 将迭代器封装成一个类
    17. template<class T>
    18. struct ListIterator
    19. {
    20. 	typedef ListIterator Self;
    21. 	typedef ListNode Node;
    22.  
    23. 	Node* _node;// iterator
    24.  
    25. 	ListConstIterator(Node* node)
    26. 		:_node(node)
    27. 	{}
    28.  
    29. 	bool operator != (const Self& it)
    30. 	{
    31. 		return _node != it._node;
    32. 	}
    33.  
    34. 	Self& operator++()
    35. 	{
    36. 		_node = _node->_next;
    37. 		return *this;
    38. 	}
    39.  
    40. 	Self operator++(int)
    41. 	{
    42. 		Self tmp(*this);
    43. 		_node = _node->_next;
    44. 		return *this;
    45. 	}
    46.  
    47. 	Self& operator--()
    48. 	{
    49. 		_node = _node->_prev;
    50. 		return *this;
    51. 	}
    52.  
    53. 	Self operator--()
    54. 	{
    55. 		Self tmp(*this);
    56. 		_node = _node->_prev;
    57. 		return tmp;
    58. 	}
    59.  
    60. 	T& operator*()
    61. 	{
    62. 		return _node->_data;
    63. 	}
    64.  
    65. 	T* operator->()
    66. 	{
    67. 		return &_node->_data;
    68. 	}
    69. };

    我们在之后的项目中，如果发现我们目前处理的数据中的内置类型不满足我们的需求，不妨我们可以将其封装成一个类！！！

    首先我们先通过画图得方式来理解代码：


     因为这个iterator类我们并不会定义私有成员，所以我们这里用的struct来定义。

    而我们在整个链表的总体类中，我们需要先找到两个 头 和 尾 结点的位置，即begin 和 end.

    1. 	iterator begin()
    2. 	{
    3. 		return iterator(_head->_next); // 匿名对象
    4.         // iterator it(_head->_next); // 调用 iterator类 里面的 构造函数
    5.         // return it;
    6. 	}
    7.  
    8.  
    9. 	iterator end()
    10. 	{
    11.     	return iterator(_head); // 匿名对象
    12.         // iterator it(_head); // 调用 iterator类 里面的 构造函数
    13.         // return it;
    14. 	}

     

     3、模板为类的时候：

    想要去到_a1, 若是不进行函数重载, 则代码为:

    1. list::iterator it = ls.begin();
    2. std::cout << it._node->_data._a1 << " " << it._node->_data._a2 << std::endl;
    3. it++;
    4. std::cout << it._node->_data._a1 << " " << it._node->_data._a2 << std::endl;

    很明显代码非常的冗长和麻烦, 因此我们可以利用函数重载:

    1. T* operator->()
    2. {
    3.     return &_node->_data;
    4. }
    1. list::iterator it = ls.begin();
    2. std::cout << it->_a1 << " " << it->_a2 << std::endl;
    3. it++;
    4. std::cout << it->_a1 << " " << it->_a2 << std::endl;

    it.operator->()->_a1 
    在这里编译器会自动优化代码，将代码的可读性提高。
    it->_a1    <==>   it.operator->()->_a1     <==>      it->->_a1
    通过公式推导，我们不难发现 it->_a1  <==>    it->->_a1    这两个式子是等价的

    4、关于const迭代器：

    const迭代器，需要的是迭代器指向的内容不能被修改而const iteratror 作返回值时，代表了迭代器的指向不可被修改。

    一：而额外封装一个const迭代器。const_iterator

    在我们实施这个方法后，我们会发现仅仅只有Self& operator*() 和 Self* operator->()的返回值是需要加const，其它的都不变

    1.  //对于每一个容器来说，都有存在const的类型接口，因此我们也需要创建一个const迭代器。
    2.  //（运用const主要还是 防止 在进行 拷贝构造 或者 ++ -- 等出现 修改一个 const链表的情况。）
    3. template<class T>
    4. struct List_const_iterator
    5. {
    6.     typedef ListNode Node;
    7.     typedef List_const_iterator Self;
    8.  
    9.     Node* _node;// 最重要的一行代码，代表在 List_iterator 类中 封装一个 _node 用来指向结点，通过在类里面
    10.     // 控制运算符重载来操纵迭代器
    11.  
    12.     List_const_iterator(Node* node) // 传值构造
    13.         :_node(node)
    14.     {}
    15.  
    16.     // ++it
    17.     Self& operator++()
    18.     {
    19.         _node = _node->_next;
    20.         return *this;
    21.     }
    22.  
    23.     // it++
    24.     Self operator++(int)
    25.     {
    26.         Self tmp(*this); // 无需写拷贝构造函数， 默认的 浅拷贝 即可完成操作
    27.         _node = _node->_next;
    28.         return *this;
    29.     }
    30.  
    31.     // *it
    32.     const T& operator*()
    33.     {
    34.         return _node->_data;
    35.     }
    36.  
    37.     // it->_data，此时的 _data 是结构体时才调用
    38.     const T* operator->()
    39.     {
    40.         return &_node->_data;
    41.     }
    42.  
    43.     bool operator!=(const Self& it)
    44.     {
    45.         return _node != it._node;
    46.     }
    47.  
    48. };

     

    因此我们没必要多此一举。

    二：利用模板

    1. // 我们在创建 const_iterator 迭代器时发现在整个类中，仅仅只是对 operator*() 与 operator->() 的返回值进行了修改
    2. // 为了尽可能的减少代码量，利用模板是一个不错的选择。
    3. // Ref == reference    ,    Prt == pointer
    4. //                      T&         T* 
    5. template<class T, class Ref, class Ptr> 
    6. //template
    7. struct List_iterator
    8. {
    9.     typedef ListNode Node;
    10.     typedef List_iterator Self;
    11.  
    12.     Node* _node;// 最重要的一行代码，代表在 List_iterator 类中 封装一个 _node 用来指向结点，通过在类里面
    13.                 // 控制运算符重载来操纵迭代器
    14.     
    15.     List_iterator(Node* node) // 传值构造
    16.         :_node(node)
    17.     {}
    18.  
    19.     // ++it
    20.     Self& operator++()
    21.     {
    22.         _node = _node->_next;
    23.         return *this;
    24.     }
    25.  
    26.     // it++
    27.     Self operator++(int)
    28.     {
    29.         Self tmp(*this); // 无需写拷贝构造函数， 默认的 浅拷贝 即可完成操作
    30.         _node = _node->_next;
    31.         return *this;
    32.     }
    33.     
    34.     // *it 返回类型为T&
    35.     Ref operator*()
    36.     {
    37.         return _node->_data;
    38.     }
    39.  
    40.  
    41.     // it->_data，此时的 _data 是结构体时才调用, 返回类型为T*
    42.     Ptr operator->()
    43.     {
    44.         return &_node->_data;
    45.     }
    46.  
    47.     bool operator!=(const Self& it)
    48.     {
    49.         return _node != it._node;
    50.     }
    51.  
    52. };

     在list类中：

    1.  template<class T>
    2.  class list
    3.  {
    4.  public:
    5.      typedef ListNode Node;
    6.      typedef List_iterator iterator;
    7.      typedef List_iteratorconst T&, const T*> const_iterator;
    8.      //typedef List_const_iterator const_iterator;
    9.      // 构造函数创建 哨兵位 的头结点

     利用模板是最高效的方法！！！

    3.vector与list的区别：

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

    总结：

    本文的代码思路与之前大为不同，本次首先接触到了利用类封装一个迭代器，其次是对结点里的类进行分类讨论，从而引出对->运算符的重载，再然后又对const的迭代器进行了扩展，发现利用模板可以有效的解决出现的一系列问题。

    代码在我的Gitee：
    ​​​​​​​my_list_practices_2/my_list_practices_2/list.h · 无双/C_Plus_Plus_Acer - Gitee.com

  • 相关阅读:
    中国石油大学(北京)-《油藏工程》第三阶段在线作业
    第七第八mooc+循环练习
    力扣349 - 两个数组的交集【哈希表+数组+双指针】
    全球建筑物提取数据集（免费下载）：微软/GlobalMLBuildingFootprints
    Django容易被遗忘却无比重要的框架默认文件介绍及使用方法
    React组件应用于Spring MVC工程
    Flink入门系列01-概述
    银河麒麟服务器x86安装ntp客户端，并配置成功可以同步时间
    几个常见的C/C++语言冷知识
    Tableau自四部曲_Part1：Tableau介绍与安装
  • 原文地址：https://blog.csdn.net/weixin_72917087/article/details/137979785