C++ premier -- 模板与泛型编程

所谓泛型编程就是以独立于任何特定类型的方式编写代码，使用泛型程序时，我们需要提供具体程序实例所操作的类型或值。泛型编程与面向对象编程一样，都依赖于某种形式的多态性。模板是泛型编程的基础，模板是创建类或函数的蓝图或公式。例如标准库定义了一个类模板，该模板定义了vector的含义，vector是用于装载同种类型的元素的容器，装载的对象是多态的，vector<int>装有很多int元素，vector<string>则装了string，但是它们有很多相似的操作，由此形成了一个模板类。“面向对象编程所依赖的多态性称为运行时多态性，泛型编程所依赖的多态性称为编译时多态性或参数式多态性。”从这句话我们可以看出，泛型编程在编译时决定使用多态中的哪一态。

单独的函数可以是一个模板，如编写一个函数比较两个值并指出第一个值是小于、等于还是大于第二个值，可以定义如下函数模板：

template<typename T> int compare( const T& a, const T& b ){
	if( a > b )
		return 1;
	if( a < b )
		return -1;
	return 0;
}

template表明这是一个函数模板，而<>里面的列表就像函数的形参列表一样，表示一种未知的，待用户提供的参数，称为模板形参。函数的形参在运行时提供实参，而模板的形参在编译时提供模板实参。这样调用函数模板：

int main(){
	int a = 0, b = 1;
	double c = 30.1, d = 40.5;
	compare( a, b );  //compare( const int&, const int& ) is instantiated
	compare( c, d );	//compare( const double&, const double& ) is instantiated
	compare( a, c );	//error: no matching function for compare( const int&, const double& )
}

调用上面函数模板的时候，编译器通过推断确定哪些模板实参绑定到模板形参。由于是先推断，后再用函数实参调用实例化后的函数，因此类型形参的实参转换是受限的。如上面代码最后一个例子编译时会出错。
类型形参的实参受限转换：
一般而言，不会转换实参以匹配已有的实例化，相反，会产生新的实例。除了产生新的实例化之外，编译器只会执行两种转换：
1. const转换：接受const引用或const指针的函数可以分别用非const对象的引用或指针来调用，无须产生新的实例化。如果函数接受非引用类型，形参类型和实参都忽略const，即无论传递const或非const对象给接受非引用类型的函数，都使用相同的实例化。
2. 数组或函数到指针的转换：如果模板形参不是引用类型，则对数组或函数类型的实参应用常规指针转换。数组实参将当作指向其第一个元素的指针，函数实参当作指向函数类型的指针。
示例如下：

template <typename T> void fobj( T a, T b ){  }
template <typename T> void fref( const T& a, const T& b ){ }
string s1("a value");
const string s2( "another value" );
fobj( s1, s2 ); //ok:calls function fobj( string, string ), const is ignored
fref( s1, s2 ); //ok:calls function fref( const string&, const string& ), s1 converted to const reference
int a[10], b[42];
fobj( a, b ); //ok:calls function fobj( int*, int* );
fref( a, b ); //error: no matching function for fref( int&[10], int&[42] )

模板形参除了用typename或class声明的类型形参外，还有用内置类型或自定义类型声明的非类型形参。如下面的函数：

template <typename T, size_t N> void printArray( const T (&array)[N] ){	
	for( size_t t=0; t!=N; ++t )
		cout<<array[t]<<" ";
	cout<<endl;
}
//调用函数：
const double a[3] = {2, 3, 4.3};
//这里我有一个问题就是，如果把a声明为double a[3]的话，编译会报错：no matching function for printArray( double[3] )
printArray( a );	//instantiate printArray( const double(&)[3] )

typename T是一种类型形参，而size_t N是一种非类型形参，当用下面两个语句调用该函数时，T在编译时初始化为double而N则初始化为3。

类也可以做成一个模板，例如vector，声明方式也是在class前先将其声明为template并接着声明其模板形参列表，使用的时候则是直接在该类名后面加上实参列表，如vector<int>。类模板中可以出现三种友声明，每一种都声明了与一个或多个实体的友元关系：
（1）普通非模板类或函数的友元声明，将友元关系授予明确指定的类或函数
（2）类模板或函数模板的友元声明，授予对友元所有实例的访问权
（3）只授予对类模板或函数模板的特定实例的访问权的友元声明。

template <class T> class Bar{
	//grants access to ordinary, nontemplate class and function
	friend class FooBar;
	friend void fcn();
	//...
};

template <class T> class Bar2{
	//grant access to Foo1 or template_fcn1 parameterized by any type
	template<class T2> friend class Foo1;
	template<class T2> friend void template_fcn1( const T2& );
	//...
};

//declaration of template class Foo2 and tempalte function template_fcn
template <class T> class Foo2;
template <class T> void template_fcn( const T& );
template <class T> class Foo{
	//grants access to a single specific instance parameterized by char*
	friend class Foo2<char*>;
	friend void template_fcn2<char*> (char* const& );
	//...
}

任意类可以拥有本身为类模板或函数模板的成员，这种成员称为成员模板，成员模板不能为虚。

我们通常会将函数声明、类声明放在头文件中而其定义放在另一些cpp文件中。如何让编译器知道函数的具体实现呢？书中介绍有两种编译模型：一是包含编译模型，在声明模板的头文件最后指明，用#include ***.cpp表示。二是分别编译模型，在模板的定义前加入export关键字。不同编译器可能会使用不同的编译模型，例如我用的是g++，使用的是包含编译模型。

最后一个话题是模板特化。模板特化可以针对模板函数，也可以针对类，可以特化整个类，也可以特化类中的一些成员。特化函数仍然举一开始的compare函数。试想如果我们这样调用该模板函数：

const char* a = "hello", *b = new char[6];
b = "hello";
compare( a, b );

此时调用的函数为compare( const char*, const char* )，而在函数体内真正进行比较的是两个指针的地址，返回的结果不具备任何意义。我们需要为const char*版本专业定义一种新的比较方法，该模板函数的模板特化如下：

template<>
int compare<char*>( char* const& a, char* const& b ){
	//cout<<"specific"<<endl;
	return strcmp( a, b );
}

 下面用一个自定义的Queue类说明前面提到的关于类的模板以及一些特化：

 

//Queue.h

#ifndef QUEUE_H
#define QUEUE_H

#include<iostream>

template<class Type> class Queue;
template<class Type> std::ostream& operator<<( std::ostream& out, const Queue<Type> &q );
std::ostream& operator<<( std::ostream& out, const Queue<const char*> &q );

template<class Type> class QueueItem{
	//声明友元
	friend class Queue<Type>;
	friend std::ostream& operator<< <Type> ( std::ostream&, const Queue<Type>& );
	//private class, no public members.
	private:
		QueueItem( const Type& t ): item(t), next(0){ }
		Type item;
		QueueItem* next;
	};
	
template<class Type> class Queue{
	friend std::ostream& operator<< <Type> ( std::ostream&, const Queue<Type>& );
	public:
		Queue():head(0),tail(0){  }
		template<class It> Queue( It beg, It end ):head(0),tail(0){
			copy_elems( beg, end );
		}
		Queue( const Queue &Q ):head(0),tail(0){
			copy_elems( Q );
		}
		Queue& operator=( const Queue& rhs );
		~Queue(){ destroy(); }
		template<class Iter> void assign( Iter, Iter );
		Type& front(){
			return head->item;
		}
		const Type& front() const{
			return head->item;
		}
		void push( const Type& );
		void pop();
		bool empty() const{
			return head == 0;
		}
	private:
		QueueItem<Type>* head;
		QueueItem<Type>* tail;
		void destroy();
		void copy_elems( const Queue& );
		template<class Iter> void copy_elems( Iter, Iter );
	};

//为特化类Queue<const char*>定义的重载函数	
template<> std::ostream& operator<<( std::ostream& out, const Queue<const char*> &q )
template<> class Queue<const char*>{
	friend std::ostream& operator<<( std::ostream&, const Queue<const char*>& );
	public:
		Queue<const char*>(){ std::cout<<"specific"<<std::endl; }
		void push( const char* );
		void pop(){ real_queue.pop(); }
		bool empty() { return real_queue.empty(); }
		std::string front(){ return real_queue.front(); }
		const std::string front() const { return real_queue.front(); }
	private:
		Queue<std::string> real_queue;
		};

//包含模型
#include "Queue.cpp"
#endif

//Queue.cpp

template<class Type> void Queue<Type>::destroy(){
	while( !empty() )
		pop();
	}
	
template<class Type> void Queue<Type>::pop(){
	QueueItem<Type>* p = head;
	head = head->next;
	delete p;
}

template<class Type> void Queue<Type>::push( const Type& elem ){
	QueueItem<Type>* p = new QueueItem<Type>( elem );
	if( empty() )
		head = tail = p;
	else{
		tail->next = p;
		tail = p;
	}
}

template<class Type> void Queue<Type>::copy_elems( const Queue& Q ){
	for( QueueItem<Type>* p=Q.head; p; p=p->next )
		push(p->item);
	}
	
template<class Type> Queue<Type>& Queue<Type>::operator=( const Queue& rhs ){
	if( this != &rhs ){
		while( !empty() )
			pop();
		copy_elems( rhs );
	}
	return *this;
}

template<class Type> template<class It> 
void Queue<Type>::assign( It beg, It end){
	destroy();
	copy_elems( beg, end );
}

template<class Type> template<class It>
void Queue<Type>::copy_elems( It beg, It end ){
	while( beg != end ){
		push(*beg);
		++beg;
	}
}

//实现特化类的成员函数
void Queue<const char*>::push( const char* val ){
	real_queue.push( val );
}

/*如果只是特化类中的成员函数，方式如下：

template<> void Queue<const char*>::push( const char* const& val ){
	std::cout<<"specific"<<std::endl;
	char* new_item = new char[strlen(val)+1];
	strncpy( new_item, val, strlen(val)+1 );
	QueueItem<const char*> *q = new QueueItem<const char*>(new_item);
	if( empty() )
		head = tail = q;
	else{
		tail->next = q;
		tail = q;
	}
}

template<> void Queue<const char*>::pop(){
	std::cout<<"specific"<<std::endl;
	QueueItem<const char*> *p = head;
	delete head->item;
	head = head->next;
	delete p;
}

*/

template<class Type> std::ostream& operator<<( std::ostream& out, const Queue<Type> &q ){
	out<<"<";
	QueueItem<Type>* p;
	for( p = q.head; p; p=p->next )
		out<<p->item<<" ";
	out<<">";
	return out;
}

std::ostream& operator<<( std::ostream& out, const Queue<const char*> &q ){
	return out<<q.real_queue;
}