View source for Generic programming: class templates, function templates, templates and inheritance, vectors, iterators

==Overview==

Templates are a feature of the C++ programming language that allow code to be written without consideration of the data type with which it will eventually be used. Templates support generic programming in C++. Templates are of great utility to programmers in C++, especially when combined with multiple inheritance and operator overloading. The C++ Standard Template Library (STL) provides many useful functions within a framework of connected templates.

There are two kinds of templates.  A '''function template''' behaves like a function that can accept arguments of many different types.  For example, the C++ Standard Template Library contains the function template <code>max(x, y)</code> which returns either ''x'' or ''y'', whichever is larger.  <code>max()</code> could be defined like this:

 template <class a>
 a max(a x, a y)
 {
  if (x < y)
   return y;
  else
   return x;
 }

This template can be called just like a function:

 cout << max(3, 7);   // outputs 7

The compiler determines by examining the arguments that this is a call to <code>max(int, int)</code> and ''instantiates'' at compile time a version of the function where the type <code>a</code> is <code>int</code>. For all calls to the template using different types, the compiler will generate a corresponding code instance of the template with the respective types. Multiple calls with the same type will all use the same generated code. 

This works whether the arguments <code>x</code> and <code>y</code> are integers, strings, or any other type for which it makes sense to say "<code>x &lt; y</code>". If you have defined your own data type, you can use operator overloading to define the meaning of <code>&lt;</code> for your type, thus allowing you to use the <code>max()</code> function. While this may seem a minor benefit in this isolated example, in the context of a comprehensive library like the STL it allows the programmer to get extensive functionality for a new data type, just by defining a few operators for it.  Merely defining <code>&lt;</code> allows a type to be used with the standard <code>sort()</code>, <code>stable_sort()</code>, and <code>binary_search()</code> algorithms; data structures such as <code>set</code>s, heaps, and associative arrays; and more. 

As a counterexample, the standard type <code>complex</code> does not define the <code>&lt;</code> operator, because there is no strict order on complex numbers.  Therefore <code>max(x, y)</code> will fail with a compile error if ''x'' and ''y'' are <code>complex</code> values.  Likewise, other templates that rely on <code>&lt;</code> cannot be applied to <code>complex</code> data.  Unfortunately, compilers historically generate somewhat esoteric and unhelpful error messages for this sort of error. 

A '''class template''' extends the same concept to classes.  Class templates are often used to make generic containers. For example, the STL has a linked list container. To make a linked list of integers, one writes <code>list&lt;int&gt;</code>. A list of strings is denoted <code>list&lt;string&gt;</code>. A <code>list</code> has a set of standard functions associated with it, which work no matter what you put between the brackets.

===Advantages and disadvantages===

Some uses of templates, such as the <code>max()</code> function, were previously filled by function-like preprocessor macros.  For example, here is a <code>max()</code> macro:

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

Both macros and templates are expanded at compile time.  Macros are always expanded inline; templates can also be expanded as inline functions when the compiler deems it appropriate.  Thus both function-like macros and function templates have no run-time overhead.

However, templates are generally considered an improvement over macros for these purposes.  Templates are type-safe.  Templates avoid some of the common errors found in code that makes heavy use of function-like macros.  Perhaps most importantly, templates were designed to be applicable to much larger problems than macros.

Templates can be used during refactoring operations, in cases where the same portions of code (or functions) are repeated but applied to different types. 

There are four primary drawbacks to the use of templates.  

*First, many compilers historically have very poor support for templates, so the use of templates can make code somewhat less portable.  
*Second, almost all compilers produce confusing, unhelpful error messages when errors are detected in template code, due to the fact that the executed code is generated by the compiler and does not appear in the original code. This can make templates difficult to develop and fix.  
*Third, each use of a template may cause the compiler to generate extra code (an ''instantiation'' of the template), so the indiscriminate use of templates can lead to code bloat, resulting in excessively large executables.
*Fourth, separate compilation of template definitions and template function declarations is not yet implemented in most compilers, resulting in the programmer having to place template function definitions in the same file where the template function is invoked. This can be solved by putting the template definition in an implementation file and <code>#include</code> it in any other implementation file that uses this template. This solution is an exception to the general rules governing the use of header files and program files in separate compilation.

==Function templates==

Consider a very simple function to swap the values of two variables passed by reference: 

 void swapValues(int& variable1, int& variable2)
 {
    int temp;
 
    temp = variable1;
    variable1 = variable2;
    variable2 = temp;
 }

Note that this function will only be able to swap values of type <code>int</code>. Yet, the swapping of other kinds of values should be possible, following exaclty the same logic, but applied to different types. So if we want to have a function to swap two values of type <code>char</code>, we must write:  

 void swapValues(char& variable1, char& variable2)
 {
    char temp;
 
    temp = variable1;
    variable1 = variable2;
    variable2 = temp;
 }

and do the same for any other type we may want to swap values for. This will lead to code duplication, which is (1) cluttering the code and (2) error-prone and (3) difficult to maintain. What we want is to be able to write the following generic version of the <code>swapValues()</code> function: 

 void swapValues(anyType& variable1, anyType& variable2)
 {
    anyType temp;
 
    temp = variable1;
    variable1 = variable2;
    variable2 = temp;
 }

This is precisely what '''function templates''' allow you to do, using the following syntax: 

===Syntax===

A function template is preceded by a '''template prefix''':

 template<class T>

that informs the compiler that the function declaration or definition that follows is a function template that has <code>T</code> has its '''type parameter'''. The identifier <code>T</code> is then used in the function declaration and definition in places where this "variable type" is to be used. In theory, the function template overloads this function with all possible types that <code>T</code> can be, i.e. virtually any type. In effect, the function is overloaded only for those types that are effectively used in a given program. It is also possible to define function templates with more than one type parameter: 

 template<class T1, class T2>

Function templates declarations and definitions should both be preceded by the template prefix.

===Example===  

 //Program to demonstrate a function template.
 #include <iostream>
 using std::cout;
 using std::endl;
 
 //Interchanges the values of variable1 and variable2.
 //The assignment operator must work for the type T.
 template<class T>
 void swapValues(T& variable1, T& variable2)
 {
    T temp;
 
    temp = variable1;
    variable1 = variable2;
    variable2 = temp;
 }
 
 int main( )
 {
    int integer1 = 1, integer2 = 2;
    cout << "Original integer values are "
         << integer1 << " " << integer2 << endl;
    swapValues(integer1, integer2);
    cout << "Swapped integer values are "
         << integer1 << " " << integer2 << endl;
 
    char symbol1 = 'A', symbol2 = 'B';
    cout << "Original character values are: "
         << symbol1 << " " << symbol2 << endl;
    swapValues(symbol1, symbol2);
    cout << "Swapped character values are: "
         << symbol1 << " " << symbol2 << endl;
    return 0;
 }

Notice that you need not use any special notation when calling a function that is defined as a function template. Upon compilation, the compiler will recognize that the function being called is a template, will generate the corresponding function instance and make it available at run-time. 

==Class templates==

The same principle and syntax can be applied to classes, yielding '''class templates'''. Class templates are instantiated at compile-time in a manner similar to function templates. However, due to the fact that they themselves represent types (a class being a type), their use to declare variables requires the use of a special notation upon invocation: 

===Syntax===

As for function templates, class templates make use of the template prefix: 

 template<class T>

Once the class template is declared and defined, objects of this class can be instantiated using the following syntax, where <code>ClassName</code> is the name of the template class, <code>typeParameter</code> is the actual parameter type of the template, and <code>variableName</code> is the name of the object instantiated: 

 ClassName<typeParameter> variableName;

or more specifically (see the example below for a definition of the template class <code>Pair</code>): 

 Pair<int> score; 
 Pair<char> seats; 

In this case, the type of the variables are said to be <code>Pair<int></code> and <code>Pair<char></code>, respectively. In cases where you want to pass an object instance of a template class to a function, the following can be used in order to pass a pair of integers: 

 int addUp(Pair<int>& thePair); 

In this case, the parameter of the function is of type <code>Pair<int></code>. Note taht in this case, the function defined is not a template, as it uses an instance of the <code>Pair</code> template, and thus does not refer to any type parameter. You can even create a function that receives a class template object as a parameter, such as in: 

 template<class T>
 int addUp(Pair<T>& thePair); 

Note that in this case, the function defined has itself to be a template function, as it needs to refers to a type parameter.

===Example===

The following program defines a class template for a simple generic class holding a pair of values of any type, defined by the template parameter. In this case, both values held are of the same type; note that it is possible to define a similar class template to hold values of differing types by adding an additional type parameter to the template: 
  
 #include <iostream>
 using std::cout;
 using std::endl; 
 
 //Class for a pair of values of type T:
 template<class T>
 class Pair
 {
 public:
    Pair( );
    Pair(T firstValue, T secondValue);
    void setFirst(T newValue);
    void setSecond(T newValue);
    T getFirst( ) const;
    T getSecond( ) const;
 private:
    T first;
    T second;
 };
 
 template<class T>
 Pair<T>::Pair(T firstValue, T secondValue)
 {
    first = firstValue;
    second = secondValue;
 }
 
 template<class T>
 void Pair<T>::setFirst(T newValue)
 {
    first = newValue;
 }
 
 template<class T>
 T Pair<T>::getFirst( ) const
 {
    return first;
 }
 
 int main( )
 {
    Pair<char> p('A', 'B');
    cout << "First is " << p.getFirst( ) << endl;
    p.setFirst('Z');
    cout << "First changed to " << p.getFirst( ) << endl;
 
    return 0;
 }

As long as the methods for a class template are not using the template type, they are to be defined exactly as for non-template classes methods. However, if the methods are refering to the class template's type parameter(s), these methods have themselves to be defined as function templates. Note that as these methods are being defined, the scope resolution operator uses <code>Pair<T></code> as the name for the class where the method resides. Also note that, somewhat curiously, the name of the constructor does not follow this same logic, and is defined as <code>Pair()</code> and not <code>Pair<T>()</code> as some might expect, and similarly for the destructor.

==Vectors==

A vector can be thought of as an array whose size can grow and shrink as the execution of the program goes. This is different from standard C++ arrays, who are of fixed size, or, in the case of dynamically allocated arrays, who have to be manually allocated/deallocated in order to grow/shrink during execution (see the lecture on [[cpp pointers|pointers]]). In C++, vectors can be used through the <code>vector<T></code> class template, as defined in the Standard Template Library (STL). This generic class is widely used and has two definite advantages over standard dynamically-allocated arrays: 

* A <code>vector</code> can contain values of any type, being implemented as a template class. 
* The <code>vector</code> template class encapsulates the memory management duties necessary for the shrinking/growing at run-time. In fact, the vector class is internally represented by a standard dynamically-allocated data structure. 

===Syntax===

The <code>vector</code> template is defined in the eponymous library <code>vector</code>, which places this template in the <code>std</code> namespace. Thus, any file refering to the <code>vector</code> class should include the following lines: 

 #include <vector> 
 using namespace std;

In order to declare a <code>vector</code>, one has to specify the type parameter of the <code>vector</code> template, such as: 

 vector<int> v; 

which declares an empty vector of integers named v. In order to initialize a <code>vector</code>, one has to rely on the constructor of the base type of the array, such as in: 

 vector<int> v(10); 

which declares a <code>vector</code> of 10 integers, all initialized to 0. Note that if one wants to create an initialized <code>vector</code> of values of a user-defined type, such as in: 

 vector<MyClass> v(10); 

then the default constructor for <code>MyClass</code> must properly (allocate and) initialize the data members of the class. Note that  other constructors are also usable in a similar manner. The elements of the vector are refered to using the standard square brackets array notation: 

 v[i]

However, note that this notation cannot be used on uninitialized <code>vector</code> elements, i.e. the square brackets notation can be used to refer to existing elements, but cannot be used to initialize new elements. In order to initialize new elements (after the initial declaration such as in <code>vector<int> v(10)</code>), the <code>vector</code> member function <code>push_back()</code> must be used, which will add one element at the end of the <code>vector</code>: 

 vector<int> v; 
 v.push_back(42); 

Once an element has been initialized either through declaration or through the <code>push_back()</code> method, it can be assigned other values using the square bracket notation. The <code>vector</code> class template also provides a <code>size()</code> method that returns the number of elements in the <code>vector</code>. That crucial information allows you (for example) to loop through a <code>vector</code>: 

 for(int i = 0; i < v.size(); i++)
   cout << v[i] << endl;

Note that using the square brackets notation to refer to an element out of the initialized bounds of the <code>vector</code> will result in erratic program behavior, as with dereferencing wild pointers (which it is, in fact, due to the internal pointer implementation of <code>vector</code>).

You can use the <code>=</code> (assignment) operator to assign one vector to another, for example 

 v1 = v2

so long as they are vectors of the same type (e.g. both <code>vector<int></code> or <code>vector<double></code>). In this case the contents of <code>v1</code> are overwritten with the contents of <code>v2</code> and <code>v1</code> is truncated or extended to be the same length as <code>v2</code>.

You might also consider using the <code>at()</code> function in preference to the square brackets. <code>v.at(92)</code> is the same as <code>v[92]</code> except that it will terminate the program if <code>v[92]</code> does not exist (see "behavior" below), whereas <code>v[92]</code> will result in erratic program behavior. The square bracket notation is widely used in other programming languages and in writing about programming generally.

===Example===

 #include <iostream>
 #include <vector>
 using namespace std;
 
 int main( )
 {
    vector<int> v;
    cout << "Enter a list of positive numbers.\n"
         << "Place a negative number at the end.\n";
 
    int next;
    cin >> next;
    while (next > 0)
    {
        v.push_back(next);
        cout << next << " added. ";
        cout << "v.size( ) = " << v.size( ) << endl;
        cin >> next;
    }
 
    cout << "You entered:\n";
    for (unsigned int i = 0; i < v.size( ); i++)
        cout << v[i] << " ";
    cout << endl;
 
    return 0;
 }

===Two-dimensional vectors===

A two-dimensional vector in C++ is just a vector of vectors. For example, you could define a two-dimensional vector of integers as follows:

 vector<vector<int> >   v2;

Note the space between <code><int></code> and the second <code>></code>. If you have them next to each other, as in <code>>></code>,the compiler interprets it as an operator and flags it as an error. This definition gives you an empty two-dimensional vector. If you wanted to grow it with <code>push_back()</code>, you would have to push back a one-dimensional vector, not a single <code>int</code>. For example:

 vector<int> v(5);
 v2.push_back(v);

To initialise a two-dimensional vector to be of a certain size, you first have to initialise a one-dimensional vector and then use this to initialise the two-dimensional one:

 vector<int> v(5);
 vector<vector<int> >   v2(8,v);

You can picture <code>v2</code> as a two-dimensional vector consisting of eight rows with five integers in each row. You may refer to individual elements of a two-dimensional vector by using two subscripts; the following sets the third element of the fifth row of <code>v2</code> to 99:

 v2[4][2] = 99;  // remember that the first element of the first row is v2[0][0]

The following procedure would display a two-dimensional vector of int:

 void display (const vector<vector<int> >& vy)
 {  for (int i = 0; i < vy.size(); i++)       // loops through each row of vy
   {  for (int j = 0; j < vy[i].size(); j++)  // loops through each element of each row 
          cout << vy[i][j] << " ";            // prints the jth element of the ith row
      cout << endl;
   }
 }

===Vectors as parameters===

Let us consider a function that returns the sum of the elements of a vector of integers:

 int total(vector<int> v)
 {  int  total = 0;
    for (int i = 0; i < v.size(); i++)
       total += v[i];
    return total;
 }

Note that the vector here is passed by value, meaning that the vector's data will be copied for use locally. If the vector is small, there is no problem, but if it is large, then the parameter-passing itself could consume a lot of resources. For this reason it is a good habit to pass vectors by reference, and use the const keyword to ensure that the data doesn't get inadvertently modified. Here is a function that takes as its arguments a vector of integers and an integer. It returns true if the integer is in the vector.

 bool isin(const vector<int>& v, int a)
 {  for (int i = 0; i < v.size(); i++)
       if (v[i] == a) return true;
    return false;
 }

Let us look at the following code fragment for loading words into a vector:

 string s;
 vector<string> v;
 while (cin >> s)
    v.push_back(s);

The system will continue to populate the vector <code>v</code> until the input stream fails. The following procedure also adds new words to a vector but does not store duplicates:

 void add_word(vector<string>& vs, string s) // the procedure modifies the vector, 
                                             // so we pass by reference (without const)
 {  for (int i = 0; i < vs.size(); i++ )
       if (s == vs[i]) return;               // don't add the word as it's 
                                             // already in the vector
    vs.push_back(s);
 } 

We could call this procedure thus:

 string s;
 vector<string> v;
 while (cin >> s)
    add_word(v,s);

===Pitfalls===

*Vectors are simple containers of homogeneous elements that take care of memory allocation of their elements. However, a vector's well behavior depends (with regards to assignation, copy, etc) on the well-behaved definition of the vectors's base type (i.e. the type of the elements of the vector). For example, when you use the constructor with an integer argument, vectors of numbers are initialized to zero of the number type. If the vector base type is a class type, the default constructor is used for the initialization of the vector's elements. If this constructor is not well defined, the use of the vector class as a container for elements of this type will be broken. 

*Same for the assignment operator. The assignment operator on vectors does an element-by-element assignment to the vector on the left-hand-side of the assignment operator (increasing the capacity and reserving memory as needed). Thus, provided the assignment operator on the base type makes an independent copy of an element of the base type, the assignment operator on the vector will make  an independent copy, not an alias, of the vector on the right-hand-side of the assignment operator.

*When you use vectors you must take care that you do not try to reference an element beyond the bounds of the vector by using a subscript outside the valid values for that vector - for example, given the declaration <code>vector <int> v(4)</code> trying to access <code>v[-1]</code> or <code>v[4]</code> or <code>v[99]</code> given the valid range [0..3] of the index of the vector. The run-time system will not check this for you and you may find yourself using values from undefined portions of memory or, worse, overwriting data. At best the run-time system might issue a segmentation fault error if you try to use a subscript that is way out of range.

*Last but not least, vectors should be used only when necessary. Because vectors in C++ are so flexible and versatile, novice programmers are inclined to overuse them. For example, if you are writing a program that reads in a file of numbers and outputs the largest. Some programmers, especially those who have just discovered vectors, will read the entire file of numbers into a vector and will then search through the vector looking for the highest. But a moment's thought will show that the vector here is not serving any purpose. You only need to inspect the numbers one at a time, and you can do that when you read them from the file in the first place. In a similar manner, passing vectors by value, or making copies of vectors, when unnecessary, can lead to tremendous waste of system memory. Unnecessary vectors, apart from being a waste of computer storage, tend to clutter a program and, often, to confuse the programmer. The vector is a very useful tool, but don't use it always and for everything.

==The Standard Template Library==

The Standard Template Library (STL) contains a range of container template classes. The <code>vector</code> class is one of them. Another is the <code>list</code> class. To use the list container class you should <code>#include</code> the <code><list></code> library. Lists are like vectors in that they are template classes and can hold collections of types, such as objects or integers. They are declared as follows:

 list<int> ilist;  // create a list of integers

The <code>list</code> class supports the member functions <code>push_back()</code> and <code>push_front()</code>, which work as you might expect. e.g.

 ilist.push_back(1);  //  1
 ilist.push_back(2);  //  1 2
 ilist.push_front(3); //  3 1 2
 ilist.push_front(4); //  4 3 1 2

Other container classes include the <code>deque</code> (for "double-ended queue"). Also the <code>set</code>, which you can think of as a binary search tree, the <code>multiset</code> (like a <code>set</code> but allowing duplicates), the <code>map</code>, which is a binary search tree of key-value pairs, and a <code>multimap</code> (a <code>map</code> allowing duplicates). Specialised versions of these are also available - the <code>stack</code>, the <code>queue</code> and the <code>priority queue</code>. This last is like a <code>queue</code> but the next item to get removed is not necessarily the one that has been there longest (as in a regular <code>queue</code>) but the one with the highest value on some attribute. For instance, if age were the attribute, then the person at the "front" of the queue would be the oldest person in the queue.

===Iterators===

Each of the STL container classes has its own type of iterator. An iterator is a construct (typically an object of some iterator class) that allows you to cycle through the data items stored in a data structure so that you can perform whatever action you want on each data item in the data structure. 

An iterator is like a pointer, but is a C++ object and therefore has its own functionality. For example, as with a pointer, you can apply the dereferencing operator to an iterator to get at the thing it is pointing at, but unlike a pointer, you can also use the auto-increment and auto-decrement operators meaning "Go on to the next item," or "Go back to the previous item." (You can use <code>++</code> and <code>--</code> with a pointer but only if it is pointing at an element of an array. You cannot use them to move along a linked list or a binary tree. With iterators, you can.)

Iterators allow you to move along lists, using the <code>begin()</code> and <code>end()</code> member functions as reference points. Note that, as with vectors, <code>end()</code> is actually the post-ultimate position, i.e. whereas <code>begin()</code> is the position of the first item in the structure, <code>end()</code> is a position after the last one. You declare an iterator variable and use it as an index to be moved along the list, much as you might use a pointer.

 list<int>::iterator intiter;  // declare an iterator; each container class has its own iterator type
 intiter = ilist.begin();

To move an iterator along the list, use the <code>++</code> and <code>--</code> operators. The following procedure prints the contents of a list:

 list<int> ilist;
 ...
 list<int>::iterator intiter;
 for (intiter = ilist.begin(); intiter != ilist.end(); intiter++)
   cout << *intiter  << " ";

<code>insert()</code> takes an iterator and an item to insert, e.g.

 ilist.insert(intiter, 5);      //  inserts a 5 before the item intiter is pointing at
 ilist.insert(ilist.end(), 6);  // equivalent to a push_back()

<code>erase()</code> takes an iterator and removes the item from the list, e.g.

 ilist.erase(intiter);      // remove selected item
 intiter = ilist.end();
 intiter--;
 ilist.erase(intiter);      // last three lines equivalent to pop_back()
 // You can't do arithmetic with iterators, eg you can't say ilist.end() - 1.

===Example===

The following example (taken from Savitch, Chapter 17), contains the definition of a <code>ListIterator</code> template class that can be used upon data structures that are based on a linked list, e.g. stacks, queues, etc (as provided here as the <code>Node</code> template class). Note that the <code>Node</code> and <code>ListIterator</code> template classes have been placed into the same namespace, as the two are itimately related, and are not very useful without the other. Note that the decrement operator for the <code>ListIterator</code> has not been defined out of simplicity. 


 //This is the header file iterator.h. This is the interface for the class ListIterator,
 //which is a template class for an iterator to use with linked lists of items of type T.
 #ifndef ITERATOR_H
 #define ITERATOR_H
 
 namespace ListNodeSavitch
 {
     template<class T>
     class Node
     {
     public:
         Node(T theData, Node<T>* theLink) : data(theData), link(theLink){}
         Node<T>* getLink( ) const { return link; }
         const T getData( ) const { return data; }
         void setData(const T& theData) { data = theData; }
         void setLink(Node<T>* pointer) { link = pointer; }
     private:
         T data;
         Node<T> *link;
     };  
  
 
     template<class T>
     class ListIterator
     {
     public:
         ListIterator( ) : current(NULL) {}  
 
         ListIterator(Node<T>* initial) : current(initial) {}
 
         const T operator *( ) const { return current->getData( ); }
         //Precondition: Not equal to the default constructor object,
         //that is, current != NULL.
         //This does not allow to use the dereferenced object as an lvalue (i.e. the left hand side in an equation). 
  
         ListIterator operator ++( ) //Prefix form
         {
             current = current->getLink( );
             return *this;
         } 
 
         ListIterator operator ++(int) //Postfix form
         {
             ListIterator startVersion(current);
             current = current->getLink( );
             return startVersion;
         } 
 
         bool operator ==(const ListIterator& rightSide) const
         { return (current == rightSide.current); }
  
         bool operator !=(const ListIterator& rightSide) const
         { return (current != rightSide.current); }
  
         //The default assignment operator and copy constructor 
          //should work correctly for ListIterator,
     private:
         Node<T> *current;
     }; 
 
 }//ListNodeSavitch 
 
 #endif //ITERATOR_H

As can be seen in this example, the <code>ListIterator</code> class is nothing but an abstraction encapsulating a pointer to the current element pointed to by the iterator object, along with operators defined in order to move from one element to the other, following the linked list (as provided by the <code>Node</code> class). The use of the iterator operators permits the programmer to use the <code>Node</code> objects without even be aware that it is implemented as a linked list. 

The <code>ListIterator</code> class can be used for any class based on a linked list structure that uses the template class <code>Node</code>. What follows is a <code>Queue</code> template class declaration using the previously defined <code>Node</code> and <code>ListIterator</code> template classes.   

 //This is the header file queue.h. This is the interface for the class Queue,
 //which is a template class for a queue of items of type T, including iterators.
 #ifndef QUEUE_H
 #define QUEUE_H
 #include "iterator.h"
 using namespace ListNodeSavitch;
 
 namespace QueueSavitch
 {
     template<class T>
     class Queue
     {
     public:
         typedef ListIterator<T> Iterator;
 
         Queue( );
         Queue(const Queue<T>& aQueue);
         Queue<T>& operator =(const Queue<T>& rightSide);
         virtual ~Queue( );
         void add(T item);
         T remove( );
         bool isEmpty( ) const;
 
         Iterator begin( ) const { return Iterator(front); }
         Iterator end( ) const { return Iterator( ); }
         //The end iterator has end( ).current == NULL.
         //Note that you cannot dereference this iterator.
     private:
         Node<T> *front;//Points to the head of a linked list. 
                        //Items are removed at the head
         Node<T> *back; //Points to the node at the other end of the linked list.
                        //Items are added at this end.
     };
 
 }//QueueSavitch
 
 #endif //QUEUE_H

As shown in the following implementation file, the member functions of the <code>Queue</code> class behave as the following: 

The member function <code>begin()</code> returns an iterator located at the front of the queue, i.e. the head node of the linked list.   Each application of the <code>++</code> operator moves the iterator to the next node. Thus, using <code>begin()</code> and <code>++</code>, you can construct a loop that will scan over all the nodes in a queue named <code>q</code>, using an iterator name <code>i</code> as follows:

 for (i = q.begin(); (stopping condition); i++)
  process *i;

The member function <code>end()</code> returns a "null iterator", i.e. an iterator whose pointer is NULL. As, in the definition of the member functions to add/delete items, the <code>link</code> pointer is set to NULL, this permits to check we have reached the end of the queue. Using the member <code>end()</code>, we can thus rewrite our preceding loop as: 

 for (i = q.begin(); i == q.end(); i++)
  process *i;

Note that <code>q.end()</code> signifies that we have gone beyond the last element, not that we are currently pointing at the last element. 

 //This is the file queue.cpp. This is the implementation of the template class Queue.
 //The interface for the template class Queue is in the header file queue.h.
 #include <iostream>
 #include <cstdlib>
 #include <cstddef>
 #include "queue.h"
 using std::cout;
 using namespace ListNodeSavitch; 
 
 namespace QueueSavitch
 { 
 
 //Uses cstddef:
 template<class T>
 Queue<T>::Queue( ) : front(NULL), back(NULL)
 {
     //Intentionally empty.
 }
 
 //Uses cstddef:
 template<class T>
 bool Queue<T>::isEmpty( ) const
 {
     return (back == NULL); //front == NULL would also work
 }  
 
 //Uses cstddef:
 template<class T>
 void Queue<T>::add(T item)
 {
     if (isEmpty( ))
        front = back = new Node<T>(item, NULL); //sets bothfront and back to point to the only node
    else
    {
        back->setLink(new Node<T>(item, NULL));
        back = back->getLink( );
    }
 }  
 
 //Uses cstdlib and iostream:
 template<class T>
 T Queue<T>::remove( )
 {
     if (isEmpty( ))
     {
         cout << "Error:Removing an item from an empty queue.\n";
         exit(1);
     }  
 
     T result = front->getData( ); 
 
     Node<T> *discard;
     discard = front;
     front = front->getLink( );
     if (front == NULL) //if you removed the last node
         back = NULL; 
 
     delete discard; 
 
     return result;
 } 
 
 template<class T>
 Queue<T>::~Queue( )
 {
     T next;
     while (! isEmpty( ))
        next = remove( ); //remove calls delete.
 } 
 
 //Uses cstddef:
 template<class T>
 Queue<T>::Queue(const Queue<T>& aQueue)
 {
     if (aQueue.isEmpty( ))
         front = back = NULL;
     else
     {
         Node<T> *temp = aQueue.front; //temp moves through the nodes from front to back of aQueue. 
 
         back = new Node<T>(temp->getData( ), NULL);
         front = back;
         //First node created and filled with data.
         //New nodes are now added AFTER this first node.  
 
         temp = temp->getLink( );//temp now points to second node or NULL if there is no second node. 
 
         while (temp != NULL)
         {
             back->setLink(new Node<T>(temp->getData( ), NULL));
             back = back->getLink( );
             temp = temp->getLink( ); 
 
         }
         //back->link == NULL
     }
 }
 
 //Uses cstddef:
 template<class T>
 Queue<T>& Queue<T>::operator =(const Queue<T>& rightSide)
 {
     if (front == rightSide.front) //if the queues are the same
         return *this;
     else                          //send left side back to freestore
     {
         T next;
         while (! isEmpty( ))
             next = remove( );     //remove calls delete.
     }  
 
     if (rightSide.isEmpty( ))
     {
         front = back = NULL;
         return *this;
     }
     else
     {
         Node<T> *temp = rightSide.front; //temp moves through the nodes from front to back of rightSide. 
 
         back = new Node<T>(temp->getData( ), NULL);
         front = back;
         //First node created and filled with data.
         //New nodes are now added AFTER this first node. 
 
         temp = temp->getLink( ); //temp now points to second node or NULL if there is no second node.
 
         while (temp != NULL)
         {
             back->setLink(new Node<T>(temp->getData( ), NULL));
             back = back->getLink( );
             temp = temp->getLink( );
         }
          //back->link == NULL; 
  
          return *this;
      }
 } 
 }//QueueSavitch

The following program uses the <code>Queue</code> template class: 

 //Program to demonstrate use of the Queue template class with iterators.
 #include <iostream>
 #include "queue.h"//not needed
 #include "queue.cpp"
 #include "iterator.h"//not needed
 using std::cin;
 using std::cout;
 using std::endl;
 using namespace QueueSavitch;
 
 int main( )
 {
     char next, ans;
 
     do
     {
         Queue<char> q;
         cout << "Enter a line of text:\n";
         cin.get(next);
         while (next != '\n')
         {
             q.add(next);
             cin.get(next);
         }  
 
         cout << "You entered:\n";
         Queue<char>::Iterator i;  
 
         for (i = q.begin( ); i != q.end( ); i++)
             cout << *i;
         cout << endl;  
 
         cout << "Again?(y/n): ";
         cin >> ans;
         cin.ignore(10000, '\n');
     }while (ans != 'n' && ans != 'N');  
 
     return 0;
 }

=References=

*[http://en.wikipedia.org/wiki/Template_%28programming%29 C++ templates]
*[[image:Sav_ch07.ppt|Walter Savitch, Absolute C++, Chapter 7]]
*[[image:Sav_ch16.ppt|Walter Savitch, Absolute C++, Chapter 16]]
*[[image:Sav_ch17.ppt|Walter Savitch, Absolute C++, Chapter 17]]
*[[image:Sav_ch19.ppt|Walter Savitch, Absolute C++, Chapter 19]]
*[[image:Generic pr.ppt|Emil Vassev, Joey Paquet, Generic programming using inheritance and templates, lecture slides, COMP6441]]
*[http://www.dcs.bbk.ac.uk/~roger/cpp/ C++ notes, by Roger Mitton and Stephen Connolly]