CSCI-1200 Computer Science II
Summer, 2002
Worksheet 13
Collection Classes, Templates

Reading: Deitel & Deitel 3.21, Chap. 12

Collection Classes

A collection class (also known as a container class) is a class which contains a number of elements of some other class. For example, you could write a program for a class Set, which would contain a number of items of a particular type. It has the restriction that no two items be the same. Your Set class might have public member functions such as the following:

void AddToSet(Elementtype element)

adds a new element to the set only if the set does not already contain that element.

bool IsInSet(Elementtype element)

returns true if element were in the set, or false if it were not.

int GetSize()

returns the number of elements in the set.

ostream & operator«(ostream &os, Set &S)

writes on ostream os the elements stored in the set.

Notice that this description of the collection class Set says nothing about how such a set would be implemented, or what the private data members would be. One obvious approach would be to have a private array of data elements, but there are other possibilities as well.

You should make a distinction between the number of elements in the set (typically zero when the set is constructed), and the size of the array, which is the maximum number of elements that the set can contain. During the run of a program the number of elements in the set should grow (and perhaps shrink) dynamically.

Notice also that Elementtype must be known when you write the code. The code for a set of students would be different from the code for a set of integers.

Exercise 1: Implement the class Set as described above. Elementtype should be int. Write a main which creates two Sets, inserts ten random integers (in the range 1, ..., 12) into each, and prints them out.

Other Collection Classes

Set is just one example of a collection class. Another example is Sequence. A sequence differs from a set in that the elements in it are ordered, and thus each element has a position number within the sequence. We will be working fairly extensively with sequences later on. A third example of a collection class is a Queue. A queue is similar to a sequence except that it has the first-in first-out property; i.e., it is like the line at the deli counter, where customers enter the end (tail) of the line and are served (removed) from the front (head) of the line. Queues have at least two member functions, void enqueue(elementtype e) which inserts a new element e into the queue at the tail, and elementtype dequeue() which removes an element from the head of the queue and returns it. There may be other functions as well, such as int queuesize() which returns the number of elements currently in the queue.

Templates

To date, whenever you created one of these container classes, you had to specify a particular element type, and this means that you had to write a separate set of code for each different element type. For example, suppose that you had written a set container class called SetOfStudents, a set where the element type was student. If you wanted to have another set class where the element type was window, you would have to define a whole new class SetOfWindows and rewrite all of the code for it. One of the most important features of C++ allows the programmer to create a generic container class, and then specify the specific type of the element. The generic class is called a template. To create a template, precede the class definition with the keywords
template <class T>¹

The identifier T is a placeholder for any data type which the user cares to use. (You can use any identifier in place of T, but T is widely used.) In a sense, it is like a variable name, but it differs from other identifiers that we have used so far in that it will be replaced by a data type, either built-in, like int or double, or programmer-defined, like Student or window.

Here is code for a very simple container class called Pair. A Pair class has two elements, called first and second. Since this is a generic or template class, the type of first and second can be any data type, built in, or user defined, and so we specify the type with the identifier T.

template <class T>
class Pair {
private:
   T first;
   T second;
public:
   Pair() { }
   Pair(T f, T s) {
      first = f;
      second = s;
   }
   T getfirst();
   T getsecond();
   void setfirst(T f); 
   void setsecond(T s); 
};

template <class T>
T Pair<T>::getfirst() {return first;}

template <class T>
T Pair<T>::getsecond() {return second;}

template <class T>
void Pair<T>::setfirst(T f) {first = f;}

template <class T>
void Pair<T>::setsecond(T s) {second = s;}

To declare an instance of a template class, it is necessary to specify the type between the < and the > characters. This statement declares a pair in which the element type is double.
Pair<double> p;
Once a template class has been instantiated with a particular type, it can be used just as if all of the code had T replaced with this type, in this case double

Here are some examples:
p.setfirst(3.456);
p.setsecond(5.948);
double d = p.getfirst();
cout << p.getsecond();

These examples have used built-in data types. Element types can also be user defined types. If you had defined a class Student and a class window as in previous examples, you could then create a pair of students and a pair of windows.
Pair<Student> PairOfStudents;
Pair<window> PairOfWindows;

You could even create a pair of pairs if this made sense in your program.
Pair<Pair<int> > PairOfPairs;

Alert: There must be a space between the two > characters in this statement. Otherwise, the compiler will think that you are referring to the >> operator and will produce an error message.

Exercise 2: Here is code for a class queue which holds integers. Modify this code to create a generic class queue. Write a short main which creates a queue of floating point numbers and a queue of integers, and test each of the member functions. You can copy this file from /dept/cs/cs2/wksht13/queue.h.

const int MAXQ=100;
class queue {
private:
   int data[MAXQ];
   int head, tail;
   int size;
public:
   queue() {head = tail = size = 0;}
   void enqueue(int item) {
        if (size == MAXQ) {
           cerr << "Full queue"  << endl;
           return;
        }
        else {
           data[tail] = item;
           ++tail;
           if (tail == MAXQ) 
              tail = 0;
           ++size;
        }
   }
   int dequeue() {
        if (size == 0) {
           cerr << "Empty queue\n";
           return 0;
        }
        else {
           int temp;
           temp = data[head];
           ++head;
           if (head == MAXQ) 
              head = 0;
           --size;
           return temp;
        }
    }
    int queuesize() {return size;}
};

Template functions

Most of our template examples involve classes, but you can also use the template concept to define a function template in which the type of the argument is determined by the type of a value passed when the function is called. Here is a simple example which defines a generic (template) function square. Once this function is written, it can be used for any type of argument for which the multiplication operator is defined.

#include <iostream.h>
template <class T>
T square(T n)
{
   return n * n;
}

int main()
{
    float f= 3.4;
    int x = 34;
    cout << square(f) << endl;   // float version of square is called
    cout << square(x) << endl;   //   int version of square is called
    return 0;
}

Templates which take multiple data types

A more complex template class could be defined which takes more than one generic type parameter. For example, suppose we wanted our Pair class to create pairs where the two members were of different types. Here is the code to do this.

template <class T1, class T2>
class Pair {
private:
   T1 first;
   T2 second;
public:
   Pair() { }
   Pair(T1 f, T2 s) {
      first = f;
      second = s;
   }
   T1 getfirst() {return first;}
   T2 getsecond() {return second;}
   void setfirst(T1 f) {first = f;}
   void setsecond(T2 s) {second = s;}
};

To declare an instance of the class Pair, you must provide both types. Here is an example:
Pair<int, float> p;
This defines an instance of the Pair class called p where the first element is of type int and the second is of type float.

Note that operator overloading makes templates much more powerful. Many member functions of template classes may make use of various operators, and all operators used in the template class must be defined for each class. For example, suppose that you have a template class Set which has a member function bool IsInSet(T item) which returns true if item is in the set and false if it is not. If your set stores the elements in an array called thedata, and num is the number of elements in the set, your code might look like this:

template <class T>
bool Set<T>::IsInSet(T item) 
{
   for (int i = 0; i < num; ++i) {
      if (thedata[i] == item)
         return true;
   }
   return false;
}

Here the operator == must be defined for type T, so if you define some class U, you must overload == for U in order to be able to declare Set<U> x, y and write a call like x.IsInSet(y).

Exercise 3: Rewrite the Set class you wrote for Exercise 1 so that it is a template class. You might be able to use the IsInSet function above as part of it. You can test your Set class using the main in /dept/cs/cs2/wksht13/setmain.cpp. The program uses a class Soda defined in /dept/cs/cs2/wksht13/soda.h. You will need to add some functions to the Soda class before you can use it in a template container class. (For instance, you must be able to compare if two soda objects are equal to each other when adding a soda to a Set.)