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的课上讲到的，明白了上面的设计想法之后，比较容易实现。这里贴出源代码，并简单讨论一下。
阅读更多…