..  Copyright (C)  Dave Parillo.  Permission is granted to copy, distribute
    and/or modify this document under the terms of the GNU Free Documentation
    License, Version 1.3 or any later version published by the Free Software
    Foundation; with Invariant Sections being Forward, and Preface,
    no Front-Cover Texts, and no Back-Cover Texts.  A copy of
    the license is included in the section entitled "GNU Free Documentation
    License".

.. index:: 
   single: function templates
   pair: templates; function

Function templates
==================

Function overloads allow programmers to reuse function names.
Functions with the same name may or may not accomplish the same task.

What if our functions actually are intended to do exactly the same thing,
but merely on different types?

Function overloads allow us to write functions with the same names and different
parameter lists, but each function still requires its own function body,
even if it's only to call another function.


.. tb-group::
   :name: overload_sum_functions

   .. tb-tab:: Example

      These two overloads each add their parameters, only on different types:

      .. code-block:: cpp

         constexpr int    sum (int a, int b);

         constexpr double sum (double a, double b);

   .. tb-tab:: Run It

      These two overloads each add their parameters, only on different types:

      .. tb-code:: cpp
         :name: ac-sum-without-templates

         #include <iostream>

         constexpr int sum (int a, int b) {
           return a+b;
         }

         constexpr double sum (double a, double b) {
           return a+b;
         }

         int main () {
           std::cout << sum (10,20) << '\n';
           std::cout << sum (1.0,1.5) << '\n';
         }

C++ provides a way to write a single piece of code
that can stand in for an entire *class of functions* that all
do exactly the same thing.

In C++, we can define a **template** for a function.
The template defines a *function generating recipe* 
using a *generic type* as a placeholder.
Templates are created using the ``template`` keyword, 
followed by zero or more template parameters in angle brackets ``<>``.
For example:

.. code-block:: cpp

   template <template-parameters> function-declaration 

.. note:: 

   **Template parameters are optional.**

   It looks strange to have a template with no template parameters,
   but it is perfectly legal. For example, as we will explore as part of
   hash tables, the overloads of ``std::hash<>`` normally do not include
   template parameters:

   .. code-block:: cpp

      struct point {
        int x;
        int y;
      }

      namespace std {
        template <>
        struct hash<point>
        {
            // hash function implementation for a point
        };
      }


.. tb-group::
   :name: sum_function_template_tabbed

   .. tb-tab:: Example

      Using templates, our previous sum functions collapse down to:

      .. code-block:: cpp

         template <class T> 
         constexpr T sum (T a, T b) {  
           return a+b;
         }

   .. tb-tab:: Run It

      .. tb-code:: cpp
         :name: ac-sum-with-templates

         #include <iostream>

         template <class T> 
         constexpr T sum (T a, T b) {  
           return a+b;
         }

         int main () {
           std::cout << sum<int> (10,20) << '\n';
           std::cout << sum<double> (1.0,1.5) << '\n';
         }


When identifying template parameter types,
it is common to see either ``typename`` or ``class``.
As we will see later, a ``class`` defines a type,
so for the purposes of a template, they are the same.
Whether you use 'typename' or 'class' is a matter of preference.

The identifier ``T`` is traditional,
but any valid variable name could be used.
In introductory template tutorials ``AnyType`` is not uncommon.

Templates are normally completely specified in header files.
Because templates are not either declarations or definitions,
it is an error to write a template in a cpp source file and then
try to use it in another source file.

Using templated functions
-------------------------

In short, using functions generated by templates is
not very different from a non-templated function.

You can explicitly provide the type:

.. code-block:: cpp

   std::cout << sum<int> (10, 20) << '\n';
   std::cout << sum<double> (1.0, 1.5) << '\n';
 
Or let the compiler deduce the type:

.. code-block:: cpp

   std::cout << sum (10, 20) << '\n';
   std::cout << sum (1.0, 1.5) << '\n';


Given a template of a single generic type,
take care when mixing types when two or more parameters are involved:

.. code-block:: cpp
   :linenos:

   #include <iostream>

   template <class T>
   constexpr T sum (const T a, const T b) {
     return a+b;
   }

   int main () {
     std::cout << sum <double> (10,1.5) << '\n';  // OK
     std::cout << sum <int>    (10,1.5) << '\n';  // Compiles with warning
     std::cout << sum          (10,1.5) << '\n';  // Compile error

     return 0;
   } 

The call to ``sum <double>`` implicitly converts the ``int``
to ``double`` without warning.

The warning for ``sum <int>`` happens because we have explicitly
declared the function to take type ``int``,
but the second argument is a double.
The warning says that the copy of ``1.5`` passed to sum 
will be truncated to ``1``,
which is a narrowing conversion.

The error is due to the compiler not be able to find a function overload
that meets the calling requirements.
Even though sum is a template,
the compiler will say:

.. code-block:: none

   no matching function for call to 'sum'

   note: candidate template ignored: deduced conflicting types 
   for parameter 'T' ('int' vs. 'double')
   
In the third call to sum, we asked the compiler to deduce the types.
Since the template defines a function with a single type
for both arguments and the return value,
it doesn't know which to choose.
Both ``int`` and ``double`` are equally valid choices.

The examples on lines 9 and 10 are valid because the compiler does not
need to deduce the type, it was explicitly told the type of the function to generate.


Multiple template parameters
----------------------------

A ``sum`` function that only adds numbers of the same type is not particularly useful.
Templates also allow defining multiple types to be used in a template
with each parameter potentially having a different type.

.. code-block:: cpp

   #include <iostream>

   template <typename T1, typename T2>
   constexpr bool are_equal (const T1& a, const T2& b) {
     return (a==b);
   }

   int main () {
     if (are_equal(10, 10.0)) {
       std::cout << "x and y are equal\n";
     } else {
       std::cout << "x and y are not equal\n";
     }
   }

There is no 'rule' that says each template parameter can be used only once
in the function declaration.

.. code-block:: cpp

   template <typename T1, typename T2>
     constexpr T2 foo (const T1& x, const T2& y) {
       T1 tmp_x = x;
       T2 tmp_y = y < 1? 1: y*y;
       while (tmp_y < tmp_x) {
         ++tmp_x;
         tmp_y *= 2;
       }
       T2 result = tmp_y;
       return result;
     }


Non-type template parameters
----------------------------

Not every template parameter has to name a type.
A template parameter can also be a compile-time value.

The following example defines a template
that defines a function that multiplies 
a value of type ``T`` by a provided ``int N``.
The template parameter ``int N`` can be used in the function body
just like any other local variable or function parameter.

Non-type template parameters are constant expressions inside the template body.

.. tb-group::
   :name: non_type_parameter_tabbed

   .. tb-tab:: Example

      .. code-block:: cpp

        template <class T, int N> 
        constexpr T multiply (const T& val) {
          return val * N;
        }

      The ``multiply`` template **must** be called using 
      template parameters

      .. code-block:: cpp

         const double two_pi = multiply<double,2>(3.14159);

   .. tb-tab:: Run It

      .. tb-code:: cpp
         :name: ac-non_type_parameter_template

         #include <iostream>

         // it is possible to forward declare a template
         template <class T, int N> 
         constexpr T multiply (const T& val);

         int main() {
           std::cout << multiply<double,2>(3.14159) << '\n';
           std::cout << multiply<long,3>(10) << '\n';
         }

         // note the definition includes ALL of the declaration
         // including the template information
         template <class T, int N> 
         constexpr T multiply (const T& val) {
           return val * N;
         }

This is exactly what the :container:`std::array <array>` class template does.
As a wrapper around a raw array,
when this container is used, the size of the array
is a required template parameter:

.. code-block:: cpp

   std::array<int,4> numbers {2, 4, 6, 8};

.. note::

   Templates that include non-type template parameters need values for those
   parameters.
   The values may be written explicitly or deduced from function arguments.
   In this ``multiply`` example, the type ``T`` can be deduced from the
   argument, but there is no argument that tells the compiler which value to use
   for ``N``.

   .. code-block:: cpp

     template <class T, int N> 
     constexpr T multiply (const T& val) {
       return val * N;
     }

     int main() {
       multiply(3);     // compile error: multiply times what?
     }



-----

.. admonition:: More to Explore

   - From cppreference.com:

     - :lang:`Template parameters <template_parameters>`
     - :lang:`Implicit type conversion <implicit_conversion>` and
       :lang:`arithmetic conversions <operator_arithmetic#Conversions>`
     - The utility function :utility:`std::hash <hash>`