TABLE OF CONTENTS (HIDE)

C++ Programming Language

Template and Generic Programming

Introduction

We are familiar in passing value/variable into function. Instead of passing a variable, we pass a type (such as int, double, and Point) into template. Passing type is known as generic programming, as we can program in generic type and invoke the code using a specific type.

The goal of generic programming is to write code that is independent of the data types. In C language, all codes are tied to a specific data type. For container data structures (such as array and structure), you need to specify the type of the elements. For algorithms (such as searching or sorting), the code works only for a specific type, you need to rewrite the code for another type. Can we write a single sorting routine that works on all types (or most of the types) by specifying the type during invocation? Can we have a general container that can work on all types?

Template lets you program on generic type, instead of on a specific type. Template supports so-called parameterized type - i.e., you can use type as argument in building a class or a function (in class template or function template). Template is extremely useful if a particular algorithm is to be applied to a variety of types, e.g., a container class which contains elements, possibly of various types.

C++'s Standard Template Library (STL) provides template implementation of many container classes, such as vector, which can be used to hold elements of all types. STL also provides generic representation of algorithm (such as searching and sorting), which works on the generic container.

Example: STL's vector Template Class

C/C++ built-in array has many drawbacks:

  1. It is fixed-size and needs to be allocated with the fixed-size during declaration. It does not support dynamic allocation. You cannot increase the size of an array during execution.
  2. Array does not provide index-bound check. You could use an index which is outside the array's bound.
  3. You need to roll your own codes to compare two arrays (via ==), copy an array into another array (via assignment =), etc.

C++ provides a vector template class, as part of Standard Template Library (STL). It is defined in header <vector>, belonging to the namespace std. (In computing, a vector refers to an array-like structure that holds a set of direct-access elements of the same kinds, instead of mathematical n-component vector.) vector is the most commonly used STL class, which provides an alternative to the error-phone array, supports dynamic memory allocation and many operations (such as comparison and assignment).

vector is a template class, which can be instantiated with a type, in the format: vector<int>, vector<double>, vector<string>. The same template class can be used to handle many types, instead of repeatably writing codes for each of the type.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
 
/* Test vector template class (TestVectorTemplate.cpp) */
#include <iostream>
#include <vector>
#include <string>
using namespace std;
 
void print(const vector<int> & v);
 
int main() {
   vector<int> v1(5);  // Create a vector with 5 elements;
 
   // Assign values into v1, using array-like index []
   // You can retrieve the size of vector via size()
   for (int i = 0; i < v1.size(); ++i) {
      v1[i] = (i+1) * 2;          // no index-bound check for []
   }
 
   // Print vector content, using at()
   for (int i = 0; i < v1.size(); ++i) {
      cout << v1.at(i) << " ";    // do index-bound check with at()
   }
   cout << endl;
 
   vector<int> v2;   // Create a vector with 0 elements
   // Assign v1 to v2 memberwise
   v2 = v1;
   for (int i = 0; i < v2.size(); ++i) {
      cout << v2[i] << " ";
   }
   cout << endl;
 
   // Compare 2 vectors memberwise
   cout << boolalpha << (v1 == v2) << endl;
 
   // Append more elements - dynamically allocate memory
   v1.push_back(80);
   v1.push_back(81);
   for (int i = 0; i < v1.size(); ++i) {
      cout << v1[i] << " ";
   }
   cout << endl;
 
   // Remove element from the end
   v1.pop_back();
   for (int i = 0; i < v1.size(); ++i) {
      cout << v1[i] << " ";
   }
   cout << endl;
 
   vector<string> v3;  // Create a vector of string with 0 element
   v3.push_back("A for Apple");    // append new elements
   v3.push_back("B for Boy");
   for (int i = 0; i < v3.size(); ++i) {
      cout << v3[i] << " ";
   }
   cout << endl;
}

Program Notes:

  • You can instantiate a vector of int via declaration vector<int> v1(n), where n specifies the initial number of elements.
  • You can use v1.size() to get the current size (number of elements) of the vector.
  • You can directly access element via v1[i] or v1.at(i). The [] operator does not perform index-bound check; whereas at() does. Try issuing an out-of-bound index via [] and at() and observe the result.
  • You can assign a vector into another vector via the assignment operator (=). The assignment is carried out memberwise.
  • You can compare two vectors memberwise via the comparison operators (==, !=).
  • You can append/remove element from the end via push_back() and pop_back(). The size of vector will be adjusted and memory allocated automatically.
  • You can also create vector of other types, such as vector<string>, vector<double>, etc. The bigger advantage of template class is the same algorithm and operation can be applied to different types - you do not need to write separate codes for different types.

Function Template

A function template is a generic function that is defined on a generic type for which a specific type can be substituted. Compiler will generate a function for each specific type used. Because types are used in the function parameters, they are also called parameterized types.

The syntax of defining function template is:

template <typename T> OR template <class T>
return-type function-name(function-parameter-list) { ...... }

Similar to function's parameter-list, which passes variables (e.g., int number), the template's parameter list passes types.

Example 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
/* Test Function Template (FunctionTemplate.cpp) */
#include <iostream>
using namespace std;
 
template <typename T>
void mySwap(T &a, T &b);
   // Swap two variables of generic type passed-by-reference
   // There is a version of swap() in <iostream>
 
int main() {
   int i1 = 1, i2 = 2;
   mySwap(i1, i2);   // Compiler generates mySwap(int &, int &)
   cout << "i1 is " << i1 << ", i2 is " << i2 << endl;
 
   char c1 = 'a', c2 = 'b';
   mySwap(c1, c2);   // Compiler generates mySwap(char &, char &)
   cout << "c1 is " << c1 << ", c2 is " << c2 << endl;
 
   double d1 = 1.1, d2 = 2.2;
   mySwap(d1, d2);   // Compiler generates mySwap(double &, double &)
   cout << "d1 is " << d1 << ", d2 is " << d2 << endl;
 
// mySwap(i1, d1);
     // error: no matching function for call to 'mySwap(int&, double&)'
     // note: candidate is:
     // note: template<class T> void mySwap(T&, T&)
}
 
template <typename T>
void mySwap(T &a, T &b) {
   T temp;
   temp = a;
   a = b;
   b = temp;
}

Take note that the C++ compiler generate a version of the code for each type used in the program, in a process known as instantiation of template. For example, with type of int, the following code will be generated by the compiler:

void mySwap(int &a, int &b) {
   int temp;
   temp = a;
   a = b;
   b = temp;
}

There is no improvement in term of execution speed or memory usage. But there is a big improvement in programmer's productivity, ease-of-use and ease-of-maintenance.

Also, the above code can handle the fundamental types (such as int, double), but not some types such as array. It, however, works for objects and structs, thanks to the memberwise assignment.

You could use <typename T> or <class T> in the template parameter list. The keywords typename and class serve the same purpose.

Example 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
/* Test function Template (TestFunctionTemplate.cpp) */
#include <iostream>
using namespace std;
 
template<typename T>
T abs(T value) {
   T result;    // result's type is also T
   result = (value >= 0) ? value : -value;
   return result;
}
 
int main() {
   int i = -5;
   cout << abs(i) << endl;
 
   double d = -55.5;
   cout << abs(d) << endl;
 
   float f = -555.5f;
   cout << abs(f) << endl;
}

The compiler creates three versions of the abs function based on the function template, for types of int, double, and float.

Function Template Overloading
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
 
/* Test Function Template Overloading (FunctionTemplateOverloading.cpp) */
#include <iostream>
using namespace std;
 
template <typename T>
void mySwap(T &a, T &b);
   // Swap two variables of generic fundamental type
 
template <typename T>
void mySwap(T a[], T b[], int size);
   // Swap two arrays of generic type
 
template <typename T>
void print(const T * const array, int size);
   // Print an array of generic type
 
int main() {
   int i1 = 1, i2 = 2;
   mySwap(i1, i2);   // Compiler generates mySwap(int &, int &)
   cout << "i1 is " << i1 << ", i2 is " << i2 << endl;
 
   const int SIZE = 3;
   int ar1[] = {1, 2, 3}, ar2[] = {4, 5, 6};
   mySwap(ar1, ar2, SIZE);
   print(ar1, SIZE);
   print(ar2, SIZE);
}
 
template <typename T>
void mySwap(T &a, T &b) {
   T temp;
   temp = a;
   a = b;
   b = temp;
}
 
template <typename T>
void mySwap(T a[], T b[], int size) {
   T temp;
   for (int i = 0; i < size; ++i) {
      temp = a[i];
      a[i] = b[i];
      b[i] = temp;
   }
}
 
template <typename T>
void print(const T * const array, int size) {
   cout << "(";
   for (int i = 0; i < size; ++i) {
      cout << array[i];
      if (i < size - 1) cout << ",";
   }
   cout << ")" << endl;
}
Explicit Specialization
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
/* Test Function Template Explicit Specialization (FunctionTemplateSpecialization.cpp) */
#include <iostream>
using namespace std;
 
 
template <typename T>
void mySwap(T &a, T &b);  // Template
 
template <>
void mySwap<int>(int &a, int &b);
   // Explicit Specialization for type int
 
int main() {
   double d1 = 1, d2 = 2;
   mySwap(d1, d2);   // use template
 
   int i1 = 1, i2 = 2;
   mySwap(i1, i2);   // use specialization
}
 
template <typename T>
void mySwap(T &a, T &b) {
   cout << "Template" << endl;
   T temp;
   temp = a;
   a = b;
   b = temp;
}
 
template <>
void mySwap<int>(int &a, int &b) {
   cout << "Specialization" << endl;
   int temp;
   temp = a;
   a = b;
   b = temp;
}

Take note that if there is any non-template definition that matches the function call. The non-template version will take precedence over explicit specialization, then template.

Class Template

The syntax for defining a class template is as follow, where T is a placeholder for a type, to be provided by the user.

template <class T>    // OR template <typename T>
class ClassName {
   ......
}

The keywords class and typename (newer and more appropriate) are synonymous in the definition of template.

To use the template defined, use the syntax ClassName<actual-type>.

For Example,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 
/*
 *  Test Class Template (TestClassTemplate.cpp)
 */
#include <iostream>
using namespace std;
 
template <typename T>
class Number {
private:
   T value;
public:
   Number(T value) { this->value = value; };
   T getValue() { return value; }
   void setValue(T value) { this->value = value; };
};
 
int main() {
   Number<int> i(55);
   cout << i.getValue() << endl;
 
   Number<double> d(55.66);
   cout << d.getValue() << endl;
 
   Number<char> c('a');
   cout << c.getValue() << endl;
 
   Number<string> s("Hello");
   cout << s.getValue() << endl;
}
Separating Template Function Declaration and Definition

If you separate the function implementation, you need to use keyword template <typename T> on each of the function implementation. For example,

template <typename T>
T Number<T>::getValue() {
   return value;
}
Keep All Template Codes in the Header file

Templates are not class nor member function definition. They are instructions to the C++ compiler how to generate the class definition. Hence, placing member functions in a separate file will not work. All template codes shall be placed in the header file - to be included in all files using the template. Template cannot be compiled separately.

A particular realization of template is called an instantiation or specialization. The C++ compiler generate a class for each of the parameterized type used in the program.

More than one Type Parameters

To use more than one type parameters in a template:

template <typename T1, typename T2, ....>
class ClassName { ...... }
Default Type

You can also provide default type in template. For example,

template <typename T = int>
class ClassName { ...... }

To instantiate with the default type, use ClassName<>.

Specialization
// General Template
template <typename T>
class Complex { ...... }
 
// Specialization for type double
template <>
class Complex<double> { ...... }
 
// Specialization for type int
template <>
class Complex<int> { ....... }

The specialization version will be matched, if available.

Example: MyComplex Template Class

MyComplex.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
 
/*
 * The MyComplex template class header (MyComplex.h)
 * All template codes are kept in the header, to be included in program
 * (Follow, modified and simplified from GNU GCC complex template class.)
 */
#ifndef MY_COMPLEX_H
#define MY_COMPLEX_H
 
#include <iostream>
 
// Forward declaration
template <typename T> class MyComplex;
 
template <typename T>
std::ostream & operator<< (std::ostream & out, const MyComplex<T> & c);
template <typename T>
std::istream & operator>> (std::istream & in, MyComplex<T> & c);
 
// MyComplex template class declaration
template <typename T>
class MyComplex {
private:
   T real, imag;
 
public:
   // Constructor
   explicit MyComplex<T> (T real = 0, T imag = 0)
         : real(real), imag(imag) { }
 
   // Overload += operator for c1 += c2
   MyComplex<T> & operator+= (const MyComplex<T> & rhs) {
      real += rhs.real;
      imag += rhs.imag;
      return *this;
   }
 
   // Overload += operator for c1 += value
   MyComplex<T> & operator+= (T value) {
      real += value;
      return *this;
   }
 
   // Overload comparison == operator for c1 == c2
   bool operator== (const MyComplex<T> & rhs) const {
      return (real == rhs.real && imag == rhs.imag);
   }
 
   // Overload comparison != operator for c1 != c2
   bool operator!= (const MyComplex<T> & rhs) const {
      return !(*this == rhs);
   }
 
   // Overload prefix increment operator ++c
   // (Separate implementation for illustration)
   MyComplex<T> & operator++ ();
 
   // Overload postfix increment operator c++
   const MyComplex<T> operator++ (int dummy);
 
   /* friends */
 
   // (Separate implementation for illustration)
   friend std::ostream & operator<< <>(std::ostream & out, const MyComplex<T> & c); // out << c
   friend std::istream & operator>> <>(std::istream & in, MyComplex<T> & c);        // in >> c
 
   // Overloading + operator for c1 + c2
   // (inline implementation for illustration)
   friend const MyComplex<T> operator+ (const MyComplex<T> & lhs, const MyComplex<T> & rhs) {
      MyComplex<T> result(lhs);
      result += rhs;  // uses overload +=
      return result;
   }
 
   // Overloading + operator for c + double
   friend const MyComplex<T> operator+ (const MyComplex<T> & lhs, T value) {
      MyComplex<T> result(lhs);
      result += value;  // uses overload +=
      return result;
   }
 
   // Overloading + operator for double + c
   friend const MyComplex<T> operator+ (T value, const MyComplex<T> & rhs) {
      return rhs + value;   // swap and use above function
   }
};
 
// Overload prefix increment operator ++c
template <typename T>
MyComplex<T> & MyComplex<T>::operator++ () {
  ++real;   // increment real part only
  return *this;
}
 
// Overload postfix increment operator c++
template <typename T>
const MyComplex<T> MyComplex<T>::operator++ (int dummy) {
   MyComplex<T> saved(*this);
   ++real;  // increment real part only
   return saved;
}
 
/* Definition of friend functions */
 
// Overload stream insertion operator out << c (friend)
template <typename T>
std::ostream & operator<< (std::ostream & out, const MyComplex<T> & c) {
   out << '(' << c.real << ',' << c.imag << ')';
   return out;
}
 
// Overload stream extraction operator in >> c (friend)
template <typename T>
std::istream & operator>> (std::istream & in, MyComplex<T> & c) {
   T inReal, inImag;
   char inChar;
   bool validInput = false;
   // Input shall be in the format "(real,imag)"
   in >> inChar;
   if (inChar == '(') {
      in >> inReal >> inChar;
      if (inChar == ',') {
         in >> inImag >> inChar;
         if (inChar == ')') {
            c = MyComplex<T>(inReal, inImag);
            validInput = true;
         }
      }
   }
   if (!validInput) in.setstate(std::ios_base::failbit);
   return in;
}
 
#endif

Program Notes:

  • [TODO]
TestMyComplex.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 
/* Test Driver for MyComplex template class (TestMyComplex.cpp) */
#include <iostream>
#include <iomanip>
#include "MyComplex.h"
 
int main() {
   std::cout << std::fixed << std::setprecision(2);
 
   MyComplex<double> c1(3.1, 4.2);
   std::cout << c1 << std::endl;  // (3.10,4.20)
   MyComplex<double> c2(3.1);
   std::cout << c2 << std::endl;  // (3.10,0.00)
 
   MyComplex<double> c3 = c1 + c2;
   std::cout << c3 << std::endl;  // (6.20,4.20)
   c3 = c1 + 2.1;
   std::cout << c3 << std::endl;  // (5.20,4.20)
   c3 = 2.2 + c1;
   std::cout << c3 << std::endl;  // (5.30,4.20)
 
   c3 += c1;
   std::cout << c3 << std::endl;  // (8.40,8.40)
   c3 += 2.3;
   std::cout << c3 << std::endl;  // (10.70,8.40)
 
   std::cout << ++c3 << std::endl; // (11.70,8.40)
   std::cout << c3++ << std::endl; // (11.70,8.40)
   std::cout << c3   << std::endl; // (12.70,8.40)
 
// c1+c2 = c3;  // error: c1+c2 returns a const
// c1++++;      // error: c1++ returns a const
 
// MyComplex<int> c4 = 5;  // error: implicit conversion disabled
   MyComplex<int> c4 = (MyComplex<int>)5;  // explicit type casting allowed
   std::cout << c4 << std::endl; // (5,0)
 
   MyComplex<int> c5;
   std::cout << "Enter a complex number in (real,imag): ";
   std::cin >> c5;
   if (std::cin.good()) {
      std::cout << c5 << std::endl;
   } else {
      std::cerr << "Invalid input" << std::endl;
   }
   return 0;
}

Program Notes:

  • [TODO]
Link to "C++ References & Resources"

Latest version tested: Cygwin/MinGW GCC 4.6.2
Last modified: May, 2013