• 【STL】：反向迭代器

    朋友们、伙计们，我们又见面了，本期来给大家解读一下有关反向迭代器的模拟实现，如果看完之后对你有一定的启发，那么请留下你的三连，祝大家心想事成！

    C 语 言 专 栏：C语言：从入门到精通

    数据结构专栏：数据结构

    个  人  主  页 ：stackY、

    C + + 专 栏   ：C++

    Linux 专 栏  ：Linux

    ​

    目录

    前言：

    1. 基本构造

    2. 接口完善

    3. 在list中使用反向迭代器

    list反向迭代器版本一：

    list反向迭代器版本二： 

    4. 在vector中使用反向迭代器 

    前言：

    前面的模拟实现vector和list中是没有实现反向迭代器的，反向迭代器与正向迭代器相比就是从数据的末端向前面访问遍历，但是两个迭代器的用法都是一样的，++就是下一个，*就可以访问到数据，但是它具体是怎么实现的呢？我们接下来看一看：

    1. 基本构造

    在list的模拟实现中讲解了如何实现正向迭代器（包含const版本和非const版本）那么在本期实现反向迭代器的时候就有了一定的前车之鉴，比如const版本和非const版本不需要实现两份代码，可以采用模板实现泛型编程。

    反向迭代器的构造可以使用正向迭代器来进行复用，因为反向迭代器的++就是正向迭代器里面的--，所以在传递模板参数的时候可以直接传递一个迭代器，直接复用这个迭代器里面的各种结构完成反向迭代器的构造。这种方式叫做迭代器适配器。

    1. #pragma once
    2.  
    3. namespace ywh
    4. {
    5. 	//反向迭代器
    6. 	template <class Iterator, class Ref, class Ptr>
    7. 	class ReverseIterator
    8. 	{
    9. 	public:
    10. 		typedef ReverseIterator Self;
    11.  
    12. 		//构造
    13. 		ReverseIterator(Iterator it)
    14. 			:_it(it)
    15. 		{}
    16.  
    17. 	private:
    18. 		Iterator _it;
    19. 	};
    20. }

    2. 接口完善

    反向迭代器的接口有++、--、*、->、!=、==，这些接口的实现都是可以通过使用模板参数中的迭代器来进行复用即可。

    头文件： reverse_iterator.h

    1. #pragma once
    2.  
    3. namespace ywh
    4. {
    5. 	//反向迭代器
    6. 	template <class Iterator, class Ref, class Ptr>
    7. 	class ReverseIterator
    8. 	{
    9. 	public:
    10. 		typedef ReverseIterator Self;
    11.  
    12. 		//构造
    13. 		ReverseIterator(Iterator it)
    14. 			:_it(it)
    15. 		{}
    16.  
    17. 		//前置
    18. 		//operator++
    19. 		Self& operator++()
    20. 		{
    21. 			//复用传过来的迭代器里面的operator--
    22. 			--_it;
    23. 			return *this;
    24. 		}
    25. 		//operator--
    26. 		Self&operator++()
    27. 		{
    28. 			++_it;
    29. 			return *this;
    30. 		}
    31.  
    32. 		//operator*
    33. 		Ref operator*()
    34. 		{
    35. 			return *_it;
    36. 		}
    37. 		//operator->
    38. 		Ptr operator->()
    39. 		{
    40. 			return _it.operator->();
    41. 		}
    42.  
    43. 		//operator==
    44. 		bool operator==(const Self& s)
    45. 		{
    46. 			return _it == s._it;
    47. 		}
    48. 		//operator!=
    49. 		bool operator!=(const Self& s)
    50. 		{
    51. 			return _it != s._it;
    52. 		}
    53. 	private:
    54. 		Iterator _it;
    55. 	};
    56. }

    3. 在list中使用反向迭代器

    要使用反向迭代器，首先得在list头文件中包含以下反向迭代器的头文件，然后进行构造：

    list反向迭代器版本一：

    1. #pragma once
    2. #include "reverse_iterator.h"
    3. namespace ywh
    4. {
    5. 	//链表结构
    6. 	template<class T>
    7. 	struct list_node
    8. 	{
    9. 		T _data;                 //节点中的数据
    10. 		list_node* _prev;    //指向前一个节点的指针
    11. 		list_node* _next;    //指向后一个节点的指针
    12.  
    13. 		//构造
    14. 		list_node(const T& x = T())
    15. 			:_data(x)
    16. 			, _prev(nullptr)
    17. 			, _next(nullptr)
    18. 		{}
    19.  
    20. 	};
    21.  
    22. 	//正向迭代器
    23. 	//   类型模板参数   传递引用      传递指针
    24. 	template<class T, class Ref, class Ptr>
    25. 	struct __list_iterator
    26. 	{
    27. 		typedef list_node Node;
    28. 		typedef __list_iterator self;
    29. 		Node* _node;
    30. 		//迭代器构造
    31. 		__list_iterator(Node* node)
    32. 			:_node(node)
    33. 		{}
    34. 		
    35. 		//前置
    36. 		//operator++
    37. 		self& operator++()
    38. 		{
    39. 			_node = _node->_next;
    40. 			return *this;
    41. 		}
    42. 		//operator--
    43. 		self& operator--()
    44. 		{
    45. 			_node = _node->_prev;
    46. 			return *this;
    47. 		}
    48.  
    49. 		//后置
    50. 		self operator++(int)
    51. 		{
    52. 			self* tmp(_node);
    53. 			_node = _node->_next;
    54. 			return tmp;
    55. 		}
    56. 		//operator--
    57. 		self operator--(int)
    58. 		{
    59. 			self* tmp(_node);
    60. 			_node = _node->_prev;
    61. 			return tmp;
    62. 		}
    63.  
    64. 		//operator*
    65. 		Ref operator*()
    66. 		{
    67. 			return _node->_data;
    68. 		}
    69. 		//operator->
    70. 		Ptr operator->()
    71. 		{
    72. 			return &_node->_data;
    73. 		}
    74. 		//operator!=
    75. 		bool operator!=(const self& s)
    76. 		{
    77. 			return _node != s._node;
    78. 		}
    79. 		//operator==
    80. 		bool operator==(const self& s)
    81. 		{
    82. 			return _node == s._node;
    83. 		}
    84. 	};
    85.  
    86. 	//list结构
    87. 	template<class T>
    88. 	class list
    89. 	{
    90. 	public:
    91. 		typedef list_node Node;
    92. 		typedef __list_iterator iterator;   //非const迭代器
    93. 		typedef __list_iteratorconst T&, const T*> const_iterator;  //const迭代器
    94. 		typedef ReverseIterator reverse_iterator;   //反向迭代器
    95. 		typedef ReverseIteratorconst T&, const T*> const_reverse_iterator;   //反向迭代器
    96.  
    97. 	public:
    98. 		基本构造///
    99. 		//...
    100. 		///正向迭代器
    101. 		iterator begin()
    102. 		{
    103. 			return iterator(_head->_next); //使用匿名对象进行构造
    104. 		}
    105. 		iterator end()
    106. 		{
    107. 			return iterator(_head);
    108. 		}
    109. 		const_iterator begin() const
    110. 		{
    111. 			return const_iterator(_head->_next);
    112. 		}
    113. 		const_iterator end() const
    114. 		{
    115. 			return const_iterator(_head);
    116. 		}
    117. 		//反向迭代器/
    118. 		reverse_iterator rbegin()
    119. 		{
    120. 			return reverse_iterator(--end());
    121. 		}
    122. 		reverse_iterator rend()
    123. 		{
    124. 			return reverse_iterator(end());
    125. 		}
    126. 		const_reverse_iterator rbegin() const
    127. 		{
    128. 			return const_reverse_iterator(--end());
    129. 		}
    130. 		const_reverse_iterator rend() const
    131. 		{
    132. 			return const_reverse_iterator(end());
    133. 		}
    134. 		///修改相关接口
    135. 		//...
    136. 	private:
    137. 		Node* _head;  //链表的头节点
    138. 		size_t _size; //节点个数
    139. 	};
    140. }

    list反向迭代器版本二： 

    我们也可以看一下库里面list的反向迭代器如何设计：

    可以看到库里面的玩法是一种对称的结构，这种对称的结构在解引用访问时访问的是下一个节点的元素，这样子写是比较好理解的，正向的起始就是反向的结束，正向的结束就是反向的起始，那么我们也可以来按照这种写法来写一下：

    头文件：reverse_iterator.h

    1. #pragma once
    2. namespace ywh
    3. {
    4. 	//反向迭代器
    5. 	template <class Iterator, class Ref, class Ptr>
    6. 	class ReverseIterator
    7. 	{
    8. 	public:
    9. 		typedef ReverseIterator Self;
    10.  
    11. 		//构造
    12. 		ReverseIterator(Iterator it)
    13. 			:_it(it)
    14. 		{}
    15.  
    16. 		//前置
    17. 		//operator++
    18. 		Self& operator++()
    19. 		{
    20. 			//复用传过来的迭代器里面的operator--
    21. 			--_it;
    22. 			return *this;
    23. 		}
    24. 		//operator--
    25. 		Self&operator++()
    26. 		{
    27. 			++_it;
    28. 			return *this;
    29. 		}
    30.  
    31. 		//operator*
    32. 		Ref operator*()
    33. 		{
    34. 			Iterator cur = _it;
    35. 			//返回下一个节点的数据
    36. 			return *(--cur);
    37. 		}
    38. 		//operator->
    39. 		Ptr operator->()
    40. 		{
    41. 			return _it.operator->();
    42. 		}
    43.  
    44. 		//operator==
    45. 		bool operator==(const Self& s)
    46. 		{
    47. 			return _it == s._it;
    48. 		}
    49. 		//operator!=
    50. 		bool operator!=(const Self& s)
    51. 		{
    52. 			return _it != s._it;
    53. 		}
    54. 	private:
    55. 		Iterator _it;
    56. 	};
    57. }

    头文件：List.h

    1. #pragma once
    2. #include "reverse_iterator.h"
    3. namespace ywh
    4. {
    5. 	//链表结构
    6. 	template<class T>
    7. 	struct list_node
    8. 	{
    9. 		T _data;                 //节点中的数据
    10. 		list_node* _prev;    //指向前一个节点的指针
    11. 		list_node* _next;    //指向后一个节点的指针
    12.  
    13. 		//构造
    14. 		list_node(const T& x = T())
    15. 			:_data(x)
    16. 			, _prev(nullptr)
    17. 			, _next(nullptr)
    18. 		{}
    19.  
    20. 	};
    21.  
    22. 	//正向迭代器
    23. 	//   类型模板参数   传递引用      传递指针
    24. 	template<class T, class Ref, class Ptr>
    25. 	struct __list_iterator
    26. 	{
    27. 		typedef list_node Node;
    28. 		typedef __list_iterator self;
    29. 		Node* _node;
    30. 		//迭代器构造
    31. 		__list_iterator(Node* node)
    32. 			:_node(node)
    33. 		{}
    34. 		
    35. 		//前置
    36. 		//operator++
    37. 		self& operator++()
    38. 		{
    39. 			_node = _node->_next;
    40. 			return *this;
    41. 		}
    42. 		//operator--
    43. 		self& operator--()
    44. 		{
    45. 			_node = _node->_prev;
    46. 			return *this;
    47. 		}
    48.  
    49. 		//后置
    50. 		self operator++(int)
    51. 		{
    52. 			self* tmp(_node);
    53. 			_node = _node->_next;
    54. 			return tmp;
    55. 		}
    56. 		//operator--
    57. 		self operator--(int)
    58. 		{
    59. 			self* tmp(_node);
    60. 			_node = _node->_prev;
    61. 			return tmp;
    62. 		}
    63.  
    64. 		//operator*
    65. 		Ref operator*()
    66. 		{
    67. 			return _node->_data;
    68. 		}
    69. 		//operator->
    70. 		Ptr operator->()
    71. 		{
    72. 			return &_node->_data;
    73. 		}
    74. 		//operator!=
    75. 		bool operator!=(const self& s)
    76. 		{
    77. 			return _node != s._node;
    78. 		}
    79. 		//operator==
    80. 		bool operator==(const self& s)
    81. 		{
    82. 			return _node == s._node;
    83. 		}
    84. 	};
    85.  
    86. 	//list结构
    87. 	template<class T>
    88. 	class list
    89. 	{
    90. 	public:
    91. 		typedef list_node Node;
    92. 		typedef __list_iterator iterator;   //非const迭代器
    93. 		typedef __list_iteratorconst T&, const T*> const_iterator;  //const迭代器
    94. 		typedef ReverseIterator reverse_iterator;   //反向迭代器
    95. 		typedef ReverseIteratorconst T&, const T*> const_reverse_iterator;   //反向迭代器
    96.  
    97. 	public:
    98. 		基本构造///
    99. 		//...
    100. 		///正向迭代器
    101. 		iterator begin()
    102. 		{
    103. 			return iterator(_head->_next); //使用匿名对象进行构造
    104. 		}
    105. 		iterator end()
    106. 		{
    107. 			return iterator(_head);
    108. 		}
    109. 		const_iterator begin() const
    110. 		{
    111. 			return const_iterator(_head->_next);
    112. 		}
    113. 		const_iterator end() const
    114. 		{
    115. 			return const_iterator(_head);
    116. 		}
    117. 		//反向迭代器/
    118. 		reverse_iterator rbegin()
    119. 		{
    120. 			return reverse_iterator(end());
    121. 		}
    122. 		reverse_iterator rend()
    123. 		{
    124. 			return reverse_iterator(begin());
    125. 		}
    126. 		const_reverse_iterator rbegin() const
    127. 		{
    128. 			return const_reverse_iterator(end());
    129. 		}
    130. 		const_reverse_iterator rend() const
    131. 		{
    132. 			return const_reverse_iterator(begin());
    133. 		}
    134. 		///修改相关接口
    135. 		//...
    136. 	private:
    137. 		Node* _head;  //链表的头节点
    138. 		size_t _size; //节点个数
    139. 	};
    140. }

    4. 在vector中使用反向迭代器 

    vector中的反向迭代器不建议使用上面的版本一，因为begin()和end()是传值返回，是临时对象，而临时对象具有常性，不好进行修改，所以还是比较建议使用这种对称的结构。

    头文件：Vector.h

    1. #pragma once
    2. #include 
    3. #include "reverse_iterator.h"
    4. namespace ywh
    5. {
    6. 	template<class T>
    7. 	class vector
    8. 	{
    9. 	public:
    10. 		typedef T* iterator;
    11. 		typedef const T* const_iterator;
    12. 		typedef ReverseIterator reverse_iterator;
    13. 		typedef ReverseIteratorconst T&, const T*> const_reverse_iterator;
    14. 	public:
    15. 		/正向迭代器
    16. 		iterator begin()
    17. 		{
    18. 			return _start;
    19. 		}
    20. 		iterator end()
    21. 		{
    22. 			return _finish;
    23. 		}
    24. 		const_iterator begin() const
    25. 		{
    26. 			return _start;
    27. 		}
    28. 		const_iterator end() const
    29. 		{
    30. 			return _finish;
    31. 		}
    32. 		/反向迭代器/
    33. 		reverse_iterator rbegin()
    34. 		{
    35. 			return reverse_iterator(end());
    36. 		}
    37. 		reverse_iterator rend()
    38. 		{
    39. 			return reverse_iterator(begin());
    40. 		}
    41. 		const_reverse_iterator rbegin() const
    42. 		{
    43. 			return const_reverse_iterator(end());
    44. 		}
    45. 		const_reverse_iterator rend() const
    46. 		{
    47. 			return const_reverse_iterator(begin());
    48. 		}
    49. 		/基本构造///
    50. 	    //...
    51. 		///容量
    52. 		//...
    53. 		///修改
    54. 		//...
    55. 	private:
    56. 		iterator _start = nullptr;   //起始位置
    57. 		iterator _finish = nullptr;  //有效数据位置
    58. 		iterator _end_of_storage = nullptr; //结束位置
    59. 	};
    60. }
    61.  
    62.

    朋友们、伙计们，美好的时光总是短暂的，我们本期的的分享就到此结束，欲知后事如何，请听下回分解~，最后看完别忘了留下你们弥足珍贵的三连喔，感谢大家的支持！   

  • 相关阅读:
    Android UI freeze分析
    Postman —— 配置环境变量
    贝塞尔函数
    建议收藏！混迹职场多年总结出的8大技巧！
    17.3.2.5 灰度（内存处理）
    数字化转型“黑话”知多少？一文让你不仅听得懂、还会落地执行
    【BOOST C++ 14 消息编程】（3） 集体数据交换
    3.1python基础01
    伴随第四次电气革命实现半导体行业的可持续智能增长
    智慧灯杆网关管理平台：城市建设的智慧化之道
  • 原文地址：https://blog.csdn.net/Yikefore/article/details/134217776