Skip to main contentCal State San Bernardino / [CNS] / [Comp Sci Dept] / [R J Botting] >> [CSci202] >> templates
[Index] [Schedule] [Syllabi] [Text] [Labs] [Projects] [Resources] [Search] [Contact] [Grading]
Notes: [01] [02] [03] [04] [05] [06] [07] [08] [09] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20]
Mon Jun 4 17:52:34 PDT 2007

Contents


    Templates

      When should I use a template?

      Whenever you can.

      Exception: when soembody already did it and put it in a library.

      Templates have very little overhead but are very easy to reuse.

      Use a template whenever you have to program some function or class that can be used with more than one type of data. It is often almost as easy to code the generic case as it is the special case.... and then the template will be a lot more use than the special purpose version. However if the particular case relies on special properties of some data, don't try to make this data into a template parameter.

      Template Functions

      You can make functions more useful by writing them so that they will work with any type of data. These are then said to be generic or template_functions. It is easy to do. It makes code more reusable. It also doesn't slow down the program because the compiler does all the hard work.

      In C++ the simplest form is to write

       		template <typename T>
      in front of a function declaration. The T above can be any variable you like. It stands for some, as yet unknown, name of a data type or a class. The word typename is used in standard C++ to indicate a predefined elementary type, or any more complex data types, including classes and structures. With older compilers use "class" not "typename", by the way.

      You write the rest of the function definition as if T was a normal data type. For example here is a function that will compare two items of data of the same type and return the biggest of the two we would use:

       		template <typename T>
       		T Max(T x, T y)
       		{	if( x>y ) return x;
       			else return y;
       		}
      You can then use the function as normal. Because the function has T as the type of at least one argument the type of the actual argument determines T. The compiler uses the data in the calls of the function to figure out what the actual T is and generates the correct code for you. T can become any elementary data type, pointer, class, struct or enum. Notice that for Max above we need the operator ">" defined for our data. Luckily this is a true of most built-in data.

      For example given:

       		cout << Max ( 12, 4);
      the compiler generates an instance of Max with T replaced by 'int':
       		int Max(int x, int y)
       		{	if( x>y ) return x;
       			else return y;
       		}
      because 12 and 4 are ints.

      But in:

       		cout << Max ( 'a', 'b');
      it generates another instance of Max with T replaced by 'char':
       		char Max(char x, char y)
       		{	if( x>y ) return x;
       			else return y;
       		}

      The compiler will have a problem if the actual arguments don't have the same type or if placing the actual data type in the code generates rubbish -- for example if it results in comparing data that doesn't have a '>' operator.

      By the way the generic Max function is worth having on hand in your personal library.

      However, some of the STL libraries already define 'max' and 'min' -- so you may not have to code it yourself. I had to use the capitalized version of the name to avoid ambiguity....

      Exercise: Write an executable program that includes the above template function definition and tests it.

      Exercise: Use the Max function as a model for define a similar Min function.

      Answer: [ tMin.cpp ]

      A Second Example

      Here is the definition of a generic swap function:
       		template<typename T>
       		void Swap( T&a, T&b){ T t=a;a=b;b=t;}
      (Again 'swap' is already defined in the library so I've capitalized my version).

      Exercise: write a small main program that shows how this function can be used to exchange int's, float's and string's.

      See Example at the end of the page for a examples of Max, Min, and Swap templates.

      Revision Exercise: Explain why there were '&'s in Swap but not in Max!

      See Answer at the end of the page.

      Template Classes

      You can make a whole class generic by putting
       		template <typename T>
      in front of the class definition.
       		template <typename T>
       		class Foo { yada yada yada };

      Again the rest of the class is written as if T was a normal data type or class name. C++ vectors are an example of a such a template class. This is a very economical way of creating standard data structures like stacks and queues. You can avoid to put a lot of work into high quality programming because it can be used in many different projects.

      Template classes are used in declarations and nearly always used with explicit actual parameters or arguments:

       		Foo <int> bar;
      The above declares a variable bar which will be an object that belongs in the class generated from Foo by replacing T by int through out Foo's definition.

      Examples:

       		vector<int>stack;
       		queue<Customers> line;
       		stack<Operators> rator_stack;
       		stack<Operands> rand_stack;

      Notice that the functions that are members of the class (declared inside it) are all template functions as well.

      If the function definitions (header+body) are outside the class you must add

       		template <...>
      in front of the normal definition
       		template <...> .... Foo::yada(...) { .... }

      Once written a template can be used in many projects. Templates are often easy to program.

      C++ Standard Library

      Modern C++ compilers come equipped with a large library of generic classes and functions. And the compiler can easily generate vectors, stacks, lists, queues, and other useful data structures for you. [ stl.html ]

      Separate Compilation

      Many compilers have a problem with separately compiled templates.

      Most compilers handle templates by using the generic source code to create functions that are compiled, they need to have a copy of the template "in front of them" as the compile it. They can not make use of a compiled template to generate a special version. This means that templates must be declared in the code where they are used. So you are forced to include the complete function definition in the #included file.

      This is an exception to my general rule. In general we avoid putting function implementation in *.h files. This repeatedly recompiles unchanged code! If the function is template then we do put the implementation in the header file. I often just put the whole definition (header+body) of the functions and classes in the header *.h files. The files that need to use a templated function or class #include the header file that contains the definition. As long as the code is small the overhead is small as well.

      Some compilers need special options and switches to be set before they will handle separately compiled templates. The options in effect tell them to file the template code away for future work.

      According to the designer of C++, Bjarne Stroustrup, a separately compiled template must have the keyword export put in front of its definition:

       export template<typename T> void swap(T&a, T&b){ T t=a; a=b; b=t; }
      If your compiler handles this ok and generates an linkable object file, then the header file can contain just the template function prototype without a body. As of November 2002 our Gnu CC did not. Instead it says
       warning: keyword 'export' not implemented and will be ignored

      See Also

      Some notes: [ stl.html ]

      Some working examples: [ Array.cc ] [ arith_float_collection.h ] [ tmax.cc ] [ tstack.cc ] [ vector.cc ] [ vector.h ] [ gin_stack.h ] [ gtin_stack.cpp ]

      An example that does not work -- template recursion: [ trex.cc ]

      Jargon

    1. template::=a piece of code that has a number of symbolic formal arguments in it that are change to fit the ways that it used. In C++ we have template_functions and template classes.

    2. template_function::= a template that generates functions as required to fit the function calls.

    3. template_class::= a template that generates classes on demand.

    4. typename::C++Keyword, used in front of the formal argument or parameter in a template declaration. In older compilers the word "class" was used instead of "typename".

    5. generic::= something that has many specific cases that all share common properties -- in C++ a template_function or a template_class.

    6. instance::=one of the specific cases that come from a single generic pattern or template.

    7. STL::=Standard Template Library. The older name for the [ C++ Standard Library ]

      Definitions

    8. prototype::=The header of a function describing how it is called and what it returns without describing how it does it.

    9. prototype::syntax= returned_type function_name( formal_argument_types) semicolon.

    10. function_implementation::syntax=returned_type function_name( formal_argument_types) compound_statement.

    11. class_member_function_definition::syntax=returned_type class_name double_colon function_name( formal_argument_types) compound_statement.

    12. function_name::=name, that appears in a prototype.

    13. class_name::=name, that appears as a class name in a class declaration.

    14. formal_argument_types::= list_of_type_names.

    15. function_call::syntax=function_name(actual_arguments).
    16. actual_arguments::syntax=expressions_of_a_matching_type.

    17. semicolon::= ";".
    18. template_class_declaration::syntax= template < template_parameters > class_declaration.
    19. template_parameters::=list_of template_parameter.
    20. template_parameter::= class variable | type variable.
    21. type::=the name of a data type or class.
    22. variable::=any identifier.
    23. class::=a struct with operations and functions.
    24. class_declaration::syntax= class class_name { declarations } semicolon.

    25. declarations::= public: public_declarations private: private_declarations... .
    26. private_declarations::= many declaration.
    27. public_declarations::= many declaration.

    28. declaration::= variable_declaration | function_prototype; | ... .

    29. member_function_declaration::syntax=returned_type class_name double_colon function_name ( formal_arguments ) compound_statement.

    30. compound_statement::= left_brace statements right_brace.

    31. returned_type::= "void" | "int" | "float" | .... | class_name.

    32. double_colon::=colon colon.
    33. left_brace::="{".
    34. right_brace::="}".
    35. colon::= ":".
    36. semicolon::=";".
    37. object::=an instance of a class.

    38. many::=zero or more occurrences of .
    39. list_of<whatever>::=a comma separated list of <whatever>.

    . . . . . . . . . ( end of section Templates) <<Contents | End>>

    Answer

    The '&' in an argument makes it an in-out argument. Operations written in the function that operate on the formal argument actually change (and access) the actual argument instead. This is precisely what we need when we want to swap the contents of two variables. However we don't want 'max' to change its arguments so we use the normal arguments with no '&' and call be value.

    Example

     	//quick test of a max function template.
     	#include <iostream.h>
     	#include <string>
     	template <typename T> T Max(T a, T b){ return (a>b)?a:b; }
     	 //the above is shorter than the example above but does the same thing
     	template <typename T> T Min(T a, T b){ return (a<b)?a:b; }
     	template <typename T> void Swap(T & a, T & b){ T t=a; a=b; b=t; }
     	int main()
     	{
     	        cout << Max(1,2)<< endl;
     	        cout << Max('a','c')<< endl;
     	        cout << Max(string("Abel"), string("Baker"))<< endl;
     	}

    Abbreviations

  1. TBA::="To Be Announced", something I have to do.
  2. TBD::="To Be Done", something you have to do.
  3. Dia::="A free Open Source Diagramming tool for Linux, Windoze, etc. ".
  4. YAGNI::="You Ain't Gonna Need It".
  5. DRY::="Don't Repeat Yourself".

End