[ C++ ] STL---反向迭代器的模拟实现-Toy模板网

这篇具有很好参考价值的文章主要介绍了[ C++ ] STL---反向迭代器的模拟实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言：

反向迭代器简介

list反向迭代器的模拟实现

反向迭代器的模拟实现(适配器模式)

SGI版本STL反向迭代器源码

STL库中解引用操作与出口设计

适配list的反向迭代器

适配vector的反向迭代器

前言：

反向迭代器是一种特殊类型的迭代器，它可以逆向遍历容器中的元素，与正向迭代器相比，反向迭代器从容器的末尾开始，向前遍历到容器的起始位置，反向迭代器提供了一种方便的方式来反向访问容器中的元素，特别适用于需要逆序处理数据的场景；

在C++标准库中，反向迭代器通常通过rbegin()和rend()成员函数来获取，一般情况下，rbegin()返回指向容器最后一个元素的迭代器，而rend()返回指向容器起始位置前一个元素的迭器；

反向迭代器简介

[ C++ ] STL---反向迭代器的模拟实现,c++,开发语言,反向迭代器

#include <iostream>
#include <list>
using namespace std;
int main()
{
	list<int> lt;
	lt.push_back(10);
	lt.push_back(20);
	lt.push_back(30);
	lt.push_back(40);
	lt.push_back(50);

	//正向遍历
	list<int>::iterator it = lt.begin();
	while (it != lt.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	//反向遍历
	list<int>::reverse_iterator rit = lt.rbegin();
	while (rit != lt.rend())
	{
		cout << *rit << " ";
		++rit;
	}
	cout << endl;
	return 0;
}

运行结果：

[ C++ ] STL---反向迭代器的模拟实现,c++,开发语言,反向迭代器

list反向迭代器的模拟实现

思考一：

从行为方式上，反向迭代器与正向迭代器的区别是什么?

[ C++ ] STL---反向迭代器的模拟实现,c++,开发语言,反向迭代器

正向迭代器与反向迭代器的除了++、- -等接口外毫无区别；

若只实现链表的反向迭代器，如何实现？

链表普通迭代器实现入口：[ C++ ] STL---list的模拟实现-CSDN博客

链表反向迭代器实现步骤：

拷贝普通迭代器，类名修改为__List_reverse_iterator；

修改前置++、后置++、前置--、后置-- 接口；

list类中重定义reverse_iterator与const_reverse_iterator；

//list反向迭代器实现代码
template<class T, class Ref, class Ptr>
struct __List_reverse_iterator//修改类名
{
	typedef ListNode<T> Node;
	Node* _node;
	__List_reverse_iterator(Node* node)
		:_node(node)
	{}
	typedef __List_reverse_iterator<T> self;

	//修改++/--接口的指向
	self& operator++()
	{
		_node = _node->_prev;
		return *this;
	}
	//it++
	self operator++(int)
	{
		self tmp(*this);
		_node = _node->_prev;
		return tmp;
	}
	//--it
	self& operator--()
	{
		_node = _node->_next;
		return *this;
	}
	//it--
	self operator--(int)
	{
		self tmp(*this);
		_node = _node->_next;
		return tmp;
	}
	bool operator==(const self& s)
	{
		return _node == s._node;
	}
	bool operator!=(const self& s)
	{
		return _node != s._node;
	}
	Ref operator*()
	{
		return _node->_data;
	}
	Ptr operator->()
	{
		return &_node->_data;
	}
};

template<class T>
class list
{
	typedef ListNode<T> Node;
public:
    //list类中重定义
	typedef __List_reverse_iterator<T, T&, T*> reverse_iterator;//重命名反向迭代器
	typedef __List_reverse_iterator<T, const T&, const T*> const_reverse_iterator;//重命名const反向迭代器

	//......

private:
	Node* _head;
};

反向迭代器的模拟实现(适配器模式)

上述实现list反向迭代器的方式会在同一份文件中，存在普通迭代器与反向迭代器两个类并且两个类中仅有个别接口略有差异，代码冗余，导致可读性变差，更好的实现方案是什么?

解决方案：

vector/list/二叉树等容器均要面临反向迭代器的实现问题，如此便采用适配器模式，即链表的正向迭代器适配（改造）出链表的反向迭代器，vector的正向迭代器适配（改造）出vector的反向迭代器；

SGI版本STL反向迭代器源码

//stl_iterator.h文件
template <class _Iterator>
class reverse_iterator 
{
protected:
  _Iterator current;
public:
  typedef typename iterator_traits<_Iterator>::iterator_category
          iterator_category;
  typedef typename iterator_traits<_Iterator>::value_type
          value_type;
  typedef typename iterator_traits<_Iterator>::difference_type
          difference_type;
  typedef typename iterator_traits<_Iterator>::pointer
          pointer;
  typedef typename iterator_traits<_Iterator>::reference
          reference;

  typedef _Iterator iterator_type;
  typedef reverse_iterator<_Iterator> _Self;

public:
  reverse_iterator() {}
  explicit reverse_iterator(iterator_type __x) : current(__x) {}

  reverse_iterator(const _Self& __x) : current(__x.current) {}
#ifdef __STL_MEMBER_TEMPLATES
  template <class _Iter>
  reverse_iterator(const reverse_iterator<_Iter>& __x)
    : current(__x.base()) {}
#endif /* __STL_MEMBER_TEMPLATES */
    
  iterator_type base() const { return current; }
  reference operator*() const {
    _Iterator __tmp = current;
    return *--__tmp;
  }
#ifndef __SGI_STL_NO_ARROW_OPERATOR
  pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */

  _Self& operator++() {
    --current;
    return *this;
  }
  _Self operator++(int) {
    _Self __tmp = *this;
    --current;
    return __tmp;
  }
  _Self& operator--() {
    ++current;
    return *this;
  }
  _Self operator--(int) {
    _Self __tmp = *this;
    ++current;
    return __tmp;
  }

  _Self operator+(difference_type __n) const {
    return _Self(current - __n);
  }
  _Self& operator+=(difference_type __n) {
    current -= __n;
    return *this;
  }
  _Self operator-(difference_type __n) const {
    return _Self(current + __n);
  }
  _Self& operator-=(difference_type __n) {
    current += __n;
    return *this;
  }
  reference operator[](difference_type __n) const { return *(*this + __n); }  
};

//stl_list.h文件
reverse_iterator rbegin() 
{ 
return reverse_iterator(end()); 
}
const_reverse_iterator rbegin() const 
{ 
return const_reverse_iterator(end()); 
}

reverse_iterator rend()
{ 
return reverse_iterator(begin()); 
}
const_reverse_iterator rend() const
{ 
return const_reverse_iterator(begin()); 
}

STL库中解引用操作与出口设计

[ C++ ] STL---反向迭代器的模拟实现,c++,开发语言,反向迭代器

STL库中设计了一种对称结构，正向迭代器的开始位置为反向迭代器的结束位置，反向迭代器的开始位置即正向迭代器的结束位置；

适配list的反向迭代器

实现思路：

将正向迭代器作为模板参数传递给反向迭代器的成员变量cur，如此反向迭代器就可以自动匹配容器，反向迭代器就可以统一实现复用了：

//ReverseIterator.h文件
//第一个模版参数为正向迭代器,利用正向迭代器改造反向迭代器;
//第二个模版参数Ref定义反向迭代器的数据类型，数据类型分为const类型/非const类型;
//第三个模版参数Ptr定义自定义类型指针所指向的数据的的读写属性;
template<class Iterator,class Ref,class Ptr>
struct ReverseIterator
{
	//成员变量cur,cur为正向迭代器类所定义的对象
	Iterator cur;
	//ReverseIterator<Iterator,Ref,Ptr> operator++()
	typedef ReverseIterator<Iterator, Ref, Ptr> Self;
	Self& operator++()
	{
		--cur;//调用cur对象所属类的operator--()函数
		return *this;
	}
	Self operator++(int)
	{
		Self tmp(cur);
		--cur;
		return tmp;
	}
	Self& operator--()
	{
		++cur;//调用cur对象所属类的operator++()函数
		return *this;
	}
	Self operator--(int)
	{
		Self tmp(cur);
		++cur;
		return tmp;
	}
	// !=/== 本质比较正向迭代器也即结点的指针
	bool operator!=(const Self& s)
	{
		return cur != s.cur;
	}
	bool operator==(const Self& s)
	{
		return cur == s.cur;
	}
	//构造函数(正向迭代器构造反向迭代器)
	ReverseIterator(Iterator it)
		:cur(it)
	{}
	Ref operator*()
	{
		Iterator tmp = cur;
		--tmp;
		return *tmp;
	}
	//需要对象指针即对象地址，所以先解引用再取&
	Ptr operator->()
	{
		return &(operator*());
	}
};

list类中统一名称并且需要提供出口；

//list.h文件代码节选
template<class T>
class list
{
typedef ListNode<T> Node;
public:
typedef __List_iterator<T, T&, T*> iterator;
typedef __List_iterator<T, const T&, const T*> const_iterator;

//list类中统一名称
typedef  ReverseIterator<iterator, T&, T*> reverse_iterator;
typedef  ReverseIterator<iterator, const T&, const T*> const_reverse_iterator;

//搭配出口,list类中实现rbegin()、rend()
reverse_iterator rbegin()
{
	return reverse_iterator(end());
}
reverse_iterator rend()
{
	return reverse_iterator(begin());
}
//......
}

适配vector的反向迭代器

//vector.h文件代码节选
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;

//vector中统一名称
typedef  ReverseIterator<iterator, T&, T*> reverse_iterator;
typedef  ReverseIterator<iterator, const T&, const T*> const_reverse_iterator;


//搭配出口,vector中实现rbegin()、rend()
reverse_iterator rbegin()
{
	return reverse_iterator(end());
}
reverse_iterator rend()
{
	return reverse_iterator(begin());
}
//......
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _endofstorage = nullptr;
};