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