• C++ 反向迭代器

    反向迭代器的++即正向迭代器的--，反向迭代器的--即正向迭代器的++，反向迭代器和正向迭代器的很多功能都是相似的，因此我们可以复用正向迭代器作为反向迭代器的底层容器来封装，从而实现出反向迭代器，即：反向迭代器内部可以包含一个正向迭代器，对正向迭代器的接口进行包装

    这样一来我们可以实现任意容器的反向迭代器，如果用的是vector的正向迭代器，那么就封装出vector的反向迭代器，如果用的是list的正向迭代器，那么就封装出list的反向迭代器，这就是迭代器适配器了

    反向迭代器：

    1. template<class Iterator,class Ref,class Ptr>
    2. class ReverseIterator
    3. {
    4. 	typedef ReverseIterator Self;
    5. public:
    6.  
    7. 	ReverseIterator(Iterator it)
    8. 		:_it(it)
    9. 	{}
    10.  
    11. 	Self& operator++()
    12. 	{
    13. 		--_it;
    14. 		return *this;
    15. 	}
    16.  
    17. 	Self operator++(int)
    18. 	{
    19. 		Self tmp(*this);
    20. 		--_it;
    21. 		return tmp;
    22. 	}
    23.  
    24. 	Self& operator--()
    25. 	{
    26. 		++_it;
    27. 		return *this;
    28. 	}
    29.  
    30. 	Self operator--(int)
    31. 	{
    32. 		Self tmp(*this);
    33. 		++_it;
    34. 		return tmp;
    35. 	}
    36.  
    37. 	Ref operator*()//返回前一个位置的数据
    38. 	{
    39. 		Iterator cur = _it;
    40. 		return *(--cur);
    41. 	}
    42.  
    43. 	Ptr operator->()
    44. 	{
    45. 		return &(operator*());
    46. 	}
    47.  
    48. 	bool operator!=(const Self& s)
    49. 	{
    50. 		return _it != s._it;
    51. 	}
    52.  
    53. 	bool operator==(const Self& s)
    54. 	{
    55. 		return _it == s._it;
    56. 	}
    57.  
    58. private:
    59. 	Iterator _it;
    60. };

    库中设计的反向迭代器与正向迭代器是对称关系，关于解引用越界问题也很巧妙的处理了~：

    解引用返回的是前一个位置的数据

     vector模拟实现：

    1. #include
    2. #include"Reverseiterator.h"
    3. namespace djx
    4. {
    5. 	template<class T>
    6. 	class vector
    7. 	{
    8. 	public:
    9. 		typedef T* iterator;
    10. 		typedef const T* const_iterator;
    11. 		typedef ReverseIterator reverse_iterator;
    12. 		typedef ReverseIteratorconst T&, const T*> const_reverse_iterator;
    13.  
    14. 		reverse_iterator rbegin()
    15. 		{
    16. 			return reverse_iterator(end());
    17. 		}
    18.  
    19. 		reverse_iterator rend()
    20. 		{
    21. 			return reverse_iterator(begin());
    22. 		}
    23.  
    24. 		const_reverse_iterator rbegin() const
    25. 		{
    26. 			return const_reverse_iterator(end());
    27. 		}
    28.  
    29. 		const_reverse_iterator rend() const
    30. 		{
    31. 			return const_reverse_iterator(begin());
    32. 		}
    33.  
    34. 		iterator begin()
    35. 		{
    36. 			return _start;
    37. 		}
    38.  
    39. 		iterator end()
    40. 		{
    41. 			return _finish;
    42. 		}
    43.  
    44. 		const_iterator begin()const
    45. 		{
    46. 			return _start;
    47. 		}
    48.  
    49. 		const_iterator end()const
    50. 		{
    51. 			return _finish;
    52. 		}
    53.  
    54. 		vector()//一定要写，因为我们已经写了拷贝构造了，编译器不会生成默认的构造函数，当要使用无参的构造时如果我们没写，就没有，会报错
    55. 		{}
    56.  
    57. 		vector(const vector& v)
    58. 		{
    59. 			reserve(v.capacity());
    60. 			for (auto& e : v)
    61. 			{
    62. 				push_back(e);
    63. 			}
    64. 		}
    65.  
    66. 		vector(size_t n, const T& val = T())
    67. 		{
    68. 			reserve(n);
    69. 			for (size_t i = 0; i < n; i++)
    70. 			{
    71. 				push_back(val);
    72. 			}
    73. 		}
    74.  
    75. 		template <class InputIterator>
    76. 		vector(InputIterator first, InputIterator last)
    77. 		{
    78. 			while (first != last)
    79. 			{
    80. 				push_back(*first);
    81. 				first++;
    82. 			}
    83. 		}
    84.  
    85. 		void swap(vector& v)
    86. 		{
    87. 			std::swap(_start, v._start);
    88. 			std::swap(_finish, v._finish);
    89. 			std::swap(_endofstorage, v._endofstorage);
    90. 		}
    91.  
    92. 		vector& operator=(vector tmp)
    93. 		{
    94. 			swap(tmp);
    95. 			return *this;
    96. 		}
    97.  
    98. 		~vector()
    99. 		{
    100. 			delete[] _start;
    101. 			_start = _finish = _endofstorage = nullptr;
    102. 		}
    103.  
    104. 		T& operator[](size_t pos)
    105. 		{
    106. 			assert(pos < size());
    107. 			return _start[pos];
    108. 		}
    109.  
    110. 		const T& operator[](size_t pos) const
    111. 		{
    112. 			assert(pos < size());
    113. 			return _start[pos];
    114. 		}
    115.  
    116. 		void reserve(size_t n)
    117. 		{
    118. 			if (n > capacity())
    119. 			{
    120. 				size_t sz = size();
    121. 				T* tmp = new T[n];
    122. 				if (_start)
    123. 				{
    124. 					for (size_t i = 0; i < sz; i++)
    125. 					{
    126. 						tmp[i] = _start[i];
    127. 					}
    128. 					delete[] _start;
    129. 				}
    130. 				_start = tmp;
    131. 				_finish = _start + sz;
    132. 				_endofstorage = _start + n;
    133. 			}
    134. 		}
    135.  
    136. 		void push_back(const T& val)
    137. 		{
    138. 			/*	if (_finish == _endofstorage)
    139. 				{
    140. 					reserve(capacity() == 0 ? 4 : capacity() * 2);
    141. 				}
    142. 				*_finish = val;
    143. 				_finish++;*/
    144.  
    145. 			insert(end(), val);//复用insert
    146. 		}
    147.  
    148. 		void resize(size_t n, const T& val = T())
    149. 		{
    150. 			if (n <= size())
    151. 			{
    152. 				_finish = _start + n;
    153. 			}
    154. 			else
    155. 			{
    156. 				reserve(n);
    157. 				while (_finish < _start + n)
    158. 				{
    159. 					*_finish = val;
    160. 					_finish++;
    161. 				}
    162. 			}
    163. 		}
    164.  
    165. 		void insert(iterator pos, const T& val)
    166. 		{
    167. 			assert(pos >= _start);
    168. 			assert(pos <= _finish);
    169. 			if (_finish == _endofstorage)
    170. 			{
    171. 				size_t len = pos - _start;
    172. 				reserve(capacity() == 0 ? 4 : capacity() * 2);
    173. 				pos = _start + len;
    174. 			}
    175.  
    176. 			iterator end = _finish - 1;
    177. 			while (end >= pos)
    178. 			{
    179. 				*(end + 1) = *end;
    180. 				end--;
    181. 			}
    182.  
    183. 			*pos = val;
    184. 			_finish++;
    185. 		}
    186.  
    187. 		iterator erase(iterator pos)
    188. 		{
    189. 			assert(pos >= _start);
    190. 			assert(pos < _finish);
    191.  
    192. 			iterator begin = pos + 1;
    193. 			while (begin < _finish)
    194. 			{
    195. 				*(begin - 1) = *begin;
    196. 				begin++;
    197. 			}
    198. 			_finish--;
    199. 			return pos;
    200. 		}
    201.  
    202. 		size_t capacity() const
    203. 		{
    204. 			return _endofstorage - _start;
    205. 		}
    206.  
    207. 		size_t size()const
    208. 		{
    209. 			return _finish - _start;
    210. 		}
    211.  
    212. 	private:
    213. 		iterator _start = nullptr;//都会走构造，拷贝构造的初始化列表
    214. 		iterator _finish = nullptr;//给缺省值，就不用我们在构造，拷贝构造函数的初始化列表给值
    215. 		iterator _endofstorage = nullptr;
    216. 	};
    217. }

    测试vector的反向迭代器：

    1. void func(const djx::vector<int>& v)
    2. {
    3. 	djx::vector<int>::const_reverse_iterator rit = v.rbegin();
    4. 	while (rit != v.rend())
    5. 	{
    6. 		cout << *rit << " ";
    7. 		rit++;
    8. 	}
    9. 	cout << endl;
    10. }
    11.  
    12. int main()
    13. {
    14. 	djx::vector<int> v;
    15. 	v.push_back(1);
    16. 	v.push_back(2);
    17. 	v.push_back(3);
    18. 	v.push_back(4);
    19.  
    20. 	djx::vector<int>::reverse_iterator rit = v.rbegin();
    21. 	while (rit != v.rend())
    22. 	{
    23. 		cout << *rit << " ";
    24. 		rit++;
    25. 	}
    26. 	cout << endl;
    27.  
    28. 	func(v);
    29. 	return 0;
    30. }

     

     

    list模拟实现：

    1. #include"Reverseiterator.h"
    2. namespace djx
    3. {
    4. 	template<class T>
    5. 	struct list_node
    6. 	{
    7. 		T _data;
    8. 		list_node* _prev;
    9. 		list_node* _next;
    10.  
    11. 		list_node(const T& x = T())
    12. 			:_data(x)
    13. 			, _prev(nullptr)
    14. 			, _next(nullptr)
    15. 		{}
    16. 	};
    17.  
    18. 	template<class T, class Ref, class Ptr>
    19. 	struct __list_iterator
    20. 	{
    21. 		typedef list_node Node;
    22. 		typedef __list_iterator self;
    23.  
    24. 		Node* _node;
    25.  
    26. 		__list_iterator(Node* node)
    27. 			:_node(node)
    28. 		{}
    29.  
    30. 		Ref operator*()
    31. 		{
    32. 			return _node->_data;
    33. 		}
    34.  
    35. 		Ptr operator->()
    36. 		{
    37. 			return &_node->_data;
    38. 		}
    39.  
    40. 		self& operator++()
    41. 		{
    42. 			_node = _node->_next;
    43. 			return *this;
    44. 		}
    45.  
    46. 		self operator++(int)
    47. 		{
    48. 			self tmp(*this);
    49. 			_node = _node->_next;
    50. 			return tmp;
    51. 		}
    52.  
    53. 		self& operator--()
    54. 		{
    55. 			_node = _node->_prev;
    56. 			return *this;
    57. 		}
    58.  
    59. 		self operator--(int)
    60. 		{
    61. 			self tmp(*this);
    62. 			_node = _node->_prev;
    63. 			return tmp;
    64. 		}
    65.  
    66. 		bool operator!=(const self& s)
    67. 		{
    68. 			return _node != s._node;
    69. 		}
    70.  
    71. 		bool operator==(const self& s)
    72. 		{
    73. 			return _node == s._node;
    74. 		}
    75. 	};
    76.  
    77. 	template<class T>
    78. 	class list
    79. 	{
    80. 		typedef list_node Node;
    81. 	public:
    82. 		typedef __list_iterator iterator;
    83. 		typedef __list_iteratorconst T&, const T*> const_iterator;
    84. 		typedef ReverseIterator reverse_iterator;
    85. 		typedef ReverseIteratorconst T&, const T*> const_reverse_iterator;
    86.  
    87. 		reverse_iterator rbegin()
    88. 		{
    89. 			return reverse_iterator(end());
    90. 		}
    91.  
    92. 		reverse_iterator rend()
    93. 		{
    94. 			return reverse_iterator(begin());
    95. 		}
    96.  
    97. 		const_reverse_iterator rbegin()const
    98. 		{
    99. 			return const_reverse_iterator(end());
    100. 		}
    101.  
    102. 		const_reverse_iterator rend() const
    103. 		{
    104. 			return const_reverse_iterator(begin());
    105. 		}
    106.  
    107. 		iterator begin()
    108. 		{
    109. 			return _head->_next;
    110. 		}
    111.  
    112. 		iterator end()
    113. 		{
    114. 			return _head;
    115. 		}
    116.  
    117. 		const_iterator begin()const
    118. 		{
    119. 			return _head->_next;
    120. 		}
    121.  
    122. 		const_iterator end()const
    123. 		{
    124. 			return _head;
    125. 		}
    126.  
    127. 		void empty_init()
    128. 		{
    129. 			_head = new Node;
    130. 			_head->_next = _head;
    131. 			_head->_prev = _head;
    132. 			_size = 0;
    133. 		}
    134.  
    135. 		list()
    136. 		{
    137. 			empty_init();
    138. 		}
    139.  
    140. 		list(const list& lt)
    141. 		{
    142. 			empty_init();
    143. 			for (auto e : lt)
    144. 			{
    145. 				push_back(e);
    146. 			}
    147. 		}
    148.  
    149. 		void swap(list& lt)
    150. 		{
    151. 			std::swap(_head, lt._head);
    152. 			std::swap(_size, lt._size);
    153. 		}
    154.  
    155. 		list& operator=(list lt)
    156. 		{
    157. 			swap(lt);
    158. 			return *this;
    159. 		}
    160.  
    161. 		~list()
    162. 		{
    163. 			clear();
    164. 			delete _head;
    165. 			_head = nullptr;
    166. 		}
    167.  
    168. 		void clear()
    169. 		{
    170. 			iterator it = begin();
    171. 			while (it != end())
    172. 			{
    173. 				it = erase(it);
    174. 			}
    175. 		}
    176.  
    177. 		void push_back(const T& x)
    178. 		{
    179. 			insert(end(), x);
    180. 		}
    181.  
    182. 		void push_front(const T& x)
    183. 		{
    184. 			insert(begin(), x);
    185. 		}
    186.  
    187. 		void pop_back()
    188. 		{
    189. 			erase(--end());
    190. 		}
    191.  
    192. 		void pop_front()
    193. 		{
    194. 			erase(begin());
    195. 		}
    196.  
    197. 		iterator insert(iterator pos, const T& x)
    198. 		{
    199. 			Node* cur = pos._node;
    200. 			Node* newnode = new Node(x);
    201. 			Node* prev = cur->_prev;
    202.  
    203. 			prev->_next = newnode;
    204. 			newnode->_prev = prev;
    205.  
    206. 			newnode->_next = cur;
    207. 			cur->_prev = newnode;
    208. 			_size++;
    209. 			return newnode;
    210. 		}
    211.  
    212. 		iterator erase(iterator pos)
    213. 		{
    214. 			Node* cur = pos._node;
    215. 			Node* next = cur->_next;
    216. 			Node* prev = cur->_prev;
    217.  
    218. 			delete cur;
    219. 			prev->_next = next;
    220. 			next->_prev = prev;
    221. 			_size--;
    222. 			return next;
    223. 		}
    224.  
    225. 		size_t size()
    226. 		{
    227. 			return _size;
    228. 		}
    229.  
    230. 	private:
    231. 		Node* _head;
    232. 		size_t _size;
    233. 	};
    234. }

    测试list的反向迭代器：

    1. void func(const djx::list<int>& lt)
    2. {
    3. 	djx::list<int>::const_reverse_iterator rit = lt.rbegin();
    4. 	while (rit != lt.rend())
    5. 	{
    6. 		cout << *rit << " ";
    7. 		rit++;
    8. 	}
    9. 	cout << endl;
    10. }
    11.  
    12. int main()
    13. {
    14. 	djx::list<int> lt;
    15. 	lt.push_back(1);
    16. 	lt.push_back(2);
    17. 	lt.push_back(3);
    18. 	lt.push_back(4);
    19.  
    20. 	djx::list<int>::reverse_iterator rit = lt.rbegin();
    21. 	while (rit != lt.rend())
    22. 	{
    23. 		cout << *rit << " ";
    24. 		rit++;
    25. 	}
    26. 	cout << endl;
    27. 	func(lt);
    28. 	return 0;
    29. }

    当然了，我们也可以按照不同于库中设计的逻辑来设计反向迭代器：但是存在一些细节需要处理

    与库中反向迭代器设计模式不同之处在于解引用的设计 

    上图版本的反向迭代器解引用重载的设计： 

    1. 	Ref operator*()
    2. 	{
    3. 		return *_it
    4. 	}

     那么，相应的在vector和list中也会发生变化：

    vector中：

    1.         reverse_iterator rbegin()
    2. 		{
    3. 			return reverse_iterator(end() - 1);
    4. 		}
    5.  
    6. 		reverse_iterator rend()
    7. 		{
    8. 			return reverse_iterator(begin() - 1);
    9. 		}
    10.  
    11. 		const_reverse_iterator rbegin() const
    12. 		{
    13. 			return const_reverse_iterator(end() - 1);
    14. 		}
    15.  
    16. 		const_reverse_iterator rend() const
    17. 		{
    18. 			return const_reverse_iterator(begin() - 1);
    19. 		}

    需要注意的是必须是end()-1 /begin()-1 而不能是--end()/--begin()

    因为vector类中迭代器的实现，我们将其设计为原生指针T*，是内置类型

    end()/begin() 为传值返回，返回的是临时对象，具有常性，不可被修改

    list中：

    1.         reverse_iterator rbegin()
    2. 		{
    3. 			return reverse_iterator(--end());
    4. 		}
    5.  
    6. 		reverse_iterator rend()
    7. 		{
    8. 			return reverse_iterator(end());
    9. 		}
    10.  
    11. 		const_reverse_iterator rbegin() const
    12. 		{
    13. 			return const_reverse_iterator(--end());
    14. 		}
    15.  
    16. 		const_reverse_iterator rend() const
    17. 		{
    18. 			return const_reverse_iterator(end());
    19. 		}

    也可以设计成end()-1,只不过list的正向迭代器是自定义类型，需要重载-运算符才可

    那么问题就来了，为什么同样是各自的--end() ，vector就报错，我们知道因为返回的是临时对象具有常性导致的，但是list却不报错可以这样设计呢？

    诚然，list的end（）返回的也是临时对象，同样具有常性，不报错是因为这是特殊情况，特殊处理：具有常性的自定义类型的对象可以调用非const的函数

    所以list中的--end（）返回的自定义类型的临时对象可以调用list迭代器类中，非const的--运算符重载函数

    如：

    1. class A
    2. {
    3. public:
    4. 	A(int x = 0)
    5. 		:_a(x)
    6. 	{}
    7.  
    8. 	void Print()
    9. 	{}
    10.  
    11. private:
    12. 	int _a;
    13. };

    我们有时候会写出这样的代码：

    A(1).Print(); // 特殊处理

    A（1）是匿名对象具有常性，而print函数是非const的 

  • 相关阅读:
    第八周复习
    如何将PDF转换为Excel?一招解决办公难题
    PHP如何切割excel大文件,使用 PHP_XLSXWriter 代替 PHPExcel 10W+ 数据秒级导出
    Vue,过滤器的了解和使用
    Centos - Mariadb Backup Script 服务搭建
    基于腾讯地图实现精准定位，实现微信小程序考勤打卡功能
    Hive基础知识概念
    ARM开发（5）ARM的接口技术（串行通信与并行通信，同步串行通信与异步串行通信，波特率，串行通信术语，uart，i2c，spi三种协议简单引入）
    mysql8配置优化
    C#可空类型
  • 原文地址：https://blog.csdn.net/weixin_73142957/article/details/133826981