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

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

目录

前言:

反向迭代器简介

list反向迭代器的模拟实现

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

SGI版本STL反向迭代器源码

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

适配list的反向迭代器

适配vector的反向迭代器


前言:

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

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

反向迭代器简介

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

[ 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博客

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

  1. 拷贝普通迭代器,类名修改为__List_reverse_iterator
  2. 修改前置++、后置++、前置--、后置-- 接口
  3. 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++,开发语言,反向迭代器

[ 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;
};

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

[ C++ ] STL---反向迭代器的模拟实现,c++,开发语言,反向迭代器文章来源地址https://www.toymoban.com/news/detail-852660.html

到了这里,关于[ C++ ] STL---反向迭代器的模拟实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【STL】模拟实现反向迭代器

    目录 1. 读源码 2. 搭建框架  3. 迭代器的操作 operator*()  operator-() operator++() operator--() operator!=() 4. 实现 list 的反向迭代器 5. 实现 vector 的反向迭代器 6. 源码分享 写在最后: 我们之前实现的 vector,list 好像都只实现了他们的正向迭代器,那有正向, 会有反向迭代器这种东西吗

    2024年02月13日
    浏览(30)
  • C++ 反向迭代器的设计与实现

    在本文开始之前,先明晰几个 的含义(T : 模板参数): Ref : T / const T Ptr : T* / const T* 一、反向迭代器设计的上帝视角 我们希望将 反向迭代器 设计成一种适配器——传 list::iterator 得到 list 的反向迭代器,传 vector::iterator 得到 vector 的反向迭代器。 STL 中,(正向)迭

    2024年03月15日
    浏览(44)
  • STL之list模拟实现(反向迭代器讲解以及迭代器失效)

    这次是关于list的模拟实现的代码,先看看下面的代码: 上面是list的代码,其底层是一个带头双向循环的链表,实现的方法就不说了,相信大家已经都会了,然后自己实心的list我没有写析构函数等,这个也很简单,循环利用成员函数中的删除函数就可以。 先来说说个人认为

    2024年02月11日
    浏览(33)
  • 【C++】反向迭代器的设计

    + 前言 STL中不少的容器需要有迭代器这样的设计, 特别是正向迭代器,几乎每个容器都有自己的特定实现方式 ,有了正向迭代器之后,我们还要提供反向迭代器以供一些特殊的需求,但是许多容器的正向迭代器实现的方式不一样,如果我们要实现其反向迭代器,每个容器的

    2024年02月02日
    浏览(29)
  • C++ stl迭代器的理解

    首先,stl采用了泛型编程,分成了容器和算法,容器和算法之间的桥梁是迭代器,迭代器的作用是可以让算法不区分容器来作用在数据上。 迭代器本质上是指针,原有类型(比如int,double等)的指针也可以是迭代器,那如何让代码区分开他们呢? 我们可以把自定义的迭代器包

    2024年02月15日
    浏览(36)
  • c++--反向迭代器的实现

    1.反向迭代器 迭代器有两种,一种是正向的,一种是反向的,方向迭代器的主要功能就是实现数据的反向访问,通过正向迭代器的适配生成的,适配器就是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结),该种模式是将一

    2024年02月16日
    浏览(32)
  • C++ [STL容器反向迭代器]

    本文已收录至《C++语言》专栏! 作者:ARMCSKGT 我们知道STL大部分容器都有迭代器,迭代器又分为正向迭代器和反向迭代器,对于正向迭代器以及实现前面我们已经了解了不少,而反向迭代器的设计思想是 适配器模式 ,本节我们介绍反向迭代器的实现! 适配器是把一个类的接

    2024年02月11日
    浏览(46)
  • C++ STL学习之【反向迭代器】

    ✨个人主页: 北 海 🎉所属专栏: C++修行之路 🎊每篇一句: 图片来源 A year from now you may wish you had started today. 明年今日,你会希望此时此刻的自己已经开始行动了。 适配器模式是 STL 中的重要组成部分,在上一篇文章中我们学习了 容器适配器 的相关知识,即 stack 与 queu

    2023年04月25日
    浏览(35)
  • 深入篇【C++】手搓模拟实现list类(详细剖析底层实现原理)&&模拟实现正反向迭代器【容器适配器模式】

    1.一个模板参数 在模拟实现list之前,我们要理解list中的迭代器是如何实现的。 在vector中迭代器可以看成一个指针,指向vector中的数据。它的解引用会访问到具体的数据本身,++会移动到下一个数据位置上去,这些都是因为vector具有天生的优势:空间上是连续的数组,这样指

    2024年02月15日
    浏览(33)
  • 【C++】STL——list的模拟实现、构造函数、迭代器类的实现、运算符重载、增删查改

    list使用文章 析构函数   在定义了一个类模板list时。我们让该类模板包含了一个内部结构体_list_node,用于表示链表的节点。该结构体包含了指向前一个节点和后一个节点的指针以及节点的值。在list中保存了链表的头节点指针和链表长度大小。       因为list的底层实现

    2024年02月14日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包