# Template 参数推导机制

在算法中运用 迭代器（iterator） 时，很可能会用到其相应的型别。在 C++ 中支持 sizeof() 并不支持 typeof() ，即使动用 RTTI 性质中的 typeid() 也只能获得型别名称而不能用作变量声明。

# 解决方法一：利用 template 的参数推导机制

	template <class I, class T>
	void fun_1(I iter, T t) {
	T tmp = 0; // 这里解决了问题。T 就是指针所指之物的型别。
	// 省略...
	}

	template <class I>
	inline void fun_2(I iter) {
	fun_1(iter, *iter); //fun_2 的工作全部移动到 fun_1 上
	}

上面虽然推出了 T 的型别，但是如果 T 必须用于函数的返回值，上面的参数推导就无法解决了。于是引入接下里的方法。

# 解决方法二：使用内嵌类型

	template <class T>
	struct Myiterater {
	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 的回返值型别
	func(I iter) {
	return *iter; // 不但推出了参数而且可以用于函数返回值的推导
	}

这里需要使用 typename 的原因是：因为 T 是一个 template 参数，在被编译器具现化之前，编译器对 T 一无所知，换句话说，编译器此时并不知道 MyIter<T>::value_type 是个型别， typename 就是告诉编译器这是一个型别，如此才能顺利通过编译。
但并不是所有的迭代器都是 class type ，比如原生指针就不能用此方法。而 STL 要求必须能接受原生指针作为迭代器，因此引出最后的方法：template 偏特化。

# 解决方法三：template 偏特化

	template <typename T>
	class C {
	typedef T value_type; // 允许接受 T 为任何型别
	};

	template <typename T>
	class C<T*> {
	typedef T value_type; // 仅适用于 T 为原生指针，如 int * 的情况
	};

	template <typename T>
	class C<const T*> {
	typedef T value_type; // 针对指向常量对象的指针
	};

# Traits 编程

介绍完上面的 template 推导，接下来进入重头戏。下面这个 class template 专门用来萃取迭代器的特性。上面介绍过的 value_type 属于迭代器的特性之一，下面我们一一介绍。
最常用到的迭代器相应型别有五种。如果希望你所开发的容器能与 STL 水乳交融，一定要为你的容器的迭代器定义这五种相应型别。

# value_type

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

	template <class I>
	struct iterator_traits {
	// 如果 I 定义有自己的 value_type，则萃取出的 value_type = I::value_type
	typedef typename I::value_type value_type;
	};

那么上面 解决方法二 中的 func() 可改写成下面这样:

	template <class I>
	typename iterator_traits<I>::value_type // 这一整行是函数回返型别
	func(I iter) { return *iter; }

# difference_type

difference_type 用来表示两个迭代器间的距离，因此也可以用来表示一个容器的最大容量。例如 count() 其返回值必须使用迭代器的 differnece_type 。
针对相应型别 difference_type , traits 的如下两个 (针对原生指针而写的) 特化版本，以 C++ 内建的 ptrdiff_t (定义于 cstddef 头文件〉作为原生指针的 difference_type :

	template <class I>
	struct iterator_traits {
	typedef typename I::difference_type difference_type;
	};

	// 针对原生指针而设计的偏特化版
	template <class T>
	struct iterator_traits<T*> {
	typedef ptrdiff_t difference_type;
	};

	// 针对原生的指向常量的指针
	template <class T>
	struct iterator_traits<const T*> {
	typedef ptrdiff_t difference_type;
	};

现在当我们需要任何迭代器工的 difference_type ，可以这么写:

typename iterator_traits<I>::difference_type

# reference_type

从 “迭代器所指之物的内容是否允许改变” 的角度观之，迭代器分为两种：不允许改变 “所指对象之内容” 者，称为 constant iterators ，例如 const int *pic ；允许改变 “所指对象之内容” 者，称为 mutable iterators ，例如 int* pi 。当我们对一个 mutabie iterators 进行提领操作时，获得的不应该是一个右值 ( rvalue )，应该是一个左值 ( lvalue )，因为右值不允许賦值操作，左值才允许:

	int* pi = new int(5);
	const int* pci = new int(9);
	*pi = 7; // 对 mutable iterator 进行提领操作时，获得的应该是个左值，允许賦值
	*pci = 1; // 这个操作不允许，因为 pci 是个 constant iterator，
	// 提领 pci 所得结果是个右值，不允许被赋值

C++ 中函数如果要传左值，都是以 by reference 的方式进行，所以当 p 是个 mutable iterators 时，如果其 value_type 是 T ，那么 *p 的型别不应该是 T ，应该是 T& 。这里所讨论的 *p 的型别，即所谓的 reference_type 。

# poniter_type

pointers 和 references 在 C++ 中有非常密切的关连。如果 “传回一个左值，令它代表 p 所指之物” 是可能的，那么 “传回一个左值，令它代表 p 所指之物的位址” 也一定可以。我们能够传回一个 pointer ，指向迭代器所指之物。

	Item& operator() const { return ptr; }
	Item* operator->() const { return ptr; }

Item& 便是 reference_type ，而 Item* 便是 pointer_type 。

# iterator_category

等我实现好前面的，看完书这部分再更新。