编程范式|程序世界里的编程范式，探索编程本质

最近看了一些关于编程范式的文章，简要做一些小结和记录

什么是编程范式

在现实生活中，为了适配各种规格的螺帽，我们需要许多种类的螺丝刀。

在编程世界中，静态语言有许多种类的数据类型。

不过，我们可以发现，无论是传统世界，还是编程世界，我们都在干一件事情，就是通过使用一种更为通用的方式，抽象和隔离，让复杂的“世界”变得简单一些。

C语言的范式例子1：swap函数

原版，swap交换变量（只能交换int型）

void swap(int* x, int* y) { int tmp = *x; *x = *y; *y = tmp; }

改进版，使用void * 抽象化数据类型，范式编程：

void swap(void* x, void* y, size_t size) { char tmp[size]; memcpy(tmp, y, size); memcpy(y, x, size); memcpy(x, tmp, size); }

函数接口中增加了一个size参数。一旦用了 void* 后，类型就会被“抽象”掉，编译器不能通过类型得到类型的尺寸了，所以需要我们手动加上一个类型长度的标识。

函数的实现中使用了memcpy()函数。因为类型被“抽象”掉了，所以不能用赋值表达式了，很有可能传进来的参数类型还是一个结构体，不过，为了要交换这些复杂类型的值，我们只能使用内存复制的方法了。

函数的实现中使用了一个temp[size]数组。这就是交换数据时需要用的 buffer，会用 buffer 来做临时的空间存储。

C语言的范式例子2：search函数

原版C语言函数，搜索target在整型数组中的位置：

int search(int* a, size_t size, int target) { for(int i=0; i<size; i++) { if (a[i] == target) { return i; } } return -1; }

把search函数变为泛型，使之不仅能查找整型数组，也能查找适配其他传入的各种类型参数。

参数a，可以遍历的数组、结构体数组等
target，void *，不定类型的数据（以适配范式）
cmpFn，函数，用户程序员自定义的各种数据的比较函数

int search(void* a, size_t size, void* target, size_t elem_size, int(*cmpFn)(void*, void*) ) { for(int i=0; i<size; i++) { // 这里不用memcmp比较，是因为 针对传入的数据类型是结构体类型时，memcmp会比较内存地址。 //使用 unsigned char * 计算地址 if ( cmpFn ((unsigned char *)a + elem_size * i, target) == 0 ) { return i; } } return -1; } //整数比较函数 int int_cmp(int* x, int* y) { return *x - *y; } //字符串比较函数 int string_cmp(char* x, char* y){ return strcmp(x, y); } //结构体比较函数 typedef struct _account { char name[10]; char id[20]; } Account; int account_cmp(Account* x, Account* y) { int n = strcmp(x->name, y->name); if (n != 0) return n; return strcmp(x->id, y->id); }

上面的泛型search函数缺陷：只支持顺序类型的数据结构，遇到复杂的图、树等无法抽象化非顺序型的数据容器

另外C语言还可以使用宏定义来泛型化。

泛型编程

一个良好的泛型编程需要解决如下几个泛型编程的问题：
1.算法的泛型；
2.类型的泛型；
3.数据结构（数据容器）的泛型。

就像前面的search()函数，里面的 for(int i=0; i<len; i++) 这样的遍历方式，只能适用于顺序型的数据结构的方式迭代，如：array、set、queue、list 和 link 等。并不适用于非顺序型的数据结构。
如哈希表 hash table，二叉树 binary tree、图 graph 等这样数据不是按顺序存放的数据结构（数据容器）。所以，如果找不到一种泛型的数据结构的操作方式（如遍历、查找、增加、删除、修改……），那么，任何的算法或是程序都不可能做到真正意义上的泛型。

比如，如果我要在一个 hash table 中查找一个 key，返回什么呢？一定不是返回“索引下标”，因为在 hash table 这样的数据结构中，数据的存放位置不是顺序的，而且还会因为容量不够的问题被重新 hash 后改变，所以返回数组下标是没有意义的。

对此，我们要把这个事做得泛型和通用一些。如果找到，返回找到的这个元素的一个指针（地址）会更靠谱一些。

所以，为了解决泛型的问题，我们需要动用以下几个 C++ 的技术。
1.使用“模板”来抽象类型，这样可以写出类型无关的数据结构（数据容器）。
2.使用一个“迭代器”来遍历或是操作数据结构内的元素。

C++的范式例子1:search函数 template<typename T, typename Iter> Iter search(Iter pStart, Iter pEnd, T target) { for(Iter p = pStart; p != pEnd; p++) { if ( *p == target ) return p; } return NULL; }

在 C++ 的泛型版本中，我们可以看到：

使用typename T抽象了数据结构中存储数据的类型。

使用typename Iter，这是不同的数据结构需要自己实现的“迭代器”，这样也就抽象掉了不同类型的数据结构，迭代器需要数据结构自己去实现。