一、垃圾回收器概述
典型的垃圾回收器算法有三种:一是引用计数(Reference Counting),二是标记并清除(Mark-Sweep),三是复制(Copying)。对于这三种算法，可以用餐巾纸的例子来通俗解释。
引用计数（ Reference Counting ）算法
拿餐巾纸的例子来说，这种算法的原理大致可以描述为：
午餐时，为了把脑子里突然跳出来的设计灵感记下来，我从餐巾纸袋中抽出一张餐巾纸，打算在上面画出系统架构的蓝图。按照“餐巾纸使用规约之引用计数版”的要求，画图之前，我必须先在餐巾纸的一角写上计数值 1，以表示我在使用这张餐巾纸。这时，如果你也想看看我画的蓝图，那你就要把餐巾纸上的计数值加1，将它改为 2，这表明目前有2个人在同时使用这张餐巾纸（当然，我是不会允许你用这张餐巾纸来擦鼻涕的）。你看完后，必须把计数值减1，表明你对该餐巾纸的使用已经结束。同样，当我将餐巾纸上的内容全部誊写到笔记本上之后，我也会自觉地把餐巾纸上的计数值减1。此时，不出意外的话，这张餐巾纸上的计数值应当是0，它会被垃圾收集器——假设那是一个专门负责打扫卫生的机器人——捡起来扔到垃圾箱里，因为垃圾收集器的惟一使命就是找到所有计数值为 0 的餐巾纸并清理它们。
引用计数算法的优点和缺陷同样明显。这一算法在执行垃圾收集任务时速度较快，但算法对程序中每一次内存分配和指针操作提出了额外的要求（增加或减少内存块的引用计数）。更重要的是，引用计数算法无法正确释放循环引用的内存块，这说明，单是使用引用计数算法还不足以解决垃圾收集中的所有问题。当然，作为一种最简单、最直观的解决方案，引用计数算法本身具有其不可替代的优越性。
标记－清除（ Mark-Sweep ）算法
第一种实用和完善的垃圾收集算法是 J. McCarthy 等人在 1960 年提出并成功地应用于 Lisp 语言的标记－清除算法。仍以餐巾纸为例，标记－清除算法的执行过程是这样的：
午餐过程中，餐厅里的所有人都根据自己的需要取用餐巾纸。当垃圾收集机器人想收集废旧餐巾纸的时候，它会让所有用餐的人先停下来，然后，依次询问餐厅里的每一个人：“你正在用餐巾纸吗？你用的是哪一张餐巾纸？”机器人根据每个人的回答将人们正在使用的餐巾纸画上记号。询问过程结束后，机器人在餐厅里寻找所有散落在餐桌上且没有记号的餐巾纸（这些显然都是用过的废旧餐巾纸），把它们统统扔到垃圾箱里。
正如其名称所暗示的那样，标记－清除算法的执行过程分为“标记”和“清除”两大阶段。这种分步执行的思路奠定了现代垃圾收集算法的思想基础。与引用计数算法不同的是，标记－清除算法不需要运行环境监测每一次内存分配和指针操作，而只要在“标记”阶段中跟踪每一个指针变量的指向——用类似思路实现的垃圾收集器也常被后人统称为跟踪收集器（ Tracing Collector ）
复制（ Copying ）算法
为了解决标记－清除算法在垃圾收集效率方面的缺陷， M. L. Minsky 于 1963 年发表了著名的论文“一种使用双存储区的 Lisp 语言垃圾收集器（ A LISP Garbage Collector Algorithm Using Serial Secondary Storage ）”。 M. L. Minsky 在该论文中描述的算法被人们称为复制算法，它也被 M. L. Minsky 本人成功地引入到了 Lisp 语言的一个实现版本中。
复制算法别出心裁地将堆空间一分为二，并使用简单的复制操作来完成垃圾收集工作，这个思路相当有趣。借用餐巾纸的比喻，我们可以这样理解 M. L. Minsky 的复制算法：
餐厅被垃圾收集机器人分成南区和北区两个大小完全相同的部分。午餐时，所有人都先在南区用餐（因为空间有限，用餐人数自然也将减少一半），用餐时可以随意使用餐巾纸。当垃圾收集机器人认为有必要回收废旧餐巾纸时，它会要求所有用餐者以最快的速度从南区转移到北区，同时随身携带自己正在使用的餐巾纸。等所有人都转移到北区之后，垃圾收集机器人只要简单地把南区中所有散落的餐巾纸扔进垃圾箱就算完成任务了。下一次垃圾收集的工作过程也大致类似，惟一的不同只是人们的转移方向变成了从北区到南区。如此循环往复，每次垃圾收集都只需简单地转移（也就是复制）一次，垃圾收集速度无与伦比——当然，对于用餐者往返奔波于南北两区之间的辛劳，垃圾收集机器人是决不会流露出丝毫怜悯的。
M.L.Minsky的发明绝对算得上一种奇思妙想。分区、复制的思路不仅大幅提高了垃圾收集的效率，而且也将原本繁纷复杂的内存分配算法变得前所未有地简明和扼要（既然每次内存回收都是对整个半区的回收，内存分配时也就不用考虑内存碎片等复杂情况，只要移动堆顶指针，按顺序分配内存就可以了），这简直是个奇迹！不过，任何奇迹的出现都有一定的代价，在垃圾收集技术中，复制算法提高效率的代价是人为地将可用内存缩小了一半。实话实说，这个代价未免也太高了一些。
二、基于引用计数的垃圾回收器
为了实现引用计数的垃圾回收器，必须有某种方法来跟踪指向每块动态分配内存的指针的数量。解决方案是：可以建立一个新的支持垃圾回收的指针类型，也就是说该指针类型支持指针的操作，又有个数据成员来跟踪指向分配内存的指针的数量。具体来说，新的指针类型必须完成三件事情：第一，它必须为使用中的动态分配的对象维护一个引用计数的链表。第二，它必须跟踪所有的指针运算符，每次某个指针指向一个对象时，都要使这个对象的引用计数增1，每次某个指针重新指向其他对象时，都要使原本指向的对象的引用计数减1。第三，它必须回收那些引用计数降为0的对象。
根据上述的设计思路，构造指针类GCPtr
template
class GCPtr
{
private:
static list > gclist; //记录分配的每块内存的引用计数
T * addr; // 当前存储指针
bool isArray;
unsigned arraySize;
static bool first; // true when first GCPtr is created,用来注册退出函数，以解决引用计数实现的垃圾回收的循环引用问题
typename list >::iterator findPtrInfo(T * ptr); //查找ptr是否已记录在gclist链表中
public:
//构造函数,复制构造函数，析构函数及指针操作的一些函数
//特别的，有几个static函数，是垃圾回收器工作的核心
static bool collect();
static void shutdown(); //atexit注册的退出函数，用于清理循环引用的对象
};
其中GCInfo设计如下
template
class GCInfo
{
public :
unsigned refcount;
T *memptr;
bool isArray;
unsigned arraySize;
GCInfo(T *mptr,unsigned size = 0)
{
refcount = 1;
memptr = mptr;
if(size != 0)
isArray = true;
else
isArray = false;
arraySize = size;
}
};
在源码中，还提供了另外两个类，Iter 和 OutOfRangeExc。Iter是封装的迭代器类，因为GCPtr虽然支持普通指针的"*"和“->”操作，但并不提供指针运算，比如“++”，“--”。Iter类提供了类型安全的指针运算，使用方法与一般迭代器相同。
OutOfRangeExc是个异常类，但并没有实际的成员。如果有需要用到异常，可通过它进行扩展。
侯捷说“源码之前，了无秘密“，放出源码在此。
