- A First Example of a Metaprogram
- Enumeration Values versus Static Constants
- Second Example: Computing the Square Root
- Using Induction Variables
- Computational Completeness
- Recursive Instantiation versus Recursive Template Arguments
- Using Metaprograms to Unroll Loops
- Afternotes
This chapter is from the book
This chapter is from the book
This chapter is from the book
17.6 Recursive Instantiation versus Recursive Template Arguments
Consider the following recursive template:
template<typename T, typename U>
struct Doublify {};
template<int N>
struct Trouble {
typedef Doublify<typename Trouble<N-1>::LongType,
typename Trouble<N-1>::LongType,> LongType;
};
template<>
struct Trouble<0> {
typedef double LongType;
};
Trouble<10>::LongType ouch;
The use of Trouble<10>::LongType not only triggers the recursive instantiation of Trouble<9>, Trouble<8>, ..., Trouble<0>, but it also instantiates Doublify over increasingly complex types. Indeed, Table 17.1 illustrates how quickly it grows.
As can be seen from Table 17.1, the complexity of the type description of the expression Trouble<N>::LongType grows exponentially with N. In general, such a situation stresses a C++ compiler even more than recursive instantiations that do not involve recursive template arguments. One of the problems here is that a compiler keeps a representation of the mangled name for the type. This mangled name encodes the exact template specialization in some way, and early C++ implementations used an encoding that is roughly proportional to the length of the template-id. These compilers then used well over 10,000 characters for Trouble<10>::LongType.
Newer C++ implementations take into account the fact that nested template-ids are fairly common in modern C++ programs and use clever compression techniques to reduce considerably the growth in name encoding (for example, a few hundred characters for Trouble<10>::LongType). Still, all other things being equal, it is probably preferable to organize recursive instantiation in such a way that template arguments need not also be nested recursively.
Table 17.1. Growth of Trouble<N>::LongType
| Trouble<0>::LongType | double |
| Trouble<1>::LongType |
Doublify<double,double> |
| Trouble<2>::LongType |
Doublify<Doubleify<double,double>,
Doubleify<double,double> >
|
| Trouble<3>::LongType |
Doublify<Doubleify<Doubleify<double,double>,
Doubleify<double,double> >,
Doubleify<double,double>,
Doubleify<double,double> > >
|