Function Templates

Overloaded Functions (review)

Recall this problem from our discussion of functions in C++:
int cube(int n)
{
  return n * n * n;
}
int i = 8;
long l = 50L;
float f = 2.5F;
double d = 3.14;
Output:
std::cout << cube(i) << std::endl; // Works fine: 512
std::cout << cube(l) << std::endl; // May or may not work: 125000
std::cout << cube(f) << std::endl; // Not quite what we want: 8
std::cout << cube(d) << std::endl; // Not quite what we want: 27
First attempt, "old skool" fix in C:
int cube_int(int n)
{
  return n * n * n;
}

float cube_float(float n)
{
  return n * n * n;
}
double cube_double(double n)
{
  return n * n * n;
}

long cube_long(long n)
{
  return n * n * n;
}
It will work as expected:
std::cout << cube_int(i) << std::endl;    // Works fine: 512
std::cout << cube_long(l) << std::endl;   // Works fine: 125000
std::cout << cube_float(f) << std::endl;  // Works fine: 15.625
std::cout << cube_double(d) << std::endl; // Works fine: 30.9591
This quickly becomes tedious and unmanageable as we write other functions to handle other types such as unsigned int, unsigned long, char, as well as user-defined types that might come along.


Then we discovered we could "fix" the problem by overloading the function:

Overloaded functions:

int cube(int val)
{
 return val * val * val;
}
long cube(long val)
{
 return val * val * val;
}
float cube(float val)
{
 return val * val * val;
}
double cube(double val)
{
 return val * val * val;
}
Client usage:

int i = cube(2);           // cube(int), i is 8
long l = cube(100L);       // cube(long), l is 1000000L
float f = cube(2.5f);      // cube(float), f is 15.625f
double d = cube(2.34e25);  // cube(double), d is 1.2812904e+76
Notes:

Function Templates

Introduction: This is our new cube function using a template: (two new keywords are introduced here)
template <typename T> T cube(T value)
{
  return value * value * value;
}
Often, the function template is written with the template and typename keywords on a separate line above so as to keep the function "clean" looking:
template <typename T> 
T cube(T value)
{
  return value * value * value;
}
Other notes: Details:

Automatic Type Deduction

Note that often the compiler can deduce the types of the arguments (and hence, the type of T) from the parameters. However, sometimes the compiler can't figure it out and generates an error (see below).

Let's modify the templated cube function to see what types are actually being passed in:

#include <typeinfo> // typeid

template <typename T> 
T cube(T value)
{
  std::cout << "cube<" << typeid(T).name() << ">" << std::endl;
  return value * value * value; 
}
Operator precedence chart for C++

Sample code:

void f2()
{
    // Compiler deduction
              //  Microsoft       Borland        GNU/Clang
  cube(2);    // cube<int>      cube<int>      cube<i>
  cube(2.0f); // cube<float>    cube<float>    cube<f>
  cube(2.0);  // cube<double>   cube<double>   cube<d>
  cube('A');  // cube<char>     cube<char>     cube<c>

    // Explicit call
                   //  Microsoft       Borland        GNU/Clang
  cube<int>(2);    // cube<int>      cube<int>      cube<i>
  cube<double>(2); // cube<double>   cube<double>   cube<d>
  cube<int>(2.1);  // cube<int>      cube<int>      cube<i>     (warning)
}
As you can see, the actual string that is printed out is dependent on the compiler.

Of course, you can always cast the parameter to force a particular call:

  // Casting will force it as well
                              //  Microsoft       Borland        GNU/Clang
cube(static_cast<int>(2));    // cube<int>      cube<int>      cube<i>
cube(static_cast<double>(2)); // cube<double>   cube<double>   cube<d>
cube(static_cast<int>(2.1));  // cube<int>      cube<int>      cube<i>   (no warning)

User-Defined Types in Template Functions

Templates only provide some of the necessary functionality.

Suppose we wanted to cube a StopWatch object:

StopWatch sw1(4);    // Create a StopWatch set to 4 seconds
StopWatch sw2;       // Create a StopWatch set to 0 seconds
sw2 = cube(sw1);     // Cube the first StopWatch and assign to second
cout << sw2 << endl; // ???
Will this compile? If so, what will it print out? To understand what's going on, look at what the compiler is generating:
StopWatch cube(StopWatch value)
{
  return value * value * value;
}


Will this cube function compile? Why or why not?


The answer is: it depends.

StopWatch-1.cpp

If there is no overloaded operator*, the compiler will generate an error message in the template function:

template <typename T> 
T cube(T value)
{
  return value * value * value; // no match for 'operator*' in 'value * value'
}
We need to ensure that there is an overloaded * operator that takes a StopWatch on the left and right side of the operator:
StopWatch StopWatch::operator*(const StopWatch &sw) const
{
  return StopWatch(seconds_ * sw.seconds_);
}
Now, the following will compile:
StopWatch sw1(4);    // Create a StopWatch set to 4 seconds
StopWatch sw2;       // Create a StopWatch set to 0 seconds
sw2 = cube(sw1);     // Cube the first StopWatch and assign to second
cout << sw2 << endl; // Displays 00:01:04 (4 * 4 * 4 = 64 seconds)
Things to realize:

Multiple Template Parameters

Suppose we want a generic Max function:
template <typename T>
T Max(T a, T b)
{
  return a > b ? a : b;
}
The conditional operator is merely a conditional expression instead of a conditional statement. The above is very similar to this:
if (a > b)
  return a;
else
  return b;
we try to use it like this:
int i = Max(25, 10);      // i = 25
double d = Max(2.5, 3.1); // d = 3.1
double e = Max(2.5, 4);   // error: no matching function for call to 'Max(double, int)'
We need to specify the type of both parameters in order to mix types:

template <typename T1, typename T2>
T1 Max(T1 a, T2 b)
{
  return a > b ? a : b;
}
This leads to:
double d1 = Max(4.5, 3); // d1 = 4.5 
double d2 = Max(3, 4.5); // d2 = 4.0 ???  (warning: converting to 'int' from 'double')
If we change the return type, it will work for the above problem:

template <typename T1, typename T2>
T2 Max(T1 a, T2 b)
{
  return a > b ? a : b;
}
But now this is problematic:
int i = Max(3, 4.5); // i = 4 ???  (warning: converting to 'int' from 'double')
Finally, add a third type:
template <typename T1, typename T2, typename T3>
T1 Max(T2 a, T3 b)
{
  return a > b ? a : b;
}
This leads to:
double d1 = Max(3, 4.5); // error: can't deduce template argument for 'T1' 
Max(3, 4.5);             // may be called this way as well (ignore return value) 
The errors are slightly different for each compiler:
GNU: no matching function for call to 'Max(int, double)'
Clang: candidate template ignored: couldn't infer template argument 'T1'
Borland: Could not find a match for 'Max(int,double)'
Microsoft: error 'T1 Max(T2,T3)' : could not deduce template argument for 'T1' 	
The simple fact is that the compiler cannot deduce the return type of a function. The user must specify it.

Various solutions:

double d2 = Max<double, int, double>(3, 4.5); // OK, all explicit
double d3 = Max<double, double, int>(4.5, 3); // OK, all explicit
double d4 = Max<double>(3, 4.5);               // Ok, first explicit, compiler deduces others
double d5 = Max<double, int, int>(4.5, 3);    // OK, all explicit, but truncating (possible warning)
double d6 = Max<int, double, int>(4.5, 3);    // OK, all explicit, but truncating (possible warning)
Suppose I made this subtle change:
template <typename T1, typename T2, typename T3>
T3 Max(T1 a, T2 b)
{
  return a > b ? a : b;
}
How does that affect the code above? Other calls to Max?

Explicit Template Specialization

Up until now, all of our templated functions have been generated from the template. (Which was the whole point.)

What if the code generated by the compiler didn't do what we expect? (It can and does happen.)

Let's create an example:
template <typename T>
bool equal(T a, T b)
{
  std::cout << a << " and " << b << " are ";

  if (a == b)
    std::cout << "equal\n";
  else
    std::cout << "not equal\n";

  return a == b;
}
void f4()
{
  int a = 5, b = 5, c = 8;
  double d1 = 3.14, d2 = 5.0;

  equal(a, b);     // 5 and 5 are equal
  equal(a, c);     // 5 and 8 are not equal
  equal(a, c - 3); // 5 and 5 are equal
  equal(d1, d2);   // 3.14 and 5 are not equal
}
So far, so good. The function is working as expected.

Here's a question: What functionality (behavior) must the type T support in order for the code above to work?


This won't work, though:

equal(a, d2); 
Error:
error: no matching function for call to 'Max(double, int)'
   double d1 = Max(4.5, 3);
                         ^
note: candidate: template T Max(T, T)
 T Max(T a, T b)
   ^
note:   template argument deduction/substitution failed:
note:   deduced conflicting types for parameter 'T' ('double' and 'int')
   double d1 = Max(4.5, 3);
But, we don't care about that. (How could we make this "work" if we did care?)

How about these:

const char s1[] = "One";
const char s2[] = "One";
const char s3[] = "Two";

equal(s1, s2);       // One and One are not equal
equal(s1, s3);       // One and Two are not equal
equal(s1, "One");    // One and One are not equal
equal(s1, s1);       // One and One are equal
equal("One", "One"); // ???
Why are we getting "odd" results?

TemplateExpansion (artist's rendering)
template <typename T>
bool equal(T a, T b)
{  
    // Compare the two
  if (a == b)

    // other stuff
}

bool equal(const char * a, const char * b)
{  
    // Compare the two
  if (a == b)

    // other stuff
}
This just won't do, so we need to take matters into our own hands.

Now this code will do what we expect:
const char s1[] = "One";
const char s2[] = "One";
const char s3[] = "Two";

  // With specialization for equal
equal(s1, s2);    // One and One are equal
equal(s1, s3);    // One and Two are not equal
equal(s1, "One"); // One and One are equal
equal(s1, s1);    // One and One are equal
Note that the type is not strictly required in the second angle brackets, since the compiler can deduce the type from the parameters. This:
template <>
bool equal<const char *>(const char *a, const char *b)
can be changed to this:
template <>
bool equal(const char *a, const char *b)


More details:

When the compiler must choose a function, the order of choice is: (from best to worst)

  1. Regular functions (programmer)
  2. Explicit specializations (programmer)
  3. Template generated (compiler)
However, if you need to, you can always force the compiler to choose a particular function by explicitly stating which function to use.


// template function
template <typename T> 
T cube(T value)
{
  std::cout << "Cubing a " << typeid(T).name() << " (template): " << value << std::endl;
  return value * value * value;
}

// explicit specialization cube<int>
template <> 
int cube<int>(int value)
{
  std::cout << "Cubing an int (specialization): " << value << std::endl;
  return value * value * value;
}

// regular function (non-template)
int cube(int value)
{
  std::cout << "Cubing an int (regular): " << value << std::endl;
  return value * value * value;
}

int main()
{
  cube(5);            // 1. regular
  cube<double>(10L); // 2. template, first instantion
  cube(2.5F);         // 3. template, first instantion
  cube<int>(2.5);    // 4. specialization
  cube<char>(5);     // 5. template, first instantion
  cube('A');         // 6. template, no instantion (uses previous instantiation from #5)
  return 0;
}
Output: (from Borland's compiler)
Cubing an int (regular): 5
Cubing a double (template): 10
Cubing a float (template): 2.5
Cubing an int (specialization): 2
Cubing a char (template): ???
Cubing a char (template): A

Also note that you cannot create an explicit specialization for a function after an implicit instantiation for that same function has been generated. For example, if we had this code before the explicit specialization for the cube function taking an int:

void foo()
{
    // implicitly instantiates cube for integers
  int i = cube<int>(25); 
}
The explicit specialization following this will generate a compiler error along these lines:
specialization of T cube(T) [with T = int] after instantiation (GNU)
Template instance 'int cube(int)' is already instantiated (Borland)
explicit specialization; 'T cube(T)' has already been instantiated (Microsoft)


Another example revisited. Given the templated Max function below (only one type specified):

template <typename T>
T Max(T a, T b)
{
  return a > b ? a : b;
}
What is printed here?
int main()
{
  cout << Max(5, 2) << endl;
  cout << Max(4.5, 3.14) << endl;
  cout << Max('A', 'a') << endl;
  cout << Max("banana", "apple") << endl;
  return 0;
}
Output:
5
4.5
a
apple
The fix:
// Explicit specialization for const char *
// to sort lexicographically
template <> 
const char* Max<const char *>(const char *a, const char *b)
{
  return strcmp(a, b) >= 0 ? a : b;
}

Overloaded Template Functions

Suppose we have this "universal" swap function:
template <typename T>
void Swap(T &a, T &b)
{
  T temp = a;
  a = b;
  b = temp;
}
and a trivial use case:
int i = 10, j = 20;
double d = 3.14, e = 2.71;

Swap(i, j); // i=20, j=10
Swap(d, e); // d=2.71, e=3.14
What is the result of this "Swap"?

int a[] = {1, 3, 5, 7,  9, 11};
int b[] = {2, 4, 6, 8, 10, 12};
Swap(a, b); // ???

To get an idea of what's going on, look at what the instantiated function might look like:

void Swap(int a[6], int b[6])
{
  int temp[6] = a; // error: initializing an array with array
  a = b;           // error: assigning an array
  b = temp;        // error: assigning an array
}
This produces errors because T instantiates to int[6]:

g++:

In instantiation of 'void Swap(T&, T&) [with T = int [6]]':
   required from here
error: array must be initialized with a brace-enclosed initializer
   T temp = a;
            ^
error: invalid array assignment
   a = b;
     ^
error: invalid array assignment
   b = temp;
     ^
Microsoft:
error C2075: 'temp' : array initialization needs curly braces
  see reference to function template instantiation 'void Swap(T (&),T (&))' being compiled
  with
  [
    T=int [6]
  ]
error C2106: '=' : left operand must be l-value
error C2106: '=' : left operand must be l-value
We need a function that can deal with arrays, so we overload the template:

  // original template function
template <typename T>
void Swap(T &a, T &b)
{
  T temp = a;
  a = b;
  b = temp;
}
  // overloaded template function
template <typename T>
void Swap(T *a, T *b, int size)
{
  for (int i = 0; i < size; i++)
  {
    T temp = a[i];
    a[i] = b[i];
    b[i] = temp;
  }
}
Reminder: This is overloading because the function name is the same, but the parameters are different. This enables the compiler to call the correct one.

Use:

int a[] = {1, 3, 5, 7,  9, 11};
int b[] = {2, 4, 6, 8, 10, 12};
int size = sizeof(a) / sizeof(*a);

Swap(a, b, size); // calls Swap(int *, int *, int) [with T = int]

Display(a, size); // 2, 4, 6, 8, 10, 12
Display(b, size); // 1, 3, 5, 7, 9, 11
In this example above, to handle C++ arrays, we need to specify the size as the third parameter.

Of course, we could have leveraged the original Swap function:

  // Using the original Swap function
template <typename T>
void Swap(T *a, T *b, int size)
{
  for (int i = 0; i < size; i++)
    Swap(a[i], b[i]);
}
Because the two Swap functions have different parameters, the compiler doesn't get confused when one function calls the other.

Implicit vs. Explicit Instantiations

main1.cppfoobar1.cpp
int foobar(int a);

int main()
{
  int x = foobar(5);

  return x;
}
int foobar(int a)
{
  return a;
}
Compiling and linking commands:
g++ -c main1.cpp 
g++ -c foobar1.cpp
g++ main1.o foobar1.o


main2.cppfoobar2.cpp
template <typename T> T foobar(T a);

int main()
{
  int x = foobar(5);

  return x;
}
template <typename T> 
T foobar(T a)
{
  return a;
}
Compiling and linking commands:
g++ -c main2.cpp 
g++ -c foobar2.cpp
g++ main2.o foobar2.o
Message:
main2.o:main2.cpp:(.text+0x32): undefined reference to `int foobar(int)'
collect2: ld returned 1 exit status
Force the compiler:
// explicit instantiation
template int foobar<int>(int);