C++模板元编程

C++模板创造之初只是为了让c++程序员编程更简单,避免书写很多冗余代码,常常和c/c++中的宏做对比,但是在后续发展过程中,模板被证明是图灵完备的,也就是可以做一些元编程,让所谓的“程序”执行变成了由C++编译器来完成,让程序员可以很轻易写出各种DSL特性,交由编译器计算,最终生成非常高效可执行代码。本文对C++元编程按照例程进行表述,用非严谨的方式证明了模板元编程的图灵完备性,也是给了各种小技巧,让大家更容易学习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