17.6 Recursive Instantiation versus Recursive Template Arguments

Ru-Brd

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

Table 17.1. Growth of Trouble<N>::LongType

Typedef Name

Underlying Type

 Trouble<0>::LongType  Trouble<1>::LongType  Trouble<2>::LongType  Trouble<3>::LongType 
 double  Doublify<double,double>  Doublify<Doublify<double,double>,           Doublify<double,double> >  Doublify<Doublify<Doublify<double,double>,                    Doublify<double,double> >,           <Doublify<double,double>,                     Doublify<double,double> > > 

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.

Ru-Brd


C++ Templates
C++ Templates: The Complete Guide
ISBN: 0201734842
EAN: 2147483647
Year: 2002
Pages: 185

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net