Data Structures

CSIS 2617

Templates Lab

 

Goals

 

What to turn in

Turn in any source code you write

 

Pre-Lab 1 – Lab preparation

 

Discussion

            There are many problems where two identical containers are required to store different kinds of data. For example, in an operating system, you have queues of processes, queues of print jobs, queues for disk access, an so on.

 

            In tonight’s lab, we will look at a common problem that uses two stacks in its solution.

 

            A container class ordinarily holds one kind of data; when the class is created, the type of data is hardcoded in the class definition. However, this causes problems when the same container class needs to hold multiple types of data. When this situation arises, there are three solutions:

Each is discussed below.

 

The Union Solution

            A union is similar to a struct; it holds multiple elements. However, unlike a struct, a union can only hold one element at a time.

 

            If, for example, I need a container to hold numbers and a second container to hold characters, I can create the following union:

union StackType {

     double val;

     char op;

};

 

            This creates a type of data that can hold either a number or a character, but not both simultaneously. You can create variables of this type, just as you can create structs or objects:

 

StackType myVar;

 

Access is the same as it is for structs and objects:

 

myVar.val = 2;

myVar.op = ‘$’;

 

            With a union, you can create a single container class, with the union as the data type.

 

The Zen Solution

            “Zen data structures” isn’t an official term, but the idea behind this approach has a Zen flavor to it. Philosophically speaking, in order to make a container that can hold any type of data, you create a container that holds no type of data. Once you specify a type of data for a container, the container is bound to only hold that type.

 

            Most containers only move data in and out, without much if any regard to what the data actually is. In these cases, it is possible to create a container that doesn’t tie itself to any specific type. Rather, you specify how many bytes to move into and out of the container.

 

            This is an older technique, and isn’t used very often. The closest you’re likely to see is the qsort( ) function, which is a data-independent sort function.

 

The Multiple Copies Solution

            The current trend in solving the problem (and one of the reasons why C++ isn’t always the most efficient solution to a problem) is to make multiple copies of a container class, one for each type of data stored.

 

            We can do this explicitly – make classes C1 and C2 which are identical except for the type of data stored. However, this is commonly done with the use of templates.

 

            Templates are rather easy to use. Essentially, a template defines a placeholder that is used in place of the data type in the class. When you create an object from the class, you indicate what kind of data fills in the placeholder. Whenever a new data type is used to fill the placeholder, the compiler automagically creates a new copy of the class.

 

A word of caution before the exercises:

            The classes created in these exercises are flawed; in the interest of space, there is no error checking, so it is possible to overflow or underflow the stack. In the Stack topic, we’ll see the correct way to implement a stack.

 

Exercise 1 – The union solution

            Take a look at eval1.cc; it is a program that evaluates a simple arithmetic expression. It makes use of two stacks, an operator stack (of characters) and an operand stack (of numbers). For this exercise, we will create a single Stack class that can accommodate both.

 

            Note the places in the program where the stack is used, and notice the code required to add and remove elements from the two stacks. There is extra code required to pack / unpack data in the union.

 

            First, edit the file Stack1.h; this will contain the class, and is included by eval1.cc. Start the file by defining the union:

union StackType {

     double val;

     char op;

};

 

This, as mentioned in the Discussion, creates a structure with enough space to hold either a number of a character, but not both simultaneously.

 

Next, we create a stack class that contains these unions:

class Stack {

 public:

  Stack( ) { top = 0; }

  ~Stack( ) { }

 

  bool isEmpty(void) { return !top; }

  int size(void) { return top; }

 

  void push(StackType d) { data[top++] = d; }

  StackType pop(void) { return data[--top]; }

 

  StackType stackTop(void) { return data[top-1]; }

 

 private:

  int top;

  StackType data[16];

};

 

Save this file.

Now, compile eval1.cc, and run it. Test it out, it should work properly.
Exercise 2 – The Zen solution

            Take a look at eval2.cc. In this exercise, we’ll create a “Zen” stack that holds any type of data. Note that when the opStack and numStack are created, they use the sizeof( ) operation to indicate how many bytes of data are pushed and popped. Notice also the code used to push and pop on the stack. Somewhat shorter than before, but the syntax is rather awkward.

 

            On to creating the stack. Edit the file Stack2.h and add the following:

class Stack {

 public:

  Stack(int _nBytes) {

    nBytes = _nBytes;

    data = new char[16*nBytes];

    top = 0;

  }

  ~Stack( ) { delete data; }

 

  bool isEmpty(void) { return !top; }

  int size(void) { return top; }

 

  void push(void *d) {

    memcpy(data+top*nBytes,d,nBytes);

    top++;

  }

  void pop(void *d) { top--; memcpy(d,data+top*nBytes,nBytes); }

 

  void stackTop(void *d) { memcpy(d,data+top*nBytes,nBytes); }

 

 private:

  int top;

  char *data;

  int nBytes;

};

 

Note the extra work that goes along with moving bytes, rather than moving a specific data type. Behind the scenes, complex data types (structs, etc.) are moved from variable to variable in this manner, but the language hides the details of how it’s done.

 

This makes a good opportunity to explore a help facility available on UNIX systems. Type the command man memcpy and read through the information that is provided.

·        What are the parameters for memcpy?

 

To wrap up this exercise, compile and test the program.

 

Exercise 3 – The template solution

            Take a look at eval3.cc. In the places where stacks are used, the syntax is now much cleaner. Note the syntax for the declaration of numStack and opStack; the data types in brackets fill in the placeholder defined in the template.

 

            To create the template stack, create the file Stack3.h and add the following:

template <class StackType>

class Stack {

 public:

  Stack( ) { top = 0; }

  ~Stack( ) { }

 

  bool isEmpty(void) { return !top; }

  int size(void) { return top; }

 

  void push(const StackType &d) { data[top++] = d; }

  StackType &pop(void) { return data[--top]; }

 

  StackType &stackTop(void) { return data[top-1]; }

 

 private:

  int top;

  StackType data[16];

};

 

Note that the code looks much like it did in exercise 1, with the main exception that we now use a placeholder to defer what type of data is stored in the stack, and specify the type later when the object is declared.

 

Compile and run the program. As with the others, it should work properly.

 

Bonus Exercise – Advanced templates

            There are three mostly philosophical issues with the way the template was written in Stack3.h; one is a personal issue, one is a software engineering issue and one is an implementation issue.

 

            Personally, I don’t like to put code inside of header files. However, without some extra steps, you cannot separate code from a templated class. Try doing that – move the code in Stack3.h into a Stack3.cc and try compiling it.

 

            The second issue is that a class is essentially defining an ADT. By separating the class definition from the code that comprises the class methods, we separate the ADT from its implementation. In Java, we’d call this class an interface, and write code that implements the interface.

 

            In C++, we don’t have interfaces per se, but we can mimic their behavior. To see this, rename your Stack3.h file as Stack3.original.h. Then, create a Stack3a.h and include the following:

template <class StackType>

class AbstractStack {

public:

 

  virtual bool isEmpty(void) = 0;

  virtual int size(void) = 0;

 

  virtual void push(const StackType &d) = 0;

  virtual StackType &pop(void) = 0;

 

  virtual StackType &stackTop(void) = 0;

};

 

            This creates a class, but it cannot be used to create objects directly. Rather, it provides an interface, and we must provide code for the five methods in order to create a concrete class.

 

            Note the virtual and = 0 sections. This defines these methods as pure virtual methods. As such, they cannot be called.

 

            To use this class, we must create a subclass that implements it. Create a file Stack3.h and add the following:

#include “Stack3a.h”

 

template <class StackType>

class Stack : public AbstractStack<StackType> {

 public:

  Stack( ) { top = 0; }

  ~Stack( ) { }

 

  bool isEmpty(void) { return !top; }

  int size(void) { return top; }

 

  void push(const StackType &d) { data[top++] = d; }

  StackType &pop(void) { return data[--top]; }

 

  StackType &stackTop(void) { return data[top-1]; }

 

 private:

  int top;

  StackType data[16];

};

 

            Note that with the exception of : AbstractStack, it is the same as the original Stack3.h.

 

            If it is largely the same, then why bother? The answer is that our Stack class could implement the AbstractStack in any way necessary. In fact, if somehow Stacks of one type and Stacks of another type needed to be treated differently, we could accommodate that as well.

 

            Try compiling and running the program.