...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
The following is an updated version of the article "C++ Type traits" by John Maddock and Steve Cleary 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 minimize the amount of code that has to differ from one type to another, and maximize 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 realized 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 specializations 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 inherits from a the type true_type
if the type has the specified property and inherits from false_type
otherwise. As we will show, these classes can be used in generic programming
to determine the properties of a given type and introduce optimizations 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 flavor for how some of the classes
are implemented. Beginning with possibly the simplest class in the library,
is_void<T>
inherits
from true_type
only if T
is void
.
template <typename T> struct is_void : public false_type{}; template <> struct is_void<void> : public true_type{};
Here we define a primary version of the template class is_void
,
and provide a full-specialization when T
is void
. While full specialization
of a template class is an important technique, sometimes we need a solution
that is halfway between a fully generic solution, and a full specialization.
This is exactly the situation for which the standards committee defined partial
template-class specialization. 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 specialization to handle all the cases where T is
a pointer:
template <typename T> struct is_pointer : public false_type{}; template <typename T> struct is_pointer<T*> : public true_type{};
The syntax for partial specialization is somewhat arcane and could easily occupy an article in its own right; like full specialization, in order to write a partial specialization for a class, you must first declare the primary template. The partial specialization contains an extra <...> after the class name that contains the partial specialization parameters; these define the types that will bind to that partial specialization rather than the default template. The rules for what can appear in a partial specialization 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 specialization 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 specialization consider the class remove_extent<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_extent { typedef T type; }; template <typename T, std::size_t N> struct remove_extent<T[N]> { typedef T type; };
The aim of remove_extent
is this: imagine a generic algorithm that is passed an array type as a template
parameter, remove_extent
provides a means of determining the underlying type of the array. For example
remove_extent<int[4][5]>::type
would evaluate to the type int[5]
. This example also shows that the number of
template parameters in a partial specialization 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:
Iter1
and Iter2
must be pointers.
Iter1
and Iter2
must point to the same type - excluding
const and volatile-qualifiers.
Iter1
must have a trivial assignment operator.
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 optimized version of copy that uses memcpy
where appropriate is given in the
examples. The code begins by defining a template function do_copy
that performs a "slow but safe"
copy. The last parameter passed to this function may be either a true_type
or a false_type
.
Following that there is an overload of docopy that
uses `memcpy`: this time the iterators are required to actually be pointers
to the same type, and the final parameter must be a `_true_type. Finally, the version
of
copy calls
docopy`, passing `_has_trivial_assign<value_type>()`
as the final parameter: this will dispatch to the optimized version where appropriate,
otherwise it will call the "slow but safe version".
It has often been repeated in these columns that "premature optimization is the root of all evil" [4]. So the question must be asked: was our optimization 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 optimization 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 optimization rule:
Table 1.1. Time taken to copy 1000 elements using `copy<const T*, T*>` (times in micro-seconds)
Version |
T |
Time |
---|---|---|
"Optimized" copy |
char |
0.99 |
Conventional copy |
char |
8.07 |
"Optimized" copy |
int |
2.52 |
Conventional copy |
int |
8.02 |
The optimized copy example shows how type traits may be used to perform optimization 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 comparison 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:
Table 1.2. Required Constructor Argument Types
Type of |
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.
Table 1.3. Using add_reference to synthesize the correct constructor type
Type of |
Type of |
Type of |
---|---|---|
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 comparison 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.