浅析STL中function template的参数推导机制（argument deduction）——以插入排序为例

 STL的中心思想就是将容器和算法分开，分别独立设计和泛型化，然后通过迭代器来连接算法和容器。容器和算法利用C++ 中class template和function template机制来泛型化。设计STL的算法时，传递过来的参数往往是迭代器类型的参数，迭代器引用的容器数据类型当前是不确定的（template是在编译时确定数据类型的），当算法中需要利用迭代器所指对象的类型来定义或声明变量时，就会出现小小的困扰，因为C++中没有提供提取对象数据类型的操作（即使利用RTTI性质中的typied（）来获取类型名，也不能用来做变量声明和定义之用）。这时我们就需利用function template的参数推导机制。下面举个简单例子来详细讨论一下：

//模板函数

template <class I>

void func(I iter){

     ...

}

这时想要在模板函数func里面定义一个迭代器引用的对象该怎么办？像我这样的初学者可能马上会想到容器中使用的方法，将该对象的类型也泛化，增加一个模板参数，即：

template <class I, class T>

void func(I iter){

     T object;

     ...

}

可是这样可以吗？在容器的定义中如果要泛化类型，我们可以这样

template <class I, class T>

class Container{

     

     ...

     T tObject;

     I  iObject;

     typedef T*  iter; 

}; 

然后声明一个类型：

Container<int*, int> c; 

而client在调用STL算法时并不需要了解容器的具体型别，因为它们是在容器声明时就已经设置好了，只需传入容器相应的迭代器。如果调用我们改进的func，编译时就会报错—— no matching function for call to 'func'。T类型是不确定的，因为T类型没有通过某种途径传递一个明确的类型过来。

如果这样像容器定义一样使用function template，我们调用

func<int*, int>(c.getIter());  //这样能行吗？确实可以编译通过，但感觉调用时不顺畅也很奇怪，也违背了STL设计的初衷。

那么该怎样解决这个问题呢？

其实STL中为迭代器指向对象的类型提供了专门技术——Traits编程技术，这里不作介绍，详见参考资料。template 参数推导机制只是简单的解决了部分  “迭代器所指对象的型别” 问题。利用参数推导机制，可以这样实现：

template <class I, class T>
void func_helper(I iter, T t){
     
     T tmp;
     ... //这里做func原本该做的工作
}

template <class I>
void func(I iter){
     func_helper(iter, *iter); //*iter作为附加参数
}

void caller(){

     func(c.getIter());
}

 

可见func_helper中T的类型就是*iter类型，利用参数推导机制解决了上述问题。下面以插入排序为例，通过参数推导来解决实际问题，详细介绍下template function的实现。

插入排序的一般实现：

//普通版本
template<class T>
void insertSort(vector<T>& v){
	int j;
	
	for(int i = 1; i < v.size(); ++i)
	{
		T tmp = v[i];
		for(j = i; j > 0 && tmp < v[j-1]; --j)
			v[j] = v[j-1];
		v[j] = tmp;
	}
}

下面再按照STL算法的形式改写，STL sort的实现为带迭代器的双参数和附加函数子的三参数的两种形式。那么我们要：

（1）编写一个双参数和三参数的形式（为什么不能用一个带有默认参数值的三参数实例来实现呢？考虑一下），双参数实 际是三参数的一个特化，因此考虑用二参数函数调用三参数来实现。

（2）数组的访问由直接传入容器变为传入容器的迭代器；

（3）插入排序中tmp的类型和less<>仿函数的具体化要用到参数推导机制。

//STL版本
template<class I, class Cmp>
void insertSort(const I& begin, const I& end, Cmp lessThan);

template <class I, class T>
void _insertSort(const I& begin, const I& end, const T t);

template<class I, class T, class Cmp>
void _insertSort(const I& begin, const I& end, Cmp lessThan, const T& t);

template <class I>
void insertSort(const I& begin, const I& end){
	if(begin != end)
		_insertSort(begin, end, *begin); //这里要取begin所指向的值，避免越界，所以先判断
}

template <class I, class T>
void _insertSort(const I& begin, const I& end, const T t){
	insertSort(begin, end, less<T>()); // 双参数调用三参数，less<T>中的类型也利用参数推导获取
	
}

template<class I, class Cmp>
void insertSort(const I& begin, const I& end, Cmp lessThan){
	if(begin != end)
		_insertSort(begin, end, lessThan, *begin);
}

//算法的具体实现
template<class I, class T, class Cmp>
void _insertSort(const I& begin, const I& end, Cmp lessThan, const T& t){


	I j;
	for(I i = begin+1; i != end; ++i){
		T tmp = *i; //通过参数推导确定T类型
		for(j = i; j != begin && lessThan(tmp, *(j-1)); --j)
			*j = *(j-1);
		*j = tmp;
	}
}

 

上面就是个人对参数推导机制的粗浅理解，要深入了解迭代器指向对象的类型可参考《STL源码剖析》，以上代码来自于下面参考文献。代码都经过调试，可以正常运行。这里做一个学习过程的标记。

参考文献：

[1] 《STL源码剖析》

[2] 《数据结构与算法分析C++描述》