Lesson of 17 July 2008

Examples of template metaprograms

Example of class specialization

File spec1.cc

:open:
 1/*
 2  Example of class specialization
 3*/
 4
 5#include <iostream>
 6#include <fstream>
 7#include <cmath>
 8
 9/*
10  Define the class vec parametrized with integer N.
11 */
12template <int N>
13class vec {
14  double vals[N] ;
15public:
16  vec()
17  { std::fill( vals, vals + N, 0 ) ; }
18  
19  vec<N> const & operator = ( vec<N> const & v ) {
20    std::copy( v.vals, v.vals + N, vals ) ;
21  }
22  
23  // many other operators may be defined
24
25  double const & operator [] ( int i ) const { return vals[i] ; }
26  double       & operator [] ( int i )       { return vals[i] ; }
27  
28} ;
29
30/*
31  Define external operator + for the class vec parametrized with integer N.
32 */
33template <int N>
34vec<N>
35operator + ( vec<N> const & a, vec<N> const & b ) {
36  vec<N> res ;
37  for ( int i = 0 ; i < N ; ++i )
38    res[i] = a[i] + b[i] ;
39  return res ;
40}
41
42/*
43  Define external operator << for the class vec parametrized with integer N.
44 */
45template <int N>
46std::ostream &
47operator << ( std::ostream & s, vec<N> const & a ) {
48  s << "[ " ;
49  for ( int i = 0 ; i < N ; ++i )
50    s << a[i] << " " ;
51  s << "]" ;
52  return s ;
53}
54
55/*
56  driver program to test specialization
57 */
58int
59main() {
60  vec<5>  a5 ;
61  vec<10> a10 ;
62
63  a5[3] = 1 ;
64  a5[2] = 12 ;
65  a5[1] = 3 ;
66  std::cout << a5 << "\n" ;
67
68  a10[3] = 1 ;
69  a10[2] = 12 ;
70  a10[1] = 3 ;
71  std::cout << a10 << "\n" ;
72
73  return 0 ;
74}

Another example of class specialization

File spec2.cc

:open:
 1/*
 2  Example of class specialization
 3*/
 4
 5#include <iostream>
 6#include <fstream>
 7#include <cmath>
 8
 9/*
10  Define the class vec parametrized with integer N and type T.
11 */
12template <typename T, int N>
13class vec {
14public:
15  // define the type valueType as an alias of type T.
16  // this will be accessible in this way
17  // VEC::valueType
18  // if VEC is an alias of vec<T,N>
19  typedef T valueType ;
20private:
21  T vals[N] ;
22public:
23  vec()
24  { std::fill( vals, vals + N, 0 ) ; }
25  
26  vec<T,N> const & operator = ( vec<T,N> const & v ) {
27    std::copy( v.vals, v.vals + N, vals ) ;
28  }
29  
30  // many other operators may be defined
31
32  T const & operator [] ( int i ) const { return vals[i] ; }
33  T       & operator [] ( int i )       { return vals[i] ; }
34  
35} ;
36
37/*
38  Define external operator + for the class vec parametrized with integer N and type T.
39 */
40template <typename T, int N>
41vec<T,N>
42operator + ( vec<T,N> const & a, vec<T,N> const & b ) {
43  vec<T,N> res ;
44  for ( int i = 0 ; i < N ; ++i )
45    res[i] = a[i] + b[i] ;
46  return res ;
47}
48
49/*
50  Define external function "dot" for the class vec parametrized with integer N and type T.
51 */
52template <typename T, int N>
53vec<T,N>
54dot( vec<T,N> const & a, vec<T,N> const & b ) {
55  typename vec<T,N>::valueType res ;
56  res = 0 ;
57  for ( int i = 0 ; i < N ; ++i )
58    res += a[i] + b[i] ;
59  return res ;
60}
61
62/*
63  Define external operator << for the class vec parametrized with integer N and type T.
64 */
65template <typename T, int N>
66std::ostream &
67operator << ( std::ostream & s, vec<T,N> const & a ) {
68  s << "[ " ;
69  for ( int i = 0 ; i < N ; ++i )
70    s << a[i] << " " ;
71  s << "]" ;
72  return s ;
73}
74
75int
76main() {
77  vec<double,5>  a5 ;
78  vec<float,10> a10 ;
79  
80  vec<double,5>::valueType scalar ; // scalar is of type double!.
81
82  a5[3] = 1.2 ;
83  a5[2] = 12 ;
84  a5[1] = 3 ;
85  std::cout << a5 << "\n" ;
86
87  a10[3] = 1.2 ;
88  a10[2] = 12 ;
89  a10[1] = 3 ;
90  std::cout << a10 << "\n" ;
91
92  return 0 ;
93}

Example of PARTIAL class specialization

File partial.cc

:open:
  1/*
  2  Example of PARTIAL class specialization
  3*/
  4
  5#include <iostream>
  6#include <fstream>
  7#include <cmath>
  8
  9/*
 10  Define the class vec parametrized with integer N and type T.
 11 */
 12template <typename T, int N>
 13class vec {
 14public:
 15  typedef T valueType ;
 16private:
 17  T vals[N] ;
 18public:
 19  vec()
 20  { std::fill( vals, vals + N, 0 ) ; }
 21  
 22  vec<T,N> const & operator = ( vec<T,N> const & v ) {
 23    std::copy( v.vals, v.vals + N, vals ) ;
 24    return *this ;
 25  }
 26  
 27  // many other operators may be defined
 28
 29  T const & operator [] ( int i ) const { return vals[i] ; }
 30  T       & operator [] ( int i )       { return vals[i] ; }
 31  
 32} ;
 33
 34/*
 35  Define external operator + for the class vec parametrized with integer N and type T.
 36 */
 37template <typename T, int N>
 38vec<T,N>
 39operator + ( vec<T,N> const & a, vec<T,N> const & b ) {
 40  std::cout << "using operator +\n" ;
 41  vec<T,N> res ;
 42  for ( int i = 0 ; i < N ; ++i )
 43    res[i] = a[i] + b[i] ;
 44  return res ;
 45}
 46
 47// add a partial specialization of operator + 
 48// for improving performance
 49template <typename T>
 50vec<T,2>
 51operator + ( vec<T,2> const & a, vec<T,2> const & b ) {
 52  std::cout << "using operator + specialized for N=2\n" ;
 53  vec<T,2> res ;
 54  res[0] = a[0] + b[0] ;
 55  res[1] = a[1] + b[1] ;
 56  return res ;
 57}
 58
 59// add a partial specialization of operator + 
 60// for improving performance
 61template <typename T>
 62vec<T,3>
 63operator + ( vec<T,3> const & a, vec<T,3> const & b ) {
 64  std::cout << "using operator + specialized for N=3\n" ;
 65  vec<T,3> res ;
 66  res[0] = a[0] + b[0] ;
 67  res[1] = a[1] + b[1] ;
 68  return res ;
 69}
 70
 71/*
 72  Define external function "dot" for the class vec parametrized with integer N and type T.
 73 */
 74template <typename T, int N>
 75vec<T,N>
 76dot( vec<T,N> const & a, vec<T,N> const & b ) {
 77  typename vec<T,N>::valueType res ;
 78  res = 0 ;
 79  for ( int i = 0 ; i < N ; ++i )
 80    res += a[i] + b[i] ;
 81  return res ;
 82}
 83
 84/*
 85  Define external operator << for the class vec parametrized with integer N and type T.
 86 */
 87template <typename T, int N>
 88std::ostream &
 89operator << ( std::ostream & s, vec<T,N> const & a ) {
 90  s << "[ " ;
 91  for ( int i = 0 ; i < N ; ++i )
 92    s << a[i] << " " ;
 93  s << "]" ;
 94  return s ;
 95}
 96
 97int
 98main() {
 99  vec<double,2> a2, b2 ;
100  vec<double,3> a3, b3 ;
101  vec<double,4> a4, b4 ;
102
103  a2 = a2 + b2 ; 
104  a3 = a3 + b3 ;
105  a4 = a4 + b4 ;
106
107  return 0 ;
108}

Use of a class as a function, example with midpoint rule

File midpoint.cc

:open:
 1/*
 2  Example of class used as function
 3*/
 4
 5#include <iostream>
 6#include <fstream>
 7#include <cmath>
 8
 9#include <algorithm>
10
11/* 
12  define the class stupid
13  with the operator () defined and used as a function
14*/
15
16class stupid {
17  double a ;
18public:
19  stupid( double _a ) : a(_a) {} 
20
21  void setup( double x ) { a = x ; }
22  
23  double 
24  operator () ( double x ) const
25  { return sin(a*x) ; }
26} ;
27
28/*
29  non template version:
30  double
31  midpoint( double  const a,
32            double  const b,
33            int const N,
34            double (FUN*)(double) ) {
35  }
36  
37  the function midpoint implement the numerical integration rule
38  by midpoint formula.
39  
40*/
41
42template <typename T>
43T
44midpoint( T   const a,
45          T   const b,
46          int const N,
47          T (*FUN)(T) ) {
48  T res = 0 ;
49  T h   = (b-a)/N ;
50  for ( int i = 1 ; i < N ; ++i )
51    res += FUN( a + h * (i-0.5) ) ;
52  return res * h ;
53}
54
55/*
56  This version of midpoint integration rule is paramtetrized also 
57  with the function argument.
58  In this way FUN can be any thing that understand operator ()
59  i.e. a function or an object with deefined the operator ()!.
60*/
61
62template <typename T, typename FTYPE>
63T
64midpoint2( T     const a,
65           T     const b,
66           int   const N,
67           FTYPE FUN ) {
68  T res = 0 ;
69  T h   = (b-a)/N ;
70  for ( int i = 1 ; i < N ; ++i )
71    res += FUN( a + h * (i-0.5) ) ;
72  return res * h ;
73}
74
75/*
76  a simple function for test
77*/
78inline
79double
80fun( double a ) 
81{ return a*a ; }
82
83int
84main() {
85  stupid like_a_function(2) ;
86  
87  std::cout << like_a_function(1.23) << "\n" ;
88  
89  double res = midpoint2<double>( 0, 2*M_PI, 1000, like_a_function ) ;
90  std::cout << "integral = " << res << "\n" ;
91
92  res = midpoint2<double>( 0, 2*M_PI, 1000, fun ) ;
93  std::cout << "integral = " << res << "\n" ;
94
95  return 0 ;
96}

Example of very simple template metaprogram

File factorial.cc

:open:
 1/*
 2  Example of very simple template metaprogram
 3*/
 4
 5#include <iostream>
 6#include <fstream>
 7#include <cmath>
 8
 9/*
10  Define the class factorial.
11  This class is empty and has a static integer value.
12  Static variables are "common" to all the instance of the 
13  classes.
14 */
15template <int N>
16class factorial {
17public:
18  /*
19    Define the static value with the following recurrence.
20    In this way compiler must instance classes 
21    
22    factorial<N-1>
23    factorial<N-2>
24    ....
25  */
26  static int const value = N*factorial<N-1>::value ;
27  /* old compiler must use this trick insted of static int const value:
28  enum { value = N*factorial<N-1>::value } ;
29  */
30} ;
31
32/*
33  Define the s[ecialization of class factorial for N=0.
34  This close the recursion when a class factorial<N> is instanced.
35 */
36template <>
37class factorial<0> {
38public:
39  static int const value = 1 ;
40  /* old compiler must use this trick insted of static int const value:
41  enum { value = 1 } ;
42  */
43} ;
44
45
46int
47main() {
48  std::cout << "1!  = " << factorial<1>::value  << "\n" ;
49  std::cout << "2!  = " << factorial<2>::value  << "\n" ;
50  std::cout << "5!  = " << factorial<5>::value  << "\n" ;
51  std::cout << "10! = " << factorial<10>::value << "\n" ;
52  return 0 ;
53}

Bubble sort with template metaprogram

File bubble.cc

:open:
  1/*
  2  Example of compile time ordering
  3*/
  4
  5#include <iostream>
  6#include <fstream>
  7#include <cmath>
  8
  9#include <algorithm>
 10
 11// standard bubble sort
 12void
 13bubbleSort( int data[], int N ) {
 14  for ( int i = N-1 ; i > 0 ; --i )
 15    for ( int j = 0 ; j < i ; ++j )
 16      if ( data[j] > data[i] )
 17        std::swap( data[i], data[j] ) ;
 18}
 19
 20// recursive ordering of a vector
 21void
 22recursiveSort( int data[], int N ) {
 23  // loop on the vector and put maximum at the end of the vector
 24  for ( int j = 0 ; j < N-1 ; ++j )
 25    if ( data[j] > data[j+1] )
 26      std::swap( data[j], data[j++] ) ;
 27  // at the end of this loop
 28  // data[N-1] is the maximum of the vector
 29  // if N > 2 reapply the algorithm to the vector vec[0..N-2]
 30  if ( N > 2 ) recursiveSort( data, N-1 ) ;
 31}
 32
 33// recursive ordering of a vector using template metaprogram
 34
 35
 36/*
 37  This class implement method compareAndSwap which 
 38  compare data[I] and data[J] and if necessary swap it.
 39 */
 40template <int I, int J>
 41class Swap {
 42public:
 43  static inline void
 44  compareAndSwap( int data[] ) {
 45    if ( data[I] > data[J] ) std::swap( data[I], data[J] ) ;
 46  }
 47} ;
 48
 49/*
 50  this class implement method loop which 
 51  recursively get the maximum of the vector data[0..N-1]
 52  and put in data[N-1]
 53 */
 54template <int N>
 55class MaxLoop {
 56public:
 57  static inline void
 58  loop( int data[] ) {
 59    MaxLoop<N-1>::loop(data) ;
 60    Swap<N-2,N-1>::compareAndSwap(data) ;
 61  }
 62} ;
 63
 64/*
 65  if the length of the vector is 1 nothing to do
 66 */
 67template <>
 68class MaxLoop<1> {
 69public:
 70  static inline void
 71  loop( int data[] ) {}
 72} ;
 73
 74/*
 75  Sort the vector 
 76 */
 77template <int N>
 78class Sort {
 79public:
 80  static inline void
 81  doSort( int data[] ) {
 82    MaxLoop<N>::loop(data) ;
 83    Sort<N-1>::doSort(data) ;
 84  }
 85} ;
 86
 87/*
 88  if the length of the vector is 1 nothing to do
 89 */
 90template <>
 91class Sort<1> {
 92public:
 93  static inline void
 94  doSort( int data[] ) {}
 95} ;
 96
 97/*
 98   Check the ordering
 99 */
100
101int
102main() {
103
104  {
105    int data[]  = { 4, 3, -1, 2, 3, -2, 1, 4 } ;
106    int const N = sizeof(data)/sizeof(data[0]) ;  
107    bubbleSort( data, N ) ;
108    for ( int i = 0 ; i < N ; ++i )
109      std::cout << data[i] << ", " ;
110    std::cout << "\n" ;
111  }
112
113  {
114    int data[]  = { 4, 3, -1, 2, 3, -2, 1, 4 } ;
115    int const N = sizeof(data)/sizeof(data[0]) ;  
116    recursiveSort( data, N) ;
117    for ( int i = 0 ; i < N ; ++i )
118      std::cout << data[i] << ", " ;
119    std::cout << "\n" ;
120  }
121
122  {
123    int data[]  = { 4, 3, -1, 2, 3, -2, 1, 4 } ;
124    int const N = sizeof(data)/sizeof(data[0]) ;  
125    Sort<N>::doSort( data ) ;
126    for ( int i = 0 ; i < N ; ++i )
127      std::cout << data[i] << ", " ;
128    std::cout << "\n" ;
129  }
130  
131  return 0 ;
132}

The lesson in a zip file

The zip file lesson8.zip