摘要
主要讨论如何获取迭代器相应型别。使用迭代器时，很可能用到其型别，若需要声明某个迭代器所指对象的型别的变量，该如何解决。方法如下：
function template的参数推导机制
例如：
template<typename I, typename T>
void func_impl(I iter, T t)
{
//T为迭代器所指对象的型别
T tmp;
//.....
}
template<typename I>
inline
void func(I iter)
{
//func工作交给func_impl完成
func_impl(iter, *iter);
}
int main()
{
int i;
func(&i);
return 0;
}
func_impl()是一个 function template，一旦被调用，编译器会自动进行template参数推导，从而导出型别T，无需自己指出型别，解决问题。迭代器相应型别不只是迭代器所指对象的型别一种而已，最常用的相应型别有五种，但并非任何情况都可利用上述template参数推导机制来取得。这就需要其他方法。
Traits编程技法
迭代器所指对象的型别，成为该迭代器的value type，上述模板参数推导并非全面可用，在需要value type作为函数返回值时，就不能解决了。template参数推导的只是参数而已。因此，声明内嵌型别就出现了。
例如：
template<typename T>
struct MyIter
{
typedef T value_type; //内嵌型别声明
T* ptr;
MyIter(T* p = nullptr):ptr(p) { }
T& operator*() const { return *ptr;}
//...
};
template<typename I>
typename I::value_type //函数func()的返回类型，为I类型迭代器中的value_type
func(I ite)
{
return *ite;
}
int main()
{
MyIter<int> ite(new int(8));
cout<<func(ite); //输出8
return 0;
}
func()函数的返回值必须加上关键字typename，用来告诉编译器这时一个模板类型。但并不是所有迭代器都为class type，原生指针就不是，它就不能定义内嵌型别。这时模板偏特化(template partial specialization)就能解决这个问题。
偏特化的意义
如果class template拥有一个以上的template参数，我们可以针对其中某个(或数个，但并非全部)template参数进行特化工作。也就是将泛化版本中的某些template参数给予明确的指定。
如：
template<typename U, typename V, typename T>
class C { };
偏特化不是template参数U、V或T指定某个参数值，而是针对(任何)template参数更进一步的条件限制所设计出来的一个特化版本。看这个例子：
//泛化版本
template<typename T>
class C { }
//偏特化版本
template<typename T>
class C<T*> { }; //解决原生指针的问题
如此便能解决前面的内嵌型别的问题。下面这个class template专门用来萃取迭代器的特性之一 ：value_type
template<typename I>
struct Iterator_traits //traits指的是特性
{
typedef typename I::value_type value_type;
};
如果I内定义了自己的value type，通过这个traits萃取出来的value type就是I::value_type,则前面的func(),可改为：
template<typename I>
typename Iterator_traits<I>::value_type
func(I ite)
{
return *ite;
}
现在写出Iterator_traits的一个偏特化版本,这就解决了原生指针的问题，如果写成Iterator_traits<int*>::value_type,便得到int：
template<typename T>
struct Iterator_traits<T*>
{
typedef T value_type;
};
但针对“指向常数对象的指针”，Iterator_traits<const int*>::value_type可萃取到const int,此时若要得到non-const int，就要设计下面这一个偏特化版本：
template<typename T>
struct Iterator_traits<const T*>
{
tpyedef T value_type; //当迭代器为pointer-to-const，得到non-const T
};
现在迭代器MyIter、原生指针int*或const int *，都能通过Iterator_traits取出正确的value type。
所以，每个迭代器应以内嵌型别定义的方式定义出相应型别，以遍traits运作。
迭代器相应型别
value type
value type指迭代器所指对象的型别。
difference type
difference type表示两个迭代器之间的距离，也能表示一个容器的最大容量，对连续的空间而言，头尾的距离就为最大容量。如STL的count()，其返回值就必须使用迭代器的difference type:
template<typename I, typename T>
typename iterator_traits<I>::difference_type //函数的返回值类型
count(I first, I last, const T& value)
{
typename iterator_traits<I>::difference_type n = 0; //记录个数
for( ; first != last; ++first)
{
if(*first == value)
++n;
}
return n;
};
针对原生指针而写的偏特化版本，以c++内建的ptrdiff_t(定义于cstddef头文件)作为原生指针的difference type:
template<typename I>
struct iterator_traits
{
//...
typedef typename I::difference_type difference_type;
};
//原生指针的偏特化版本
template<typename T>
struct iterator_traits<T*>
{
typedef ptrdiff_t difference_type;
};
//pointer-to-const的偏特化版本
template<typename T>
struct iterator_traits<const T*>
{
typedef ptrdiff_t difference_type;
};
现在，我们可以通过写
typename iterator_traits<I>::difference_type
来得到任何迭代器I的difference_type。
reference type
引用类型，传回一个迭代器所指对象的引用
pointer type
传回一个，指向迭代器所指之物的pointer。
Item& operator*() const { return *ptr; }
Item* operator->() const { return ptr; }
Item&便是某个迭代器的reference type，而Item*便是其pointer type。在traits内：
template<typename I>
struct iterator_traits
{
typedef typename I::pointer pointer;
typedef typename I::reference reference;
};
//针对原生指针的偏特化版本
template<typename T>
struct iterator_traits<T*>
{
typedef T* pointer;
typedef T& reference;
};
//针对pointer-to-const的偏特化版本
template<typename T>
struct iterator_traits<const T*>
{
typedef const T* pointer;
typedef const T& reference;
};
iterator_category
根据移动特性，迭代器被分为五类：
- Input Iterator: read only
- Output Iterator: write only
- Forward Iterator: 允许写入型算法在这种迭代器所形成的区间上进行读写操作
- Bidirectional Iterator: 可双向移动
- Random Access Iterator: 涵盖所有指针算数能力，包括p+n，p-n，p[n]等等
它们从上到下，功能依次强化。
下面以advance()函数为例，该函数有两个参数迭代器p，数值n；函数内部将p累进n次。
下面针对三种不同迭代器进行示范：
//InputIterator
template<typename InputIterator, typename Distance>
void advance_II(InputIterator& i, Distance n)
{
//单向逐一前进
while(n--) ++i;
}
//BidirectionalIterator
template<typename BidirectionalIterator, typename Distance>
void advance_BI(BidirectionalIterator& i, Distance n)
{
//双向逐一前进
if(n >= 0)
while(n--) ++i;
else
while(n++) --i;
}
//RandomAccessIterator
template<typename RandomAccessIterator, typename Distance>
void advance_RAI(RandomAccessIteraor& i, Distance n)
{
//双向跳跃前进
i += n;
}
//封装版本
template<typename InputIterator, typename Distance>
void advance(InputIterator& i, Distance n)
{
//分别判断迭代器类型
if(is_random_access_iterator(i))
advance_RAI(i, n);
else if(is_bidirectionl_iterator(i))
advance_BI(i, n);
else
advance_II(i, n);
}
这样在执行期才决定使用哪个版本，会影响效率。最好能在编译器就选择正确版本，重载函数机制就解决了这个问题。
前面3个advance_xx()都有两个template 参数，类型不确定，为了形成重载函数，必须加上一个型别已经确定的函数参数。下面五个classes代表了五种迭代器类型：
//标记用的型别
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 { };
这些classes当做标记用，作为第三个参数，使能达到重载函数的目的：
//InputIterator
template<typename InputIterator, typename Distance>
void _advance(InputIterator& i, Distance n, input_iterator_tag)
{
//单向逐一前进
while(n--) ++i;
}
//ForwardIterator
template<typename ForwardIterator, typenmae Distance>
void _advance(ForwardIterator& i, Distance n, forward_iterator_tag)
{
_advance(i, n, input_iterator_tag())
}
//BidirectionalIterator
template<typename BidirectionalIterator, typename Distance>
void _advance_BI(BidirectionalIterator& i, Distance n, bidirectional_iterator_tag)
{
//双向逐一前进
if(n >= 0)
while(n--) ++i;
else
while(n++) --i;
}
//RandomAccessIterator
template<typename RandomAccessIterator, typename Distance>
void advance_RAI(RandomAccessIteraor& i, Distance n, random_access_iterator_tag)
{
//双向跳跃前进
i += n;
}
每一个_advance()的最后一个参数只声明型别，是为了激活重载函数机制，并不需要参数名称，并且函数中并不使用该参数。下面是对外开放的接口，以调用不同的_advance()。
template<typename InputIterator, typename Distance>
inline void advance(InputIterator& i, Distance n)
{
_advance(i, n, iterator_traits<InputIterator>::iterator_category());
}
//iterator_category()在stl_iterator.h中定义
template<typename I>
inline typename iterator_traites<I>::iterator_category
iterator_category(const I&)
{
typedef typename iterator_traits<I>:iterator_category category;
return category();
}
为满足上述行为，traits中增加相应型别：
template<typename I>
struct iterator_traits
{
//...
typedef typename I::iterator_category iterator_category;
};
//针对原生指针的偏特化版本
template<typename T>
struct iterator_traits<T*>
{
//...
//原生指针为一种RandomAccessIterator
typedef random_access_iterator_tag iterator_category;
};
//针对pointer-to-const的偏特化版本
template<typename T>
struct iterator_traits<const T*>
{
//...
typedef randow_access_iterator_tag iterator_category;
};
任何一个迭代器，它的类型应属于迭代器类型中功能最强大的类型如int* ，既是Random又是Bidirectional，既是Forward又是Input，他应为Random。
总结
设计适当的型别，是迭代器的责任。设计适当的迭代器，是容器的责任。只有容器本身，才知道什么样的迭代器适合自己。至于算法，完全独立于容器和迭代器，只要设计时以迭代器为对外接口就行。
tratis编程技法大量用于STL中，它利用内嵌型别技巧和编译器的template参数推导功能，增强C++的能力。