Section 16.1. Template Definitions


16.1. Template Definitions

Let's imagine that we want to write a function to compare two values and indicate whether the first is less than, equal to, or greater than the second. In practice, we'd want to define several such functions, each of which could compare values of a given type. Our first attempt might be to define several overloaded functions:

      // returns 0 if the values are equal, -1 if v1 is smaller, 1 if v2 is smaller      int compare(const string &v1, const string &v2)      {          if (v1 < v2) return -1;          if (v2 < v1) return 1;          return 0;      }      int compare(const double &v1, const double &v2)      {          if (v1 < v2) return -1;          if (v2 < v1) return 1;          return 0;      } 

These functions are nearly identical: The only difference between them is the type of their parameters. The function body is the same in each function.

Having to repeat the body of the function for each type that we compare is tedious and error-prone. More importantly, we need to know in advance all the types that we might ever want to compare. This strategy cannot work if we want to be able to use the function on types that we don't know about.

16.1.1. Defining a Function Template

Rather than defining a new function for each type, we can define a single function template. A function template is a type-independent function that is used as a formula for generating a type-specific version of the function. For example, we might write a function template named compare, which would tell the compiler how to generate specific versions of compare for the types that we want to compare.

The following is a template version of compare:

      // implement strcmp-like generic compare function      // returns 0 if the values are equal, 1 if v1 is larger, -1 if v1 is smaller      template <typename T>      int compare(const T &v1, const T &v2)      {          if (v1 < v2) return -1;          if (v2 < v1) return 1;          return 0;      } 

A template definition starts with the keyword template followed by a template parameter list, which is a comma-separated list of one or more template parameters bracketed by the less-than (<) and greater-than (>) tokens.

The template parameter list cannot be empty.



Template Parameter List

The template parameter list acts much like a function parameter list. A function parameter list defines local variable(s) of a specified type but leaves those variables uninitialized. At run time, arguments are supplied that initialize the parameters.

Analogously, template parameters represent types or values we can use in the definition of a class or function. For example, our compare function declares one type parameter named T. Inside compare, we can use the name T to refer to a type. Which actual type T represents is determined by the compiler based on how the function is used.

A template parameter can be a type parameter, which represents a type, or a nontype parameter, which represents a constant expression. A nontype parameter is declared following a type specifier. We'll see more about nontype parameters in Section 16.1.5 (p. 632). A type parameter is defined following the keyword class or typename. For example, class T is a type parameter named T. There is no difference between class and typename in this context.

Using a Function Template

When we use a function template, the compiler infers what template argument(s) to bind to the template parameter(s). Once the compiler determines the actual template argument(s), it instantiates an instance of the function template for us. Essentially, the compiler figures out what type to use in place of each type parameter and what value to use in place of each nontype parameter. Having deduced the actual template arguments, it generates and compiles a version of the function using those arguments in place of the corresponding template parameters. The compiler takes on the tedium of (re)writing the function for each type we use.

Given the calls

      int main ()      {          // T is int;          // compiler instantiates int compare(const int&, const int&)          cout << compare(1, 0) << endl;          // T is string;          // compiler instantiates int compare(const string&, const string&)          string s1 = "hi", s2 = "world";          cout << compare(s1, s2) << endl;          return 0;      } 

the compiler will instantiate two different versions of compare. The compiler will create one version that replaces T by int and a second version that uses string in place of T.

inline Function Templates

A function template can be declared inline in the same way as a nontemplate function. The specifier is placed following the template parameter list and before the return type. It is not placed in front of the template keyword.

      // ok: inline specifier follows template parameter list      template <typename T> inline T min(const T&, const T&);      // error: incorrect placement of inline specifier      inline template <typename T> T min(const T&, const T&); 

Exercises Section 16.1.1

Exercise 16.1:

Write a template that returns the absolute value of its parameter. Call the template on values of at least three different types. Note: until we discuss how the compiler handles template instantiation in Section 16.3 (p. 643), you should put each template definition and all uses of that template in the same file.

Exercise 16.2:

Write a function template that takes a reference to an ostream and a value, and writes the value to the stream. Call the function on at least four different types. Test your program by writing to cout, to a file, and to a stringstream.

Exercise 16.3:

When we called compare on two strings, we passed two string objects, which we initialized from string literals. What would happen if we wrote:

      compare ("hi", "world"); 


16.1.2. Defining a Class Template

Just as we can define function templates, we can also define class templates.

To illustrate class templates, we'll implement our own version of the standard library queue (Section 9.7, p. 348) class. User programs ought to use the standard queue class, not the one we define here.



Our Queue must be able to hold objects of different types, so we'll define it as a class template. The operations our Queue will support are a subset of the interface of the standard queue:

  • push to add an item to the back of the queue

  • pop to remove the item at the head of the queue

  • front to return a reference to the element at the head of the queue

  • empty to indicate whether there are any elements in the queue

We'll look at how we might implement our Queue in Section 16.4 (p. 647), but we can start by defining its interface:

      template <class Type> class Queue {      public:          Queue ();                // default constructor          Type &front ();          // return element from head of Queue          const Type &front () const;          void push (const Type &); // add element to back of Queue          void pop();              // remove element from head of Queue          bool empty() const;      // true if no elements in the Queue      private:          // ...      }; 

A class template is a template, so it must begin with the keyword template followed by a template parameter list. Our Queue template takes a single template type parameter named Type.

With the exception of the template parameter list, the definition of a class template looks like any other class. A class template may define data, function, and type members; it may use access labels to control access to those members; it defines constructors and destructors; and so on. In the definition of the class and its members, we can use the template parameters as stand-ins for types or values that will be supplied when the class is used.

For example, our Queue template has one template type parameter. We can use that parameter anywhere a type name can be used. In this template definition, we use Type to name the return type from the overloaded front operations and as the parameter type for the push operation.

Using a Class Template

In contrast to calling a function template, when we use a class template, we must explicitly specify arguments for the template parameters:

      Queue<int> qi;                 // Queue that holds ints      Queue< vector<double> > qc;    // Queue that holds vectors of doubles      Queue<string> qs;              // Queue that holds strings 

The compiler uses the arguments to instantiate a type-specific version of the class. Essentially, the compiler rewrites our Queue class replacing Type by the specified actual type provided by the user. In this case, the compiler will instantiate three classes: a version of Queue with Type replaced by int, a second Queue class that uses vector<double> in place of Type, and a third that replaces Type by string.

Exercises Section 16.1.2

Exercise 16.4:

What is a function template? What is a class template?

Exercise 16.5:

Define a function template to return the larger of two values.

Exercise 16.6:

Similar to our a simplified version of queue, write a class template named List that is a simplified version of the standard list class.


16.1.3. Template Parameters

As with a function parameter, the name chosen by the programmer for a template parameter has no intrinsic meaning. In our example, we named compare's template type parameter T, but we could have named it anything:

      // equivalent template definition      template <class Glorp>      int compare(const Glorp &v1, const Glorp &v2)      {          if (v1 < v2) return -1;          if (v2 < v1) return 1;          return 0;      } 

This code defines the same compare template as before.

The only meaning we can ascribe to a template parameter is to distinguish whether the parameter is a type parameter or a nontype parameter. If it is a type parameter, then we know that the parameter represents an as yet unknown type. If it is a nontype parameter, we know it is an as yet unknown value.

When we wish to use the type or value that a template parameter represents, we use the same name as the corresponding template parameter. For example, all references to Glorp in the compare function template will be resolved to the same type when the function is instantiated.

Template Parameter Scope

The name of a template parameter can be used after it has been declared as a template parameter and until the end of the template declaration or definition.

Template parameters follow normal name-hiding rules. A template parameter with the same name as an object, function, or type declared in global scope hides the global name:

      typedef double T;      template <class T> T calc(const T &a, const T &b)      {           // tmp has the type of the template parameter T           // not that of the global typedef           T tmp = a;           // ...           return tmp;      } 

The global typedef that defines T as double is hidden by the type parameter named T. Thus, tmp is not a double. Instead, the type of tmp is whatever type gets bound to the template parameter T.

Restrictions on the Use of a Template Parameter Name

A name used as a template parameter may not be reused within the template:

      template <class T> T calc(const T &a, const T &b)      {          typedef double T; // error: redeclares template parameter T          T tmp = a;          // ...          return tmp;      } 

This restriction also means that the name of a template parameter can be used only once within the same template parameter list:

      // error: illegal reuse of template parameter name V      template <class V, class V> V calc(const V&, const V&) ; 

Of course, just as we can reuse function parameter names, the name of a template parameter can be reused across different templates:

      // ok: reuses parameter type name across different templates      template <class T> T calc (const T&, const T&) ;      template <class T> int compare(const T&, const T&) ; 

Template Declarations

As with any other function or class, we can declare a template without defining it. A declaration must indicate that the function or class is a template:

      // declares compare but does not define it      template <class T> int compare(const T&, const T&) ; 

The names of the template parameters need not be the same across declarations and the definition of the same template:

      // all three uses of calc refer to the same function template      // forward declarations of the template      template <class T> T calc(const T&, const T&) ;      template <class U> U calc(const U&, const U&) ;      // actual definition of the template      template <class Type>      Type calc(const Type& a, const Type& b) { /* ... */ } 

Each template type parameter must be preceded either by the keyword class or typename; each nontype parameter must be preceded by a type name. It is an error to omit the keyword or a type specifier:

      // error: must precede U by either typename or class      template <typename T, U> T calc (const T&, const U&) ; 

Exercises Section 16.1.3

Exercise 16.7:

Explain each of the following function template definitions and identify whether any are illegal. Correct each error that you find.

      (a) template <class T, U, typename V> void f1(T, U, V) ;      (b) template <class T> T f2(int &T) ;      (c) inline template <class T> T foo(T, unsigned int*) ;      (d) template <class T> f4 (T, T) ;      (e) typedef char Ctype ;          template <typename Ctype> Ctype f5(Ctype a) ; 

Exercise 16.8:

Explain which, if any, of the following declarations are errors and why.

      (a) template <class Type> Type bar(Type, Type) ;          template <class Type> Type bar(Type, Type) ;      (b) template <class T1, class T2> void bar(T1, T2) ;          template <class C1, typename C2> void bar(C1, C2) ; 

Exercise 16.9:

Write a template that acts like the library find algorithm. Your template should take a single type parameter that will name the type for a pair of iterators that should be parameters to the function. Use your function to find a given value in a vector<int> and in a list<string>.


16.1.4. Template Type Parameters

Type parameters consist of the keyword class or the keyword typename followed by an identifier. In a template parameter list, these keywords have the same meaning: They indicate that the name that follows represents a type.

A template type parameter can be used as a type specifier anywhere in the template, in exactly the same way as a built-in or class type specifier. In particular, it can be used to name the return type or a function parameter type, and for variable declarations or casts inside the function body:

      // ok: same type used for the return type and both parameters      template <class T> T calc (const T& a, const T& b)      {           // ok: tmp will have same type as the parameters & return type           T tmp = a;           // ...           return tmp;      } 

Distinction Between typename and class

In a function template parameter list, the keywords typename and class have the same meaning and can be used interchangeably. Both keywords can be used in the same template parameter list:

      // ok: no distinction between typename and class in template parameter list      template <typename T, class U> calc (const T&, const U&); 

It may seem more intuitive to use the keyword typename instead of the keyword class to designate a template type parameter; after all, we can use built-in (nonclass types) types as the actual type parameter. Moreover, typename more clearly indicates that the name that follows is a type name. However, the keyword typename was added to C++ as part of Standard C++, so older programs are more likely to use the keyword class exclusively.

Designating Types inside the Template Definition

In addition to defining data or function members, a class may define type members. For example, the library container classes define various types, such as size_type, that allow us to use the containers in a machine-independent way. When we want to use such types inside a function template, we must tell the compiler that the name we are using refers to a type. We must be explicit because the compiler (and a reader of our program) cannot tell by inspection when a name defined by a type parameter is a type or a value. As an example, consider the following function:

      template <class Parm, class U>      Parm fcn(Parm* array, U value)      {          Parm: :size_type * p; // If Parm::size_type is a type, then a declaration                               // If Parm::size_type is an object, then multiplication      } 

We know that size_type must be a member of the type bound to Parm, but we do not know whether size_type is the name of a type or a data member. By default, the compiler assumes that such names name data members, not types.

If we want the compiler to treat size_type as a type, then we must explicitly tell the compiler to do so:

      template <class Parm, class U>      Parm fcn(Parm* array, U value)      {          typename Parm::size_type * p; // ok: declares p to be a pointer      } 

We tell the compiler to treat a member as a type by prefixing uses of the member name with the keyword typename. By writing typename Parm::size_type we say that member size_type of the type bound to Parm is the name of a type. Of course, this declaration puts an obligation on the types used to instantiate fcn: Those types must have a member named size_type that is a type.

If there is any doubt as to whether typename is necessary to indicate that a name is a type, it is a good idea to specify it. There is no harm in specifying typename before a type, so if the typename was unnecessary, it won't matter.



Exercises Section 16.1.4

Exercise 16.10:

What, if any, are the differences between a type parameter that is declared as a typename and one that is declared as a class?

Exercise 16.11:

When must typename be used?

Exercise 16.12:

Write a function template that takes a pair of values that represent iterators of unknown type. Find the value that occurs most frequently in the sequence.

Exercise 16.13:

Write a function that takes a reference to a container and prints the elements in that container. Use the container's size_type and size members to control the loop that prints the elements.

Exercise 16.14:

Rewrite the function from the previous exercise to use iterators returned from begin and end to control the loop.


16.1.5. Nontype Template Parameters

A template parameter need not be a type. In this section we'll look at nontype parameters as used by function templates. We'll look at nontype parameters for class templates in Section 16.4.2 (p. 655) after we've seen more about how class templates are implemented.

Nontype parameters are replaced by values when the function is called. The type of that value is specified in the template parameter list. For example, the following function template declares array_init as a function template with one type and one nontype template parameter. The function itself takes a single parameter, which is a reference to an array (Section 7.2.4, p. 240):

      // initialize elements of an array to zero      template <class T, size_t N> void array_init(T (&parm)[N])      {          for (size_t i = 0; i != N; ++i) {              parm[i] = 0;          }      } 

A template nontype parameter is a constant value inside the template definition. A nontype parameter can be used when constant expressions are requiredfor example, as we do hereto specify the size of an array.

When array_init is called, the compiler figures out the value of the nontype parameter from the array argument:

      int x[42];      double y[10];      array_init(x);  // instantiates array_init(int(&)[42]      array_init(y);  // instantiates array_init(double(&)[10] 

The compiler will instantiate a separate version of array_init for each kind of array used in a call to array_init. For the program above, the compiler instantiates two versions of array_init: The first instance has its parameter bound to int[42], and in the other, that parameter is bound to double[10].

Type Equivalence and Nontype Parameters

Expressions that evaluate to the same value are considered equivalent template arguments for a template nontype parameter. The following calls to array_init both refer to the same instantiation, array_init<int, 42>:

      int x[42];      const int sz = 40;      int y[sz + 2];      array_init(x);  // instantiates array_init(int(&)[42])      array_init(y);  // equivalent instantiation 

Exercises Section 16.1.5

Exercise 16.15:

Write a function template that can determine the size of an array.

Exercise 16.16:

Rewrite the printValues function from page 240 as a function template that could be used to print the contents of arrays of varying sizes.


16.1.6. Writing Generic Programs

When we write a template, the code may not be overtly type-specific, but template code always makes some assumptions about the types that will be used. For example, although our compare function is technically valid for any type, in practice the instantiated version might be illegal.

Whether the generated program is legal depends on the operations used in the function and the operations supported by the type or types used. Our compare function has has three statements:

      if (v1 < v2) return -1; // < on two objects of type T      if (v2 < v1) return 1;  // < on two objects of type T      return 0;               // return int; not dependent on T 

The first two statements contain code that implicitly depends on the parameter type. The if tests use the < operator on the parameters. The type of those parameters isn't known until the compiler sees a call to compare and T is bound to an actual type. Which < operator is used depends entirely on the argument type.

If we call compare on an object that does not support the < operator, then the call will be invalid:

      Sales_item item1, item2;      // error: no < on Sales_item      cout << compare(item1, item2) << endl; 

The program is in error. The Sales_item type does not define the < operator, so the program won't compile.

The operations performed inside a function template constrains the types that can be used to instantiate the function. It is up to the programmer to guarantee that the types used as the function arguments actually support any operations that are used, and that those operations behave correctly in the context in which the template uses them.



Writing Type-Independent Code

The art of writing good generic code is beyond the scope of this language primer. However, there is one overall guideline that is worth noting.

When writing template code, it is useful to keep the number of requirements placed on the argument types as small as possible.



Simple though it is, our compare function illustrates two important principles for writing generic code:

  • The parameters to the template are const references.

  • The tests in the body use only < comparisons.

By making the parameters const references, we allow types that do not allow copying. Most typesincluding the built-in types and, except for the IO types, all the library types we've useddo allow copying. However, there can be class types that do not allow copying. By making our parameters const references, we ensure that such types can be used with our compare function. Moreover, if compare is called with large objects, then this design will also make the function run faster.

Some readers might think it would be more natural for the comparisons to be done using both the < and > operators:

      // expected comparison      if (v1 < v2) return -1;      if (v1 > v2) return 1;      return 0; 

However, by writing the code as

      // expected comparison      if (v1 < v2) return -1;      if (v2 < v1) return 1; // equivalent to v1 > v2      return 0; 

we reduce the requirements on types that can be used with our compare function. Those types must support <, but they need not also support >.

Exercises Section 16.1.6

Exercise 16.17:

In the "Key Concept" box on page 95, we noted that as a matter of habit C++ programmers prefer using != to using <. Explain the rationale for this habit.

Exercise 16.18:

In this section we noted that we deliberately wrote the test in compare to avoid requiring a type to have both the < and > operators. On the other hand, we tend to assume that types will have both == and !=. Explain why this seeming discrepancy in treatment actually reflects good programming style.


Caution: Compile-Time Errors at Link-Time

In general, when compiling a template, there are three stages during which the compiler might flag an error: The first is when we compile the template definition itself. The compiler generally can't find many errors at this stage. Syntax errors, such as forgetting a semicolon or misspelling a variable name, can be detected.

The second error-detection time is when the compiler sees a use of the template. At this stage, there is still not much the compiler can check. For a call to a function template, many compilers check only that the number and types of the arguments are appropriate. The compiler can detect that there are too many or too few arguments. It can also detect whether two arguments that are supposed to have the same type do so. For a class template, the compiler can check that the right number of template arguments are provided but not much else.

The third time when errors are generated is during instantiation. It is only then that type-related errors can be found. Depending on how the compiler manages instantiation, which we'll cover on page 643, these errors may be reported at link time.

It is important to realize that when we compile a template definition, we do not know much about how valid the program is. Similarly, we may obtain compiler errors even after we have successfully compiled each file that uses the template. It is not uncommon to detect errors only during instantiation, which may happen at link-time.




C++ Primer
C Primer Plus (5th Edition)
ISBN: 0672326965
EAN: 2147483647
Year: 2006
Pages: 223
Authors: Stephen Prata

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net