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 oncetemplate<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;
};
}
