Sept 98 Factory Floor
Volume Number: 14
Issue Number: 9
Column Tag: From The Factory Floor
The New C++ Standard:
Partial Template Specialization
by Howard Hinnant and Dave Mark, ©1998 by Metrowerks, Inc., all rights reserved.
In last month's column, we continued our exploration of the new C++ standard,
specifically taking a look at the subject of locales. In this month's column, Howard
Hinnant is back once again, and will take us through partial template specialization.
Howard Hinnant is a software engineer on the MSL team at Metrowerks, and is
responsible for the C++ and EC++ libraries. Howard is a refugee from the aerospace
industry where FORTRAN still rules. He has extensive experience in scientific
computing including C++ implementations of linear algebra, finite difference and
finite element solvers.
Dave: What exactly is partial template specialization?
Howard: In order to explain partial template specialization, it might first be easier
to describe full template specialization. Consider:
template
class vector
This works well for most items that we might want to keep a list of. However, if we
wanted to keep a vector, then an obvious optimization would be store each value
in one bit, instead of actually storing a list of bools. This could be neatly accomplished
by defining a specialization of our vector class:
template <>
class vector
This is known as template specialization.
Now consider a class template with two type parameters. I'll keep picking on vector:
template
And let's say we still want to optimize for when T == bool. We can do this by:
template
Since not all template parameters have been nailed down, this is known as partial
template specialization. So now when I say:
vector a;
I get the optimized implementation for bool.
Dave: Cool. Any other useful optimizations you could do?
Howard: You can do some really cool things with this concept. For example, let's say
you wanted to make a special vector for holding pointers. Here is a possibility:
template
class vector
This might come in handy if you wanted some special behavior for when the element
type was a pointer to something. For instance, one might want to treat vectors of
pointers as pointing to heap based objects, and manage those pointers with new and
delete. The standard library, of course, does not do this.
Dave: So how does partial template specialization affect the standard
library?
Howard: MSL does use partial template specialization to implement vector as
alluded to earlier. Additionally, there is a struct in that looks like:
template
struct iterator_traits
{
typedef typename Iterator::difference_type difference_type;
typedef typename Iterator::value_type value_type;
typedef typename Iterator::pointer pointer;
typedef typename Iterator::reference reference;
typedef typename Iterator::iterator_category iterator_category;
};
The purpose of this class is to help code that takes iterators find out valuable things
about the iterator that it's working on. For example, consider the standard algorithm
iter_swap that takes two iterators, and swaps the values that the iterators point to:
template
void
iter_swap(ForwardIterator1 a, ForwardIterator2 b)
iterator_traits::value_type Value;
Value tmp(*a);
*a = *b;
*b = tmp;
}
The routine iter_swap must create a temporary variable in order to accomplish the
swap. But what is the type of the temporary? It queries the iterator to find out the
proper type.
Thus all valid iterators (at least those that want to be used in standard algorithms and
containers) must create the typedefs referred to above so that they can be queried via
iterator_traits. This can be easily accomplished by deriving your custom iterators
from the standard iterator struct:
In :
template
class Pointer = T*, class Reference = T&>
struct iterator
{
typedef Distance difference_type;
typedef T value_type;
typedef Pointer pointer;
typedef Reference reference;
typedef Category iterator_category;
};
In your code:
class MyIterator
: public std::iterator
Dave: I see. But if I remember right, an iterator is just a generalization of a built-in
pointer. In fact, built-in pointers can be used in all the standard algorithms. So how
does iter_swap query a built-in pointer for its value_type? You can't derive int*
from std::iterator.
Howard: Ahh... Exactly! This is where partial template specialization rides in to save
the day. The standard library defines a specialization of iterator_traits for a pointer to
anything:
template
struct iterator_traits
{
typedef ptrdiff_t difference_type;
typedef T value_type;
typedef T* pointer;
typedef T& reference;
typedef random_access_iterator_tag iterator_category;
};
So now when iter_swap tries to define Value:
typedef typename iterator_traits::value_type Value;
And ForwardIterator1 has the type int*, iterator_traits picks up the partial
specialization and answers back with int. This is really a pretty slick design.
Dave: That is neat. But partial template specialization is a relatively
new feature of CodeWarrior. How did MSL handle this problem before
this feature was available?
Howard: Oh, yes... The Dark Time. We took advantage of the fact that we did have full
template specialization available to us. So we created full specializations for
iterator_traits for every type we could think of: char*, int*, bool*, short*, long* ...
plus all combinations of unsigned and const modifiers. This worked pretty well except
for one minor little detail. We could not create a specialization for myType*. Here
myType represents all of the classes which the customer created.
In order to combat this last problem, we (actually Dennis C. De Mars) created a macro
which defined a full specialization of iterator_traits for its argument myType:
#define __MSL_FIX_ITERATORS__(myType)
template<>
struct std::iterator_traits {
typedef ptrdiff_t difference_type;
typedef myType value_type;
typedef myType* pointer;
typedef myType& reference;
typedef random_access_iterator_tag iterator_category;
};
Yes, everyone knows about __MSL_FIX_ITERATORS__. And you now know the full
story behind this macro. It is a macro that no one liked, but we could not live without
it.
Even if you didn't use the standard algorithms, you got bit by this when you used the
standard containers, because they used it. We had plans to reduce MSL's dependence on
iterator_traits, but Andreas (our C++ compiler guru) came out with partial
specialization before we could implement those plans. This was really best as we could
have only reduced the dependence, not eliminated it.