C语言中实现模板函数小结

程序设计 | | 2009.05.20

                        —-by boluor 2009/5/20
      如果要写个函数支持多种数据类型，首先想到的就是C++的模板了，但是有时候只能用C语言，比如在linux内核开发中，为了减少代码量，或者是某面试官的要求…
      考虑了一阵子后，就想到了qsort上.qsort的函数原型：
void qsort( void *base, size_t num, size_t width, int (__cdecl *compare )(const void *elem1, const void *elem2 ) );
      快排时，只要自己实现相应数据类型的比较函数cmpare就可以了.如果比较int型时,一个典型的compare函数如下：

int cmp(const void *a,const void *b){
    return *((int *)a)-*((int *)b);
}

      那么,就是说可以利用void *. void *意指未指定类型，也可以理解为任意类型。其他类型的指针可以直接赋值给void *变量，但是void *变量需要强制类型转换为其它指针类型。这个相信大家都知道。那么下面以一个简单的题目为例，来探讨如何在C语言中实现模板函数。
      方法1： 利用void *.
    在看下面的源程序之前，需要了解几点。首先，在32位平台上，任何类型的指针所占的字节都是4个字节，因为32位机器虚拟内存一般为4G，即2的32次方，只要32位即4个字节就可以足够寻址，sizeof(void *)=4； 其次，虽然各种不同类型的指针所占的空间都为4个字节，但是不同类型的指针所指的空间的字节数却不同(这一点尤为重要，下面的程序我在开始没有调通就因为这点意识不强)。所以，如果你将一个指针强制转换为另一个类型的指针，指针本身所占的字节是不变的，但是，如果对这个指针进行运算，比如 *p,p++,p-=1等一般都是不同的。 再次，函数指针应该了解下，这里不多说。 最后，因为Sandy跟我说，C++开始的时候模板的实现其实就是利用宏替换，在编译的时候确定类型。所以，为了方便，类型也用了预编译指令#define。

#include "stdio.h"
#include "stdlib.h"
 
//typedef int T;  //或者下面的也可以.
#define  T int
 
int cmp(const void *a,const void *b){
    return *((T *)a)-*((T *)b);
}
/*
//这个FindMin是Sandy写的.felix021也写了个,差不多的就不贴出来的.
void FindMin(const void  *arr,int arr_size,int arrmembersize,int *index,    
             int (*cmp)(const void *,const void *b)){
    int i;
	*index=0;
	char *p=(char *)arr;
	char *tmp=p;
    for (i=1;i<arr_size ;i++){
        if (cmp(tmp,p)>0){
            tmp=p;
        }
		p+=arrmembersize;
    }
	(*index)=((int)(tmp-arr))/arrmembersize;
}
*/
 
int FindMin(const void *arr,int arr_size,int arrmembersize,int (*cmp)(const void *,const void *)){
	char *p=(char *)arr;	//可以把指针看作是char *,如果转换为int *,那下面的位移就不正确了.
	int index=0;
	int i;
	for (i=1;i</arr_size><arr_size ;++i){
		if (cmp(p+index*arrmembersize,p+i*arrmembersize)>0){
			index=i;
		}
	}
 
	return index;
}
 
 
int main(){
    int arr[]={2,1,1,2,3,4,5,0,2,3,1,3};
    //int *result;
    int result;//result保存的是最小值索引.
    result=FindMin(arr,12,sizeof(arr[0]),cmp);
 
    printf("%d,%d
",result,arr[result]);
	system("PAUSE");
    return 0;
}

      方法2：利用宏。在编译的时候确定类型。查阅资料的时候，很多都说这种方法比较好，方便调试，也很直观，虽然很啰嗦。

#include <stdio .h>
 
#ifndef _INT_
#define _INT_
#endif
 
int cmp(const void *a,const void *b){    
    #ifdef _INT_
        return (*(int *)a-*(int *)b);
    #elif _FLOAT_
        return (fabs(*(float *)a-*(float *)b)&lt;1e-6)?-1:1;
    #elif _DOUBLE_
        return (fabs(*(double *a)-*(double *)b)&lt;1e-9)?-1:1;
    #endif
}
 
#ifdef _INT_
void FindMin(int *arr,int arr_size,int *result,int cmp(const void *a,const void *b))
#elif _FLOAT_
void  FindMin(float *arr,int arr_size,float *result,int cmp(const void *a,const void *b))
#elif _DOUBLE_
void  FindMin(double *arr,int arr_size,double *result,int cmp(const void *a,const void *b))
#endif
{
    int i;
    *result=arr[0];    
    for(i=1;i<arr_size ;++i){
        if(cmp(&arr[i],result)>0)    
            *result=arr[i];
    }
}
 
int main(){
    int arr1[]={1,2,4,2,1,7};
    int result;
    FindMin(arr1,6,&result,cmp);
    printf("%d
",result);    
    return 0;
}

      方法3：在findmin中，不用强制类型转换为char *，直接利用memcpy内存拷贝过去，这时，还可以在参数列表中保存结果，而不是索引。此方法由CSDN上的ltc_mouse提供。

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
 
void FindMin(void *arr,int arr_size,int arrmembersize,void * result,
             int (*fpCmp)(const void *,const void *b)){
    int i;
    unsigned char *pSrc = (unsigned char *)arr;
    unsigned char *pRes = (unsigned char *)result;
    memcpy( (void *)pRes, (const void *)pSrc, arrmembersize );
    for (i=1;i</arr_size><arr_size ;i++){
        pSrc += arrmembersize;
        if ( fpCmp((const void *)pSrc, result)&lt;0 ){
            memcpy( (void *)pRes, (const void *)pSrc, arrmembersize );
        }
    }
}
int cmp_int(const void *a, const void *b)
{
    return ( *(int *)a - *(int *)b );
}
int cmp_double(const void *a, const void *b)
{
    return ( (fabs(*(double *)a < *(double *)b ))&lt;1e-9) ? -1 : 1; //这个可能要调整下
}
int main()
{
    int iArr[]={1,3,5,-1,3,4,7};
    double fArr[]={-3.2, 2.3, 7.8, -9.3, 4.7, 10.5};
    int iMin;
    double fMin;
    FindMin( (void *)iArr, sizeof(iArr)/sizeof(iArr[0]), sizeof(iArr[0]), (void *)&iMin, cmp_int );
    FindMin( (void *)fArr, sizeof(fArr)/sizeof(fArr[0]), sizeof(fArr[0]), (void *)&fMin, cmp_double);
    printf("Min of iArr is %d
", iMin);
    printf("Min of fArr is %lf
", fMin);
    return 0;
}

参考资料：
      1.CSDN上的讨论帖.
      2.在C中实现函数模板的方法.

后记：
      感谢所有帮助解决这个问题了朋友！这问题纠结了我两天，通过这个感觉对指针的理解又多了一点。
      CSDN上的hikaliv建议看下va_list,va_args等看下可变参数如何读取,顺便理解了下，其实之前Sandy跟我说过，只是一直没看，现在看了感觉收获蛮大。Felix021说我的代码风格不好，开始不明白，不过等他和Sandy写出来他们写的FindMin后，就明白了，我的代码太晦涩了，还是写个自己看的，别人看了看不出大概，真的多注意了。
      虽然，在C语言中实现模板不是不可能，但是我还是倾向于用模板，C++我了解的太少了。

Trackback URL | Say something...

4 Comments are ready?

  1. 李博 CSDN hikaliv said on: 2009年05月20日 02:37

    我来了。写得不错。
    分析得很深刻啊。

    [回复]

    boluor　回复  于   五月 20th, 2009 at 16:13

    大家的劳动成果阿.呵呵.

    [回复]

  2. sandy said on: 2009年05月26日 17:58

    不是我说你，这文章写的实在是令人无语……
    要是让felix看到了估计你又得被BS了。

    首先你知道何为“模板”？何为模板函数？你写的三个例子一个模板都没有————别狡辩说C里面没有模板，就算用define来模拟模板也完全不是你那个样子，你根本把模板的概念就没搞清楚。

    其次，你的方法2，你在哪里看到说“这种方法比较好，方便调试”————把说这话的人找出来，我非找他论理不可，简直是不堪入目的写法。

    方法3，不要以为csdn上的人就牛B了，那个方法是更加的糟糕，不仅没有解决问题，反倒增加了复杂度降低了效率，不知道你怎么还认为这算一种好方法……你可以让felix来看看，看他怎么说……

    [回复]

    Felix021　回复  于   五月 27th, 2009 at 12:51

    差不多吧，我以前写的很多东西也很挫。
    不过C++的模板，那个typename的实现差不多也就是typedef吧。
    那个调试方法我也用过，确实很挫，把代码搞的一团糟，太难看了。
    特别是第二段代码17行开始的#if，那简直就是搞笑。
    最后，我倾向于直接返回索引，而不是把保存索引的int的地址传过去，太晦涩了。

    [回复]

  3. agassi_p said on: 2009年12月10日 13:02

    博主，你好！能不能把–他和Sandy写出来他们写的FindMin–他们写的代码贴出来看看呀，谢谢了！！
    “Felix021说我的代码风格不好，开始不明白，不过等他和Sandy写出来他们写的FindMin后，就明白了，我的代码太晦涩了，还是写个自己看的，别人看了看不出大概，真的多注意了。
    ”

    [回复]

    boluor　回复  于   十二月 10th, 2009 at 13:30

    Felix021当时写的。Sandy写的上面已经有了。主要是代码风格，他们两个的很清晰。

    #include <stdio.h>
 
int lessthan(void *a, void *b){
    int *aa = (int *)a, *bb = (int *)b;
    return (*aa < *bb) ? 1 : 0;
}
 
int findmin(void *a, int a_size, int a_num,
            int (*lessthan)(void *, void*))
{
    char *p = a, *q;
    int i;
    if(a_num <= 0) return -1;
    for (i = 1; i < a_num; ++i){
        q = (char*)a + i * a_size;
        if(lessthan(p, q) == 0){
            p = q;
        }
    }
    return (p - (char *)a) / a_size;
}
 
int main(){
    int d[] = {5,3,6,1,2,4,7,8,9};
    int index = findmin(d, sizeof(int), 9, lessthan);
    printf("d[%d] = %d\n", index, d[index]);
    return 0;
}

    [回复]

  4. voxdei said on: 2010年06月27日 01:40

    #include
    #include
    #include

    #ifndef TYPE
    # define TYPE int
    #endif

    TYPE cmp(TYPE *a, TYPE *b)
    {
    return (*a – *b);
    }

    int main()
    {
    TYPE x = 1;
    TYPE y = -1;
    (void)printf(“%d\n”, cmp(&x, &y));
    return 0;
    }

    gcc evil.c -DTYPE=char -std=c99
    ./a.out
    2

    gcc evil.c -DTYPE=bool -std=c99
    ./a.out
    0

    不过很邪恶啊

    [回复]

Post a Comment

Your email is never published nor shared. Required fields are marked *

*

*

click to changeSecurity Code