在官方库中,反向迭代器是使用适配器封装的,即用普通的迭代器去作为适配器,然后封装出一个反向迭代器出来。
关于迭代器的解析,在介绍实习list以及迭代器这篇文章中有较详细讲解。此处重点是反向迭代器的原理和实现。list---迭代器的原理和实现
首先是类模板,Iterator代表的是适配器,Ref和Ptr代表的是引用和取地址。
template<class Iterator,class Ref,class Ptr>
class Reverse_Iterator
{
public:
typedef Reverse_Iterator<Iterator,Ref,Ptr> Slef;
private:
Iterator _it;//_it的类型是Iterator,是传进来的适配器的类型
};
正向迭代器的++/--,即是反向迭代器的--/++:
因为是通过正向迭代器作为适配器的,当it进行++或--的时候,就会去调用正向迭代器中的operator++()和operator--();
Slef& operator++()
{
--it;//会调用正向迭代器的operator--();
return *this;
}
Slef& operator--()
{
++it;//会调用正向迭代器的operator++();
return *this;
}
根据官方库中的源代码,我们可以分析得到,反向迭代器中的rbegin和rend,与正向迭代器的end()和begin()是对称的。
如下图:
因此,当解引用的时候,需要减一步,才能解引用。比如上图:rbegin()在头节点上,减一步,就到了节点的值为4的节点上,然后一值遍历的话,最终会在遍历完1的节点后结束。
Ref operator*()
{
Iterator tmp = _it;
return *(--tmp);
}
对于operator->(),返回的是数据的地址,我们可以使用operator*()拿到数据,然后取地址即可。
Ptr operator->()
{
return *(operator*());
}
只需在初始化列表上,将迭代器指向的节点或顺序表中的某个位置赋值给反向迭代器的对象即可。
Reverse_Iterator(Iterator it)
:_it(it)
{}
因为是需要指向同一块地址,所以不需要深拷贝,不需要析构函数!
最后稍微完善一下即可:
template<class Iterator,class Ref,class Ptr>
class Reverse_Iterator
{
public:
typedef Reverse_Iterator<Iterator,Ref,Ptr> Slef;
Reverse_Iterator(Iterator it)
:_it(it)
{}
Ref operator*()
{
Iterator tmp = _it;
return *(--tmp);
}
Ptr operator->()
{
return *(operator*());
}
Slef& operator++()
{
--it;
return *this;
}
Slef& operator--()
{
++it;
return *this;
}
bool operator!=(const Slef& s)
{
return _it != s._it;
}
private:
Iterator _it;
};
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());
}
//反向迭代器的rbegin()
reverse_iterator rbegin()
{
//通过end()返回链表的哨兵位头节点,然后通过构造函数将反向迭代器的对象初始化,并且是浅拷贝,指向同一块空间
return reverse_iterator(end());
}
//反向迭代器的rend()
reverse_iterator rend()
{
//通过begin()返回链表的尾节点,然后通过构造函数将反向迭代器的对象初始化,并且是浅拷贝,指向同一块空间
return reverse_iterator(begin());
}
//const版本反向迭代器的rbegin()
const_reverse_iterator rbegin() const
{
return const_reverse_iterator(end());
}
//const版本反向迭代器的rend()
const_reverse_iterator rend() const
{
return const_reverse_iterator(begin());
}
这样实现的反向迭代器,就可以用到list,vector等等的容器,因为只需提供适合的迭代器作为适配器即可。