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

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

目录

1. 读源码

2. 搭建框架 

3. 迭代器的操作

operator*() 

operator->()

operator++()

operator--()

operator!=()

4. 实现 list 的反向迭代器

5. 实现 vector 的反向迭代器

6. 源码分享

写在最后:


1. 读源码

我们之前实现的 vector,list 好像都只实现了他们的正向迭代器,那有正向,

会有反向迭代器这种东西吗?答案是有的,那我们该怎么实现呢?

实际上根据我们之前的经验,根据每个容器的特色实现一份就好了,

但是之前在读源码的时候,好像并没有看到源码实现,这是怎么一回事呢?

来读读 list 的源码是怎么做的:

【STL】模拟实现反向迭代器,C++学习,c++,开发语言,stl

我们在这里找到了 list 的反向迭代器,他没有自己实现,

而是直接使用了这个 reverse_iterator 的类模板,这又是怎么一回事呢?

我们在 STL 源码的 stl_iterator.h 文件中找到了答案:

【STL】模拟实现反向迭代器,C++学习,c++,开发语言,stl

这里面竟然存在这样一个类,reverse_iterator,难道说其他的容器,

也都不是自己实现一份反向迭代器,而是直接使用这个类吗?

想到这里,我们赶紧去看一眼 vector 的源码:

【STL】模拟实现反向迭代器,C++学习,c++,开发语言,stl

发现了没有,他们的调用方式是一模一样的,都是同样的调用,

使用的类型是他们各自的迭代器类型,通过模板的特性,

让编译器实例化出不同的代码,达成实现他们各自的迭代器的目的,

非常巧妙的设计,只一份代码,让所有的容器的反向迭代器都复用,

那他是怎么实现的呢?我们来看看他实现的源码:

【STL】模拟实现反向迭代器,C++学习,c++,开发语言,stl

我们可以看到这个就是迭代器类型的成员变量了。

还是老规矩,看完成员变量,我们去看一下核心的接口实现,

先来看 ++ 的重载 :

【STL】模拟实现反向迭代器,C++学习,c++,开发语言,stl

他的 ++ 就是让原先的正向迭代器执行 -- 操作,没毛病,

再来看 -- 的重载:

【STL】模拟实现反向迭代器,C++学习,c++,开发语言,stl

也没毛病,我们再来看看他的解引用操作:

【STL】模拟实现反向迭代器,C++学习,c++,开发语言,stl

这下怪了,为啥解引用取到的位置是原先位置的前一个位置呢? 

那我们就得去看看那些容器的反向迭代器是怎么确定初始位置的了,

先来看 list 的:

【STL】模拟实现反向迭代器,C++学习,c++,开发语言,stl

正向迭代器的 begin 就是第一个位置,end 就是哨兵位的头结点,

但是 rbegin 用的是 end 来初始化反向迭代器,也就是他在 end 的位置(哨兵位上)

而 rend 用的是 begin 来初始化反向迭代器,也就是他在 begin 的位置(第一个位置上)

我们也可以看一下 vector 是不是这样的:

【STL】模拟实现反向迭代器,C++学习,c++,开发语言,stl

可以看到也是这样的。

那这样好像不太对啊,如果直接使用迭代器,

第一次解引用就会出问题:(这里我写段伪代码感受一下)

rit =  rbegin()

while(rit != rend()) {

        cout << *rit << endl; // 这里就出问题了

        rit++;

}

所以库里在实现的解引用操作符的时候,解引用的就是他的前一个位置,

我再截出来看一眼:

【STL】模拟实现反向迭代器,C++学习,c++,开发语言,stl

现在看的也差不多了,马上开始动手实现吧~

2. 搭建框架 

namespace xl {
	template <class Iterator>
	class reverse_iterator {
	private:
		Iterator _it;

	public:
		reverse_iterator(Iterator it)
			: _it(it)
		{}
	};
}

其实框架就一点点啦,

就是写个成员变量,写个构造函数就差不多完成啦。

3. 迭代器的操作

operator*() 

我们直接上手:

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

这个时候我们遇到了一些困难,

我们该怎么返回这个值呢?还是跟之前一样我们需要让他支持 const 类型,

先来看看源码是怎么实现的:

【STL】模拟实现反向迭代器,C++学习,c++,开发语言,stl

他这里的 reference 通过了一系列的复杂操作然后套了出来,

这里他用的操作是萃取,比较的麻烦,还涉及模板的特化,

所以我们打算用一个比较方便暴力的方法,就是通过模板参数直接传过来:

 【STL】模拟实现反向迭代器,C++学习,c++,开发语言,stl

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

这样下面的实现也解决了:

operator->()

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

operator++()

这里我们再顺便把类名 typedef 一下,因为他太长了:

【STL】模拟实现反向迭代器,C++学习,c++,开发语言,stl

然后来实现 ++ :(这里我都是前置和后置都实现了)

self& operator++() {
	--_it;
	return *this;
}

self operator++(int) {
	self tmp = _it;
	--_it;
	return tmp;
}

operator--()

self& operator--() {
	++_it;
	return *this;
}

self operator--(int) {
	self tmp = _it;
	++_it;
	return tmp;
}

operator!=()

直接用正向迭代器的 != 比较即可:

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

4. 实现 list 的反向迭代器

typedef reverse_iterator<iterator, const T&, const T*> const_reverse_iterator;
typedef reverse_iterator<iterator, T&, T*> reverse_iterator;

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

 我们来测试一下:

#include "iterator.h"
#include "list.h"

int main()
{
	xl::list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);

	for (auto e : lt) cout << e << " ";
	cout << endl;

	xl::list<int>::reverse_iterator rit = lt.rbegin();
	while (rit != lt.rend()) {
		cout << *rit << " ";
		++rit;
	}
	cout << endl;

	return 0; 
}

输出:

【STL】模拟实现反向迭代器,C++学习,c++,开发语言,stl

输出没毛病~ 

5. 实现 vector 的反向迭代器

跟 list 一模一样的操作(直接把代码粘过来即可)

然后我们直接测试:

void test_vector() {
	xl::vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);

	for (auto e : v) cout << e << " ";
	cout << endl;

	xl::vector<int>::reverse_iterator rit = v.rbegin();
	while (rit != v.rend()) {
		cout << *rit << " ";
		++rit;
	}
	cout << endl;
}

输出:

【STL】模拟实现反向迭代器,C++学习,c++,开发语言,stl

结果也没毛病~ 

6. 源码分享

模拟实现简易STL: 模拟实现简易STL (gitee.com)

写在最后:

以上就是本篇文章的内容了,感谢你的阅读。

如果感到有所收获的话可以给博主点一个哦。

如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~文章来源地址https://www.toymoban.com/news/detail-635611.html

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

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

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

相关文章

  • C++ [STL容器反向迭代器]

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

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

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

    2023年04月25日
    浏览(46)
  • 【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)
  • [STL-list]介绍、与vector的对比、模拟实现的迭代器问题

     list的底层是 带头双向链表 结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向其前一个元素和后一个元素。 与其他的序列式容器相比(array,vector,deque),list通常 在任意位置进行插入、移除元素的执行效率更好 list最大的缺陷是 不支持任意位

    2024年04月15日
    浏览(94)
  • 【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日
    浏览(38)
  • 【C++】STL——list的模拟实现、构造函数、迭代器类的实现、运算符重载、增删查改

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

    2024年02月14日
    浏览(48)
  • 【C++】STL——string的模拟实现、常用构造函数、迭代器、运算符重载、扩容函数、增删查改

    string使用文章   这里我们 实现常用的第四个string(const char* s)和析构函数     拷贝构造函数实现:   在堆上使用new为当前对象的成员变量_str分配内存空间,大小为s._capacity + 1字节,即字符串的容量加上一个结束符\\0的空间。   我们使用深拷贝而不是浅拷贝,

    2024年02月15日
    浏览(50)
  • 带你深入理解“栈”(c语言 c++和stl Stack三个版本的模拟实现)

    目录 一.栈的概念及结构 二.栈的实现(c语言版) 2.1静态增长的栈 2.2动态增长的栈 2.3动态栈的模拟实现    1.栈的初始化   2.入栈  3.出栈 4.获取栈顶元素 5.获取栈中有效数据个数 6.检查栈是否为空 7.栈的销毁 三.C++ 版本模拟实现栈  1.C++版本的源代码 四.c语言版本的源代码

    2024年02月08日
    浏览(44)
  • 面试之快速学习STL-迭代适配器

    参考:http://c.biancheng.net/view/7255.html 例子: 想使用反向迭代器实现逆序遍历容器,则该容器的迭代器类型必须是双向迭代器或者随机访问迭代器。 常见操作 注意这里不能用std::list,因为它是双向迭代器, +3的操作需要随机访问迭代器 。故联想到std::list排序只能使用list提供的

    2024年02月11日
    浏览(42)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包