C++模板元编程

1 .Template Metaprogramming in C++ Giuseppe Attardi and Haoyuan Li Dipartimento di Informatica Università di Pisa Università di Pisa

2 .Generic versus Generative Generic programming focuses on representing families of domain concepts ( parameterization ) Generative programming also includes the process of creating concrete instances of concepts ( metaprogramming ) In generative programming, the principles of generic programming are applied to the solution space

3 .Metaprogramming Automating the production of individually configured systems Building adaptive systems that need to be able to dynamically adjust themselves to a changing environment Writing programs that represent and manipulate other programs or themselves (reflection)

4 .Types of System Configuration Static Dynamic Static Dynamic Selection of configuration Creation of Components and Configurations

5 .Metaprograms Compile time Post-runtime Information for static analysis only Linking Loading Runtime Complete execution history Metaprograms Analysis Generation

6 .C++ Support for Configuration Dynamic Configuration Dynamic polymorphism (virtual methods) Static Configuration Static typing Static binding Inlining Templates Parameterized inheritance typedef Member types and nested classes

7 .C++ as a Two-Level Language Normal code is compiled and executed at runtime Meta code is evaluated at compile time C++ templates together with other C++ features constitute a Turing-complete compile-time language! Iteration – template recursion Conditional – template specialization

8 .Example of C++ Static Code template < int i> struct C { enum { RET = i }; }; cout << C<2>::RET << endl ; // Output 2 int n = 2; cout << C<n>::RET << endl ; // ??? Template parameter is a value, not a type, aka dependent type. Not possible with Java or C# generics.

9 .C++ enum example s truct Test { enum {a = 7, b, c}; void print() { cout << b; } }; Test(t); t .print ();

10 .Recursive Factorial int factorial( int n) { return (n == 0) ? 1 : n * factorial(n – 1); } cout << factorial(7) << endl ; // 5040

11 .Template Factorial template< int n> struct Fact { enum { RET = n * Fact<n-1> ::RET }; }; template<> struct Fact<0> { enum { RET = 1 }; }; cout << Fact<7>::RET << endl ; // 5040 int i = 3; Fact< i >::RET; // ???

12 .Dynamic Fibonacci Number int fibo (long long int n) { if (n == 0) return 0; if (n == 1) return 1; return fibo (n - 1) + fibo (n - 2); } cout << fibo (45) << endl ; // 1134903170 // 31.890s with Intel Core 2 Duo 2.4GHz CPU!

13 .Template Fibonacci template<long n> struct Fib { static const long RET = Fib<n-1> ::RET + Fib<n-2> ::RET; }; template<> struct Fib<0> { static const long RET = 0; }; template<> struct Fib<1> { static const long RET = 1; };

14 .Efficiency of Static Code long x = Fib<45>::RET; cout << x << endl ; // 1134903170 // runtime 0.006s // compile time 0.314s long x = Fib<500>::RET; // !!!!! cout << x << endl ; // 2171430676560690477 // runtime 0.005s // compile time 0.373s

15 .Why? There is no double-recursion in generated code! Compiler sees Fib<7>::RET and instantiates the template Fib<> for n=7 Which requires Fib<6>::RET and Fib<5>::RET All the way to Fib<0> Since instantiations are cached, Fib<6> is only computed once and similarly for others We can regard Fib<> as a function, which is evaluated at compile time Generated code only does “ << ”!

16 .Functional Flavor of Static Level Class templates as functions Integers and types as data Symbolic names instead of variables Constant initialization and typedef instead of assignment Template recursion instead of loops Conditional operator and template specialization as conditional construct

17 .Template Metaprogramming Map Metainformation Metafunctions Member Traits Traits Classes Traits Templates Lists and Trees as Nested Templates Computing Numbers Fibonacci<> Control Structures Computing Types IF<>,SWITCH<>, WHILE<>,DO<>,FOR<> Computing Code EWHILE<>,EDO<>, EFOR<> Expression Templates

18 .Member Traits struct Car { enum Brand { alfaromeo , fiat, peugeot }; }; struct AlfaRomeo : Car { enum { brand = alfaromeo }; }; struct Fiat: Car { enum { brand = fiat }; }; struct Peugeot: Car { enum { brand = peugeot }; }; myCar.brand == myCar :: peugeot ; // compile type test

19 .Traits Templates template<class T> class car_traits { public: enum Made { Italy, France}; enum Fuel { Diesel, Petrol}; static const Made made = Italy; static const Fuel fuel = Petrol; static const bool trans = 0; static const short gearbox = 0; static const short doors = 0; static const float volume = 0.0; };

20 .Traits Templates: Specialization template<> class car_traits < Peugeot > { public: enum Made { Italy, France}; enum Fuel { Diesel, Petrol}; static const Made made = France; static const Fuel fuel = Petrol; static const short doors = 0; static const short speeds = 0; static const float volume = 0.0; };

21 .Traits Templates: Extension class DieselCar { public: enum Fuel { Diesel, Petrol }; static const Fuel fuel = Diesel; }; template<> class car_traits < MyCar >: public DieselCar { static const short doors = 5; static const short speeds = 5; static const float volume = 1.9; };

22 .IF<> with Partial Specialization template< bool condition, class Then, class Else> struct IF { typedef Then RET; }; template<class Then, class Else> struct IF<false, Then, Else> { typedef Else RET; }; IF<(1+2>4), short, int >::RET i ; // i is int

23 .Use of Meta IF class DieselEngine : Engine { public: void assemble() { … } }; class PetrolEngine : Engine { public: void assemble() { … } }; IF<Car::Engine == Car::DIESEL, DieselEngine , PetrolEngine >::RET engine; engine.assemble (); // compile time, not late, binding

24 .Other Operators struct FALSE {}; struct TRUE {}; template <class T> struct isPointer { typedef FALSE RET ; }; template <class T> struct isPointer <T*> { typedef TRUE RET ; };

25 .Conditional template<int n1, int n2> struct Max { enum { RET = (n1 > n2) ? n1 : n2 }; }

26 .Template Metafunctions C(k, n) = n! / (k! * (n-k)!) template<int k, int n> struct Comb { enum { RET = Fact<n>::RET / (Fact<k>::RET * Fact<n-k>::RET) }; }; cout << Comb<2, 4>::RET << endl;

27 .Prime Numbers template < int p, int i > struct is_prime { enum { prim = (p % i && is_prime <p , i - 1>:: prim) }; }; template < int p > Struct is_prime <p , 1> { public: enum { prim = 1 }; };

28 .Metaprogramming constructs Conditionals with partial template specialization Loops with recursive template definitions Returns using typedefs

29 .C++11 Type T raits Primary Type Categories i s_array , is_void , is_pointer , etc. Composite Type Categories is_scalar , is_object , is_reference , etc. Type Properties Is_const , is_empty , is_signed , etc. Type Relationships i s_same , is_base_of , is_convertible Logic functions conditional