|
The authors of the Boost library for type traits explains their value, especially in generic programming.
October 01, 2000
URL:http://drdobbs.com/cpp/c-type-traits/184404270
Generic programming -- that is, writing code that works with any data type meeting a set of requirements -- has become the method of choice for delivering reusable code. However, there are times in generic programming when generic just isn't good enough -- sometimes the differences between types are too great 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, you can minimize the amount of code that has to differ from one type to another, and maximize the amount of generic code.
For 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. The C library functions strlen and wcslen, for instance, 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 terms a "baggage class." In the Boost type-traits library, we 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 called value -- a compile-time constant that is true if the type has the specified property, and false otherwise. 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, this namespace qualification is omitted in most of the code samples presented here.
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 full details). However, most of the implementation is fairly repetitive anyway, so in this article we will give you a flavor 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; see Listing One. Here we have defined the primary version of the template class is_void, and provided a full specialization when T is void.
template <typename T>
struct is_void
{ static const bool value = false; };
template <>
struct is_void<void>
{ static const bool value = true; };
While full specialization of a template class is an important technique, you sometimes 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. To illustrate, 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; see Listing Two.
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 specialization is somewhat arcane and could easily occupy an article in its own right. Like full specialization, 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 primary 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_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; see Listing Three.
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 specialization does not have to match the number in the primary 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 primary template.
copyAs 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. 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 (that is, an arithmetic type, enumeration type, pointer, pointer to member, or const- or volatile-qualified version of one of these types) 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 specialized 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 Listing Four. 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 specialization for copier<true>. Again, this defines a static template member function do_copy, but this version uses memcpy to perform an optimized copy.
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);
}
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 Four 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- or volatile qualifiers: This will let copy 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:
is_same.
is_pointer previously described.
has_trivial_assign.
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 it's possible to use memcpy, then it will do so; otherwise it will use a generic copy.
According to Donald Knuth, "premature optimization is the root of all evil" (ACM Computing Surveys, December, 1974). So the question must be asked: Was our optimization premature? To put this in perspective, Table 1 lists the timings for our version of copy compared to a conventional generic copy. (The test code is available as part of the boost utility library; see algo_opt_ examples.cpp. The code was compiled with gcc 2.95 with all optimizations turned on.
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:
memcpy is the right algorithm.
The optimized copy example shows how type traits can be used to perform optimization decisions at compile time. Another important use of type traits is to allow code to compile that otherwise would not do so unless excessive partial specialization were 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. (John Maddock and Howard Hinnant have submitted a compressed_pair library to Boost, which uses a technique similar to the one described here to hold references. Their pair also uses type traits to determine if any of the types are empty, and will derive to conserve space instead of contain; hence the name "compressed.") First, we'll examine the definition of std::pair, omitting the comparison operators, default constructor, and template copy constructor for simplicity; see Listing Five.
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) { }
};
This pair cannot hold references as it currently stands, because the constructor would require taking a reference to a reference, which is currently illegal. (This is actually an issue with the C++ Core Language Working Group, issue #106, submitted by Bjarne Stroustrup. The tentative resolution is to allow a "reference to a reference to T" to mean the same thing as a "reference to T," but only in template instantiation, in a method similar to multiple cv-qualifiers.) Consider in Table 2 what the constructor's parameters would have to be to allow pair to hold nonreference types, references, and constant references.
A little familiarity with the type-traits classes lets you construct a single mapping that allows you to determine the type of parameter from the type of the contained class. The type-traits classes provide a transformation add_reference (Table 3), which adds a reference to its type, unless it is already a reference.
This lets you build a primary template definition for pair that can contain nonreference types, reference types, and constant reference types; see Listing Six.
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 let you define a single primary template that adjusts itself to any of these partial specializations, instead of a brute-force partial specialization approach. Using type traits in this fashion lets you delegate partial specialization to the type-traits classes, resulting in code that is easier to maintain and easier to understand.
Templates have enabled C++ users to take advantage of the code reuse that generic programming brings. However, generic programming does not have to sink to the lowest common denominator, and templates can be optimal as well as generic. Therein lies the value of type traits.
We would like to thank Beman Dawes and Howard Hinnant for their helpful comments when preparing this article.
John is an independent programmer in England with an interest in generic programming. Steve, who lives in Michigan, currently works on a variety of systems for Control Engineering Company. They can be contacted at john_maddock@compuserve .com and [email protected], respectively.
Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.