0 前言
最近深感自己的coding能力太差，于是很自觉地找来了stanford的网络课程来充实自己。最近在学的是由Jerry Cain主讲的Programming Paradigm课程。该课程的内容像一锅大杂烩，涵盖了C/C++，assembly, python等程序设计语言，以及sequential / concurrent programming，procedure-oriented / object-oriented programming等多种程序设计模式。此外，该课程还捎带了计算机体系结构，操作系统，编译原理等相关课程的知识，真是琳琅满目啊！最可贵的是，该课程的assignment各个都是经过精心设计的，不但有趣而且实用，有一定的代码量和难度，做下来一定受益匪浅！
目前我学完了前10个lecture，觉得收获最大的是学会了C语言通用类型容器的设计，本篇日志将围绕这个话题展开讨论。Hope you’ll like it 
1 为什么要写C版本的通用容器
也许我们已经习惯了C++标准库中的多种容器，比如最常用的vector，还有map，set等等。这些容器让我们彻底舍弃了恼人的数组。而C并未为我们提供这些，如果贪恋vector的便利，那么何不自己动手写一份呢？而且，使用C版本的容器在工业界是非常有现实意义的。当我们面对有限的主存时（比如手机，PDA等），通过C++通用容器生成的汇编代码会占用大量的空间。比如，当我们声明vector<int>类型的变量时，编译器会生成一份只接纳int类型的代码，当声明vector<double>时，编译器又生成了另一份代码，以此类推… 而C语言的容器会为所有的类型使用同一份代码。虽然你需要为此牺牲类型的安全性以及使用上的便利性，但是汇编代码的巨大缩减会让你觉得这是值得的。事实上，微软，苹果，Sun的系统工程师也在使用自己编写的容器来替代C++的vector以提高系统效率。
另外，正如Jerry老师在assignment 3（C语言vector和hashset的实现）的handout中所讲，“这件事儿会让你发现C原来这么牛逼，一但你成功编写，debug，用C vector做练习，你对于指针，主存，动态分配的理解会达到顶尖水平。这是我对你们的承诺。”
2 C与C++相比差了什么
抛开C与C++在标准库上的差距，我们单纯从语言特性上来看看C和C++差了什么。
首先进入我脑海的是C没有reference。没关系，Jerry老师会告诉你，reference其实只是会自动dereference的pointer。两者在功能上是无差别的。其实，pointer版的swap和reference版的swap生成的汇编代码是完全一样的。
此外，C没有Class，无法隐藏结构/类的成员。Jerry老师又告诉你了，没办法，这是C的短板，在使用C容器的时候，我们就假装结构的成员变量是不可见的，只调用配套的函数，不直接对成员变量进行操作。另外，我们无法在C的struct中定义函数，于是我们无法用’.’或’->’操作符调用成员方法，只能在struct之外定义函数，并将容器指针作为参数传入。
接下来是最要紧的，C没有Template，于是乎，我们不能告诉容器它所存储的类型，配套的函数也无法得知类型信息。怎么办呢？如果没有这方便的编程经验，恐怕会对这个问题一筹莫展。下面就是我在这门课上学到的精髓：通过传递void *类型参数，辅以容器所存储的类型的size，我们就可以对所存储的类型进行各种操作。这句话可能让你摸不着头脑，没关系，我们看看下面的例子。比如，我们想在vector中存储fraction类型，fraction的定义如下：
typedef struct { int num; int denum; } fraction;
如果是C++，我们直接通过vector<fraction>的方式在初始化的时候告诉vector它所存储的类型，通过fraction类型参数传递/操作容器外的元素。对于C语言，我们在初始化vector时传入整形参数sizeof(fraction)以利于存储空间的动态分配，容器内元素的移动等操作；而在需要对容器外元素进行操作的时候，传入void*类型参数，并对其进行强制类型转换(fraction*)，然后就可以访问fraction元素了。如下例,
VectorSomeFunc(/*some parameters*/ void *elemAddr) { fraction *f = (fraction *)elemAddr; // do something to f->num or f->denum } fraction f; f.num = 22; f.denum = 7; VectorSomeFunc(/*some parameters*/ &f);
这里使用void *类型作为函数参数是非常精妙的，因为它可以接受任何类型的指针，当我们需要用vector存储int时，我们传入int *类型的参数，需要用vector存储char *时，我们传入char **类型的参数，再分别在函数内部做(int *)，(char **)的强制转换之后就可以访问元素了。正是如此，我们才实现了“通用(generic)”这两个字。这里需要提醒一下，void *类型的参数是不能够直接deference的，也就是说，不能用对void *类型的参数进行’*'和’->’操作，强制转换以后才可以。
3 管中窥豹——stack的实现
stack的实现是在cs107的课上讲到的，明白了上面的设计想法之后，比较容易实现。这里贴出源代码，并简单讨论一下。
stack.h
#ifndef __STACK_H__ #define __STACK_H__ typedef struct { void *elems; int elemSize; int logLength; int allocLength; void (*freeFn)(void *); } stack; void stackNew(stack *s, int elemSize, void (*freeFn)(void *)); void stackDispose(stack *s); void stackPush(stack *s, void *elemAddr); void stackPop(stack *s, void *elemAddr); #endif // __STACK_H__
stack结构中的elems是stack存储空间的头指针，因为要实现“通用”，所以声明为void *类型。
elemSize是上文提到的元素的size。
logLength是stack存储元素的个数。allocLength是已分配空间所能容纳的元素的个数。注意，这两个概念是不同的。我将在下文合适的位置对此做详细的解释。
freeFn是用来释放元素的，对于int之类不需要释放的类型，可以传入NULL，而对于自定义结构，数组，指针，则需要客户来写释放函数，并在初始化的时候传给vector。
剩下的函数的功能通过函数名已经可以很好地自说明了，这里不再赘述。
stack.c
#include "stack.h" #include <assert.h> #include <stdlib.h> #include <string.h> void stackNew(stack *s, int elemSize, void (*freeFn)(void *)) { assert(elemSize > 0); s->elemSize = elemSize; s->logLength = 0; s->allocLength = 4; s->elems = malloc(s->allocLength * elemSize); assert(s->elems != NULL); s->freeFn = freeFn; } void stackDispose(stack *s) { if(s->freeFn != NULL) { for(int i = 0; i < s->logLength; i++) { s->freeFn((char *)s->elems + i * s->elemSize); } } free(s->elems); } static void stackGrow(stack *s) { s->allocLength *= 2; s->elems = realloc(s->elems, s->allocLength * s->elemSize); assert(s->elems != NULL); } void stackPush(stack *s, void *elemAddr) { if(s->logLength == s->allocLength) stackGrow(s); void *target = (char *)s->elems + s->logLength * s->elemSize; memcpy(target, elemAddr, s->elemSize); s->logLength++; } void stackPop(stack *s, void *elemAddr) { void *source = (char *)s->elems + (s->logLength - 1) * s->elemSize; memcpy(elemAddr, source, s->elemSize); s->logLength--; }
对于stackNew，有以下两点要解释：
1. assert是一个宏，而非函数，定义在assert.h中，用于确保括号内的条件(elemSize > 0)成立，如果elemSize <= 0（无意义的情况），则会打印包含源文件名和行号的错误信息，并终止程序的运行。
2. logLength初始为0，这个好理解，因为还没有元素。而allocLength初始为4，这个就费点功夫了。我们知道stack是动态增长的。理论上，我们可以在每次push的时候才分配新空间。但是，重分配需要调用realloc函数，可能会移动所有的元素到新的地址，很费时间，所以，我们要尽量减少重分配的次数以提高效率，于是，我们采用在初始化的时候分配4个元素的空间，当4个不够用的时候，就重新分配，扩充到8个，8个不够的时候扩充到16个，以此类推，每次需要重新分配的时候都将allocLength倍增。这样，下面的
s->elems = malloc(s->allocLength * elemSize);
和stackGrow中的
s->allocLength *= 2; s->elems = realloc(s->elems, s->allocLength * s->elemSize);
就好理解了。
对于stackGrow，经过刚才的讲解，应该很清晰了。值得注意的是，该函数被标示为static，意思是该函数只能被本源文件中的其他函数调用，而不能被本源文件之外的函数调用。其实相当于C++中Class的private方法。
对于剩下的stackDispose，stackPush，stackPop，实现的时候要注意指针的运算。这里有一个技巧，在进行指针运算之前，要将s->elems强制转换成char *类型，因为char类型占用一个字节（也可以用unsigned short，但是显然char打起来更快:P），elemSize也是以字节为单位的，这样计算的时候就不会出错。
最后，贴一个简单的测试程序（连接的时候不要忘了stack.o :p）。
main.c
#include "stack.h" #include <stdio.h> #include <stdlib.h> #include <string.h> void stringFree(void *); int main() { stack s; stackNew(&s, sizeof(char *), stringFree); const char *days[] = {"Monday", "Tuesday", "Wednesday", "Thurday", "Friday", "Saturday", "Sunday"}; int i; for(i = 0; i < 7; i++) { char *copy = strdup(days[i]); stackPush(&s, ©); } for(i = 0; i < 7; i++) { char *day; stackPop(&s, &day); printf("%s\n", day); free(day); } stackDispose(&s); return 0; } void stringFree(void *elem) { free(*(char **)elem); }
请自行琢磨一下倒数第二行的*(char **)elem吧:)。
4 实战——vector和hashset的实现
掌握了以上的知识，你就可以大胆去实现cs107 assignment3中的vector了。TA已经帮你写好了框架，并帮你准备好了变态的测试程序，你所要做的是考虑vector结构需要哪些成员变量以及如何实现每个函数。用到的东西大多都包含在上面的例子了。哦对了，你可能需要man一下memmove/qsort/bsearch。由于篇幅所限，这里就不贴上代码了，感兴趣的同学请点击这里下载我实现的vector。
实现了vector之后就可以动手实现hashset了。TA同样为你写好了框架和测试程序，但是，hashset这个容器实在是让人觉得生疏，handout上也只有只言片语。没办法，google之，你会发现，hash_set是STL库中的容器（STL是Standard Template Library的缩写）。看下来以后依然一头雾水，网上关于hashset内部数据结构的介绍又非常匮乏，没办法，再回头去挖掘handout，一边写代码，一边琢磨，最终终于琢磨透了hashset的结构，在这里与大家分享一下。
hashset中最核心的部分莫过于hash函数。hash函数由客户根据所要存储的类型自行定义。所谓hash函数，是指将同一类型的各种元素映射到不同的bucket中。bucket的总数是固定的，设为numBuckets。那么hash函数也就是：num = hash(elem)，其中num属于[0, numBuckets)。参考下图numBuckets = 5的情况：
图1 hash函数
每个bucket实际上是一个vector，hash函数完成“分组”之后，将元素添加到相应的vector中去。在添加的时候，要根据客户提供的比较函数cmpfn去判断该元素是否已经存在，搜索vector中的元素，一一进行比对，如果不存在，则插入vector对尾，否则，要替换原有的元素。既然两个元素一样为什么要替换呢？因为这里所说的“一样”不一定是完全相等，这要看cmpfn是怎么定义的，很有可能两个元素中的某个关键成员变量相同，就认为这两个元素“一样”了。
那么，hashset这样的存储方式有什么优点呢？答案是hashset可以提供非常快速的查找。当需要查找某元素时，首先对其执行hash函数找到它的“组织”，然后只需在“组织”内查找，因为该元素是不可能出现在别的组织当中的。如果numBuckets = 5，则平均查找时间缩短了接近4/5。如果numBuckets = 1009（通常取大质数），则平均搜索时间几乎只是连续存储型容器的千分之一。
所以，hashset非常适合存储用于查询的大量数据，比如一个20多MB纯文本的同义词词典（这也是assignment 3的终极测试数据源:p）。
这里是我实现的hashset。
5 结语
我这里也仅仅总结了一下自己学到的东西，可能有疏漏，可能有谬误，欢迎各位读者指正。我想通过此文让更多的编程入门者体验到这其中的乐趣。我在这里强烈建议已经耐心地看到这里的各位去听一听stanford的公开课程，花上一些时间，费上一些脑筋，去完成课程的编程作业，一定会像我一样收获颇丰的！
References
[1] Introduction to computer science | programming paradigms http://see.stanford.edu/see/courseinfo.aspx?coll=2d712634-2bf1-4b55-9a3a-ca9d470755ee
[2] STL hash_set http://www.sgi.com/tech/stl/hash_set.html
原创辛苦，转载请注明出处，谢谢！
写得真好啊！嘛都没看懂，恩恩