by John Maddock and Steve Cleary
This is the draft version of an article that appeared in the October 2000 issue of Dr Dobb's Journal
Generic programming (writing code which works with any data type meeting a set of requirements) has become the method of choice for providing reusable code. However, there are times in generic programming when "generic" just isn't good enough - sometimes the differences between types are too large for an efficient generic implementation. This is when the traits technique becomes important - by encapsulating those properties that need to be considered on a type by type basis inside a traits class, we can minimise the amount of code that has to differ from one type to another, and maximise the amount of generic code.
Consider an example: when working with character strings, one common operation is to determine the length of a null terminated string. Clearly it's possible to write generic code that can do this, but it turns out that there are much more efficient methods available: for example, the C library functions strlen and wcslen are usually written in assembler, and with suitable hardware support can be considerably faster than a generic version written in C++. The authors of the C++ standard library realised this, and abstracted the properties of char and wchar_t into the class char_traits. Generic code that works with character strings can simply use char_traits<>::length to determine the length of a null terminated string, safe in the knowledge that specialisations of char_traits will use the most appropriate method available to them.
Class char_traits is a classic example of a collection of type specific properties wrapped up in a single class - what Nathan Myers termed a baggage class[1]. In the Boost type-traits library, we[2] have written a set of very specific traits classes, each of which encapsulate a single trait from the C++ type system; for example, is a type a pointer or a reference type? Or does a type have a trivial constructor, or a const-qualifier? The type-traits classes share a unified design: each class has a single member value, a compile-time constant that is true if the type has the specified property, and false otherwise. As we will show, these classes can be used in generic programming to determine the properties of a given type and introduce optimisations that are appropriate for that case.
The type-traits library also contains a set of classes that perform a specific transformation on a type; for example, they can remove a top-level const or volatile qualifier from a type. Each class that performs a transformation defines a single typedef-member type that is the result of the transformation. All of the type-traits classes are defined inside namespace boost; for brevity, namespace-qualification is omitted in most of the code samples given.
There are far too many separate classes contained in the type-traits library to give a full implementation here - see the source code in the Boost library for the full details - however, most of the implementation is fairly repetitive anyway, so here we will just give you a flavour for how some of the classes are implemented. Beginning with possibly the simplest class in the library, is_void<T> has a member value that is true only if T is void.
template <typename T> struct is_void { static const bool value = false; }; template <> struct is_void<void> { static const bool value = true; };
Here we define a primary version of the template class is_void, and provide a full-specialisation when T is void. While full specialisation of a template class is an important technique, sometimes we need a solution that is halfway between a fully generic solution, and a full specialisation. This is exactly the situation for which the standards committee defined partial template-class specialisation. As an example, consider the class boost::is_pointer<T>: here we needed a primary version that handles all the cases where T is not a pointer, and a partial specialisation to handle all the cases where T is a pointer:
template <typename T> struct is_pointer { static const bool value = false; }; template <typename T> struct is_pointer<T*> { static const bool value = true; };
The syntax for partial specialisation is somewhat arcane and could easily occupy an article in its own right; like full specialisation, in order to write a partial specialisation for a class, you must first declare the primary template. The partial specialisation contains an extra < > after the class name that contains the partial specialisation parameters; these define the types that will bind to that partial specialisation rather than the default template. The rules for what can appear in a partial specialisation are somewhat convoluted, but as a rule of thumb if you can legally write two function overloads of the form:
void foo(T); void foo(U);
Then you can also write a partial specialisation of the form:
template <typename T> class c{ /*details*/ }; template <typename T> class c<U>{ /*details*/ };
This rule is by no means foolproof, but it is reasonably simple to remember and close enough to the actual rule to be useful for everyday use.
As a more complex example of partial specialisation consider the class remove_bounds<T>. This class defines a single typedef-member type that is the same type as T but with any top-level array bounds removed; this is an example of a traits class that performs a transformation on a type:
template <typename T> struct remove_bounds { typedef T type; }; template <typename T, std::size_t N> struct remove_bounds<T[N]> { typedef T type; };
The aim of remove_bounds is this: imagine a generic algorithm
that is passed an array type as a template parameter, remove_bounds provides a means
of determining the underlying type of the array. For example remove_bounds<int[4][5]>::type
would evaluate to the type int[5]
. This example also
shows that the number of template parameters in a partial
specialisation does not have to match the number in the default
template. However, the number of parameters that appear after the
class name do have to match the number and type of the parameters
in the default template.
As an example of how the type traits classes can be used, consider the standard library algorithm copy:
template<typename Iter1, typename Iter2> Iter2 copy(Iter1 first, Iter1 last, Iter2 out);
Obviously, there's no problem writing a generic version of copy that works for all iterator types Iter1 and Iter2; however, there are some circumstances when the copy operation can best be performed by a call to memcpy. In order to implement copy in terms of memcpy all of the following conditions need to be met:
By trivial assignment operator we mean that the type is either a scalar type[3] or:
If all these conditions are met then a type can be copied
using memcpy rather than
using a compiler generated assignment operator. The type-traits
library provides a class has_trivial_assign, such that has_trivial_assign<T>::value
is true only if T has a trivial assignment operator. This class
"just works" for scalar types, but has to be explicitly
specialised for class/struct types that also happen to have a
trivial assignment operator. In other words if has_trivial_assign
gives the wrong answer, it will give the "safe" wrong
answer - that trivial assignment is not allowable.
The code for an optimised version of copy that uses memcpy where appropriate is given in listing 1. The code begins by defining a template class copier, that takes a single Boolean template parameter, and has a static template member function do_copy which performs the generic version of copy (in other words the "slow but safe version"). Following that there is a specialisation for copier<true>: again this defines a static template member function do_copy, but this version uses memcpy to perform an "optimised" copy.
In order to complete the implementation, what we need now is a
version of copy, that calls copier<true>::do_copy
if it is safe to use memcpy,
and otherwise calls copier<false>::do_copy
to
do a "generic" copy. This is what the version in
listing 1 does. To understand how the code works look at the code
for copy and consider
first the two typedefs v1_t and v2_t. These use std::iterator_traits<Iter1>::value_type
to determine what type the two iterators point to, and then feed
the result into another type-traits class remove_cv that
removes the top-level const-volatile-qualifiers: this will allow
copy to compare the two types without regard to const- or
volatile-qualifiers. Next, copy
declares an enumerated value can_opt that will become the
template parameter to copier - declaring this here as a constant
is really just a convenience - the value could be passed directly
to class copier. The
value of can_opt is computed by verifying that all of the
following are true:
Finally we can use the value of can_opt as the template argument to copier - this version of copy will now adapt to whatever parameters are passed to it, if its possible to use memcpy, then it will do so, otherwise it will use a generic copy.
It has often been repeated in these columns that "premature optimisation is the root of all evil" [4]. So the question must be asked: was our optimisation premature? To put this in perspective the timings for our version of copy compared a conventional generic copy[5] are shown in table 1.
Clearly the optimisation makes a difference in this case; but, to be fair, the timings are loaded to exclude cache miss effects - without this accurate comparison between algorithms becomes difficult. However, perhaps we can add a couple of caveats to the premature optimisation rule:
Version |
T |
Time |
"Optimised" copy | char | 0.99 |
Conventional copy | char | 8.07 |
"Optimised" copy | int | 2.52 |
Conventional copy | int | 8.02 |
The optimised copy example shows how type traits may be used to perform optimisation decisions at compile-time. Another important usage of type traits is to allow code to compile that otherwise would not do so unless excessive partial specialization is used. This is possible by delegating partial specialization to the type traits classes. Our example for this form of usage is a pair that can hold references [6].
First, let us examine the definition of "std::pair", omitting the comparision operators, default constructor, and template copy constructor for simplicity:
template <typename T1, typename T2> struct pair { typedef T1 first_type; typedef T2 second_type; T1 first; T2 second; pair(const T1 & nfirst, const T2 & nsecond) :first(nfirst), second(nsecond) { } };
Now, this "pair" cannot hold references as it currently stands, because the constructor would require taking a reference to a reference, which is currently illegal [7]. Let us consider what the constructor's parameters would have to be in order to allow "pair" to hold non-reference types, references, and constant references:
Type of "T1" | Type of parameter to initializing constructor |
T |
const T & |
T & |
T & |
const T & |
const T & |
A little familiarity with the type traits classes allows us to construct a single mapping that allows us to determine the type of parameter from the type of the contained class. The type traits classes provide a transformation "add_reference", which adds a reference to its type, unless it is already a reference.
Type of "T1" | Type of "const T1" | Type of "add_reference<const T1>::type" |
T |
const T |
const T & |
T & |
T & [8] |
T & |
const T & |
const T & |
const T & |
This allows us to build a primary template definition for "pair" that can contain non-reference types, reference types, and constant reference types:
template <typename T1, typename T2> struct pair { typedef T1 first_type; typedef T2 second_type; T1 first; T2 second; pair(boost::add_reference<const T1>::type nfirst, boost::add_reference<const T2>::type nsecond) :first(nfirst), second(nsecond) { } };
Add back in the standard comparision operators, default constructor, and template copy constructor (which are all the same), and you have a std::pair that can hold reference types!
This same extension could have been done using partial template specialization of "pair", but to specialize "pair" in this way would require three partial specializations, plus the primary template. Type traits allows us to define a single primary template that adjusts itself auto-magically to any of these partial specializations, instead of a brute-force partial specialization approach. Using type traits in this fashion allows programmers to delegate partial specialization to the type traits classes, resulting in code that is easier to maintain and easier to understand.
We hope that in this article we have been able to give you some idea of what type-traits are all about. A more complete listing of the available classes are in the boost documentation, along with further examples using type traits. Templates have enabled C++ uses to take the advantage of the code reuse that generic programming brings; hopefully this article has shown that generic programming does not have to sink to the lowest common denominator, and that templates can be optimal as well as generic.
The authors would like to thank Beman Dawes and Howard Hinnant for their helpful comments when preparing this article.
namespace detail{ template <bool b> struct copier { template<typename I1, typename I2> static I2 do_copy(I1 first, I1 last, I2 out); }; template <bool b> template<typename I1, typename I2> I2 copier<b>::do_copy(I1 first, I1 last, I2 out) { while(first != last) { *out = *first; ++out; ++first; } return out; } template <> struct copier<true> { template<typename I1, typename I2> static I2* do_copy(I1* first, I1* last, I2* out) { memcpy(out, first, (last-first)*sizeof(I2)); return out+(last-first); } }; } template<typename I1, typename I2> inline I2 copy(I1 first, I1 last, I2 out) { typedef typename boost::remove_cv< typename std::iterator_traits<I1> ::value_type>::type v1_t; typedef typename boost::remove_cv< typename std::iterator_traits<I2> ::value_type>::type v2_t; enum{ can_opt = boost::is_same<v1_t, v2_t>::value && boost::is_pointer<I1>::value && boost::is_pointer<I2>::value && boost:: has_trivial_assign<v1_t>::value }; return detail::copier<can_opt>:: do_copy(first, last, out); }
© Copyright John Maddock and Steve Cleary, 2000