********************
Topic 1b - Templates
********************

Before continuing and introducing data structures, we need to introduce the concept of templates in C++.

Consider the problem of finding the largest item in an array of items.

We can do a very simple linear search to find it.

.. admonition:: Activity
    :class: warning

    Do you think that the logic of this algorithm change depending on the type?


Until now, the function were strongly typed. It lacks flexibility, and C++ dev find a way around this problem by creating **templates**.

There are two types of templates:

*  Function Templates
*  Class Templates

If you know Java, it should be very familiar.


Function Templates
==================

It will be very quick, as function templates are very easy to write.

Declaration
-----------

We will consider the following function template :code:`findMax`:

.. literalinclude:: ../code/topic1b/findMax.cpp
    :language: cpp
    :linenos:

It is short, but summarize everything.

Before the declaration of the function, we define the template argument :code:`Comparable`:

.. literalinclude:: ../code/topic1b/findMax.cpp
    :language: cpp
    :lines: 7

The type you will use will replace :code:`Comparable` if it has the correct properties.

Then in the function declaration, where you would put the type you have :code:`Comparable` instead:

.. literalinclude:: ../code/topic1b/findMax.cpp
    :language: cpp
    :lines: 8

Using a function template
-------------------------

Once define, it is very simple to use the function template:

.. literalinclude:: ../code/topic1b/findMaxMain.cpp
    :language: cpp
    :linenos:

During the compilation the compiler will create the function for each type used.

As no :code:`operator<` was define for :code:`Int` the following line is illegal:

.. literalinclude:: ../code/topic1b/findMaxMain.cpp
    :language: cpp
    :lines: 13

One last thing. Because templates arguments can assume any class type, when deciding on parameter-passing and return-passing conventions, it should be assumed that template arguments are not primitive types.

That is why we have returned by constant reference.

Class Templates
===============

Remember the class :code:`Int` that was memorizing a value of type :code:`int`, it was very limited as only a value of type int could be stored inside.

We will use this example, to show how we can create class templates.

Similarly to the function template, we need to define the template argument. In this case, I will choose :code:`Object`, because I want it to work for any type.

.. literalinclude:: ../code/topic1b/Fig01_21.cpp
    :language: cpp
    :lines: 9

The class template will be called :code:`MemoryCell`, because we want to store object both primitive and class types.

.. literalinclude:: ../code/topic1b/Fig01_21.cpp
    :language: cpp
    :linenos:
    :lines: 9-11,27-29

As you can see we store a type :code:`Object`.

Now we can redefine all the methods by replacing the type :code:`int` by :code:`Object`.

.. literalinclude:: ../code/topic1b/Fig01_21.cpp
    :language: cpp
    :linenos:
    :lines: 9-29

It doesn't change much from the class :code:`Int`, except for the constructor.

Indeed, as we can accept any class type, the default constructor create :code:`Object` with its zero-parameter constructor.

.. literalinclude:: ../code/topic1b/Fig01_21.cpp
    :language: cpp
    :linenos:
    :lines: 13-17

That is basically all that you need to know. After that it is practice, your own research, etc.

.. warning::

    For class templates we don't separate the interface from the implementation, everything is in the header file `.h`.

    Otherwise it is not working properly; there is a way to avoid this issue, but we will not cover it today.