Templates in C++: Passing Types
-------------------------------

C++ provides a powerful technique called **templates** (or **generics**) that
let you pass a *type* to a function or class in a way that allows the compiler
to still do static type checking.

As an example, consider these two functions::

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

    void swap(string& a, string& b) {
        string temp = a;
        a = b;
        b = temp;
    }

The only difference is that one uses the type ``int``, and the other uses the
type ``string``. Templates let you pass the type to the function so you need
write only one function to handle both cases::

    template<class T> 
    void swap(T& a, T& b) {
        T temp = a;
        a = b;
        b = temp;
    }

    // ...

    int x = 3;
    int y = 4;
    swap(x, y);  // T is int

    string s = "cat";
    string t = "dog";
    swap(s, y);  // T is string

The C++ compiler infers at compile-time what the value of the template
variable ``T` ought to be by examining the types of the variables passed to
``swap``. This generic ``swap`` function works with any type of value that has
assignment defined for it.


Generic Algorithms
------------------

C++'s standard template library (STL) implements numerous fundamental data
structures and algorithms in this way. For example, here is how the ``find``
function in the STL is often implemented::

    template<class InputIt, class T>
    InputIt find(InputIt first, InputIt last, const T& value)
    {
        for (; first != last; ++first) {
            if (*first == value) {
                return first;
            }
        }
        return last;
    }

The template here has two input types: one called ``InputIt`` (an input
iterator type), and ``T`` (the type of the objects being searched). In C++,
iterator types are essentially objects that act like pointers, i.e. iterators
are objects that refer to other objects, and can be compared, incremented, and
de-referenced like regular pointers.

The parameters to ``find`` are two iterators, ``first`` and ``last``, that
specify a range of objects. Many programmers find this to be an unusual way of
calling at algorithm, but with practice it soon becomes natural. Plus, this
approach turns out to be extremely flexible, allow you to, for instance,
easily search sub-sequence of an array or vector or any other container where
that makes sense.

For example, here is how you can use the STL ``sort`` function to sort the
"middle" part of an array and a vector::

    int arr[] = {7, 9, 1, -4, 0, 2, 2};
    vector<int> vec = {8, 1, 1, 2, 8, 9, 0, 1};

    sort(arr + 1, arr + 6);
    for(int x : arr) cout << x << ' ';

    cout << '\n';

    sort(vec.begin() + 1, vec.end() - 1);
    for(int x : vec) cout << x << ' ';


Generic Containers
------------------

Another important application of templates in C++ is to create type-safe
collections of objects. For example, ``vector<T>`` is the type of a vector
containing just objects of type ``T``. Type-safe means that you will get a
compiler-time error if you try to put an object that is not of type ``T`` in
it.


Comments on Templates
---------------------

An example of the power (and complexity!) of templates, a technique known as
`template meta-programming
<http://en.wikipedia.org/wiki/Template_metaprogramming>`_ can be used to make
C++ templates perform *any* calculation at compile-time. This actually has
practical uses, such as for fix-sized vectors, or doing small matrix
computations.

While many basic examples of using templates are easy to understand and use,
C++ templates have many subtle rules that make them one of the most complex
features in C++.

A significant problem with C++ templates in practice is that the error
messages they generate, sometimes even for simple errors, can be hundreds
thousands of characters long (see the `The Grand C++ Error Explosion
Competition <http://tgceec.tumblr.com/post/74534916370/results-of-the-grand-c
-error-explosion?is_related_post=1>`_ for some pathological examples of C++
errors --- the winner resulted in an error message almost **six billion**
times the size of the program that produced it). This makes it quite hard to
debug template errors.

Other languages, such as Java, C#, and Ada, implement variations of templates,
but with various different rules, restrictions, and performance
characteristics.


Generics (not) in Go
--------------------

Go_ has a reputation for being a simple language, but some programmers think
it is *too* simple. In particular, many programmers criticize Go_ for its lack
of generics.

Go_ doesn't have a any feature quite like C++ templates, and so this means you
can end up re-writing Go_ functions that are identical except for the type of
a variable, e.g.::

    func maxFloat64(a, b float64) float64 {
        if a > b {
            return a
        } else {
            return b
        }
    }

    func maxString(a, b string) string {
        if a > b {
            return a
        } else {
            return b
        }
    }

Go_ does have a trick for dealing with unknown types: ``interface{}``.
Basically, you can use ``interface{}`` to declare variables that can refer to
any type, e.g.::

    var a interface{}  // the value a refers to can be any type
    a = 5
    fmt.Println(a)     // 5
    a = "cat"
    fmt.Println(a)     // cat

However, you **cannot** write a function like this::

    func max(a, b interface{}) interface{} {
        if a > b {
            return a
        } else {
            return b
        }
    }

There are a couple of problems with this:

- It's not necessarily the case that ``a`` and ``b`` work with the ``>``
  operator.

- For a sensible ``max`` function, ``a``, ``b``, and the function's return
  type should all be the same type. But nothing in ``max`` ensures that they
  are.

If you write a Haskell_ type signature for a ``max`` function, you can see
what ``Go_`` is missing::

    maxGood :: Ord t => t -> t -> t

This says that the two inputs to ``maxGood``, and its output, must all have
the same type ``t``. Furthermore, ``t`` must implement the ``Ord`` type class,
meaning that the inputs to ``maxGood`` must be comparable using ``>``.

The Go_ function using ``interface{}`` would be the same as this Haskell_
function::

    maxWrong :: t -> u -> v

The types for this function need not be the same, and there is no requirement
that ``>`` works for any of them.

The issue of generics in Go_ has been around since Go_ was first released, and
many programmers have strong opinions. Some feel that Go_ desperately needs
generics, while others feel that the benefits of generics don't outweigh the
extra burden they will put on the compiler and the programmer. A number of
proposals have been put forward for adding generics to Go_, but so far the
developers of Go_ haven't committed to adding them.