void*实现泛型编程


引言


typename *p是指向某类型的指针:在常规情况下,p指向的内存,存放着typename类型的数据。

  • p += n意味着 p += n * sizeof(typename)
  • *p意味着从p开始取sizeof(typename)个字节,以typename类型进行数据读取。

然而( 尤其是C语言 )很多情况下,我们并不能确定数据的类型。

如果直接定义具体的typename *的指针,则无法实现接口函数的重用性,编程效率大大降低。

那么特殊的typename— void能不能帮我们解决这一问题?

无类型指针


void* ,即无类型指针。

区分空指针:typename* p = NULL

1. void*的使用规则

int *a;
void *p;
p = a;    
// 无类型指针可以指向任意类型(因此可作为参数,实现泛型编程)
a = (int*)p;    
// 无类型指针通过强制类型转换,赋值给其他类型指针

因为指向void,所以p += n 和 * p均是无意义的 [ ANSI标准下会报错,GNU当成char*的来运算 ] 。

但我们可以用 p += n * sizeof(typename) 和 * (typename * ) p 来实现自定义类型的操作。

/* 定义 */
int x[2] = { 5, 10 };
void *p = x;
/* 运算 */
++p;    // 不合法
cout << *p;    // 不合法
p += sizeof(int);    // 正确
cout << *(int*)p;    // 正确(GNU)
//最后输出结果为: 10

2. 常见的void*实例

作为返回值:

内存分配函数 malloc 的返回值就是void*型指针。

一般调用时,我们会用到强制类型转换。即形如(int*)malloc(sizeof(int))的使用方式。

作为参数:

内存拷贝函数 void* memcpy(void *dest, const void *src, size_t len)参数就是void*型指针。

之前提过无类型指针可以指向任意类型,即可接收任意类型指针的赋值

在调用时,若p1和p2均为char类型的指针,memcpy(p1, p2, sizeof(char)),则将 从p2开始的sizeof(char)字节的内存 拷贝到 从p1开始的sizeof(char)字节内存中。

void*的泛型编程


泛型编程,即编写完全一般化且可重复使用的算法来提高编程效率

1. 例一

让我们先看一个例子:

/* 交换值 */
// int
void swap(int* a, int* b)
{
    int* tmp = a;
    a = b;
    b = tmp;
}

// float
void swap(float* a, float* b)
{
    float* tmp = a;
    a = b;
    b = tmp;
}

// ......

为了不重复编写,我们可以使用无类型指针void*来接受不同类型指针的参数。

void swap(void *p1, void *p2, int size)
{
    char buffer[size];    // 前提是GCC编译器
    // 分配size个字节的内存
    memcpy(buffer, p1, size);
    memcpy(p1, p2, size);
    memcpy(p2, buffer, size);
}

此时,我们调用swap,可以像如下这样操作:

int a = 1, b = 2;
swap(&a, &b, sizeof(int));

2. 例二

接下来,我们再看一个例子:

/* 查找(返回下标) */
// int
int Search(int key, int array[], int len)
{
    for(int i = 0; i < len; i++)
        if(key == array[i])
            return i;
    return -1;
}

// float
int Search(float key, float array[], int len)
{
    for(int i = 0; i < len; i++)
        if(key == array[i])
            return i;
    return -1;
}

// ......

使用void*改造为泛型函数:

/* 查找(返回地址) */
void* Search(void *key, void *base, int len, int size)
{
    char *elementAddress = (char*)base;    // 以1字节为基本单位[char为1字节]
    for(int i = 0; i < len; i++)
    {
       if(memcmp(key, elementAddress, size) == 0)
           return (void*)elementAddress;
       elementAddress += size;
    }
    return NULL;
}

此时,我们调用Search,可以像如下这样操作:

int array[] = { 10, 20, 30, 40, 50 };
int key = 30;
int *result = (int*)Search(&key, array, 6, sizeof(int));
if(result)
    cout << "Found -- " << *result;
else
    cout << "Not Found";

//输出结果:Found -- 30

3. 例三

最后,让我们基于例二拓展一下,实现行为的泛型化

在例二中,Search函数中调用了memcmp函数,即包含了“内存比较”这一行为

而在实际应用中,我们可能要使用到各种不同规则的比较行为

/* 行为 1 —— 比较int的大小 */
int IntCmp(void* elem1,void* elem2)
{
    int *ip1 = (int*)elem1;
    int *ip2 = (int*)elem2;
    return *ip1-*ip2;
}

/* 行为 2 —— 比较长方体(结构体)的宽度 */
struct Cuboid
{
    int length;
    int wide;
    int height;
};

int Cuboid_WideCmp(void* elem1,void* elem2)
{
    int ip1 = (*(struct Cuboid*)elem1).wide;
    int ip2 = (*(struct Cuboid*)elem2).wide;
    return ip1-ip2;
}

对于以上不同的行为,均可使用函数指针,实现行为的泛型化。

/* 查找(返回地址) */
void* Search(void *key, void *base, int len, int size, int(*cmp)(void*, void*))
{
    char *elementAddress = (char*)base;    // 以1字节为基本单位[char为1字节]
    for(int i = 0; i < len; i++)
    {
       if(cmp(key, elementAddress) == 0)
           return (void*)elementAddress;
       elementAddress += size;
    }
    return NULL;
}

调用方法如下:

/* 行为 1 —— 比较int的大小 */
int array1[] = { 1, 2, 3, 4 };
int key1 = 2;
int *result = (int*)Search(&key1, array1, 4, sizeof(int), IntCmp);
if(result)
    cout << "Found -- " << *result;
else
    cout << "Not Found";

//输出结果:Found -- 2


/* 行为 2 —— 比较长方体(结构体)的宽度 */
struct Cuboid array2[4];
array2[0].wide = 1;
array2[1].wide = 2;
array2[2].wide = 3;
array2[3].wide = 4;
struct Cuboid key2;
key2.wide = 4;
struct Cuboid *result;
result = (struct Cuboid*)Search(&key2, array2, 4, sizeof(struct Cuboid), Cuboid_WideCmp);
if(result)
    cout << "Found -- " << (*result).wide;
else
    cout << "Not Found";

//输出结果:Found -- 4

其中,行为2框架下的Search函数功能变为:寻找与目标长方体宽度相同的长方体

由此可见,行为泛型化在泛型编程中的意义之重大。

结语


在C++中的模板(template) 和STL标准模板库(Standard Template Library) 是泛型编程实现的典例。

而在C语言中,使用void*实现的泛型编程,是极其有限的。

尤其是在安全性方面,系统很难完成全面、有效的检查,需要我们编程时更加严谨、仔细。


  目录