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

04-23 1210阅读 0评论

前言：

反向迭代器简介

list反向迭代器的模拟实现

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

SGI版本STL反向迭代器源码

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

适配list的反向迭代器

适配vector的反向迭代器

前言：

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

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

反向迭代器简介

#include 
#include 
using namespace std;
int main()
{
	list lt;
	lt.push_back(10);
	lt.push_back(20);
	lt.push_back(30);
	lt.push_back(40);
	lt.push_back(50);
	//正向遍历
	list::iterator it = lt.begin();
	while (it != lt.end())
	{
		cout ()
	{
		return &_node->_data;
	}
};
template
class list
{
	typedef ListNode Node;
public:
    //list类中重定义
	typedef __List_reverse_iterator reverse_iterator;//重命名反向迭代器
	typedef __List_reverse_iterator const_reverse_iterator;//重命名const反向迭代器
	//......
private:
	Node* _head;
};

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

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

解决方案：

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

SGI版本STL反向迭代器源码

//stl_iterator.h文件
template 
class reverse_iterator 
{
protected:
  _Iterator current;
public:
  typedef typename iterator_traits::iterator_category
          iterator_category;
  typedef typename iterator_traits::value_type
          value_type;
  typedef typename iterator_traits::difference_type
          difference_type;
  typedef typename iterator_traits::pointer
          pointer;
  typedef typename iterator_traits::reference
          reference;
  typedef _Iterator iterator_type;
  typedef reverse_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 
  reverse_iterator(const reverse_iterator& __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库中解引用操作与出口设计

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

适配list的反向迭代器

实现思路：

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

//ReverseIterator.h文件
//第一个模版参数为正向迭代器,利用正向迭代器改造反向迭代器;
//第二个模版参数Ref定义反向迭代器的数据类型，数据类型分为const类型/非const类型;
//第三个模版参数Ptr定义自定义类型指针所指向的数据的的读写属性;
template
struct ReverseIterator
{
	//成员变量cur,cur为正向迭代器类所定义的对象
	Iterator cur;
	//ReverseIterator operator++()
	typedef ReverseIterator 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 list
{
typedef ListNode Node;
public:
typedef __List_iterator iterator;
typedef __List_iterator const_iterator;
//list类中统一名称
typedef  ReverseIterator reverse_iterator;
typedef  ReverseIterator 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 vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
//vector中统一名称
typedef  ReverseIterator reverse_iterator;
typedef  ReverseIterator 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;
};

欢迎大家批评指正，博主会持续输出优质内容，谢谢大家观看，码字画图不易，希望大家给个一键三连支持~ 你的支持是我创作的不竭动力~