“Better code, better life. ”
C++ Traits
假设我们的算法中要声明一个变量，以迭代器所指对象的型别为型别，应该如何实现？毕竟C++只支持sizeof()并不支持typeif()！即便使用RTTI性质中的typeid()，获得的也只是型别名称，不能用来做变量的声明。
解决办法是使用Type Traits(型别萃取)。
型别萃取编程可以说是STL迭代器实现的基础。它利用function template的参数推导机制，实现提取迭代器所指对象的型别。先看一个简单的例子：
template <class I, class T>
void func_impl(I iter, T t)
{
T tmp; //这里T就是迭代器所指之物的型别，本例为int
};
template <class I>
inline void func(T iter){
func_impl(iter, *iter);
}
int main(){
int i;
func(&i);
}
在上面的例子里func()是一个接口，实际的操作全部置于func_impl()中，由于func_impl()是一个function template，一旦被调用，编译器会自动进行temaplte参数推到。于是导出了型别T，顺利解决了问题。
迭代器的value type
迭代器所指对象的型别，成为该迭代器的value type，上述的参数型别推导技巧虽然可用于value type，却并非全面可用。万一value type必须用于函数的返回值，就没办法了，毕竟函数的template 参数推导机制推导的时参数，无法推导函数的返回值类型。
针对以上情况，我们可以声明内嵌型别，像这样：
template <class T>
struct MyIter {
typedef T value_type;
T* ptr;
MyIter(T* p=0):ptr(p){}
T& operator*() const {return *ptr;}
//...
}
template <class I>
typename I::value_type
func(I ite){
return *ite;
}
int main(){
MyIter<int> it(new int(8));
cout<<func(it); //输出8
}
注意，func()的返回型别前必须加上关键字typename，因为T时一个template参数，在它被编译器推导完成之前，编译器对T一无所悉，并不知道MyIter<T>::value_type代表的是一个型别或是一个member function或者是一个data mamber。
上面的代码基本上可以满足我们的需求，但是还有一个隐晦的问题：并不是所有迭代器都是class type。原生指针就不是！如果不是class type，就无法为它定义内嵌型别，但STL绝对必须接受原生指针作为一种迭代器，所以有没有办法则可以让上述的一般化概念针对特定情况（比如原生指针）做特殊化处理呢？
有的，template partial specialization可以做到。
偏特化（partial specialization）
偏特化在很多本C++的书籍中都有解释，其大致的意义是：如果class template拥有一个以上的template参数，我们可以针对其中某个（或数个，但非全部）template参数进行特化工作。换句话说，我们可以在泛化设计中提供一个特化版本（也就是将繁华版本中的某些template参数服务明确的指定）。来看一个例子：
假如有一个class template如下：
template< typename U, typename V, typename T>
class C{
//...
};
partial specialization的字面意义容易误导我们以为，所谓偏特化一定是对template参数（或某种组合)指定某个参数值，其实不然。
面对如下的一个class template:
template<typename T> //这个泛化版本允许T为任意型别
class C {//...};
那么其偏特化形式可以为：
template<typename T> //这个泛化版本仅适用于T为原生指针的情况
class C<T*>{...};
有了这个特性，我们便可以解决前述内嵌型别未能解决的问题。之前的问题是，原生指针并非class type，因此无法为它们定义内嵌型别。现在，我们可以对其设计特化版的迭代器。
型别萃取
下面这个class template专门用来萃取迭代器的特性，而value type正是迭代器的特性之一：
template<class I>
struct iterator_traits{
typedef typename I::value_type value_type;
}
这个所谓的traits的意义是，如果I定义又自己的value type，那么通过这个traits，萃取出来的value type就是I::value_type，这是，前文的func()函数可以改写为：
template <class I>
typename iterator_traits<I>::value_type
func(I it){
return *it;
}
对于T为原生指针的情况，我们可以定义偏特化版：
template <class T>
struct iterator_traits<T*>{
typedef T value_type;
}
于是，原生指针int*即便不是一种class type，也可以通过traits萃取其value_type，这边解决了先前的问题。
const指针
我们解决了原生指针的型别问题，但是对于const T*类型，我们使用traits萃取出的型别是const int，并不是我们所期望的，因为const T无法修改，所以这个声明并没有起到作用。因此，如果迭代器是个常量指针，我们应该设计另外一个特化版本：
template <class T>
struct iterator_traits<const T*>{
typedef T value_type;
}
五种常用的迭代器型别
根据经验，最常用到的迭代器的相应型别有五种：
- value type
- difference type
- pointer
- reference
- iterator category
如果你希望你所实现的容器能与STL完美融合，就一定要实现这五种型别。
value type
所谓value type就是只迭代器所指的对象的型别。
difference type
difference type用来表示两个迭代器之间的距离，也可以用来表示一个容器的最大容量。因为对于连续空间的容器而言，头尾之间的距离就是其最大容量。如STL的count()，其返回值就必须使用迭代器的difference type：
template <class I, class T>
typename iterator_traits<I>::difference_type
count(I first, I last, const T& value){
for(; first != last; ++first){
if(*first == value){
++n;
}
}
return n;
}
reference type
当我们对一个mutable iterators进行操作时，获得的不应该是一个右值，应该是一个左值，因为右值不允许赋值操作，左值才可以。
在C++中，函数如果要返回，都是以by reference的方式进行，所以当p是个mutable iterators时，如果其value type是T，那么p的型别不应该是T，应该是T&。
pointer type
pointers和reference在C++中关系非常密切。如果返回一个左值，令它代表p所指之物是可能的，那么返回一个左值，令它代表p所指之物的地址也一定可以。
template <class I>
struct iterator_traits{
typedef typename I::pointer pointer;
typedef typename I::reference reference;
}
//下面是针对原生指针的偏特化版本
template <class I>
struct iterator_traits<T*>{
typedef T* pointer;
typedef T& reference;
}
//下面是针对原生const指针的偏特化版本
template <class I>
struct iterator_traits<const T*>{
typedef T* pointer;
typedef T& reference;
}
iterator category
最后一个型别最复杂，我们必须要讨论迭代器的分类。根据移动特性与实时操作，迭代器被分为五类：
- input iterator: 只读迭代器，不允许被外界改变。
- output iterator: 只写迭代器。
- forward iterator: 允许
写入型算法，例如replace()。在这种迭代器所形成的区间上进行读写。 - bidirectional iterator: 前四种迭代器斗志提供部分指针算术能力，前三种支持
operator++，第四种额外支持operator--。 - random access iterator: 支持所有指针算术能力，包括
p+n, p-n, p[n], p1-p2, p1<p2。
设计算法是，如果可能，尽量针对以上某种迭代器提供一个明确定义，并针对更强化的迭代器提供另一种定义，这样才能在不同的情况下效率最大化。
以advance()为例，advance()方法有两个参数，迭代器p和数值n；函数内部将p累进n次，如果是第五种迭代器，那我们可以很容易的写出高效的算法：
template <class RandomAccessIterator, class Distance>
void advance_RAI(RandomAccessIterator& i, Distance n){
i += n;
}
但对于其他几种，则不可避免地要加入循环：
template <class RandomAccessIterator, class Distance>
void advance_RAI(RandomAccessIterator& i, Distance n){
while(n--) ++i;
}
所以，如果traits有能力萃取出迭代器的种类，我们便可以利用这个特性来分别实现相应的advanced()。只要给该函数增加一个IteratorType参数即可。参数的型别一定是一个class type，不能只是数值号码之类的东西，因为编译器依赖它进行函数重载。所以需要额外定义五种相应的classes：
struct input_iterator_tag{};
struct output_iterator_tag{};
struct forward_iterator_tag{};
struct bidirectional_iterator_tag : public input_iterator_tag{};
struct random_access_iterator_tag : public bidirectional_iterator_tag{};
这些类型都只做标记用，所以不需要实现。
所以，改进后的advance()应该是这样的：
template <class InputIterator, class Distance>
inline void advance(InputIterator& i, Distance n){
__advance(i, n, iterator_traits<InputIterator>::iterator_category());
}
