目录
前言:
1 对反向迭代器的构造思想
2 实现反向迭代器
3 完整代码
前言:
本篇文章主要介绍了STL容器当中的反向迭代器,可能有朋友会说:“反向迭代器有什么好学的?不一样还是迭代器吗,我正向能写出来,还写不出反向?”有这种想法的朋友那你可得好好的看看咯,相信这对你有很大的帮助。
1 对反向迭代器的构造思想
以同类逻辑去考虑迭代器,我们反向迭代器应该与正向迭代器构造思想相同,正向迭代器的begin指向第一个数据,end指向最后一个数据的后一位,那么我们的反向迭代器也应该是rbegin指向倒数第一个数据,rend指向第一个数据的前一位,如下图:
我相信大多数人对于第一次遇到反向迭代器的想法都是这样的,包括博主自己,这也没有任何的问题,同样是能够实现反向迭代器的功能,但是这不是重点,我们实现这个思想时,多数会向下方代码那样,我以list举例,以这样的想法我们就会构建出这样的反向迭代器。
template<class T, class Ref, class Ptr>
struct __list_reverse_iterator
{
typedef list_node<T> node;
typedef __list_reverse_iterator<T, Ref, Ptr> self;
node* _node;
__list_reverse_iterator(node* n)
:_node(n)
{}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
self& operator++()
{
_node = _node->_prev;
return *this;
}
self operator++(int)
{
self tmp(*this);
_node = _node->_prev;
return tmp;
}
self& operator--()
{
_node = _node->_next;
return *this;
}
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;
}
};
上述代码没有任何问题,博主也测试过能够实现反向迭代器的功能,但是呢看着这个代码是不是觉得很不爽啊,因为这反向迭代器通过这种另外封装一个类的方式,然后实现了一个与正向迭代器相互冗余的功能,这代码相似度太高了,写出来都觉得代码很挫,不好意思说出去是自己写的。
基于此,请看看大佬是如何设计的吧。
大佬干了啥,直接将正向迭代器作为反向迭代器的模板类型,在反向迭代器中重定义操作符,然后使用正向迭代器的功能,当然这个方式也是需要重新封装一个类,大伙还是看不出来有啥牛逼的,请继续往下看。
2 实现反向迭代器
代码:
template<class iterator, class Ref, class Ptr>
struct __list_reverse_iterator
{
typedef __list_reverse_iterator<iterator, Ref, Ptr> Self;
iterator _cur;
__list_reverse_iterator(iterator it)
:_cur(it)
{}
Ref operator*()
{
iterator temp = _cur;
return *(--temp);
}
Self& operator++()
{
--_cur;
return *this;
}
Self& operator--()
{
++_cur;
return *this;
}
bool operator!=(const Self& ss)
{
return _cur != ss._cur;
}
};
看到我们的代码,因为反向迭代器的类型是正向迭代器,所以我们需要在里面放置一个正向迭代器类型变量供使用。
但是看到我们的反向迭代器构造了吗?我们对_cur变量赋初值等于iterator类型的it,但是it是怎么出来的?我们在使用反向迭代器的时候难道不是vv.rbegin();这种方式吗?我们有传递任何的数据吗?更何况还是一个正向迭代器类型的变量。
此时就需要看到我们的rbegin函数了。
reverse_iterator rbegin()
{
return reverse_iterator(end());
}
reverse_iterator rend()
{
return reverse_iterator(begin());
}
这样看可能不是很清楚,那我换一种方式表示:
reverse_iterator rbegin()
{
return reverse_iterator(iterator(_head));
}reverse_iterator rend()
{
return reverse_iterator(iterator(_head->next));
}
我们调用rbegin时,会实例化一个反向迭代器类,它通过正向迭代器去构造,正向迭代器通过结点指针构造。
大家有注意到吗?这种实现方式的rbegin和rend指向我们数据的那个位置?和我们开头的思想相同吗?很明显不同,它的头指向了最后一个数据的下一个位置,它的尾指向了第一个位置,如下图。
可是这样做的好处是什么?甚至我没有看到好处只看到了我之后*迭代器得到的数据都不对了,第一个数据都取不到了,但事实真的时是这样吗?回到代码中看:
Ref operator*()
{
iterator temp = _cur;
return *(--temp);
}
我们在反向迭代器当中重定义*操作符函数下干了啥?我们创建了一个临时对象,将临时对象--在解引用,那么这样我们不就获取到了正确的数据了吗?所以这种构造思想没有错误。
但是上面的道理大家都明白,好处在哪里?好了,重点到了!!
看到上图,我们的begin对应的是rend,end对应的是rbegin,那么我们可以做一件什么事情呢?那就是反向迭代器类的参数传递可以通过正向迭代器的begin()、end()函数构建。也就是下方代码。
reverse_iterator rbegin()
{
return reverse_iterator(end());
}
reverse_iterator rend()
{
return reverse_iterator(begin());
}
这也不是最重要的,最重要的是,我们将这份反向迭代器直接原封不动的放到vector当中,会有什么效果?你一定想不到,我们vector的反向迭代器也实现了!!
如下:
namespace boqi
{
template<class iterator, class Ref, class Ptr>
struct __list_reverse_iterator
{
typedef __list_reverse_iterator<iterator, Ref, Ptr> Self;
iterator _cur;
__list_reverse_iterator(iterator it)
:_cur(it)
{}
Ref operator*()
{
iterator temp = _cur;
return *(--temp);
}
Self& operator++()
{
--_cur;
return *this;
}
Self& operator--()
{
++_cur;
return *this;
}
bool operator!=(const Self& ss)
{
return _cur != ss._cur;
}
};
template<class T>
class vector
{
public:
//迭代器定义
typedef T* iterator;
typedef const T* const_iterator;
typedef struct __list_reverse_iterator<iterator, T&, T*> reverse_iterator;
typedef struct __list_reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
reverse_iterator rbegin()
{
return reverse_iterator(end());
}
reverse_iterator rend()
{
return reverse_iterator(begin());
}
private:
//三个迭代器表示一个开辟空间数组的3个位置
iterator _start;
iterator _finish;
iterator _end_of_storage;
};
}
看到,博主甚至连名字都没有更换,再看它是否能用。
测试代码:
void test9()
{
yf::vector<int> vv;
vv.push_back(1);
vv.push_back(2);
vv.push_back(3);
vv.push_back(4);
yf::vector<int>::reverse_iterator rit = vv.rbegin();
while (rit != vv.rend())
{
cout << *rit << " ";
++rit;
}
cout << endl;
}
输出:
看到了吗?我们的vector的反向迭代器直接就能用了,我们都知道vector和list的底层完全不同,通过大佬的这种方式实现,却将两个完全不同的迭代器完美的联系起来了,并且共用一份代码!而且不只是这两个容器可以用,任何由迭代器的容器都可以使用,因为只要你有迭代器,那一定支持++和--,而且它不关心你的正向迭代器是怎么实现的。对此我只能膜拜,大佬不愧是大佬。
3 完整代码
#pragma once
#include<iostream>
#include<list>
#include<vector>
#include<algorithm>
#include<assert.h>
namespace yf
{
template<class T>
struct node
{
//结点类在list创建时分配数据
node(const T& val = T())
:next(nullptr)
, prev(nullptr)
, data(val)
{}
//前结点、后结点、T类型数据
struct node<T>* next;
struct node<T>* prev;
T data;
};
//迭代器类
//Ref和Ptr分别是T&,和T*,目的是为了不让代码冗余,const T&,const T*
template<class T, class Ref, class Ptr>
struct __list_iterator
{
typedef struct node<T> Node;
typedef struct __list_iterator<T, Ref, Ptr> self;
//浅拷贝传入过来的结点指针,不需要去开辟新空间
//因为我们要的就是原本的结点
struct __list_iterator(Node* node)
:Pos(node)
{}
//*迭代器返回结点内部的数据
Ref operator*()
{
return Pos->data;
}
//到下一个结点,而不是结点指针的下一个位置
self& operator++()
{
Pos = Pos->next;
return *this;
}
self operator++(int)
{
self temp = *this;
Pos = Pos->next;
return temp;
}
self& operator--()
{
Pos = Pos->prev;
return *this;
}
self operator--(int)
{
self temp = *this;
Pos = Pos->prev;
return temp;
}
//返回节点数据的地址
Ptr operator->()
{
//Pos已经是结点了,但是如果需要访问的数据也是一个结构体
//那么获取到了它的地址,就能用->去访问了
return &Pos->data;
}
bool operator==(const self& val)
{
return Pos == val.Pos;
}
bool operator!=(const self& val)
{
return Pos != val.Pos;
}
Node* Pos;
};
//反向迭代器
template<class iterator, class Ref, class Ptr>
struct __list_reverse_iterator
{
typedef __list_reverse_iterator<iterator, Ref, Ptr> Self;
iterator _cur;
__list_reverse_iterator(iterator it)
:_cur(it)
{}
Ref operator*()
{
iterator temp = _cur;
return *(--temp);
}
Self& operator++()
{
--_cur;
return *this;
}
Self& operator--()
{
++_cur;
return *this;
}
bool operator!=(const Self& ss)
{
return _cur != ss._cur;
}
};
//带头双向循环链表
template<class T>
class list
{
public:
typedef struct node<T> Node;
typedef struct __list_iterator<T, T&, T*> iterator;
typedef struct __list_iterator<T,const T&, const T*> const_iterator;
typedef struct __list_reverse_iterator<iterator, T&, T*> reverse_iterator;
typedef struct __list_reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;
iterator begin()
{
//进入迭代器类当中去,然后传入起始值的数据初始化
return iterator(_head->next);
}
iterator end()
{
//_head相当于循环里的迭代器最后一个数据的下一个
//所以初始化就用_head去初始化
return iterator(_head);
}
const_iterator begin() const
{
return const_iterator(_head->next);
}
const_iterator end() const
{
return const_iterator(_head);
}
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());
}
//构造时,有的对象是没有头结点的,所以需要帮忙开辟
void Init_head()
{
_head = new Node;
_head->next = _head;
_head->prev = _head;
}
//无参
list()
{
Init_head();
}
//拷贝
list(const list<T>& val)
{
Init_head();
list<T> temp(val.begin(), val.end());
std::swap(_head, temp._head);
}
//赋值重载
list<T>& operator=(list<T> val)
{
std::swap(_head, val._head);
return *this;
}
//迭代器区间构造
template<class InputIterator>
list(InputIterator first, InputIterator last)
{
Init_head();
while (first != last)
{
push_back(*first);
++first;
}
}
//插入
void insert(iterator pos, const T& val)
{
Node* cur = pos.Pos;
Node* NewNode = new Node(val);
cur->prev->next = NewNode;
NewNode->prev = cur->prev;
NewNode->next = cur;
cur->prev = NewNode;
}
//尾插
void push_back(const T& val)
{
iterator it = end();
insert(it,val);
}
//头插
void push_front(const T& val)
{
iterator it = begin();
insert(it,val);
}
//删除
void erase(iterator pos)
{
assert(pos != end());
Node* cur = pos.Pos;
cur->prev->next = cur->next;
cur->next->prev = cur->prev;
delete cur;
}
//尾删
void pop_back()
{
iterator it = end();
erase(--it);
}
//头删
void pop_front()
{
iterator it = begin();
erase(it);
}
//判空
bool empty()
{
return _head->next == _head;
}
//清空除头结点之外的所有结点
void clear()
{
iterator it = begin();
while (it != end())
{
erase(it++);
}
}
//析构
~list()
{
clear();
delete _head;
}
private:
Node* _head;
};
}
以上就是我对反向迭代器的全部理解,谢谢大家观看。