C++/Templates 1

At times we find difficulties in programming, we want to make something work the same for different objects and we often have to design the same thing several times in order to make it work. Suppose you want to make a simple Vector class, as in std::vector. Practically, in C, there is only one way to do it: Keeping type information stored somewhere in your list. This is a very common problem in C, and several people came up with several solutions for that, but now, in C++, the solution to all type-insensitive (those who do not rely on class functions / members) classes and functions came up. If you are one of those interested in the concept of generics (same as type-insensitive), you are on the right place. Welcome to C++ templates.

Introduction

Templates are the mechanism by which C++ implements the generics concept. The following example illustrates two non-generic (type-sensitive) functions for multiplying two numbers, x and y:

int multiply ( int x, int y )
{
    return (x * y);
}

double multiply ( double x, double y )
{
    return (x * y);
}

Two functions that do exactly the same thing, but cannot be defined as a single function because they use different data types.

Function Templates

Templates were made to fullfil the need to design generic code, that work the same way in different situations. Many people get scared when they first look at a template, as the syntax looks too complex for a very simple thing. Although the syntax is indeed a little complex, it is just different, not harder, not easier than other syntax presented in C++.

Syntax

To start a template, you must provide the following declaration:

template<class Type>

or

template<typename Type>

The keywords class and typename have exactly the same meaning in this case, but some compilers may replace the word class for typename when giving you information about the class, as it's often better accepted by programmers.

Type is our generic data type's name, and when the template is to be used, it would be the same as if Type was a typedef for your datatype, and that's exactly how it behaves. Therefore, whenever you use the word Type, you are talking about the data type being used on your template. The following example now illustrates how the multiply function would be written using a template:

template<class Type>
Type multiply ( Type x, Type y )
{
    return (x * y);
}

To use the function, however, the full syntax is a bit weird:

int result = multiply<int> ( 2, 5 ); /* Yields 10 */

As a syntax sugar, C++ provides the option of hiding the type information, case in which the data type used on the function call is assumed. For instance:

int r1 = multiply ( 2, 5 );
int r2 = multiply<int> ( 2, 5 );

Both yield the same result, as they are exactly the same. An important note to take from here is that this is the one of the very few syntax sugars that templates have.

Optionally, a template can have more type options, and the syntax is pretty simple. For a template with three types, called First, Second and Third, we have:

template<class First, class Second, class Third>

And it works exactly as the single-typed template. The template data types are order sensitive, of course, so doing:

multiply<char, int> ( 2, 5 );

Is not the same as doing:

multiply<int, char> ( 2, 5 );

As the order the types are assigned changed.

Class Templates

As another powerful feature of C++, you can also make template classes, which are classes that can have members of the generic type.

The Standard Template Library (STL) relies heavily on the power of template classes for its many functionalities, as the containers std::vector and std::list, for example. Examples on the implementation of both containers will be presented later on, as well as some more.

Syntax

The syntax for template classes is exactly the same as for template functions. A small difference is that you can never hide the type of a template class when you instantiate it.

Therefore, a small class Node, with three members, previous, value and next can be written as:

template<class Type>
class Node
{
public:

    Type value;

    Node* previous;
    Node* next;
};

Notice one important thing: Although the data type for Node pointers previous and next is hidden, the type Type is assumed. The same declarations could be written as:

Node<Type>* previous;
Node<Type>* next;

Also notice that the exact same syntax used for function calling is used for class instantiating. You can hide data types in specific cases, but for legibility and to establish a solid coding convention, you shouldn't, unless you are on the same class as the variable being declared / instantiated.

There is also the possibility of setting a default type, as in:

template<class T1, class T2 = int>

Or

template<class T1, class T2 = DefaultTemplateClass<T1> >

Both syntax are equally valid, and you can use previous types to define next ones (as T1 is the template type for type T2). Note the space between the two closing >, which prevent the compile to read them as one token (left-shift operator).

Note it only works effectively when you have more than one type. When you have only one type, you would be lacking the template argument, causing the compiler to give you an error. For example:

template<class T1 = int>
class Useless
{
public:

    T1 value;
};

Useless value; /* Wrong! */

Although the default type for the template class is valid, you can not lack the type list when instantiating, but it can be empty, as in:

template<class T1 = int>
class Useless
{
public:

    T1 value;
};

Useless<> value; /* Valid */

Note: The default type setting is available only for template classes, functions do not present this feature, as they already set the defaults, as explained before.

Implementation

Now let's get our hands to work on a simple yet useful class, which we'll call Vector. Not to worry with minor problems such as dynamic memory allocation, which is needed in this case (to make the Vector grow when needed and optionally make it shrink when needed), we'll use an imaginary pointer that we believe contains an allocated array for us to use as a storage.

Our Vector class will have two functions: push and pop. We will also define an interesting thing we find in STL's std::vector, the iterators (to walk through the list), together with iterating functions begin and end.

To reach this goal, we will rely on a template class and some new concepts which will be explained with the code. This is how it looks:

template<class Type>
class Vector
{
public:

    typedef typename Type* iterator;

    Vector ( Type* storage, unsigned long storageSize )
    : data(storage), size(0), maxSize(storageSize)
    {
    }

    ~Vector ( void )
    {
        /* Optionally free the allocated buffer here */
    }

    /* Puts the object on the last place in the data array */
    void push ( const Type& object )
    {
        if (size >= maxSize)
          throw std::out_of_range("Attempted to push past the maxSize for Vector");
        data[size] = object;
        size++;
    }

    /* Virtually pops a member by saying size is one less */
    void pop ( void )
    {
        if (0 != size)
          size--;
    }

    /* Returns an iterator to vector's begin */
    iterator begin ( void )
    {
        if (0 == size)
          return end();
        return &data[0];
    }

    /* Returns an iterator to vector's end (after last element) */
    iterator end ( void )
    {
        return (data + size);
    }

private:

    const Type* data;

    unsigned long size;

    const unsigned long maxSize;
};

This illustrates how simple templates can be. Now get your hands to work and, if you know how iterators work, play a little bit with the class; if not, don't worry, a fast and objective explanation will be given soon. If you got curious about the typedef we used to define iterator, head to the section relative to it in this lesson.

  Aside: Iterators


  Iterators are an essential part of STL containers, that use this concept as a base for container walkingthrough. Although they have the same name in all of the various containers, their definition is rather different, as each kind of container uses a different method for storing objects.
  As an example, take our Vector class definition for iterator: a pointer, as simple as that. As our data class member is an array (probably allocated with new[]), we can walk trough its members by simple incrementing / decrementing the pointer and get a reference to the value pointed to by dereferencing it.  The function begin returns an iterator to the first element inside our array (the data pointer itself, in this case), and the function end returns an iterator to the position where a new element will be stored in next push. When our iterator equals end, there are no more elements to be seen. 
  For the definitions of other iterators in STL, check STL sourcecode or your favorite documentation page.

A simple use of our vector class:

Vector<int> v;
Vector<int>::iterator vit;

for ( int i = 0; i < 10; i++ )
{
	v.push ( i );
}

for ( vit = v.begin(); vit != v.end(); vit++ )
{
	std::cout << (*vit) << std::endl;
}

Which then prints numbers from 0 to 10 in new lines, sequentially. It also illustrates the use of iterators to walk trough the list.

As requested by HappyCamper, here is an example of a container template class called List, that uses the same concept of std::list, the linked list.

template<class Type>
class Node
{
public:

    Node ( Node* previous, const Type& val )
    {
        value = val;

        prev = previous;

        if ( previous != NULL )
        {
            previous->next = this;
        }

        next = NULL;
    }

    ~Node ( void )
    {
    }

    Type value;

    Node* prev;
    Node* next;
};

template<class Type>
class _List_Iterator
{
public:

    _List_Iterator ( void )
    {
    }

    _List_Iterator ( Node<Type>* object )
    {
        node = object;
    }

    ~_List_Iterator ( void )
    {
    }

    _List_Iterator& operator = ( const _List_Iterator& it )
    {
        node = it.node;

        return (*this);
    }

    bool operator != ( const _List_Iterator& it )
    {
        return (node != it.node);
    }

    /* Sets internal Node pointer to next node */
    _List_Iterator& operator ++ ( void )
    {
        node = node->next;

        return (*this);
    }

    /* Sets internal Node pointer to previous node */
    _List_Iterator& operator -- ( void )
    {
        node = node->prev;

        return (*this);
    }

    Type& operator * ( void )
    {
        return node->value;
    }

    Node<Type>* node;
};

template<class Type>
class List
{
public:

    typedef typename _List_Iterator<Type> iterator;

    List ( void )
    {
        first = NULL;
        last = NULL;
    }

    ~List ( void )
    {
        Node<Type>* node;
        Node<Type>* next;

        node = first;

        while ( node )
        {
            next = node->next;

            delete node;

            node = next;
        }
    }

    iterator begin ( void )
    {
        return iterator ( first );
    }

    iterator end ( void )
    {
        return iterator ( NULL );
    }

    void push ( const Type& object )
    {
        Node<Type>* node;
        
        node = new Node<Type> ( last, object );

        if ( first == NULL )
        {
            first = node;
        }

        last = node;
    }

    void pop ( void )
    {
        Node<Type>* aux;

        aux = last;

        if ( first == last )
        {
            first = NULL;
            last = NULL;
        }
        else
        {
            last = last->prev;
            last->next = NULL;
        }

        delete aux;
    }

protected:

    Node<Type>* first;
    Node<Type>* last;
};

A new iterator class had to be designed in order to overload the operators (to be the same as our Vector class iterators, in practice). Also notice that, when the template class instantiated (inside another class) is not of the class type, it requires the argument list to be written.

Warning: Both of the classes, Vector and List, were written in request-time, e.g. they didn't go through exhaustive tests to assure its secure execution, it just illustrates the concept of template containers.

We can also easily design our counterpart of STL's std::pair, which we'll name Pair. It goes as follows:

template<class T1, class T2>
class Pair
{
public:

    Pair ( void )
    {
    }

    Pair ( const T1& f, const T2& s )
    {
        first = f;
        second = s;
    }

    ~Pair ( void )
    {
    }

    T1 first;
    T2 second;
};

A pair is a very simple structure that holds two values (hence the term pair) that may be of different types. For such achievement we use two arguments in our template. Function first returns a reference to the first value and, function second, a reference to the second one.

To be continued

Where To Go Next

Topics in C++
Beginners	Data Structures	Advanced
Part of the School of Computer Science