"The fundamental question about memory management can be stated in this way: If f() passes or returns a pointer to an object to g(), who is responsible for the object's destruction? A secondary question must also be answered: When can it be destroyed? ... From the point of view of a library provider, the ideal answers are 'the system, and 'whenever nobody is using the object any longer.'"

Many other languages provide built-in "garbage collection" that comes very close to this ideal. Using a garbage collector means never having to say delete: the garbage collection system itself figures out which objects are no longer in use and deletes them automatically. The draft C++ Standard has no garbage collection, so if you need it you must borrow it, buy it, or build it. Below I present one approach to building a garbage collector.

Many implementations of garbage collection are possible, most too complex to present in a short article. I have chosen to present a very simple "mark and sweep" collector. Fortunately, the performance of a well implemented mark and sweep collector can be excellent for programs not requiring bounded real-time response.

A mark and sweep collector operates in two phases:

• In the mark phase it starts from the root pointers and marks every garbage collected object which can be reached from those pointers.
• In the sweep phase it destroys all the unmarked objects.

template <class alloc>
void*
operator new(size_t n,alloc& a) {
    return a.allocate(n);
}
template <class X>
struct gc {
    X* allocate(size_t);
};

template<class X>
struct gc_ptr {
    gc_ptr(X* p=0);
    ~gc_ptr();
    gc_ptr& operator=(const
gc_ptr&);
    gc_ptr& operator=(X*);
    operator X*() const;
    X* operator->() const;
    X operator[](size_t) const;
    X& operator[](size_t);
};

The template gc is an allocator for garbage collected objects. To be garbage collected, an object must be allocated with a gc allocator using the template operator new.

The gc_ptr template declares classes of "smart pointers." Objects allocated with the gc allocator will be destroyed by the garbage collector when they are no longer reachable through any root gc_ptr. A root is a gc_ptr that is not itself in a garbage-collected object.

The usage of a gc_ptr is much the same as for an ordinary pointer. The gc_ptr template provides conversions to and from ordinary pointers, so that a gc_ptr can be used in most all places a pointer can be, with the added convenience of not needing to call delete. This convenience is not without costs. One obvious cost is that implementing an efficient garbage collector is a non-trivial task. Another cost is that the overloaded pointer operations may require function calls and other overhead, and the actual garbage collection can take enough time to cause noticeable pauses in program execution.

A more subtle cost is the uncertainty of when, and in what order, the destructors for garbage collected objects will be called. This can cause difficulties in multi-threaded systems, or if the destructor for a garbage-collected object tries to access another object that has already been destroyed by the garbage collector.

To get maximum efficiency and safety from gc_ptr, follow these simple rules:

1. Always wrap pointers to newly allocated garbage collected objects with a gc_ptr.

2. Avoid unnecessary construction and assignment of gc_ptr objects. In particular, do not define gc_ptr variables as function parameters. Use raw pointers instead.

3. Always use gc_ptr variables for class members that may point at collected objects.

4. Do not access any gc_ptr in the destructor for a garbage-collected object.

Note that the following statements, though allowable, do not create garbage-collected objects:

gc_ptr<T> p(new T);
gc_ptr<T> q(&t);

gc_ptr<T> p(new(gc<T>())T);

T* p = new(gc<T>())T;

void f(T*);
f (new(gc<T>()) T;

f (gc_ptr<T>(new(gc<T>()) T));

References

[2] D.R. Edelson and I. Pohl. "Smart Pointers: They're smart but they're not pointers." In Proceedings of the 1991 Usenix C++ Conference.

[3] J.R. Ellis and D.L. Detlefs. "Safe, efficient garbage collection for C++." In Proceedings of the 1994 Usenix C++ Conference.

[4] B.S. Stroustrup. The C++ Programming Language, Second Edition (Addison-Wesley, 1991).

[5] B.S. Stroustrup. The Design and Evolution of C++ (Addison-Wesley, 1994).

[6] P.R. Wilson. "Uniprocessor Garbage Collection Techniques." In Proceedings of the 1992 International Workshop on Memory Management.