What’s The Problem?

What’s the Problem?

Consider the implementation of a min() function for ints:

int min(int a, int b)
{
  return a < b ? a : b;
}

You can’t use the above code for doubles, even though the algorithm is exactly the same.  Only the types change:

int min(double a, double b)
{
  return a < b ? a : b;
}

So, you have to provide a different version of min() for every type that you want to support.

If you want to have a min() for a user-defined type, then the user has to implement it;  the vendor doesn’t know all the types the user will want to implement.

At least in C++, unlike C, you can use a single name for all these functions!

One Solution: Macros

One could use macros to solve the problem:

#define min(a,b) (a) < (b) ? (a) : (b)

Notice the care with which you have to construct this — all those parentheses!  And it still isn’t safe! 

For example, the following:

min(10, 20);
min(25.46, 193.7);

will work with this form, but:

min(p++, myfunc());

will not.  Why?

Macros are not safe, nor are they type-safe.

The Real Solution…

We need some way of writing a function, and parameterizing it, so that the proper definition can be used at compile time. 

In C++, these are called Function Templates, and are defined and used like:

//
//  main.cpp
//  Function Templates
//
//  Created by Bryan Higgs on 10/11/24.
//

#include <iostream>

template <typename Type>
Type min(Type a, Type b)
{
  return a < b ? a : b;
}

int main(int argc, const char * argv[]) 
{
  std::cout << "min(10, 20) = "
            << min(10, 20) << std::endl;
  std::cout << "min(25.46, 193.7) = "
            << min(25.46, 193.7) << std::endl;
  
  return 0;
}

… which produces the following output:

min(10, 20) = 10
min(25.46, 193.7) = 25.46
Program ended with exit code: 0

The above template definition:

template <typename Type>
Type min(Type a, Type b)
{
  return a < b ? a : b;
}

specifies a family of functions that returns the maximum of two values.

Function Template Instantiation

In order to make this program work, the compiler has to do the following for each call to min():

  1. Find the appropriate function template definition.
  2. Construct an instantiation of the function template, causing the appropriate real function definition to be created.
  3. Generate the code to invoke the function.

In other words, the actual function definition comes into being as an automatic side-effect of either invoking, or taking the address of, a template function.

At least, that’s how it’s supposed to be!  

Historically, the use of templates is one of the most troublesome and inconsistently implemented features in C++.  Different compilers have implemented templates differently, and often have had incomplete levels of support for the C++ standard definition of templates. The situation has been improving, and by now is much better.

For example, imagine you’re trying to implement a function that accepts an array of Type, and returns the minimum value contained within the array of that Type:

Thus the function template:

//
//  min1.h
//  Function Templates
//
//  Created by Bryan Higgs on 10/11/24.
//

#ifndef min1_h
#define min1_h

template <typename Type>
Type min(Type array[], size_t size)
{
  Type min_val = array[0];
  for (size_t i = 1; i < size; i++)
  {
    if (array[i] < min_val)
      min_val = array[i];
  }
  return min_val;
}

#endif /* min1_h */

When called like:

//
//  main.cpp
//  Function Templates
//
//  Created by Bryan Higgs on 10/11/24.
//

#include <iostream>
#include "min1.h"

int main(int argc, const char * argv[]) 
{
  int array[] = { 12, 45, 3, 19, 157 };
  std::cout << "Minimum value = "
            << min( array, sizeof(array)/sizeof(int) )
            << std::endl;

  return 0;
}

will be instantiated as follows:

int min(Type array[], size_t size)
{
  int min_val = array[0];
  for (size_t i = 1; i < size; i++)
  {
    if (array[i] < min_val)
      min_val = array[i];
  }
  return min_val;
}

… and produces the following output:

Minimum value = 3
Program ended with exit code: 0

Note that the compiler will only allocate space for functions actually called and therefore instantiated. It will not allocate space for functions that are not called by the program.

Template Parameters

The first line of a template function:

template < comma-separated-list-of parameters >

specifies a list of template parameters. In the above max example, the list consists of a single parameter:

typename Type

which indicates that Type (it’s just a name) is a yet-to-be-determined type that is referred to in the body of the template.

Historically, when templates were introduced, C++ used the keyword class, as in:

template <class T>

The use of the keyword class is potentially confusing. It does not indicate that Type is actually a class; it simply is the original way that C++ used to indicate that Type is a type. Since then, C++ has added a new keyword, typename, which was not present when the first template implementations became available. So, now, we prefer to use the following instead:

typename Type

The use of the keyword class still exists in a lot of code. Its use is simply historical, and should be viewed as equivalent to using typename. The two keywords are totally equivalent in this context. typename is now preferred.

The determination of the actual type of Type is done when the function template is instantiated as a result of a call to the template function, such as:

min(10, 20)

In this case, the compiler determines from the function arguments that Type is of type int.

A function call:

min(10.6, 0.7)

will result in a Type of type double for this instantiation.

The Template Parameter List

A template parameter list consists of a comma-separated list of template parameters enclosed within angle brackets (< and >):

template <typename Type, int size>

You may have as many template parameters as you like.

There are two kinds of template parameters:

  • A template type parameter (of “type type”):
    • typename type (or class type)
  • A template non-type parameter (aka Value Parameters):
    • int size, double value, etc.

Type parameters are by far the most common, but value parameters are essential for many important techniques. We’ll postpone discussion of value parameter usage until later.

Note that the name of each template parameter is chosen by the programmer:

template <typename Glump, int bog>
…

A Simple Function Template

Let’s write a simple function template.  It implements a simple bubble sort on a vector.

Note that the Standard C++ Template Library implements many algorithms, including sorting. This example uses our own implementation of a bubble sort for purposes of simple explanation.

//
//  templbubble.h
//  Function Templates
//
//  Created by Bryan Higgs on 10/11/24.
//

#ifndef templbubble_h
#define templbubble_h

#include <vector>

template<typename TYPE>
void sort(std::vector<TYPE> &v)
{
  size_t n = v.size();
  for (size_t i = 0; i < n - 1; i++)
  {
    for (size_t j = n - 1; i < j; j--)
    {
      if (v[j] < v[j - 1])
      {  // swap v[j] and v[j-1]
        TYPE temp = v[j];
        v[j] = v[j-1];
        v[j - 1] = temp;
      }
    }
  }
}

#endif /* templbubble_h */
//
//  templbubble.cpp
//  Function Templates
//
//  Created by Bryan Higgs on 10/11/24.
//

#include <iostream>
#include <string>
#include <vector>
#include "templbubble.h"

void itTakesAllSorts(std::vector<int>          &vi,
                     std::vector<double>       &vd,
                     std::vector<std::string>  &vs)
{
  std::cout << "Sorting vi (vector<int>)\n";
  sort(vi);      // sort(Vector<int>    &v)
  
  std::cout << "Sorting vd (vector<double>)\n";
  sort(vd);      // sort(Vector<double> &v)
  
  std::cout << "Sorting vs (vector<double>)\n";
  sort(vs);      // sort(Vector<char *> &v)
}

int main(int argc, const char * argv[])
{
  std::vector<int>          vints(4);
  std::vector<double>       vdbls(5);
  std::vector<std::string>  vstrs(3);
  
  vints[0] = 3; 
  vints[1] = 1;
  vints[2] = 5; 
  vints[3] = 6;
  vdbls[0] = 34.5; 
  vdbls[1] = 102.3;
  vdbls[2] = 3.6;  
  vdbls[3] = 97.1;
  vdbls[4] = 45.8;
  vstrs[0] = "Vera"; 
  vstrs[1] = "Mary";
  vstrs[2] = "Fred";
  
  itTakesAllSorts(vints, vdbls, vstrs);
  
  std::cout << std::endl << "ints:    ";
  for (int i = 0; i < vints.size(); i++)
  {
    std::cout << vints[i] << ' ';
  }
  std::cout << std::endl << "doubles: ";
  for (int i = 0; i < vdbls.size(); i++)
  {
    std::cout << vdbls[i] << ' ';
  }
  std::cout << std::endl << "strings: ";
  for (int i = 0; i < vstrs.size(); i++)
  {
    std::cout << vstrs[i] << ' ';
  }
  std::cout << std::endl;

  return 0;
}

… which produces the following output:

Sorting vi (vector<int>)
Sorting vd (vector<double>)
Sorting vs (vector<double>)

ints:    1 3 5 6 
doubles: 3.6 34.5 45.8 97.1 102.3 
strings: Fred Mary Vera 
Program ended with exit code: 0
Next: Template Explicit Serialization

Table of Contents

→ Index