An introduction to C++ template programming

1 .An introduction to C++ template programming Hayo Thielecke University of Birmingham http://www.cs.bham.ac.uk/~hxt March 2015 

2 .Templates and parametric polymorphism Template parameters Member functions of template classes Object oriented patterns Lambda expressions in C++11 Void pointer polymorphism in C Template specialization 

3 .C++ polymorphism Templates Dynamic polymorphism When compile-time run-time Typing Type parameters Subtyping Efficiency + no runtime overhead - indirection via pointers - potential code bloat at runtime Related to OCAML and Haskell polymorphism Objective C messages Java generics Java methods ML functors Over the last two decades, templates have developed from a relatively simple idea to the backbone of most advanced C programming. (Stroustrup 2012, section 25.1) 

4 .C++ templates templates are important: Standard Template Library type-safe collections templates interact/collide with other C++ features templates allow compile-time computation ⇒ zero overhead templates are a different language design dimension from object-orientation one way to use them is similar to polymorphism in functional languages In this module, we will build on your knowledge of functional programming 

5 .Templates and polymorphism There are two kinds of templates in C++: 1. Class templates 2. Function templates These correspond roughly to polymorphic data types and polymorphic functions in functional languages. 

6 .Polymorphism in functional languages # [1; 2; 3];; - : int list = [1; 2; 3] type ’a bt = Leaf of ’a | Internal of ’a bt * ’a bt ;; # let twice f x = f ( f x ) ;; val twice : ( ’ a -> ’a ) -> ’a -> ’a = <fun > 

7 .Templates: keyword template template < typename T > struct s { ... T ... T ... }; Then instantiating the template with argument A in s<A> is like struct sA { ... A ... A ... }; Compare: λ calculus. 

8 .Templates: type parameter template < typename T > struct S { // members here may depend on type parameter T T data ; // for example a data member void f ( T ) ; // or a member function using t = T ; // or making t an alias for T }; 

9 .Class template example template < typename T > struct Linked { T head ; Linked <T >* tail ; }; Class template - other keywords template < class T > class Linked { public : T head ; Linked <T >* tail ; }; 

10 .Telling a template what to do We can pass types to templates We may also configure its behaviour sometimes called “policy”, “callbacks”, etc like higher-order functions there are many ways of doing this in C++ classes with static member functions function pointers function objects, “functors” lambda expressions (new in C++11) 

11 .Function template example We pass a type T and a class Ops that provides two operations. template < typename T , typename Ops > T fold ( Linked <T > * p ) { T acc = Ops :: initial () ; while ( p ) { acc = Ops :: bin ( acc , p - > head ) ; p = p - > tail ; } return acc ; } Note: we pass the class, not an object. 

12 .Class as argument of a template This class provides integer operations: struct IntOps { static int initial () { return 0; }; static int bin ( int x , int y ) { return x + y ; } }; In essence, this class is just a pair of functions. 

13 .Using the templates on int lists int main ( int argc , const char * argv []) { auto sumup = fold < int , IntOps >; Linked < int > x {3 , nullptr }; Linked < int > y {2 , & x }; std :: cout << sumup (& y ) ; return 0; } 

14 .Another class: string operations This provides string operations: class StrOps { public : static std :: string initial () { return " " ; }; static std :: string bin ( std :: string x , std :: string y ) { return x + y ; } }; 

15 .Using the template on string lists int main ( int argc , const char * argv []) { Linked < std :: string > b = { " bar " , nullptr }; Linked < std :: string > a = { " foo " , & b }; auto sumupstr = fold < std :: string , StrOps >; std :: cout << sumupstr (& a ) << " \ n " ; return 0; } 

16 .Function pointer as template argument Here we pass a type T, a value of type T and a binary operation on T template < typename T , T init , T (* bin ) (T , T ) > T fold2 ( Linked <T > * p ) { T acc = init ; while ( p != nullptr ) { acc = bin ( acc , p - > data ) ; p = p - > next ; } return acc ; } 

17 .Function pointer as template argument: using it inline int sum ( int x , int y ) { return x + y ; } auto sumup2 = fold2 < int , 0 , sum >; 

18 .Member functions of template classes template < typename T > struct Linked { T data ; Linked <T >* next ; void apply_each ( void (* f ) ( T ) ) ; }; template < typename T > void Linked <T >:: apply_each ( void (* f ) ( T ) ) { T * p = data ; while ( p ) { f (p - > data ) ; p = p - > next ; } } 

19 .Functors/function objects in C++ A function object is an object that can be used like a function. One of its member functions overloads the function call syntax () Such an object can have its own data members. We can create function object dynamically, unlike C functions. In functional programming terms, function objects simulate closures. Function objects are often used with templates. Objects cannot be template parameters, only function parameters. 

20 .Function object example // class for curried addition function class cadd { private : int n ; public : cadd ( int n ) { this - > n = n ; } int operator () ( int m ) { return n + m ; } }; int main ( int argc , const char * argv []) { // make a new function object in local var cadd addfive (5) ; cout << addfive (7) ; } This prints 12. 

21 .Function objects and templates template < typename T , typename Op > T twice ( T x , Op f ) { return f ( f ( x ) ) ; } int main ( int argc , const char * argv []) { cadd addfive (5) ; // create function object cout << twice < int , cadd >(10 , addfive ) << endl ; cout << twice (10 , addfive ) << endl ; } This prints 20 twice. 

22 .Virtual member function templates? Suppose we want a worker that computes XML from a tree of ints. template < typename T > class polyworker { public : virtual T workplus (T , T ) ; virtual T workconstant ( int ) ; }; 

23 .Virtual member function templates? Suppose we want a worker that computes XML from a tree of ints. template < typename T > class polyworker { public : virtual T workplus (T , T ) ; virtual T workconstant ( int ) ; }; class Base { public : template < typename T > virtual T employ ( polyworker <T >*) = 0; // compilation error }; See our paper on A Type-theoretic Reconstruction of the Visitor Pattern 

24 .Visitor pattern The Visitor pattern is one of the classic patterns from the “Gang of Four” OO Patterns book Design patterns : elements of reusable object-oriented software Related patterns are Composite and Interpreter worker and employ are like visit visitor and accept in GoF GoF visitors use local state in the object rather than return types; they have void return types The GoF book is from 1995 There is a lot of emphasis on inheritance Since them, C++ has taken on more ideas from functional programming (e.g., lambda, auto) 

25 .Some object-oriented patterns Behavioural patterns are related Composite = object-oriented idiom to define trees Visitor = tree walker, internal vs external visitor stateful vs functional Interpreter, special case of Composite for a grammar of a language Iterator: internal visitors from lambda expression with reference 

26 .Visitor pattern as per Gang of Four 1 class gofvisitor { public : virtual void visitplus ( class plus *) = 0; virtual void visitconstant ( class constant *) = 0 ; }; class plus : public gofbase { class gofbase * p1 , * p2 ; public : plus ( gofbase * p1 , gofbase * p2 ) { this - > p1 = p1 ; this - > p2 = p2 ; } void accept ( gofvisitor * v ) { p1 - > accept ( v ) ; p2 - > accept ( v ) ; v - > visitplus ( this ) ; } 

27 .Visitor pattern as per Gang of Four 2 class plus : public gofbase { gofbase * p1 , * p2 ; public : plus ( gofbase * p1 , gofbase * p2 ) { this - > p1 = p1 ; this - > p2 = p2 ; } virtual void accept ( gofvisitor * v ) { p1 - > accept ( v ) ; p2 - > accept ( v ) ; v - > visitplus ( this ) ; } }; 

28 .Visitor pattern as per Gang of Four 3 Because the return type is void, the visitor must use internal state to accumulate its result: class countplusvisitor : public gofvisitor { int count ; public : void visitconstant ( class constant * p ) {} void visitplus ( class plus * p ) { count ++; } int getcount () { return count ; } countplusvisitor () { count = 0; } }; 

29 .Internal iterator and lambda expressions Now suppose we want to do some work only at the leaf nodes on the data, not the internal nodes that determine the shape of the data structure. We do not need a whole class. A function to be called on each leaf.