迭代器萃取与反向迭代器

迭代器是什么

• 迭代器是一种行为类似指针的对象,通过重载一些操作指针的如++，--，*，->,可以不知道容器的结构来访问容器。

为什么每一种容器都提供有专属的迭代器

迭代器的作用:

• 1.可以不知道容器的结构来访问容器。
• 2.向胶水一样的把算法完美的作用到容器上。

STL的核心思想：效率和复用

• 算法：算法关注的是逻辑
• 容器：数据管理

算法是通过迭代器作用到算法上的，所以为了算法的效率，于是就有了迭代器萃取，根据迭代器的内嵌类型，决定出迭代器类型，选出合适的算法。

问题： 算法中要定义一个变量， 以“迭代器指向对象的类型value type”为型别，该怎么定义这个变量？

• function template的推演

算法中可以根据传入的迭代器参数，通过模板参数类型的推演出，推演出其迭代器所指对象的类型；但返回值无法推演。

• 在迭代器里面设置内嵌value type 型别，在需要的地方通过 Iterator::value type来解决。

对于迭代器是class type可以设置内嵌类型value type来解决；但若例如vector的迭代器是T*，就无法设置迭代器的内嵌型别。

• 偏特化（partial specialization）解决上面问题

template<class it>
struct iterator_traits{   //对内嵌多一层封装，用来萃取。
    typedef typename it::value_type value_type;
}
template<class T>
struct iterator_traits<T*>{  //偏特化版本——迭代器是一个原生指针
    typedef T value_type;
}
template<class T>
struct iterator_traits<const T*>{ //偏特化版本——对于“指向常数对象的指针”，要让它的value_type变成no-const，赋值不能赋值。
    typedef T value_type;
}

这里使用的是类型萃取的方法，通过上面的偏特化萃取出原生指针迭代器的value_type，这个iterator_traits不仅可以萃取value_type，通过这个“特性萃取机”可以过得相应的型别，特性就是迭代器相应的五种类型，若下所示；用上方的方法同样可以是对以下五种相别进行萃取，得出和迭代器匹配的类型。

• 五个内嵌型别

tempalte<class It>
struct iterator_traits{
    typedef typename It::value_type value_type;
    typedef typename It::different_type different_type;
    typedef typename It::pointer pointer;
    typedef typename It::reference reference;
    typedef typename It::iterator_category iterator_category; //迭代器的种类，被分成5类
}

• 迭代器的五种种类  

• input iterator ：只读，不允许被修改
• output iterator ：只写，形式上的一类，不存在只写的迭代器
• Forward iterator :单向迭代器
• Bidirectional iterator ：双向迭代器
• Random Access iterator ：随机迭代器，支持所有指针的算术能力，如p++，p--，p[n]等。

struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag {};
struct random_access_iterator_tag : public bidirectional_iterator_tag {};

迭代器种类的萃取是为了算法的高效率

以上就是迭代器的萃取，可以通过下面代码实例加深理解：

迭代器的保证

为了符合规范，任何迭代器必须定义五个内嵌型别，以便于traits萃取，否则将自别与STL架构，可能无法与STL的组件完美搭配。

反向迭代器

• 通过正向迭代器适配出反向迭代器，在反向迭代器里顶一个正向迭代器对象，对这个对象进行反向操作，具体看下面代码。
• 反向迭代器的REnd()是正向迭代器的Begin()
• 反向迭代器的RBegin()是正向迭代器的End()。

解引用的时候返回正向顺序的下一个位置的值，也就是逆序的前一个值，可以达到上面的效果。

• explicit 加到构造函数前面避免隐式类型装换，防止 把正向迭代器的Begin或end隐式的赋给反向迭代器

/***********************反向迭代器（适配器）***********************************/
template<class It>
struct ReverseIterator 
{
	It _it;  //某个正向迭代器
	typedef typename IteratorTraits<It>::IteratorCategory IteratorCategory;
	typedef typename IteratorTraits<It>::ValueType ValueType;
	typedef typename IteratorTraits<It>::DifferenceType DifferenceType;
	typedef typename IteratorTraits<It>::Pointer Pointer;
	typedef typename IteratorTraits<It>::Reference Reference;
	typedef ReverseIterator<It> Self;

	//explicit 避免隐式类型转换，例如把 ReIt = l.Begin(),这是不允许的。
	explicit ReverseIterator(It it)
		:_it(it)
	{}

 	Self& operator++()
	{
		--_it;
		return *this;
	}
	Self& operator++(int)
	{
		Self tmp = *this;
		--_it;
		return tmp;
	}
	Self& operator--()
	{
		++_it;
		return *this;
	}
	Self& operator--(int)
	{
		Self tmp = *this;
		++_it;
		return tmp;
	}
	Reference operator*()
	{
		//为了RBegin和REnd符合常规思维，随意这里解引用后一个位置，
		It tmp = _it;
		--tmp;
		return (*tmp);
	}
	Pointer operator->()
	{
		return &(*_it);
	}
	bool operator==(Self& it)
	{
		return _it == it._it ? true : false;
	}
	bool operator!=(Self& it)
	{
		return _it != it._it ? true : false;
	}

};