泛型程序设计

类属函数

• 采用通用指针类型的参数
• 函数模板

通用指针参数实现

typedef unsigned char byte;
void sort(void *base, //需排序的数据（数组）内存首地址
 		  unsigned int num, //数据元素的个数
 		  unsigned int element_size, //一个数据元素所占内存大小（字节数）
  		  bool (*cmp)(const void *, const void *) ) //比较两个元素的函数
{   //不论采用何种排序算法，一般都需要对数组进行以下操作： 
     //取第i个元素
        (byte *)base+i*element_size
     //比较第i个和第j个元素的大小 （利用调用者提供的回调函数cmp实现）
        cmp((byte *)base+i*element_size,(byte *)base+j*element_size)
     //交换第i个和第j个元素的位置
        byte *p1=(byte *)base+i*element_size,
        *p2=(byte *)base+j*element_size;
        for (int k=0; k<element_size; k++){  
            byte temp=p1[k]; p1[k] = p2[k]; p2[k] = temp;
        } 
}

函数模板

template <class T1, class T2, ...> //class也可以写成typename

template <class T> 
void sort(T elements[], unsigned int count)
{ 
 //取第i个元素
 elements[i] 
 //比较第i个和第j个元素的大小
 elements[i] < elements [j] 
 //交换第i个和第j个元素
 T temp=elements [i];
 elements[i] = elements [j];
 elements[j] = temp;
}


//使用
int a[100];
sort(a,100);  //对int类型数组进行排序

double b[200]; 
sort(b,200);  //对double类型数组进行排序

A c[300]; 
sort(c,300);  //对A类型数组进行排序
           	  //在类A中，需重载操作符：<
     		  //可能还需要自定义拷贝构造函数和重载操作符=

template <class T> 
T max(T a, T b)
{ return a>b ? a : b; }

int x;
double m;
max(x,m);	//无法判断使用哪一种类型

//解决方法
max((double)x,m); //调用：double max(double a,double b)
max(x,(int)m); //调用：int max(int a,int b)
max<double>(x,m); 
max<int>(x,m);

类模板

template <class T>
class Stack{  
    T buffer[100];
  	int top;
 	public:
  	Stack() { top = -1; }
  	void push(const T &x);
  	void pop(T &x);
};

template <class T> 
void Stack <T>::push(const T &x) { ...... }

template <class T> 
void Stack <T>::pop(T &x) { ...... }

类模板实例化需要显式指出类型

Stack <int> st1;

STL（标准模板库）

• 容器
• 算法
• 迭代器

容器

• vector
• list
• deque
• stack
• queue
• priority_queue
• map
• multimap
• set
• multiset
• string