动态语言与 C 语言泛型

动态语言如 python，javascript，php 等，它们的变量和值是分开来的。 变量是没有类型的，可以把任何的值赋给变量。你可以把一个整数赋值给这个变量，然后再把这个字符串赋值给这个变量。 这毫无问题。

C 语言是一种偏向底层的语言，历史悠久，特性很少但是都是久经考验的。 在用 C 实现一种泛型容器时，一种设计是使用 void *指针来储存任意数据。

很久以前我就感觉到这两者中有某种的相似和联系之处，特别是在写泛型代码时。现在我想把它具体的表达出来。

1. 什么是泛型？

1.1. 类型

想理解泛型，得到先理解类型的概念。

不管什么语言，甚至是神秘的 lisp，只要是编程语言，其功能都是对你脑子里的某种模型的描述。 而你脑子里的这种模型，是对现实世界的一种抽象。

现实世界中的各种信息，抽象到脑子里，就是 数据 。 数据有很多种，每种数据都是不一样的。 这种不一样的性质，有些语言如 C 语言能够直接用语法给表达出来，就成为 类型 。

比如说一个老师和学生互动的小程序中，涉及到两种主要数据：老师的数据和学生的数据。

用 C 语言描述它们，就是：

sturct Student {
    int student_no;
    char *name;
    int age;
    char *cass_name;
    /* ... */
};

sturct Teacher {
    char *name;
    int age;
    char *subject;
    /* ... */
};

这里面，Student 用于描述学生数据，Teacher 用于描述教师数据，它们是两种类型。

如果熟悉 C 之类的强类型语言，类型的概念应该是刻在脑子里的； 但是如果使用 php 之流的弱类型语言，是很容易忽视类型这个概念的。

但是不管使用什么语言，类型的概念，都是 非常重要 的，和你使用的语言无关。

1.2. 泛型

知道了类型的概念后，泛型也就很容易解释了。 所谓泛型，也就是一段代码，可以对多个类型操作。

1.2.1. 举例一 容器

最典型的例子是容器。链表，栈，队列等。 写的通用的容器，里面应该能够装所有类型的数据。 总不能说，我写了一个只能装 int 类型数据的链表。 那我要是那天需要一个装 double 类型数据的链表，怎么办？ 难不成把类似的代码重新写一遍？

写一个链表库，我从这个链表库定义出的链表实例，可以随意指定里面放什么数据。 可以是 int，也可以是 char *，或者是其它的数据类型。

这段链表代码，可以对多个类型操作，也就是 泛型 。

1.2.2. 举例二 算法

我再举另外一个 C 语言上的例子。 把具有独立功能的代码写成函数，是一个很好的代码习惯。 好处有很多，既能提高代码复用，也能提升代码的可读性。最重要的是，构造了适当的抽象。 这个不是重点，掠过。

有一天在写 C 语言小程序的时候，发现需要一个功能，取两个整数的最大值。于是写了个函数：

int max_int(int n1, int n2)
{
    return (n1 > n2) ? n1 : n2;
}

之后我发现我需要找出两个 double 型的数中最大的那个。于是又写个函数：

int max_double(double n1, double n2)
{
    return (n1 > n2) ? n1 : n2;
}

然后，我还发现我又得需要找出两个 unsigned 数中最大的那个。 。。。。。 难道把同样的代码，再写一遍？

int max_uint(unsigned n1, unsigned n2)
{
    return (n1 > n2) ? n1 : n2;
}

这个时候，假如能写出一种很厉害的 max 函数，即能对 int 型操作，又能对 double 型操作。那该多好。

这种很厉害的 max 函数，就是泛型函数了。

2. 泛型的重要性

泛型是编程当中一个很 重要 的东西。 但是在我之前学习动态语言时，我对泛型有点误解。

python 之流的动态特性使得泛型程序写起来很简单，简单到你甚至感觉不到泛型的存在。 它并不像 C++之类逼着你用模板语法，时时刻刻向自己暗示这是一段泛型代码。

python 的语言特性非常好，很方便。 但是我这种初学者，却因此忽略了泛型的存在，进而忽视了泛型的重要性。 结果我很懊恼一个问题： 明明 python 语法这么优雅，为什么我写出来的代码这么渣？

好在现在这个问题有了一些答案。 编程的本质不以语言的改变而改变，无论你用 C++，python 甚至是 lisp， 泛型和前面说的类型一样，都是一个 重要 的概念。

很重要！！！ 很重要！！！ 很重要！！！

3. 动态语言

3.1. 动态语言特点

先说明一下，这里指的动态语言其实是像 python，javascript 这种，变量可以赋任意类型的值。 比如在 python 中，你可以把一个整数赋值给一个变量，然后再把一个字符串赋值给一个变量。 没有问题。

demo_var = 10
print(demo_var)
demo_var = "This is a string"
print(demo_var)

这些语言的变量有一个特点，变量和值分离。 这些语言中的变量只是一个引用，真正的数据储存在值里面。

以上面的代码为例，demo_var 这个变量一开始是“指向”了 10 这个值。 之后，使用 demo_var 的地方，是使用它指向的这个值。

然后，再把 10 这个值和变量 demo_var 断开，再让变量 demo_var 指向”This is a string”这个值。

可以发现，这些语言的变量都类似 C 语言中的指针，所以前面用了”指向“这个词。 而且，变量是可以指向任意的值的，前后还可以指向不同的值。

3.2. 动态语言中的泛型代码

有了这个特点，在动态语言中的泛型代码写起来非常轻松，轻松到你都意识不到这是泛型代码。

先来看看容器。 使用 python 写容器代码，写出来的容器天然的就能放入任意的值进去。 前面说了，python 的变量是可以指向任意值的，放在容器数据结构里面的变量，也能够指向任意值。 所以你就能把任何类型的数据给放进去。

用这类语言写泛型算法也非常轻松，轻松到你都没有感觉到这是泛型算法。 比如前面的那个很厉害的 max 函数，稍微一写：

def my_max(a, b):
    if a > b:
        return a
    else:
        return b

你会惊讶的发现，这个函数，即能对整数操作，也能对浮点数数操作，甚至是对字符串操作：

print(my_max(5, 10))
print(my_max(5.2, 10.3))
print(my_max("world", "word"))

不过要注意的是，这个函数并不是对所有的类型都能操作，它只能对 满足某种条件 的类型操作。 这个不是本文的重点，以后再说吧。

4. C 语言

4.1. 试图用类型别名提升容器的通用性

在用 C 语言写数据结构的时候，数据结构的入门书籍都会强调代码应该要更通用。 比如《数据结构和算法分析》一书中，告诉读者通过 typedef 把容器里的类型包装下。 如链表里这样：

/* list.h */
sturct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;

typedef int ElementType;
List MakeEmpty(List L);
void Insert(ElementType X, List L, Position P);
void DeleteList(List L);
/* ... */

/* lish.c */
struct Node {
    ElementType Element;
    Position Next;
};

/* ... */

容器里的储存的类型使用的是 ElementType。当把它定义成 int 时候，就成为了可以装入 int 类型数据的链表。 如果我把它改成 double，就成了可以装入 double 类型数据的链表。比起不用别名定义，要更通用。

可问题是，如果我需要两个链表实例，一个里面要装 int 数据，另外一个里面要装 double 数据，怎么办？

我们发现，上面的代码描述的链表，虽然能够自己灵活的选择装入什么类型的数据， 但是一旦确定装入某种数据，那么所有的链表实例都得只能装入这种数据。

所以说，这个代码并不是真正的泛型。 之所以《数据结构和算法分析》这么教，我觉得是因为在 C 语言实现真正的泛型是很麻烦的一件事情， 这本书也不可能讲太多复杂的无关东西。

4.2. void * 指针

C 语言中实现泛型这种“通用”的需求的，是 void * 指针。 实际上，C 语言之所以弄出 void * 指针，其原本的目的是储存任意类型的数据。

4.2.1. 容器泛型

先看容器。实现泛型容器的思路是，容器里面只储存 void * 型的指针， 对容器的使用者来说，放进去的是 void * ，之后拿出来的也是 void * 。

使用者不管想要储存什么数据，都得把指向这些数据的指针转为 void * 存进去， 需要拿出来时再拿出来，转回成原本的指针类型，继续使用。

按照我的编程习惯，写出来的代码类似这样：

/* list.h */
sturct Node_s;
typedef struct Node_s Node;
typedef struct Node_s List;
typedef void *ElementType;

List *list_init(List *L);
ElementType list_get(List *L, int nth);
void list_append(List *L, ElementType X);
void list_delete(List *L);
/* ... */

/* lish.c */
struct Node_s {
    ElementType element;
    struct Node_s *next;
};

/* ... */

使用者的代码类似这样： 这是在链表里放入字符串：

List str_list_demo;
list_init(&str_list_demo);
char *str1 = strdup("This is a string");
char *str2 = strdup("This is a string, too");
list_append(&int_list_demo, &str1);
list_append(&int_list_demo, &str2);

char *str_data = list_get(&str_list_demo, 0);
printf("%s\n", str_data);

free(str1);
free(str2);
list_delete(&str_list_demo);

这是在链表里放入整型数据：

/* bug code */
List int_list_demo;
list_init(&int_list_demo);
int n1 = 10;
int n2 = 20;
list_append(&int_list_demo, &n1);
list_append(&int_list_demo, &n2);

int *int_data = list_get(&int_list_demo, 0);
printf("%d\n", *int_data);
list_delete(&int_list_demo);

相信你注意到上面代码里的问题了。放入容器里的指针是指向栈内存的。 一旦代码所在的函数返回，容器的指针指向的数据就没了，指针也将会成为野指针。

这也就是 C 语言用 void * 来实现泛型的一个麻烦的地方，内存管理。 使用这种方式，即使想放点类似 char, int 这种小数据，还必须用 malloc 在堆中申请空间。 不仅增多了很多麻烦，还降低了代码的效率。

4.2.2. 算法泛型

C 语言中的算法泛型是使用 void * 指针，再加一种类似函数式语言的风格实现的。

再回头看看前面所说的很厉害的 max 函数。 仔细分析这个函数你会发现，这个函数并不是对所有的类型都能使用。 max 函数作用的类型要有个前提条件： 必须支持大于（>）比较 。

这种条件是个非常非常重要的东西，非常非常 重要 ！

函数式语言最重要的特点是，函数是 first-class 的，能够当做参数传入另一个函数。 函数式语言对于这个厉害的 max 函数，是这样实现的（python 描述）：

def my_max(a, b, more_func):
    if more_func(a, b):
        return a
    else:
        return b

# 找出两个整数的最大的那个
my_max(1, 3, lambda a, b: return a > b)
# 找出两个字符串的最大的那个
my_max("abc", "def", lambda a, b: return a > b)
# 我还可以换一种对于字符串"大"的定义，来找两个字符串中最大的那个
my_max("abcd", "def", lambda a, b: return len(a) > len(b))

泛型函数对可以操作的类型有前提条件，如那种厉害的 max 函数要求类型必须支持大于函数。 这种思想的核心是，不仅接收需要处理数据，还把前提条件支持的操作作为一个函数传递过来，像上面的大于函数。

C 语言就借鉴了这种思想，使用这种思路来实现算法泛型。 典型的例子就是标准库的 qsort 函数，能够对数组里的数据，进行快速排序。 和上面的 max 类似，qsort 也要求对操作的类型必须满足特点的条件：必须支持比较操作。

qsort 也是要求将比较操作作为一个函数，当成参数传进来。 虽然 C 语言中的函数不是 first-class 的，但是通过 C 语言的函数指针， 也能够做到这一点，就是麻烦了一点。哦不，麻烦的不是一点。。。

来看标准库 qsort 的函数原型：

void qsort(void *ptr, size_t count, size_t size,
           int (*comp)(const void *, const void*));

这个函数接收四个参数，其中 ptr 是待排序数组的首地址，count 是待排序数组的元素个数。 comp 是个函数指针，指向的函数，对该种类型进行比较操作。 返回负值表示第一个参数比第二个参数小，返回零表示相等，返回正值表示大于。

至于 size 参数，由于 C 语言是一种底层语言，C 语言的数组，里面的一个个元素是在内存中紧密挨在一起的。 如果是一种已知类型的数据，C 语言当然能知晓元素之间的边界在哪； 然而在这个函数里面，为了泛型的支持，ptr 指针是 void * 型的。 所以这里面，size 参数含义是数组中单个元素所占的内存大小，通过它，就能通过计算定位出元素之间的边界。

比如用 qsort 对整型数组进行排序：

int int_comp(const void *p_n1, const void *p_n2)
{
    /* 另一种更简洁的写法是直接写 return *(int *)p_n1 - *(int *)p_n2; */
    if (*(int *)p_n1 < *(int *)p_n2) {
        return -1;
    } else if (*(int *)p_n1 > *(int *)p_n2) {
        return 1;
    } else {
        return 0;
    }
}

int arr[] = {5, 10, 6, 2, 15};
qsort(arr, 5, sizeof(int), int_comp);

我们可以看见，qsort 不清楚传入的数组里面到底是什么数据，只是把这些数据交给传入的比较函数比较。 在这个阶段，使用 void * 传递数据。 但是比较函数是针对于某一种类型的，它是知道 void * 指向的到底是什么数据，将其转回原来的数据指针，进行比较。

这个 qsort 函数实现了泛型算法，对于任意的 实现了比较函数 的类型，它对能够对该类型的数组进行排序。

5. 共通之处

虽然动态语言和 C 语言，是两种相差很大的语言。但是它们对泛型的支持，却是很类似的。 动态语言可以指向一切值的变量，和 C 语言的 void * 指针，都是一种能够指向一切数据的东西。

泛型容器中想要储存任意数据，是通过这种能指向一切数据的东西储存的。 而泛型算法中传递不同类型的数据，也是通过这种能指向一切数据的东西作为媒介的。

6. 这种方式的缺点

写到这里忽然发现写的有点多。 作为一个写博客的新手，不知道如何合理安排详略，只是一股脑的把想到的分析出来。 不仅使文章拖的很长，还得花费我大量时间去构思。看来以后得吸取经验啊

最后总结下这种方式泛型的缺点，作为本篇博客的结尾吧。

6.1. 类型安全

这一点，在动态语言里就不用说了。动态语言根本就没有类型检查，也谈不上类型安全。 动态语言也不仅是在这方面有这种问题，它在所有的方面都有这个问题，这是动态语言的诟病之一。 你有可能一不小心把整型当成字符串来用，把字符串当成某个数据来用，然后 gg。

C 语言作为强类型语言，类型安全是一大特点之一。 如果你一不小心把整型当成字符串来用，编译器是会报错的。 但是通过 void * 实现泛型的这些代码，却享受不到这些好处。 你有可能一开始把整数数据存放到了容器里，结果后来不小心给当成字符串给取了出来。 使用 void * 泛型容器时犯了这些错误，编译器不能帮你检查出来。

6.2. 无法及时暴露错误

动态语言还是一样，不仅仅在这方面有这个问题。 动态语言由于缺乏类型检查，很多地方上的错误必须等运行到那里时才能暴露出来。

前面说了，C 语言在使用 void * 实现的泛型代码时，编译器无法检查出类型错误。 这就意味着，这些错误和动态语言一样，必须等到代码运行到这个地方，然后 gg，你才知道出错误了。 而且 C 语言出了错误，很可能是段错误或者往内存里乱写东西，这都是很严重的问题。

6.3. 性能问题

比起专用的容器和算法，泛型的容器和算法会有性能损失。

动态语言在这方面问题不大。 首先动态语言不是很看重性能，其次是这种弱类型是动态语言特性的一部分，解释器会专门的对其做优化。

但是在Ｃ语言中，首先使用 void* 会使得代码多一次寻址，会有一点点的性能损失。 更重要的是，使用 void * 储存数据，会遇到内存管理上的麻烦。 你不得不在堆上分配一块内存，然后指针指过去。这就增多了堆内存分配的开销。