Home arrow C++ arrow Page 8 - A Simple Garbage Collector for C++

A Simple Garbage Collector for C++

The use of dynamically allocated memory must be managed, because it has a tremendous effect on the performance of your programs. The current trend in handling dynamic memory seems to be shifting toward an automated approach. While C++ uses the manual approach for managing dynamic memory, this does not mean that it can't be automated in that language -- thus giving the C++ programmer the best of both worlds. This article explains how to do it. It is excerpted from chapter two of The Art of C++, written by Herbert Schildt (McGraw-Hill/Osborne, 2004; ISBN: 0072255129).

Author Info:
By: McGraw-Hill/Osborne
Rating: 4 stars4 stars4 stars4 stars4 stars / 73
June 21, 2005
  1. · A Simple Garbage Collector for C++
  2. · Comparing the Two Approaches to Memory Management
  3. · Choosing a Garbage Collection Algorithm
  4. · What About auto_ptr?
  5. · An Overview of the Garbage Collector Classes
  6. · GCPtr In Detail
  7. · The Overloaded Assignment Operators
  8. · GCInfo
  9. · How to Use GCPtr
  10. · Allocating Arrays
  11. · A Larger Demonstration Program
  12. · Load Testing

print this article

A Simple Garbage Collector for C++ - GCInfo
(Page 8 of 12 )

The garbage collection list in gclist holds objects of type GCInfo. The GCInfo class is shown here:

// This class defines an element that is stored
// in the garbage collection information list.
template <class T> class GCInfo {
unsigned refcount; // current reference count
T *memPtr; // pointer to allocated memory
/* isArray is true if memPtr points
     to an allocated array. It is false
     otherwise. */
  bool isArray; // true if pointing to array
/* If memPtr is pointing to an allocated
     array, then arraySize contains its size */
  unsigned arraySize; // size of array
// Here, mPtr points to the allocated memory.
  // If this is an array, then size specifies
  // the size of the array.
  GCInfo(T *mPtr, unsigned size=0) {
refcount = 1;
    memPtr = mPtr;
    if(size != 0)
isArray = true;
      isArray = false;
arraySize = size;

As mentioned earlier, each GCInfo object stores a pointer to allocated memory in memPtr and the reference count associated with that memory in refcount. If the memory pointed to by memPtr contains an array, then the length of that array must be specified when the GCInfo object is created. In this case, isArray is set to true, and the length of the array will be stored in arraySize.

GCInfo objects are stored in an STL list. To enable searches on this list, it is necessary to define operator==( ), as shown here:

// Overloading operator== allows GCInfos to be compared.
// This is needed by the STL list class.
template <class T> bool operator==(const GCInfo<T> &ob1,
const GCInfo<T> &ob2) {
  return (ob1.memPtr == ob2.memPtr);

Two objects are equal only if both their memPtr fields are identical. Depending upon the compiler you are using, other operators may need to be overloaded to enable GCInfos to be stored in an STL list.


The Iter class implements an iterator-like object that can be used to cycle through the elements of an allocated array. Iter is not technically necessary because a GCPtr can be converted to a normal pointer of its base type, but Iter offers two advantages. First, it lets you cycle through an allocated array in a fashion similar to the way in which you cycle through the contents of an STL container. Thus, the syntax for using an Iter is familiar. Second, Iter will not allow out-of-range accesses. Thus, an Iter is a safe alternative to using a normal pointer. Understand, however, that Iter does not participate in garbage collection. Thus, if the underlying GCPtr on which an Iter is based goes out of scope, the memory to which it points will be freed whether or not it is still needed by that Iter.

Iter is a template class defined like this:

template <class T> class Iter {

The type of data to which the Iter points is passed through T.

Iter defines these instance variables:

T *ptr;   // current pointer value
T *end;   // points to element one past end
T *begin; // points to start of allocated array
unsigned length; // length of sequence

The address to which the Iter currently points is held in ptr. The address to the start of the array is stored in begin, and the address of an element one past the end of the array is stored in end. The length of the dynamic array is stored in length.

Iter defines the two constructors shown here. The first is the default constructor. The second constructs an Iter, given an initial value for ptr, and pointers to the beginning and end of the array.

Iter() {
ptr = end = begin = NULL;
  length = 0;
Iter(T *p, T *first, T *last) {
  ptr = p;
  end = last;
  begin = first;
  length = last - first;

For use by the garbage collector code shown in this chapter, the initial value of ptr will always equal begin. However, you are free to construct Iters in which the initial value of ptr is a different value.

To enable Iters pointer-like nature, it overloads the * and > pointer operators, and the array indexing operator [ ], as shown here:

// Return value pointed to by ptr.
// Do not allow out-of-bounds access.
T &operator*() {
if( (ptr >= end) || (ptr < begin) )
throw OutOfRangeExc();
  return *ptr;
// Return address contained in ptr.
// Do not allow out-of-bounds access.
T *operator->() {
if( (ptr >= end) || (ptr < begin) )
    throw OutOfRangeExc();
return ptr;
// Return a reference to the object at the
// specified index. Do not allow out-of-bounds
// access.
T &operator[](int i) {
if( (i < 0) || (i >= (end-begin)) )
    throw OutOfRangeExc();
  return ptr[i];

The * operator returns a reference to the element currently being pointed to in the dynamic array. The > returns the address of the element currently being pointed to. The [ ] returns a reference to the element at the specified index. Notice that these operations do not allow an out-of-bounds access. If one is attempted, an OutOfRangeExc exception is thrown.

Iter defines the various pointer arithmetic operators, such as ++, , and so on, which increment or decrement an Iter. These operators enable you to cycle through a dynamic array. In the interest of speed, none of the arithmetic operators perform range checks themselves. However, any attempt to access an out-of-bounds element will cause an exception, which prevents a boundary error. Iter also defines the relational operators. Both the pointer arithmetic and relational functions are straightforward and easy to understand.

Iter also defines a utility function called size( ), which returns the length of the array to which the Iter points.

As mentioned earlier, inside GCPtr, Iter<T> is typedefed to GCiterator for each instance of GCPtr, which simplifies the declaration of an iterator. This means that you can use the type name GCiterator to obtain the Iter for any GCPtr.


blog comments powered by Disqus

- Intel Threading Building Blocks
- Threading Building Blocks with C++
- Video Memory Programming in Text Mode
- More Tricks to Gain Speed in Programming Con...
- Easy and Efficient Programming for Contests
- Preparing For Programming Contests
- Programming Contests: Why Bother?
- Polymorphism in C++
- Overview of Virtual Functions
- Inheritance in C++
- Extending the Basic Streams in C++
- Using Stringstreams in C++
- Custom Stream Manipulation in C++
- General Stream Manipulation in C++
- Serialize Your Class into Streams in C++

Watch our Tech Videos 
Dev Articles Forums 
 RSS  Articles
 RSS  Forums
 RSS  All Feeds
Write For Us 
Weekly Newsletter
Developer Updates  
Free Website Content 
Contact Us 
Site Map 
Privacy Policy 

Developer Shed Affiliates


© 2003-2018 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap
Popular Web Development Topics
All Web Development Tutorials