C++ STL学习之【反向迭代器】

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

✨个人主页: 北 海
🎉所属专栏: C++修行之路
🎊每篇一句: 图片来源

  • A year from now you may wish you had started today.
    • 明年今日,你会希望此时此刻的自己已经开始行动了。

C++ STL学习之【反向迭代器】



🌇前言

适配器模式是 STL 中的重要组成部分,在上一篇文章中我们学习了 容器适配器 的相关知识,即 stackqueue,除了 容器适配器 外,还有 迭代器适配器,借助 迭代器适配器,可以轻松将各种容器中的普通迭代器转变为反向迭代器,这正是适配器的核心思想

C++ STL学习之【反向迭代器】


🏙️正文

反向迭代器适用于所有的容器,因此它是作为一个单独的 .h 文件出现的,别的容器如果想使用,直接包含就行了

1、反向迭代器设计

反向迭代器 reverse_iterator 可以用来反向遍历容器,在某些场景下很实用

C++ STL学习之【反向迭代器】
反向迭代器类中需要有:正向迭代器对象构造函数

template<class Iterator>
struct __reverse_iterator
{
	Iterator _cur;	//正向迭代器类

	//需要借助构造函数,构成出正向迭代器
	__reverse_iterator(Iterator cur)
		:_cur(cur)
	{}
};

注意源码中的反向迭代器设计较为复杂,涉及 萃取 等操作,为了方便学习,这里实现的是简易版本

1.1、反向思想

何谓反向?与正向相反就是反向,比如时钟正常都是顺时针转,但如果时钟逆时针选择,此时就称为反方向的钟

C++ STL学习之【反向迭代器】

存在 vector<int>() = {1, 2, 3, 4, 5} 不同方向的遍历结果不同

正向迭代器:正向遍历
结果:1 2 3 4 5

反向迭代器:反向遍历
结果:5 4 3 2 1

C++ STL学习之【反向迭代器】

注:库中的反向迭代器在设计时,为了最求极致的对称,rbegin() 指向最后一个有效元素的下一个位置,rend() 指向第一个有效元素(位置是与正向迭代器相反的)

//_cur 为正向迭代器
self& operator++()
{
	--_cur;	//你要++,我就--
	return *this;
}
self operator++(int)
{
	Iterator tmp = _cur;
	--_cur;
	return tmp;
}

self& operator--()
{
	++_cur;	//你要--,我就++,反过来操作
	return *this;
}
self operator--(int)
{
	Iterator tmp = _cur;
	++_cur;
	return tmp;
}

1.2、多参数模板

在模拟实现 list 迭代器类时,为了解决普通对象与 const 对象的代码冗余问题,引入了多参数,通过对形参传递不同的对象,变换为不同属性的迭代器;在反向迭代器类中,这一种巧妙思想也得到了继承

template<class Iterator, class Ref, class Ptr>
struct __reverse_iterator
{
	typedef __reverse_iterator<Iterator, Ref, Ptr> self;	//重命名迭代器类为 self
	Iterator _cur;	//正向迭代器类
	
	//……
};

在涉及 operator*() 时,需要返回目标对象引用,使用 Ref;同理,在涉及 operator->() 时,需要返回目标对象指针,使用 Ptr

具体返回对象(引用 / 指针)是否为 const 修饰,取决于调用方

1.3、极致对称

在反向迭代器类中,有一个十分奇怪的函数 operator*(),它返回的并非当前所指向的对象,而且上一个对象

Ref operator*()
{
	Iterator tmp = _cur;
	return *--tmp;	//返回的是上一个对象
}

原因:大佬在设计时为了追求与正向迭代器的绝对对称,故意指向位置与其保持一致,仅仅是 rend()begin() 处,rbegin()end()

C++ STL学习之【反向迭代器】
经过这样设计后,rbegin()rend() 函数的实现就变得简单了,此时压力给到了 operator*() 的实现

reverse_iterator rbegin() { reverse_iterator(end()); }	//开始 -> 尾
reverse_iterator rend() { reverse_iterator(begin()); }	//结束 -> 头

1.4、其他功能

假设想通过迭代器直接访问自定义对象中的成员时,需要用到 operator->() 函数,作用是取出迭代器所指向对象的指针 Ptr

Ptr operator->()
{
	return &(operator*());	//采取复用的形式
}

迭代器还需要比较函数 operator==()operator!=(),具体实现时,都是在复用具体对象的比较函数

bool operator==(const self& s)
{
	return (_cur == s._cur);
}
bool operator!=(const self& s)
{
	return (_cur != s._cur);
}

以上就是反向迭代器所必须的基础功能,如果你还想实现更多比较逻辑,如 operator<() 等,可以自己实现

反向迭代器类的完整代码:

#pragma once

namespace Yohifo
{
	template<class Iterator, class Ref, class Ptr>
	struct __reverse_iterator
	{
		typedef __reverse_iterator<Iterator, Ref, Ptr> self;	//重命名迭代器类为 self
		Iterator _cur;	//正向迭代器类

		__reverse_iterator(Iterator cur)
			:_cur(cur)
		{}

		Ref operator*()
		{
			Iterator tmp = _cur;
			return *--tmp;
		}

		Ptr operator->()
		{
			return &(operator*());
		}

		//_cur 为普通(正向)迭代器
		self& operator++()
		{
			--_cur;
			return *this;
		}
		self operator++(int)
		{
			Iterator tmp = _cur;
			--_cur;
			return tmp;
		}

		self& operator--()
		{
			++_cur;
			return *this;
		}
		self operator--(int)
		{
			Iterator tmp = _cur;
			++_cur;
			return tmp;
		}

		bool operator==(const self& s)
		{
			return (_cur == s._cur);
		}
		bool operator!=(const self& s)
		{
			return (_cur != s._cur);
		}
	};
}

编写完成此头文件 reverse_iterator.hpp 后,任何具有正向迭代器的容器,都可以利用迭代器适配器,适配出属于自己的反向迭代器

具体使用例子可以接着往下看


2、应用于 vector

vector 模拟实现中,引入头文件 reverse_iterator.hpp,定义出反向迭代器所必须的函数

#pragma once
#include <iostream>
#include <string>
#include <assert.h>
#include <vector>	//对比测试用
#include <algorithm>	//排序所需要的头文件
#include <functional>	//仿函数头文件
#include "reverse_iterator.hpp"	//使用反向迭代器必须的头文件

using std::cin;
using std::cout;
using std::endl;
using std::string;

template<class T>
class vector
{
public:
	//……

	//=====反向迭代器=====
	typedef __reverse_iterator<iterator, T&, T*> reverse_iterator;
	typedef __reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;

	reverse_iterator rbegin() { return reverse_iterator(end()); }
	reverse_iterator rend() { return reverse_iterator(begin()); }

	const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
	const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
	
	//……

private:
	iterator _start;	//指向起始位置
	iterator _finish;	//指向有效元素的下一个位置
	iterator _end_of_storage;	//指向可用空间的下一个位置
};

通过反向迭代器进行遍历

void TestVector9()
{
	int arr[] = { 1,2,3,4,5,6,7,8,9 };
	vector<int> v(arr, arr + sizeof(arr) / sizeof(arr[0]));

	vector<int>::reverse_iterator rit = v.rbegin();
	while (rit != v.rend())
	{
		cout << *rit << " ";
		++rit;	//反向迭代器++,就是--
	}
	cout << endl;
}

C++ STL学习之【反向迭代器】
可以成功使用反向迭代器进行遍历


3、应用于 list

既然是迭代器适配器,那么反向迭代器也可以适用于 list

#pragma once
#include <iostream>
#include <cassert>
#include <vector>
#include "reverse_iterator.hpp"	//使用反向迭代器

using namespace std;

//……

//list本类
template<class T>
class list
{
	typedef __list_node<T> node;
	typedef T value_type;
	typedef T& refence;
	typedef const T& const_refence;
public:

	//……
	
	//=====反向迭代器=====
	typedef __reverse_iterator<iterator, T&, T*> reverse_iterator;
	typedef __reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;

	reverse_iterator rbegin() { return reverse_iterator(end()); }
	reverse_iterator rend() { return reverse_iterator(begin()); }

	const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
	const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }

	//……
	
private:
	//初始化出头节点
	void empty_init()
	{
		_head = new node;
		_head->_prev = _head->_next = _head;
	}

	node* _head;	//哨兵位节点
};

通过反向迭代器对自定义类型数据进行遍历

struct B
{
	B(int a = 0, char c = 0)
		:_a(a)
		,_c(c)
	{}

	int _a;
	char _c;
};

void TestList()
{
	list<B> lb;

	lb.push_back(B(1, 'a'));
	lb.push_back(B(2, 'b'));
	lb.push_back(B(3, 'c'));

	list<B>::reverse_iterator rit = lb.rbegin();
	while (rit != lb.rend())
	{
		cout << "_a: " << rit->_a << " | " << "_c: " << rit->_c << endl;
		++rit;	//即使是反向迭代器,也是++
	}
	cout << endl;
}

C++ STL学习之【反向迭代器】
此时主要是用到了 operator->() 访问自定义类型中的成员变量


4、源码

关于 vectorlist (迭代器版)的源码在下面仓库中

vector(反向迭代器版)

list(反向迭代器版)


🌆总结

以上就是本篇关于 C++ STL 学习之【反向迭代器】的全部内容了,在本篇文章中,我们主要学习了反向迭代器类的思想及实现,最后分别用了 vectorlist 进行了测试,成功实现了反向遍历

如果你觉得本文写的还不错的话,可以留下一个小小的赞👍,你的支持是我分享的最大动力!

如果本文有不足或错误的地方,随时欢迎指出,我会在第一时间改正


C++ STL学习之【反向迭代器】

文章来源地址https://www.toymoban.com/news/detail-424545.html

相关文章推荐

STL 之 适配器

C++ STL学习之【容器适配器】

===============

STL 之 list 类

C++ STL学习之【list的模拟实现】

C++ STL学习之【list的使用】

===============

STL 之 vector 类

C++ STL学习之【vector的模拟实现】

C++ STL学习之【vector的使用】

C++ STL学习之【反向迭代器】

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

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

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

相关文章

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

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

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

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

    2024年02月11日
    浏览(41)
  • 【C++STL】list的反向迭代器

    list的反向迭代器 reverse.h list.h test.cpp 疑问1:为什么在迭代器当中不需要写深拷贝、析构函数 1、因为迭代器就是希望做到浅拷贝,就是需要拿到地址而不是值,因为迭代器的修改是会影响对象中的内容的 2、因为迭代器并没有申请额外的空间,所以不需要析构,如果写了析构

    2024年02月12日
    浏览(37)
  • 【STL】优先级队列&反向迭代器详解

    目录 一,栈_刷题必备 二,stack实现 1.什么是容器适配器 2.STL标准库中stack和queue的底层结构  了解补充:容器——deque  1. deque的缺陷 2. 为什么选择deque作为stack和queue的底层默认容器 三,queue实现 1. 普通queue  2,优先级队列(有难度) 1. 功能 2. 模拟实现 1). 利用迭代器_构造

    2024年02月13日
    浏览(36)
  • 【C++_STL】优先级队列&反向迭代器详解

    目录 一,栈_刷题必备 二,stack实现 1.什么是容器适配器 2.STL标准库中stack和queue的底层结构  了解补充:容器——deque  1. deque的缺陷 2. 为什么选择deque作为stack和queue的底层默认容器 三,queue实现 1. 普通queue  2,优先级队列(有难度) 1. 功能 2. 模拟实现 1). 利用迭代器_构造

    2024年02月09日
    浏览(37)
  • C++ 反向迭代器

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

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

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

    2024年02月02日
    浏览(38)
  • C++迭代器(STL迭代器)iterator详解

    要访问顺序容器和关联容器中的元素,需要通过“迭代器(iterator)”进行。迭代器是一个变量,相当于容器和操纵容器的算法之间的中介。迭代器可以指向容器中的某个元素,通过迭代器就可以读写它指向的元素。从这一点上看,迭代器和指针类似。 迭代器按照定义方式分

    2024年02月03日
    浏览(45)
  • 细说C++反向迭代器:原理与用法

    迭代器与反向迭代器的概念引入 迭代器(Iterator)是C++标准模板库(STL)中的一个核心概念,它提供了一种访问容器中元素的方式,而无需了解容器底层的实现细节。迭代器就像是一个指向容器中元素的指针,通过它可以遍历容器中的元素,进行读取、修改或删除操作。 反向

    2024年03月18日
    浏览(41)
  • C++【栈&队列(3种)&反向迭代器】

    适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结),该种模式是将一个类的接口转换成客户希望的另外一个接口。 后面所介绍的栈,队列,反向迭代器都是一种适配器。 虽然stack和queue中也可以存放元素,但在STL中

    2023年04月17日
    浏览(39)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包