Friday, August 03, 2007

Curiously Recurring Template Pattern (CRTP)

The funny named phrase is used to describe the use of a derived class type as a template parameter for its own base class! In simplest form, this is what I'm talking about:

template < typename T >
class Base{ };

class Derived : public Base< Derived > { };

Let me give a very simple example of where this might be useful. Suppose you want to keep track of how many objects of a particular class are alive at any point in time:

Simple approach is:
1) Keep a private static "count" member in the class
2) Increment the count in every constructor
3) Decrement the count in the destructor
4) Provide a public interface to query the value of the count

This approach is fine. However you have to do this for every class that you want to count the objects of. CRTP can pitch in and provide an elegant solution that is highly reusable.

template < typename CountedType >
class ObjectCounter
{
  private:
    static int counter;

  protected:
    ObjectCounter()
    {
      ++( ObjectCounter< CountedType >::counter );
    }

    ObjectCounter( const ObjectCounter< CountedType >& obj )
    {
      ++( ObjectCounter< CountedType >::counter );
    }

    ~ObjectCounter()
    {
      --( ObjectCounter< CountedType >::counter );
    }

  public:
    static int live()
    {
      return ObjectCounter< CountedType >::counter;
    }
};

template < typename CountedType >
int ObjectCounter< CountedType >::counter = 0;

Any class that wants to do object counting will inherit from the above class as follows:

class TestClass : public ObjectCounter< TestClass >{ };

TestClass::live() will give the number of objects alive at that point in time.

6 comments:

Shantanu said...

Interesting and simple solution in C++.


This kind of implementation is very much possible in C++, as multiple inheritance is supported by the language semantics. This allows other classes to be simultaneously inherited.

This solution is costly in a language like Java, where multiple inheritance is will-fully left out.

Not getting into whether multiple inheritance should be supported or not, here is a

unextended(non-inherited), composed solution in Java :

class Parent {
static Integer count=0;
Parent(){
count++;
}
public Integer getCount(){
return count;
}
}
public class Child {
Parent parent=null;
Child(){
parent=new Parent();
}
public Integer getCount(){
return parent.getCount();
}

public static void main(String[] args) {
// TODO Auto-generated method stub
Child child1=new Child();
Child child2=new Child();
Child child3=new Child();
System.out.println(child1.getCount());
}

}

A similar solution is obviously possible in C++ .
Which is the better solution?

Srinivas said...

I don't think multiple inheritance has anything to do here. If you already have an inheritance heirarchy in C++, then modifying the base class of the heirarchy to inherit from the ObjectCounter class will provide object counting mechanism for all the derived classes.

Problems with multiple inheritance will crop up when you have the dreaded diamond - again, the fall back, is to use virtual inheritance.

In Java, you can have an abstract class that provides object counting and any class that needs object counting can extend this abstract class. Again, if the intention is to create an inheritance heirarchy, then the base class can extend the ObjectCounter class.

Ex: If you already have this sort of a heirarchy (In C++ or Java - does not matter which language)

Base <-- Derived_1 <-- Derived_2

Change this to:

ObjectCounter <-- Base <-- Derived_1 <-- Derived_2

But the base class might not be available for modification in most cases. This presents a problem.

What is the most elegant way to plug in object counting in all the classes without having to modify all the classes. I have not thought about it. Something nice to think about :)

Shantanu said...

Object counting is mainly for accounting transactions. Ideally this should take an independent out-of-box solution. A possible candidate is a JVM query to get the instance count.

Kiran said...

If you're talking of high level lang like java or c# which runs on a vm, the simplest way to solve this prob would be to get hold of the stack, and then iterate thru it and count the num of obj ur interested in...
the pseudo code might look like

int Count(Type type-of-obj){
int count = 0;
StackTrace trace=new StackTrace();
foreach(StackFrame frame in trace.Frames)
{
if(frame.GetTypeOfObj() == type-of-obj )
count++;
}
return count;
}

Srinivas said...

I am not really familiar with Java, but, even if you manage to count objects in the way you have mentioned, does it include all the dynamically created objects? I guess the objects on stack and those that are dynamically created will be in different areas in memory. Also, in Java, there might be a skew due to out-of-use-but-not-yet-garbage-collected dynamically created objects.

Given the presence of garbage collectors in managed environments like that of Java and C#, it might be difficult to provide a mechanism to count objects in the runtime environment itself. This has to be made a reusable library of code IMO.

Kiran said...

1. When I said 'Stack' it meant the whole program execution stack which includes both stack and heap in c++ jargon. So of course you account for dynamically created objects...after all stack and heap in c++ can ultimately be in same physical memory rt? usually we don't bother to differentiate b/w them in a managed env. (the luxury you get when you don't have to clean up ur own mess !)

2. out-of-use-but-not-yet-garbage-collected
is a good point. but usually you have enough support from GC to identify such objects. ('coz GC has to identify if an object is active before eliminating it!) and also you can force garbage collection if you want. so doing it before the count is also an option.