In the past, reusable code meant a sacrifice of efficiency for convenience. The C standard library qsort performs comparisons via a function pointer. OOP dosen't help, inheritance and virtual functions are still an overhead.
C++ introduces generic programming, with templates, eliminating the need for runtime binding, but at first glance this still looks like a compromise, after all, the same algorithm will not work optimally with every data structure. Sorting a linked list is different to sorting an array. Sorted data can be searched much faster than unsorted data.
The C++ traits technique provides an answer.
Think of a trait as a small object whose main purpose is to carry information used by another object or algorithm to determine "policy" or "implementation details". - Bjarne Stroustrup
Both C and C++ programmers should be familiar with limits.h, and float.h, which are used to determine the various properties of the integer and floating point types.
Most C++ programmers are familiar with std::numeric_limits, which at first glance simply provides the same service, implemented differently. By taking a closer look at numeric_limits we uncover the first advantage of traits, a consistent interface.
Using float.h, and limits.h, you have to remember the type prefix and the trait, for example, DBL_MAX contains the "maximum value" trait for the double data type. By using a traits class such as numeric_limits the type becomes part of the name, so that the maximum value for a double becomes numeric_limits< double >::max(), more to the point, you don't need to know which type you need to use. For example, take this simple template function [2], which returns the largest value in an array:
template< class T >
T findMax(const T* data, int numItems)
{
// Obtain the minimum value for type T
T largest = std::numeric_limits<T>::min();
for (int i=0; i < numItems; ++i)
if (data[i] > largest)
largest = data[i];
return largest;
}
Note the use of numeric_limits. As you can see, where as with the C style limits.h idiom, where you must know the type, with the C++ traits idiom, only the compiler needs to know the type. Not only that, but numeric_limits, as with most traits, can be extended to include your own custom types (such as a fixed point, or arbitrary precision arithmetic classes) simply by creating a specialisation of the template.
But I'd like to move away from numeric_limits, its just an example of traits in action, and I'd like to take you through creating traits classes of your own.
First lets look at one of the simplest traits classes you can get (from boost.org) and that's the is_void [3] trait.
First, a generic template is defined that implements the default behaviour. In this case, all but one type is void, so is_void::value should be false, so we start with:
template< typename T >
struct is_void{
static const bool value = false;
};
Add to that a specialisation for void:
template<>
struct is_void< void >{
static const bool value = true;
};
And we have a complete traits type that can be used to detect if any given type, passed in as a template parameter, is void. Not the most useful piece of code on its own, but definitely a useful demonstration of the technique.
Now, while fully specialised templates are useful and in my experiance, the most common sort of trait class specialisation, I think that it is worth quickly looking at partial specialisation, in this case, boost::is_pointer [3]. Again, a default template class is defined:
template< typename T >
struct is_pointer{
static const bool value = false;
};
And a partial specialisation for all pointer types is added:
template< typename T >
struct is_pointer< T* >{
static const bool value = true;
};
So, having got this far, how can this technique be used to solve the lowest common denominator problem? How can it be used to select an appropriate algorythm at compile time? This is best demonstrated with an example.
First a default traits class is created, for this example we'll call it supports_optimised_implementation, and, other than the name, it will be the same is the is_void example. Next the default algorithm is implemented, inside a templated algorithm_selector, in this example the algorithm_selector template is parameterised with a bool, but in situations where a number of algorithms could be appropriate it could just as easily be parameterised with an int, or and enum. In this case "true" will mean "use optimised algorithm in object".
template< bool b >
struct algorithm_selector {
template< typename T >
static void implementation( T& object )
{
//implement the alorithm operating on "object" here
}
};
Next the a specialisation of algorithm_selector is added which, in this case, passes the responsability for implementing the algorithm back to the author of the object being operated on, but could well implement a second version of the operation itself.
template<>
struct algorithm_selector< true > {
template< typename T >
static void implementation( T& object )
{
object.optimised_implementation();
}
};
Then we write the generic function that the end user of your algorithm will call, note that it in turn calls algorithm_selector, parameterised using our supports_optimised_implementation traits class:
template< typename T >
void algorithm( T& object )
{
algorithm_selector< supports_optimised_implementation< T >::value >::implementation(object);
}
Now all that's left to do is test it against a class that doesn't support the feature ( class ObjectA{}; ), and a class that does:
class ObjectB
{
public:
void optimised_implementation()
{
//...
}
};
//specialisation of supports_optimised_implementation trait for ObjectB
template<>
struct supports_optimised_implementation< ObjectB > {
static const bool value = true;
};
Finally, instantiate the templates:
int main(int argc, char* argv[])
{
ObjectA a;
algorithm( a ); // calls default implementation
ObjectB b;
algorithm( b ); // calls ObjectB::optimised_implementation();
return 0;
}
Originally posted to kuro5hin on Mar 01, 2001, here: http://www.kuro5hin.org/story/2001/3/1/72020/17594.
[ Download: C++ Traits Example Source Code in full. ]
It should be noted that the examples in this article require a cutting edge, standard compliant, compiler. For example, MSVC++ 6.0 does not support static constants, and will balk on:
static const bool value = false;
This particular problem can be worked around by using an enum in its place, ie:
enum { value = false };
Please contact your compiler vendor for appropriate work arounds and bug fixes for your platform.