C/C++ Contributing Editors

STL & Generic Programming: Traits Classes

Thomas Becker

Traits classes are a mainstay of the Standard C++ library. Here's an opportunity to understand them in depth.

Introduction

The overall plan for my column on STL and Generic Programming is to first make one pass through the STL, giving you whatever advice I think you may need in addition to what you’ll find in your favorite documentation or introductory book. After that, I will be talking about generic programming techniques in general, such as template metaprogramming and the like. Within this overall plan, we’re still on the first part, taking a trip through the STL. Nevertheless, I will digress briefly this month and talk about a generic programming technique that is not specific to the STL, namely, traits classes. The reason for this digression is that traits classes are showing up more and more in articles on C++ programming, most notably in this magazine. Traits are also frequently encountered at <www.boost.org>, a great source for all kinds of nifty free stuff related to generic programming in general and the STL in particular. Therefore, I believe that the time has come to take a step back and paint the big picture on this subject: What are traits classes, what problem do they solve, and how do they solve it?

I am not going to try and give you a definition of what a traits class is before showing an example. Let me just say that the earliest reference on the subject that I know of is N.C. Myers’ article [1] in the now-defunct C++ Report, also available at <www.cantrip.org/traits.html>. The subject was taken up again by Andrei Alexandrescu in [2]. Both articles are highly recommended reading.

Explicit and Partial Template Specialization

Traits classes rely heavily on explicit and partial template specialization. Therefore, we must at least briefly review those two features of C++ before we can look at traits classes. Say you have defined a class template like this:

template<typename T>
class X
{
public:
  void foo(){ /* do something */ }
  // more stuff
};

Then, whenever you use an instantiation of the class template X, as in:

X<int> anX;
anX.foo();

the compiler will use your general definition of class X to generate the code for foo(), and, if necessary, the constructor and destructor for the object anX. Now suppose you decide that for the particular type int, you do not want to use this definition of the class template X. Instead, you want to use a completely different implementation. I will not go out of my way here to give you an example of why you may want to do this; examples will abound in the discussion of traits classes below. You can achieve this by providing a so-called explicit template specialization for the type int, like this:

template<>
class X<int>
{
public:
  void foo(){ /* do something else */ }
  // more stuff
};

Now if you write:

X<int> anX;
anX.foo();

the special implementation that you have provided for the type int will be used. Since this specialization is no longer a class template, you may actually place the definitions of the member functions of the specialization into a separate source file without further ado. Listing 1 shows a possible organization of the headers and sources. Note how the header Xint.h only needs a forward declaration of the class template X, not the entire definition.

Next, suppose that you have a class template with two template parameters, as in:

template<typename S, typename T>
class Y
{
public:
  void foobar(){ /* do something */ }
  // more stuff
};

Suppose you wish to use a different implementation whenever the first template parameter is specialized to int, regardless of what the second one is. C++ allows you to do this by using a so-called partial template specialization, like this:

template<typename T>
class Y<int, T>
{
public:
  void foobar(){ /* do something else*/ }
  // more stuff
};

Now whenever you use an instantiation of the class template Y with the first template parameter being int, as in:

Y<int, SomeClass> aY;
aY.foobar();

then the implementation specified in your partial specialization will be compiled and used.

Partial template specialization is not restricted to specifying one or more of several template parameters. Instead, you can specify patterns to be matched for the template arguments. An important example is partial template specialization for all pointer types. Consider again the class template X that we used before:

template<typename T>
class X
{
public:
  void foo(){ /* do something */ }
  // more stuff
};

We may now write a partial specialization for all pointer types like this:

template<typename T>
class X<T*>
{
public:
  void foo(){ /* do something else */ }
  // more stuff
};

Any instantiation where a pointer type is used for the template argument T will use this partial template specialization. An example would be:

X<char*> anX;
anX.foo();

In all other cases, the original general implementation is used. It should be obvious now how you can write partial template specializations that apply to all reference types, all const types, all pointers to const, and so on and so forth.

If you’re using Microsoft’s Visual C++ compiler, be warned that it does not support partial template specialization, thereby effectively locking you out of a whole world of exciting and important C++ programming techniques. Please do read on, though. I have written this column so that all examples get by with explicit rather than partial template specialization.

The Prototype Factory Example

To give you a better feeling for the relevance of traits classes, I will use a real-life, real-world example rather than yet another version of the manager, shape, or widget example. Suppose you have decided that you want to use the prototype pattern in your software. (For a full and detailed description of the prototype pattern, see Chapter 3 of the Gang-of-Four book [4].)

Creating objects from prototypes is a good idea whenever the following scenario occurs: your program uses a finite number of different, but closely related kinds of objects. Creation of the first object of each kind is costly, perhaps involving file-system or database access. After that, the creation of further copies of each kind from the first object can be achieved by a much cheaper cloning operation. In this case, it is a good idea to create one prototype of each kind up front, typically during program initialization, store them all in a factory object, and then obtain clones of the prototypes from the factory object. The prototypes can be objects of completely unrelated types, of different types that have a common base class, all of the exact same type, or a combination of all of the above. A practical example of such a collection of prototypes is shown in the nuts and bolts and other parts that go into a CAD drawing. Creating the first instance of a particular nut or bolt typically involves a trip to some large database or a website. It is expected that many copies of this first instance will be needed, and each of these is easily obtained as a clone of the first one.

Suppose now you have decided that your prototypes will have a common base class, let’s say, Widget. Therefore, you are going to write a prototype factory class that holds pointers to objects of type Widget. Let us further assume that the prototypes are indexed by integer IDs. Also, as is to be expected of a factory class, your widget factory class will be a singleton, of which only one instance exists. Once these design decisions have been made, we can achieve a good measure of genericity and hence reusability by simply using two template parameters instead of the object type Widget and the ID type int. Listing 2 shows the skeleton of the resulting semi-generic prototype factory class. This skeleton completely omits the singleton aspect of the factory class, and it suppresses a number of issues such as error checking, ownership of pointers, and the like. These are of course important issues, but they are irrelevant to the purpose of my example.

Notice that the prototype factory’s GetClone member function calls a method Clone on the prototype whose clone is to be obtained. Clone is a common choice for the name of this kind of method, and it is what you used in your Widget class. Rather obviously, your prototype factory class template can be reused only for prototype classes that provide an appropriate method for cloning. Moreover, that method must be named Clone. That’s fine as long as the prototype class is written by you or someone close to you, but that may not be the case. Classes that are candidates for prototyping often have issues concerning deep versus shallow copying. For example, a part in a CAD drawing may be a composite, and such a composite can be deep-copied, where each part of the composite is copied, or it can be shallow-copied, where copies of pointers to the parts of the composite are made. In these cases, it is quite likely that the designer of the class has chosen names such as DeepCopy, ShallowCopy, etc., but there is no method named Clone. Now your prototype factory class template cannot be used as is, because the GetClone method must call DeepCopy on the prototype object rather than Clone.

This is certainly a very annoying situation. A rather accidental choice of nomenclature shoots down our carefully designed scheme for code reuse. Let’s look at the traditional options that spring to mind for resolving this situation. Suppose the offending class is called Gadget, and it has a method called DeepCopy that we want to use in lieu of Clone. The first thing you should think of when confronted with a class whose interface doesn’t match the requirements of your code is the adapter pattern (see Chapter 4 of [4]). Using this pattern, you would slap a new interface on the Gadget class, either through inheritance or through aggregation, giving it a new method Clone that forwards to DeepCopy. If you have other, additional reasons for wanting to write an adapter for the Gadget class, you’re fine. Doing it just for the sake of being able to reuse the prototype class template is most certainly a poor tradeoff. The extra work needed and the additional complexity introduced into your code by writing the Gadget adapter are simply not justified by the gain.

The other option for dealing with the situation is to derive a new class from the prototype factory class template, overriding GetClone so as to make it call DeepCopy rather than Clone on the prototype. Ten years ago, most people would have considered this to be the correct solution. In the years since, we have learned the hard way that this kind of design leads straight into the thickets of impenetrably complex class hierarchies, a place that is only marginally preferable to the chaos of non-object-oriented spaghetti code. It is not a good idea to use inheritance to create a gaggle of different versions of a class to make it reusable in different contexts.

Traits Classes

Fortunately, there is a solution to our problem that is simple, elegant, and efficient, namely, using what’s called a traits class. Let us take a step back and state our problem in the most general terms. We are looking at a class template whose implementation, at one point, needs to take different action according to the value of one of the template parameters. Specifically, in our case, if the template parameter Proto is Widget, or any other class whose cloning operation is called Clone, the method Clone must be called on the prototype. If Proto is Gadget, then DeepCopy must be called. In other cases, yet other methods may have to be called. In other words, we want the implementation of the factory’s GetClone to behave like the following pseudocode:

Proto* p = protoTypeCollection[id];
If Proto is Gadget Then
  return p->DeepCopy();
ElseIf  
  // more cases
Else
  return p->Clone();
EndIf

Notice that this pseudocode has no chance of ever becoming valid C++ code. Even though the conditional expression "Proto is Gadget" could be written in C++ as:

typeid(Proto) == typeid(Gadget)

the code still would not compile in general. For example, if Proto is Gadget, then the compiler would complain about the call p->Clone, because Gadget does not have a method called Clone. It is true that the same compiler would probably optimize away the Else-branch at some later stage of compilation, but that does not help. C++ code must be syntactically correct before any optimization; those are the rules, and they’re not likely to change any time soon.

Traits classes provide a way to implement the above “if-else of types” [5] in C++. Here’s how it’s done. First, we write a class template called prototype_traits as follows:

template<typename T>
class prototype_traits
{
public:
  static T* Clone(T* p)
  { return p->Clone(); }
};

We then write the prototype factory’s implementation of GetClone as follows:

Proto* ProtoTypeFactory::GetClone(Id id)
{
  return prototype_traits<Proto>::Clone(
    protoTypeCollection[id]
    );
}

So far, GetClone behaves just as it did in Listing 2, except for an additional level of indirection: it first calls the static member function Clone of prototype_traits, passing p as an argument, and that static member function then calls p->Clone. And here comes the punch line: to make our prototype factory class call DeepCopy instead of Clone when the prototypes are Gadgets, all we have to do is provide an explicit specialization of prototype_traits for Gadgets, like this:

template<>
class prototype_traits<Gadget>
{
public:
  static Gadget* Clone(Gadget* p)
  { return p->DeepCopy(); }
}

Now if the template parameter Proto of the class template ProtoTypeFactory equals Gadget, and the member function GetClone gets called, the above explicit specialization of prototype_traits will be used. Therefore, DeepCopy gets called on the prototype p.

Let’s summarize. The problem: you have a class template that sometimes needs to take different action depending on the value of a certain template parameter. The solution: the actions that are different for different values of the template parameter get routed through an external class template named xxx_traits. The default implementation of this class template does what is expected to be the right thing in most cases. If a particular value of the template parameter requires different action, then an explicit instantiation of the traits class template for that type is provided that takes the appropriate action.

Notice that the customization provided by traits classes is entirely external. The class template that is being customized (ProtoTypeFactory in our case) has to be written only once; no changes to the source code are necessary when a new case, such as the Gadget class with its DeepCopy method, shows up. Neither do we have to do anything to the Gadget class. All that needs to be done is to provide a new explicit specialization for the traits class, and this specialization must be included only in the new code that deals with the factory of Gadgets. No existing code that uses ProtoTypeFactory without Gadget or Gadget without ProtoTypeFactory needs to be recompiled.

Typedefs in Traits Classes

If you look at traits classes written by other people, you’ll find that they contain mostly typedefs. Providing appropriate typedefs is in fact one of the main reasons for having traits classes, and our prototype factory example provides ample opportunity to illustrate this. We have decided to let our factory hold pointers to prototype objects. However, it is entirely conceivable that the cloning operation of the prototype class returns the clone by value. To accommodate this kind of prototype, we let the factory’s GetClone method obtain its result type from the traits class, rather than hardcode it to Proto*. Listing 3 shows a version of the prototype factory class template that incorporates this and some other improvements. The default implementation of the traits class defines the type that is returned from GetClone with the typedef:

typedef Proto* cloning_result_type;

If a particular type of prototype, say, Gadget, wishes to return the clone by value, it must define in its explicit specialization of the traits class:

typedef Gadget cloning_result_type;

Our prototype factory class was originally meant to hold plain pointers to the prototype objects. While we’re at it customizing types, we might as well let the factory pull the type of object that is stored in the collection from the traits class. Again, Listing 3 incorporates this improvement by letting the traits class provide a typedef named stored_type. The type that is stored inside the factory can now be a plain old pointer, an actual prototype object, or even some sort of smart pointer, perhaps reference counted to automate the handling of lifetime issues.

Booleans in Traits Classes

Speaking of lifetime issues, now that we have made the type of the stored object customizable, we should look at what the destructor of the factory object does. As you would expect, the destructor is customized by routing its action through the traits class. The destructor itself loops over the collection of prototype objects and calls a function that is provided by the traits class on each object:

~ProtoTypeFactory()
{
  std::for_each(
    protoTypeCollection.begin(),
    protoTypeCollection.end(),
    DestroyPrototype()
   );
}

Here, DestroyPrototype is a function object whose overloaded operator() calls a static member function of the traits class to destroy each of the prototype objects (see Listing 3 for details).

Explicit specializations of the traits class for other kinds of prototypes may wish to perform some other action to destroy the object, such as calling a method like DestroyWindow, or they may elect to do nothing at all. This works fine, but there is still a flaw in this design. If a certain type of stored prototype needs no action at all upon destruction, then the factory’s destructor loops over the collection of prototypes for nothing. This may not be a big deal in practice, but then maybe it is. One way of dealing with this would be to move the entire loop into the traits class. But that’s really ugly, because the traits class should only make statements about the prototype class; it should not be burdened with implementation details of the factory class. The solution is to let the traits class provide a boolean that states if the prototype class needs to have anything done at all upon destruction. The factory’s destructor then enters the loop over its collection of prototypes only if it’s really necessary. Listing 3 shows how this is done. Notice how the boolean value that determines whether or not to do anything at all upon destruction of the prototypes is provided as an enum value. This is the standard way of doing it because it’s more economical than using a boolean member variable: an enum does not require space inside the objects. In fact, you can get the enum value at class level without instantiating an object at all.

Classes Providing Their Own Traits

The default implementation of our prototype_traits in Listing 3 contains what we think is most likely to be appropriate in practice. If you expect most of the prototype classes to be written with knowledge and consideration of the prototype_traits class, then you should write the default implementation of the traits class in such a way that it pulls everything out of the prototype class itself. An explicit specialization is then necessary only for “outside” classes that are unaware of the traits class. Listing 4 shows how to do that. STL iterator_traits employ this technique.

Function Overloading with Traits

So far, the prototype factory code shows two ways of branching on the value of the template argument: one way is to use a function that is provided by the prototype class, as in the method GetClone. This type of branching happens at compile time. The other is to pull a boolean from the traits class and then acting conditionally according to that boolean, as shown in the destructor of ProtoTypeFactory. Here, the branching happens at run time. A third way of doing it is to use function overloading. Many STL algorithms use this technique. Listing 5 demonstrates the general idea. The top-level algorithm calls an internal helper that takes an additional dummy argument of type iterator_category. The helper is overloaded on the type of the dummy object. Therefore, the appropriate version of the helper will be chosen at compile time, depending on the type of the iterator template argument.

References

[1] N.C. Myers. “Traits: A New and Useful Template Technique,” C++ Report, June 1995, <www.cantrip.org/traits.html>.

[2] A. Alexandrescu. “Traits: The if-else-then of Types,” C++ Report, April 2000.

[3] A. Alexandrescu. Modern C++ Design (Addison-Wesley, 2001).

[4] Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides. Design Patterns (Addison-Wesley, 1994).

[5] I believe it was Scott Meyers who came up with this succinct description of the purpose of traits classes.

Thomas Becker works as a senior software engineer for Zephyr Associates, Inc. in Zephyr Cove, NV. He can be reached at thomas@styleadvisor.com.