STLtraits编程技法

迭代器是一种抽象的设计概念，定义为：提供一种方法，使之能够依序巡访某个容器所含的各个元素，而又无需暴露该容器的内部表达式。迭代器是一种类似指针的对象，具有遍历复杂数据结构的能力，其下层运行机制取决于其所遍历的数据结构，因此，每一种容器型别都必须提供自己的迭代器。事实上每种容器都将其迭代器以嵌套方式定义于内部。

迭代器相应型别

//<stl_iterator_base.h>, stl source code v3.3
struct iterator {
    typedef _Category  iterator_category;
	typedef _Tp        value_type;
	typedef _Distance  difference_type;
	typedef _Pointer   pointer;
	typedef _Reference reference;
};

value_type 是指迭代器所指对象的型别，任何一个打算与 STL 算法有完美搭配的 class，都应该定义自己的 value type 内嵌型别；

difference_type 用来表示两个迭代器之间的距离，因此它可以用来表示一个容量的最大容量，对于连续空间的容器而言，头尾之间的距离就是其最大容量。

reference ，从迭代器所指之物的内容是否允许改变的角度来看，可分为 “所指对象之内容不可改变” 和 “所指对象之内容可改变”。其中后者可作为左值，在C++中，函数如果要传回左值，都是以 by reference 的方式进行。

iterator_category（迭代器类型，本文重点讨论对象，包括后面的 iterator_traits 也主要讨论这个）可分为以下五类：

input iterator：这种迭代器所指的对象，不允许外界改变，只读型，只能一次一个向前读取元素（不支持 operator–），按此顺序一个个传回元素值。

output iterator：唯写型，与 input iterator 相反，其作用是向前将元素值一个个写入（不支持 operator–），只能一个元素一个元素地赋新值。

forward iterator：允许 “写入型” 算法在此种迭代器所形成的区间上进行一个个读写操作（不支持 operator–）。

bidirectional iterator：可双向一个个移动（支持 operator–），某些算法需要逆向走访某个迭代器区间（如 copy_back() ）。

random access iterator：随机存取迭代器，涵盖所有指针算数能力，包括 p+n，p-n，p[n]，p1-p2，p1<p2。

给出一例代码，针对某种迭代器提供定义，以便在不同情况下提供最大效率。

template <class _InputIter, class _Distance>
inline void __advance(_InputIter& __i, _Distance __n/*, input_iterator_tag*/)
{
	while (__n--) ++__i;     //单步前进
	//时间复杂度 O(N)
}
template <class _BidirectionalIterator, class _Distance>
inline void __advance(_BidirectionalIterator& __i, _Distance __n/*, bidirectional_iterator_tag*/)
{
	if (__n >= 0)
		while (__n--) ++__i;   //可进（单步）
	else
		while (__n++) --__i;   //可退（单步）
	//时间复杂度 O(N)
}
template <class _RandomAccessIterator, class _Distance>
inline void __advance(_RandomAccessIterator& __i, _Distance __n/*, random_access_iterator_tag*/) 
{
	__i += __n;   //双向跳跃前进
	//时间复杂度 O(1)
}

如果 _RandomAccessIterator 型别的选择第二个函数调用，无疑增大了时间复杂度，效率下降。所以需要在编译期就选择正确的版本，重载函数机制可以达成这个目标。由于这三个函数的型别未定（因为都是 template 参数），为了形成重载函数，我们必须加上一个型别已确定的函数参数，使函数重载机制得以有效运作起来。

于是 SGI STL 采用了 traits 编程技法，其实质就是 traits 依靠显示模板特殊化来把代码中因类型不同而发生变化的片段拖出来，用统一的接口来包装。traits 有能力通过模板特殊化来萃取出迭代器的种类，我们可以利用这个 “迭代器类型” 相应型别作为 __advance() 的第三个参数，这个相应型别必须为一个 class type。因为编译器需依赖它来进行重载决议。

回顾前面的 __advance() 函数，加上第三个参数形成重载。另外没有针对 forward_iterator 而设计的版本，因为那和针对 input_iterator 而设计的版本完全一致。如果硬要设计一个那就是：

/*下面这个函数定义并不存在*/
template <class _ForwardIterator, class _Distance>
inline void __advance(_ForwardIterator& __i, _Distance __n, forward_iterator_tag) 
{
	advance(__i, __n, input_iterator_tag);
}
//额外贴上 advance() 代码
template <class _InputIterator, class _Distance>
inline void advance(_InputIterator& __i, _Distance __n)
{
	__advance(__i, __n, iterator_category(__i));
}

上面的 advance() 其 template 型别参数之所以命名为 _InputIterator，是为了遵循 STL 算法的命名规则：以算法所能接受之最初级类型来为其迭代器型别参数命名。要理解这里说的最初级类型。也就是说 advance() 并没有指定是 _InputIterator 类型，当客端调用 advance() 并使用 outputIterator 或 forwardIterator 或 BidirectionalIterator 时（迭代器类型之间存在着继承关系），统统都会传递调用 inputIterator 版的那个 __advance() 函数。

相信大家都看到了，上面的 advance() 函数接口只有两个参数，当它转调用 __advance() 时，才自行加上第三参数：迭代器类型。因此，这个函数（advance()）必须有能力从它所获得的迭代器中推导出其类型。这个工作交由 traits 机制处理，我们现在转到第三个参数 iterator_category()。

template <class _Iter>
inline typename iterator_traits<_Iter>::iterator_category
iterator_category(const _Iter& __i) 
{ 
	return __iterator_category(__i);
}
template <class _Iter>
inline typename iterator_traits<_Iter>::iterator_category
__iterator_category(const _Iter&)
{
	typedef typename iterator_traits<_Iter>::iterator_category _Category;
	return _Category();
}

整理后 __advance() 函数的原型就是这样

1	__advance(__i, __n, iterator_traits<_InputIterator>::iterator_category());

iterator_category() 函数被用来判定迭代器的类型，它的返回值是一个类对象，这个返回值取决于这个函数的参数型别，换句话说就是 iterator_category() 函数的返回值类型取决于它的参数类型，所以这个函数的参数类型必须是一个迭代器类型，现在这种机制已经被 iterator_traits 机制取代（iterator_traits 还添加了一开始介绍的几种 type）。

另外，还需要五个作为标记用的型别来代表五种迭代器类型：

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

都为空，没有成员，只是单纯的定义为 “tag”，结合前面示例：如果 iterator_category() 的参数类型为 output iterator,那么他的返回值就是 output _ iterator_tag 类型的。

下面贴出一份简单的代码来帮助理解：通过模板特化把类型不同的区分出来

#include <iostream>
using namespace std;
class IntType
{
public:
    IntType() :sum(0) {}
    void GetSum(int x)
    {
        sum += x;
        cout << "int type: " << sum << endl;
    }
private:
    int sum;
};
class FloatType
{
public:
    FloatType() :sum(0.0f) {}
    void GetSum(float x)
    {
        sum += x;
        cout << "float type: " << sum << endl;
    }
private:
    float sum;
};
//定义基本模板类，为空，无成员，只包含类型信息
template<class T>
class Traits
{
};
/*模板特化，将输入类型定义成相同的名称，为编制模板类共同的调用接口做准备*/
template<>
class Traits<IntType>  //特化定义的模板形参为 IntType
{
public:
    typedef int inputtype;
};
template<>
class Traits<FloatType>  //特化定义的模板形参为 FloatType
{
public:
    typedef float inputtype;
};
//公共接口
template<class T>
class Test
{
public:
    typename typedef Traits<T>::inputtype input;
    void GetSum(T& t, input x)
    {
        t.GetSum(x);
    }
};
int main()
{
    IntType intt;             //类实例化
    FloatType floatt;         //类实例化
    Test<IntType> t1;          
    Test<FloatType> t2;        
    //公共接口
    t1.GetSum(intt, 3);                //output：  int type: 3
    t2.GetSum(floatt, 3.2f);           //output：  float type: 3.2 
    return 0;
}