S1: Templates: Type-Parametric Data Abstraction
Copyright: S. Shekhar, C. S. Dept., University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S2: Templates and Type Parameters
  • Purpose of Templates
    • Passing class names (e.g. int, string) to a function/class
    • Analogy: passing value parameters (e.g. 1.5) to functions
      • Why not pass types ?
    • Syntax of Templates
      template < class Id1, class Id2, ... > declaration
    • declaration ::= a function declaration or a class declaration
    • scope of Id1, Id2, ... = body of the unit (function/class)
  • Example Template Declaration
    template < class aType >
    aType larger (aType a, aType b)
    {if (a > b) return a; else return b;}
    SpaceN%1.5
    Q? Is it declaring a template function or a template class?
    Q? Identify type parameters, body and other components.
Copyright: S. Shekhar, C. S. Dept., University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S3: Function Templates: Why Type Parameters?
  • Comparison with Alternatives :
    • (1) Overloaded functions = > lot of code
      int max(int a, int b) {return (a > b) ? a : b;};
      char max(char a, char b){return (a > b) ? a : b;};
      float max(float a, float b){ return (a > b) ? a : b; };
      cout << max(2, 3) << max(1.2, 0.2) << max('a', 'A');
    • (2) Macro = > no type checks, hard to debug
      #define max(a, b) \
      ( ((x) > (y)) ? (x) : (y) ) ## complex syntax
    • (3) A function template: Definition and Usage
    • One skeleton functions, full type checking
    • Using function templates = > No new syntax
    • Compiler generates actual (template) functions
      template < class T >
      T max (T a, T b) {return (a > b) ? a : b;}
      cout << max(2, 3) << max(1.2, 0.2) << max('a', 'A');
  • Template = a clever macro that obeys
    • the scope, naming and type rules of C++
Copyright: S. Shekhar, C. S. Dept., University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S4: How to define a function template in C++
  • Template definition Syntax has the following components
    • keyword template
    • A left angle bracket ( < )
    • A list of parametric types,e.g. class T, class U, class V
      • each type (T, U, V) must be used in function header
      • No fixed type may used, e.g. class T, int size //error
    • A right angular bracket ( > )
    • function definition, i.e. header, body, etc.
  • Usage syntax same as usual function call
  • Ex. What is wrong with following template declarations?
    < class Tree > Tree function1(Tree argTree) { }
    template < S > S function2(Tree argTree) { }
    template < class A > A function3() { }
    template < class T, class T > Tree function4(T arg){ }
    template < class B, class C > void function5(B arg) { }
    template < class T, U > void function6(T arg1, U arg2) { }
Copyright: S. Shekhar, C. S. Dept., University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S5: Restrictions on Function Templates in C++
  • (i) Actual type-parameter must have relevant operators
    • Q? What will cout << max("ab", "cd") output?
    • Undefined, since it will compare pointers
  • (ii)Specialized instance function may be needed
    • e.g. char* - neither has nor can have ' > ' operator
      char* max(char * a, char * b){ return strcmp(a, b) ? a : b;};
    • Name conflict resolution: template max vs. function max
      • (1) find an exact match on functions
      • (2) find a template which can generate an exact match function
      • (3) try ordinary overloading resolution for the functions
    • (iii) No implicit type conversions available in 1995
      max (4, 5.1); // error: Could not find a match for 'max(int, double)'
      template < class T > void f(T, const int) {}
      ... int x =1; f(1,x); //error: Could not find a match for 'f(int, int)'
    • (iii) Default function arguments are error-prone!
      template < class T > void ff(T x, T y = 0)
      {cout << "x = " << x << " y = " << y << endl; }
      int main() { f(1.2); } // outputs x = 1.2 y = 1.113 e-316
Copyright: S. Shekhar, C. S. Dept., University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S6: Class Templates : Motivation
  • Motivation: avoid code duplication across related classes
    • Ex.- stack of integers, stack of students, ...
      • Element type differ, but operations are identical
    • Implementation Choices:
      • (a) Implement each class independently
      • (b) Class template (to generate type-specific class instances)
    • Q? List the following in the program: objects, class templates
    • classes and their data members and member functions
      template < class elmntType, int max_size = 100 >
      class stack {
      public: stack();
      int push(elmntType x);
      int pop(elmntType& x);
      int is_empty();
      private: int top; elmntType data[max_size];
      }
      typedef stack < int > stack_of_ints; typedef stack < char > char_stack;
      stack < tree > STrees(26);
      stack_of_ints intStk(120); char_stack palindrome(20);
Copyright: S. Shekhar, C. S. Dept., University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S7: Class Template Definition
  • Definition Syntax = template < parameter-list > class-definition
    • parameter-list is non-empty and
      • has multiple parameters separated by commas
    • Each parameter is a class/type or an EXPRESSION
    • class definition has data members and member functions
      template < class T > class one {
      { public: one(T initValue);
      void display();
      private: T value; Boolean initialized;
      };
  • template class instantiation
    • Syntax: template-name < actual parameters >
    • Either use typedef to create new classes
    • Or use directly in object/variable declarations.
      int main() {
      typedef One < int > aclass;
      aclass anInteger(-999); anInteger.display();
      one < string > aString("abc"); aString.display();
      }
Copyright: S. Shekhar, C. S. Dept., University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S8: More on Definition of Class Templates
  • Name of parametrized class includes list of type parameters
    • e.g. one < T > , rather than 'one'
  • Member functions Syntax : same as function templates
    template < class T >
    one(T initValue) { value = initValue; }
  • Can be defined inside or outside class body
    • Inside body = > scope resolution not needed
    • Outside body = > need scope resolution
      template < class T >
      one < T > :: one(T initValue)
      { value = initValue ; initialized = TRUE; }
      template < class T >
      one < T > :: display() { cout << value << endl ; }
Copyright: S. Shekhar, C. S. Dept., University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S9: Specialization of Class Templates
  • A class template MAY NOT work well with all parameter values.
    • Q? What operators must be defined on elmntType?
      PQueue < class elmntType > :: min()
      { int z, i; z = 0;
      for (i=1; i < size ; i++)
      if collection[i] < collection[z] z = i;
      return collection[z];
      }
  • Specialization: customize for a given types
    template < class T >
    class test { T data;
    public: test();
    test(const test < T > & t) : data(t.data) {} // see note
    }
    • test(char*) t("ab");= > copies pointer, not string
    • Specialized constructors for character strings
      test < T > :: test() : data(0) {}
      test < char* > ::test() : data(new char[1]) { data[0] = '\0';}
Copyright: S. Shekhar, C. S. Dept., University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S10: Restrictions and Common Errors
  • General form of templates are fairly complex
    • Hard to understand error messages
    • Beginners should stick with simple form
    • Have someone review your template definition
  • Strict rules for legal parameters
    • Types, Constants or Constant Expressions, Functions
    • Nothing else!
  • No implicit type conversion for 1995!
    template < class T > int search( T target, int size, const T items [])
    linear-search( int, 26, s_id_list ); // may not match last parameter
  • Each actual parameter must evaluate at compile-time
    template < int *p > class BufPtr { /*...*/ }; //error!
  • Global templates only.
    • No template definitions inside another class or function!
    • Limited overloading
    • Can not have two templates with same name in a program!
Copyright: S. Shekhar, C. S. Dept., University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S11: Class Templates and Collection classes
  • Collection classes
    • e.g. stack of floats, stack of students, ...
    • Element type differ, but operations are identical
    • Recall DataType was not specified in implementations (Ch#5)
    • Datatype = int = > stack of integers
    • Datatype = student = > stack of students
  • Implementation via Templates
    • Allows generalization of existing classes
    • DataType can be made a type parameter!
    • Avoid code duplication across stack of integer and stack of floats
    • Compare class stack (pp 191-3) and
      • template class stack (pp 298-9)
Copyright: S. Shekhar, C. S. Dept., University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)