Recitation 5

These notes were prepared by Petros Komodromos.

Topics

1. Function templates 
2. Class templates 
3. Sorting and searching algorithms 
4. Insertion sort
5. Selection sort 
6. Shellsort 
7. Quicksort
8. Linear search 
9. Binary search 

1. Function Templates

The template mechanism of C++ allows the development of general functions and classes without the need to know the data type of the variables used during implementation. Templates allow the development of type-independent source code. Suppose that we want to find the maximum of a set of numbers that may be of int, float, or double data type, the algorithm is the same regardless of the particular data type. Using templates a single function, a function template, can be written that can selectively be instantiated and work considering a specific data type. Similarly, class templates can provide generic descriptions of classes without the need to specify the data types used.

A template line, called template parameter list, precedes a template function declaration or definition specifying the parameters that are to be used as data types in the function. One or more data types are parameterized, allowing the instantiation of the function with varying data types specified to the corresponding parameters. The template parameter list begins with the keyword template followed by comma separated parameters enclosed in <> brackets. Two types of parameters can be specified as template parameters: template type parameters, that consist of the keyword class, or typename, and an identifier; and template nontype parameters which are essentially ordinary parameter declarations that are used to represent a constant in the template definition.

The template parameter list is followed by a function template declaration or definition. The only difference of the function definition of a template function from an ordinary function is the presence and use of the template type parameters as data types. The template type parameters can be used in the same way as any other built-in or user-defined data type, in the template declaration or definition that follows the template line. Similarly, the template nontype parameters can be used as constant values. If there is a name conflict in the function template declaration or definition with a name used in the global scope, the latter is hidden. Although the name of a template parameter can be used in several function template declarations and definitions, it is not allowable to use the name of a template parameter more than once in the same template parameter list. The template parameter names used in template declarations and the actual definition of a function template may be different. To specify a function template as inline or extern, the corresponding keyword must be used after the template parameter list, i.e before the return type of the function.

A template function is a specification for an actual function that is created when the template is instantiated with a certain data type. During template instantiation, the parameters of a template are replaced by the actual data types, and the actual code for an individual function (with the data types defined) is created by the compiler. Any data type dependent errors are detected only during instantiation and not at the template definition. Prior to instantiation a function is not defined, since the function template is simply a specification on how function should be created during instantiation. A function template is instantiated either when it is  invoked, or when its address is taken to be assigned to a pointer to a function. Then, according to the arguments that are used for the function call, the data types that correspond to the template type parameters, and the values corresponding to the template nontype parameters are determined. This process is called template argument deduction and it is based on the examination of the function arguments. Note, that the return data type of the function template is not considered in the template argument deduction. In addition, the template arguments can be explicitly specified, instead of relying on the template argument deduction mechanism. Template arguments can be explicitly specified by a comma separated list of template arguments in a <> brackets between the name of the function template and its, enclosed in parentheses, argument list.

The following simple example shows how a template function can be used to determine the maximum element of a vector of numbers that can be of int or double data type.

/*  Simple example of using function templates */

template<typename MyType>
MyType findMax(MyType vect[], int n)
{
  MyType maximum = vect[0];

  for(int i=1; i<n ;i++)
    if(vect[i]>maximum)
      maximum = vect[i];

  return maximum;
}

template<class MyType, int SIZE>        // keywords class and typename are equivalent
inline MyType findMin(MyType (&vect)[SIZE])
{
  MyType minimum = vect[0];

  for(int i=1; i<SIZE ;i++)
    if(vect[i]<minimum)
      minimum = vect[i];

  return minimum;
}

int main(void)
{
  int nx = 10, x[] = {3, -78, 12, 52, 17, -53, 2, 49, -9, 43}, ny = 7;
  double y[] = {39.2, -72.8, 5.2, 14.7, -15.3, 41.9, -92.3};

  cout << "\n Maximum element of x = " << findMax(x,nx) << endl;
  cout << " Maximum element of y = " << findMax(y,ny) << endl;

  cout << "\n Minimum element of x = " << findMin(x) << endl;
  cout << " Minimum element of y = " << findMin(y) << endl;

  return EXIT_SUCCESS;
}

Output

 Maximum element of x = 52
 Maximum element of y = 41.9

 

 Minimum element of x = -78
 Minimum element of y = -92.3

The definition must be visible at the point of instantiation, e.g. when a function template is called. In the above simple example the definition of the function template and the code in which it was instantiated appeared in the same file.

For larger programs the function template definitions are typically provided in a header file that is included in every file in which the function template is used, similarly as when using inline functions.

2. Class Templates

Class templates can be used to develop a generic class prototype (specification) that can be instantiated with different data types. This is very useful when the same kind of class is used with different data types for individual members of the class. Parameterized types are used as data types, as in the function templates, and then a class can be instantiated, i.e. constructed and used, by providing arguments for the parameters of the class template. A class template is a specification of how a class should be built (i.e. instantiated) given the data type or values of its parameters.

A class template is defined by a line which defines the parameters, using the keyword template followed by the parameters (template type and nontype parameters) enclosed in <> brackets known as template parameter list. Each template type parameter is preceded by the keyword class or typename, and it is replaced by the corresponding argument when the class is instantiated. The name of a template type parameter represents a built-in or user-defined data type that would be defined during the class instantiation. A template nontype parameter is like a an ordinary (function-parameter) declaration, and represents a constant in the class template definition, i.e. it should be possible to be determined at compilation time. A parameter can be specified only once in the template parameter list and should not have the same name with a member of the class. The name of a template parameter can be reused in other template declarations or definitions, and also can be different in declarations or definitions of the same class template. If the name of a template parameter is the same as a global variable then the latter is hidden by the parameter.

In addition, the class template parameters (both type and nontype) can have default arguments that are used, during class template instantiation, if arguments are not provided. Because the provided arguments are used starting from the far left parameter, default arguments should be provided for the rightmost parameters.

Then, the declaration or definition of the class follows, using the defined type parameters as data types. The definition of a class template as well as the definitions of externally defined member functions are similar to ordinary class and member function definitions with the only difference being, besides the template parameter list at their beginning, the use of the template parameters. To define externally defined member functions of a class template, the template parameter list must precede the definition to make the parameters available to the function. In addition, the template parameters should also be used in <> brackets list before the scope resolution operator to indicate the actual name of the specific class which is a certain instantiation of the class template. A member function of a class template is itself a function template which is instantiated only whenever the function is invoked or its address is taken (and not when the class template is instantiated), using the corresponding data types used for the associated class object.

To create a particular class and define an object of that class the name of the template class is used followed by a comma-separated list of either data types that are used as arguments to the type parameters, i.e. specifying the data types to be used for the class creation, or arguments that are passed as values to the non-type parameters of the class template. This is process is called template substitution. Each different instantiation of a class template is considered a different class which is identified by the name of the class template followed a comma separated list of parameters enclosed in <> brackets that are used for the instantiation. In contrast to function templates, where some non-type parameters may be deduced from the way they are used, e.g. the size of an array, the template parameters must be either provided as arguments or have default values that can be used.

Sometimes ambiguity may arise during instantiation of a template class, e.g. due to already existing member functions using certain data types which come in conflict with generated member functions using the specified data type which may happen to be the same.

The following simple example demonstrates the definition and use of a class template.

myTemplate.h

?

template <class myTypeX, typename myTypeY>
class Point; template <typename myTypeX, class myTypeY>
class Point
{
private:
    myTypeX x;
    myTypeY y;
    Point();

 

 

public:

    Point(myTypeX x, myTypeY y)
      {
         this->x = x;
         Point::y = y;
      }

  void print(void);
};

template <class myTypeX, class myTypeY>
void Point<myTypeX,myTypeY>::print(void)
{
   cout << " (x,y) = (" << x << "," << y << ")  "  ;
}

 

 

myTemplate.C

#include  <iostream.h>
#include  <stdlib.h>
#include  "myTemplate.h"

 

int main ( )
{
  Point<int,double> p1(3,9.25);
  cout << "\n p1 = ";
  p1.print();

  Point<double,int> p2(3.74,9);
  cout << "\n p2 = ";
  p2.print();

  cout << endl;
  return EXIT_SUCCESS;
}

3. Sorting and Searching Algorithms

Sorting and searching are fundamental operations in computation and information technology.

Because searching a sorted array is much more efficient than searching an unsorted one, sorting is used to facilitate searching. In many programs the running time is determined by the time required for sorting. Therefore, it is important to implement a fast sorting algorithm.

For all algorithms, presented below, assume that the N data (elements) are stored in an array named A.

4. Insertion Sort

This is an elementary algorithm with nested loops which cause an O(N²) time.

Each element, starting from the element A[0], is considered one at a time and it is positioned in the proper ordered among those who have already been considered.

Example:
 

5. Selection Sort

This is another elementary sorting algorithm with an O(N²) time.

The element with the smallest value in the array is identified and placed in the first position. Then, the element with the smallest value among the remaining N-1 elements is selected and placed in the first position of the N-1 subarray. Continuing this procedure the array is sorted as shown by the following example.

Example:
 

6. Shellsort

Shellsort is an extension of insertion sort which can increase its efficiency. It allows exchanges of non adjacent elements. Although in some rare cases an O(N^2) time is required, the required time is usually O(N^3/2).

First, a gap size is selected by dividing the number of the elements by 2. Then, the corresponding every "gap-size" elements are sorted. Next, the "gap-size" is divided by 2 and repeat the sorting of the elements at every "gap-size". Finally, the "gap-size" becomes equal to 1 and the entire array is sorted.

Example:
 

7. Quicksort

Quicksort is a very fast sorting algorithm which has O(N.lgN) average times. Its worst case performance is O(N²), but can be avoided with certain techniques. It is a "divide and conquer" algorithm for sorting. It partitions the data into two parts and then sort them independently.
It uses in place sorting and a simple recursive structure.

An element of the array, called pivot, is picked.

Then, one index start from each side of the array moving towards each other. The higher index is decreased until an element with a value smaller than the value of the pivot is found. Similarly the lower index is increased until an element with a value higher than the value of the pivot is found. If the two indices are different, the two corresponding elements are out of order and need to be exchanged with each other.

The above step is repeated from the point where the process was interrupted.
If the two indices are the same, then if the value of the selected element is less than that of the pivot the selected element and the pivot are exchanged. Otherwise, no exchange should occur.

At this point the algorithm has grouped the elements of the array into two subarrays. One has all elements smaller than or equal to the pivot and the other all the elements larger or equal to the pivot.

Then, the algorithm is applied recursively to each subarray until the number of the elements of a subarray is equal to 0 or 1.
 

Example:
 
 
 

pivot   -   left index  -  right index -both indices

 Black cells are used to separate the elements of the array, i.e. they are not elements of the array.
The above array is of size N=8.

8. Linear Search

Linear search is the simplest searching algorithm and can be applied to unsorted data. The search proceeds in sequence searching for a certain element. In the worst case, which is the case of an unsuccessful search, it takes N iterations. On average it takes N/2 iterations.

Example:

Search for element with key value equal to 33
 

9. Binary Search

Binary search can be used on sorted data. It splits the data in half, determines in which half the desired element must be located (if it exists in the data set). Then, recursively repeats the cutting in half of the elements and keeps selecting the part in which he desired data element may be.
This algorithm requires O(lgN) computational time.

Example:

Search for element with key value equal to 33