C++——反向迭代器

🕗 发布于 2024-10-12 11:58 c++ 数据库 list 开发语言 算法

1.回顾

template<class T>
struct __list_iterator
{
typedef list_node<T> Node;
typedef __list_iterator<T> self;
Node* _node;
 
__list_iterator(Node* node)
:_node(node)
{}
 
self& operator++()
{
_node = _node->_next;
return *this;
}
 
T& operator*()
{
return _node->_data;
}
 
bool operator!=(const self& s)
{
return (_node != s._node);
}
};

2.list的反向迭代器

2.1库中反向迭代器的使用

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

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

return 0;
}

2.2模拟实现

复用已经实现的迭代器实现反向迭代器

使用正向迭代器适配出反向迭代器

2.2.1反向迭代器

//reverse_iterator.h

#pragma once
//适配器模式
//使用正向迭代器适配出一个反向迭代器

// vector::iterator 适配出 vector 的 ReverseIterator
// list::iterator 适配出 list 的 ReverseIterator
// ...

template<class Iterator, class Ref, class Ptr>
class ReverseIterator
{
public:
typedef ReverseIterator<Iterator, Ref, Ptr> Self;

ReverseIterator(Iterator it)
:_it(it)
{}

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

//普通迭代器和const迭代器的唯一区别：
//一个是可读可写，另一个是只读的

Ref operator*()//这里不知道T和Iterator的关系
{
return *_it;
}

Ptr operator->()
{
//return _it->operator();//???
return _it.operator->();//这里只能显式调用
}

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

private:
Iterator _it;
};

2.2.2 list

//list.h

#pragma once
//编译器为了节省编译时间，只会向上查找
#include"reverse_iterator.h"

namespace jxy
{

template<class T>
class list//list的框架本质是封装+运算符重载
{
typedef list_node<T> Node;

public:
typedef __list_iterator<T,T&,T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;

//反向的普通迭代器
typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
//反向的const迭代器
typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;

//普通迭代器使用普通的适配
//const的使用const适配

reverse_iterator rbegin()
{
//构造
return reverse_iterator(--end());
}

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

const_reverse_iterator rbegin() const
{
return const_reverse_iterator(--end());
}

const_reverse_iterator rend() const
{
return const_reverse_iterator(end());//注意end()的类型
}

private:
Node* _head;
size_t _size;
};
}

2.3测试反向迭代器

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

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

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

return 0;
}

2.4测试const反向迭代器

void func(const jxy::list<int>& lt)
{
jxy::list<int>::const_reverse_iterator rit = lt.rbegin();
while (rit != lt.rend())
{
//迭代器指向的内容不能修改
//*rit += 10;

cout << *rit << " ";
++rit;
}
cout << endl;
}

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

func(lt);

return 0;
}

3.vector的反向迭代器

3.1模拟实现

与list迭代器类似，直接CV一份

#pragma once
#include"reverse_iterator.h"
#include<assert.h>
namespace jxy
{

template <class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;


typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
typedef ReverseIterator<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());
}

//注意：越界不是在编译时报错

iterator begin()
{
return _start;
}

iterator end()
{
return _finish;
}

const_iterator begin() const
{
return _start;
}

const_iterator end() const
{
return _finish;
}
};

}

此时出现了问题，编译不通过

3.2C++编译器的特殊处理

//演示这个特殊处理
class A
{
public:
A(int a=0)
:_a(a)
{}

void Print()
{
cout << "A" << endl;
}

private:
int _a;
};


int main()
{

A();//A的一个临时对象
//匿名对象也是一个临时对象

那么它具不具有常性？它具有常性，证明如下：

//A& ref = A(1);//这里不能给它取别名
const A& ref = A(); //但加上const就可以了

这里体现了const属性


能不能调用非const成员函数？
//按理说是不能的，因为有权限的放大
A(1).Print();//但事实上却是可以调用，这就很奇怪

这里又没有体现const属性


可以认为这里是C++处理的一个特例
A(1).Print();
//因为存在使用匿名对象去调用函数的需求，所以这里做出了特殊处理

return 0;
}

3.3修改

所以要对vector的反向迭代器进行修改。

list的反向迭代器也可以修改，但要重载运算符 - ，而且在意义上是不建议重载的

#pragma once
#include"reverse_iterator.h"
#include<assert.h>
namespace jxy
{

template <class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;


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

reverse_iterator rbegin()
{
//构造
//return reverse_iterator(--end());
return reverse_iterator(end()-1);
//所以这里改为减一即可
}

reverse_iterator rend()
{
//return reverse_iterator(--begin());
return reverse_iterator(begin()-1);
}

const_reverse_iterator rbegin() const
{
//return const_reverse_iterator(--end());
return const_reverse_iterator(end()-1);
}

const_reverse_iterator rend() const
{
//return const_reverse_iterator(--begin());
return const_reverse_iterator(begin()-1);
}

//注意：越界不是在编译时报错

iterator begin()
{
return _start;
}

iterator end()
{
return _finish;
}

const_iterator begin() const
{
return _start;
}

const_iterator end() const
{
return _finish;
}
};
}


int main()
{
//就和这里类似

int a = 10;
--a;//变量可以--
a - 1;//也可以-1

//--10;  //报错，10是常量
10 - 1;//可以 

return 0;
}

3.4测试反向迭代器

void func(const jxy::vector<int>& lt)
{
jxy::vector<int>::const_reverse_iterator rit = lt.rbegin();
while (rit != lt.rend())
{
//迭代器指向的内容不能修改
//*rit += 10;

cout << *rit << " ";
++rit;
}
cout << endl;
}


int main()
{
jxy::vector<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);

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

func(lt);

return 0;
}

4.SGI版本库中反向迭代器的实现

乍看库中的实现，vector会越界

list没有访问到第一个值，而且访问了哨兵位，是随机值

但实际上，这只是另外一种实现方式，它拥有自己的优势

为避免上述情况，在其中访问元素时，访问的是前一个位置

5.依照库中的思路再次模拟实现

5.1反向迭代器

//reverse_iterator.h

#pragma once


template<class Iterator, class Ref, class Ptr>
class ReverseIterator
{
public:
typedef ReverseIterator<Iterator, Ref, Ptr> Self;

ReverseIterator(Iterator it)
:_it(it)
{}

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

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

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

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

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

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

private:
Iterator _it;
};

5.2vector反向迭代器

#pragma once
#include"reverse_iterator.h"
#include<assert.h>

namespace jxy
{

template <class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;


    typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
    typedef ReverseIterator<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());
}

iterator begin()
{
return _start;
}

iterator end()
{
return _finish;
}

const_iterator begin() const
{
return _start;
}

const_iterator end() const
{
return _finish;
}
};
}

5.3list反向迭代器

//list.h

#pragma once
#include"reverse_iterator.h"

namespace jxy
{

template<class T>
class list//list的框架本质是封装+运算符重载
{
typedef list_node<T> Node;

public:
typedef __list_iterator<T,T&,T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;

//反向的普通迭代器
typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
//反向的const迭代器
typedef ReverseIterator<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:
Node* _head;
size_t _size;
};
}

原文地址：https://blog.csdn.net/2301_80342122/article/details/142765406

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：数据结构常用术语
下一篇：【优选算法】（第三十四篇）

Vivado - 在硬件中调试 Serial I/O (IBERT)
本文分享在 ZCU102 和 ZCU106 板卡上使用 IBERT Ultrascale GTY进行眼图测量的示例。
阅读更多2024-10-12
Spring Boot课程答疑：技术问题快速解答
在整个系统测试中，根据需求文档和设计文档，逐一对功能进行检测并写好测试用例，有效避免残片缺陷，因为产品出现缺陷不仅影响功能，而且可以导致数据的不准确，导致产品质量的降低，经过测试，才能使得产品的稳定性
阅读更多2024-10-12
Java后端面试----某团一面
mysql主要有有三种日志文件分别为：binlog,undolog,redolog三类binlog又称为归档日志（二进制日志），主要是对数据库的中的数据进行数据备份，崩溃恢复，数据复制等操作，binl
阅读更多2024-10-12
STM32F103C8T6 - 定时器
PSC、CNT和自动重装载寄存器构成了最基本的计时电路（时基单元），基本定时器只能选择内部时钟，所以时基单元直接连接到了内部时钟输入CK_INT。RCC的TIMxCLK一般都是系统的主频72MHz。时
阅读更多2024-10-12
java抽象类和接口-cnblog
在解决实际问题时,一般将父类作为抽象类，子类继承父类，并且实例化对象在一个类中，只要有有一个方法是抽象的，类就是抽象的抽象类被继承后需要实现所有的抽象方法，抽象类的关键词是abstract。
阅读更多2024-10-12
Mysql(八) --- 视图
前面我们学习了索引，这次我们来学习视图视图是一个虚拟的表，它是基于一个或多个基本表或其他视图的查询结果集。视图本身不存储数据，而是通过执行查询来动态生成数据。用户可以像操作普通表一样使用视图进行查询、
阅读更多2024-10-12
根据请求错误的状态码判断代理配置问题
使用雷池社区版配置代理的时候可以能会有很多的问题，配置代理可能回遇到不同的问题，这时候需要查看状态码
阅读更多2024-10-12
数据结构：单链表OJ题
相交链表、环形链表、链表随机复制（深拷贝）
阅读更多2024-10-12
yolo5快速上手训练数据集
names配置，就是lables中的类。根目录新建datasets目录。
阅读更多2024-10-12
【忆】Window 下可以ping，但是无法telnet ubuntu服务器端口
1、添加端口8096。
阅读更多2024-10-12