垃圾回收算法

---

一、引用计数 (Reference Counting)

原理：每个对象维护引用计数，当计数归零时释放内存。

C++示例：

#include <iostream>class RefCounted {int count = 0;public:void addRef() { count++; }void release() {if (--count == 0) {delete this;}}protected:virtual ~RefCounted() = default; // 允许派生类析构
};class MyObject : public RefCounted {
public:MyObject() { std::cout << "Created\n"; }~MyObject() { std::cout << "Destroyed\n"; }
};int main() {MyObject* obj = new MyObject();obj->addRef(); // 引用计数=1obj->addRef(); // 引用计数=2obj->release(); // 引用计数=1obj->release(); // 引用计数=0，触发析构return 0;
}

缺点：无法处理循环引用（如A引用B，B引用A）。

二、标记-清除 (Mark-Sweep)

原理：从根对象出发标记所有可达对象，清除未标记的。

C++示例：

#include <iostream>
#include <vector>class GCObject {static GCObject* head;  // 全局对象链表GCObject* next = nullptr;bool marked = false;public:GCObject() { // 添加到链表next = head;head = this;}virtual ~GCObject() {}virtual void markChildren() {} // 标记引用的子对象void mark() {if (marked) return;marked = true;markChildren(); // 递归标记子对象}static void sweep() {GCObject** curr = &head;while (*curr) {GCObject* obj = *curr;if (!obj->marked) {*curr = obj->next;delete obj;} else {obj->marked = false;curr = &obj->next;}}}
};GCObject* GCObject::head = nullptr;// 根对象集合
std::vector<GCObject*> roots;class Node : public GCObject {
public:Node* child = nullptr;void markChildren() override {if (child) child->mark();}
};int main() {// 创建对象图：root -> node1 -> node2Node* node1 = new Node();roots.push_back(node1);Node* node2 = new Node();node1->child = node2;// 执行垃圾回收for (auto root : roots) root->mark();GCObject::sweep();// 手动清除根（示例中未释放roots，实际需管理生命周期）return 0;
}

缺点：内存碎片化，需暂停程序运行（Stop-the-World）。

三、标记-整理 (Mark-Compact)

原理：标记后移动存活对象至内存一端，整理后释放剩余空间。

简化示例（通过句柄间接访问对象）：

#include <vector>class Object {// 假设所有对象通过Handle访问
};class Handle {Object* ptr;public:Object* get() const { return ptr; }void relocate(Object* new_ptr) { ptr = new_ptr; }
};std::vector<Handle*> handles; // 所有句柄需注册void compact(std::vector<Object*>& alive) {// 移动存活对象到新内存区域for (auto& handle : handles) {if (/* 对象存活 */) {Object* new_addr = /* 新地址 */;handle->relocate(new_addr);}}// 释放旧内存
}

缺点：对象移动需更新所有引用，实现复杂。

四、分代回收 (Generational)

原理：按对象存活时间分代（年轻代、老年代），优先回收年轻代。

简化示例：

class Generation {std::vector<GCObject*> young;std::vector<GCObject*> old;void promote(GCObject* obj) {// 将对象从年轻代晋升到老年代old.push_back(obj);}public:void collectYoung() {// 标记-清除年轻代for (auto obj : young) if (isRoot(obj)) obj->mark();sweep();// 晋升存活对象for (auto obj : young) if (obj->marked) promote(obj);young.clear();}
};

优点：减少扫描范围，提升效率。