Prev  

Classes

Introduction to classes

A class is a factory for producing objects. It also provides the implementations of the operations, usually called methods, that are done by the objects in the class.

A class is similar to an abstract data type, and we will use classes to implement abstract data types in a secure manner, hiding what needs to be hidden.

Aside: Subclasses and polymorphism

Classes also provide a way for the compiler to manage polymorphism, which allows one method to work on several different classes of objects. The fact that an object is a member of a certain class indicates that it has at least a certain signature. It might have more methods and variables than are described in the class. There is a mechanism for indicating that one class has the signature of another, plus additional operations. If class B has all of class A's operations, and possibly more, then class B is said to be a subclass of class A, and an object of class B can be used where an object of class A is required.

We do not deal with subclasses in these notes, but they form an important part of object-oriented programming.

"Membership"

In object-oriented programming, the word member is used in more than one way.

  1. An object that is created by a class is a member of that class, in the same way that the number 2 is a member of type int.

  2. But objects themselves have parts, and those parts are called members of the object. For example, if object x carries with it a method called grove, then grove is a member method of the object.

Now comes the difficulty: objects are described by describing their classes. Hence, a member method of an object is said to be a member method of its class. You must understand that the word member in this context really refers to membership in the objects that the class builds.

The class interface

Ideally, the class interface would tell only the class name and the operations that its objects support. Unfortunately, for reasons similar to those that required structures to be put in header files, you must provide information about the data representation in the header file. A feature of classes that partially counteracts this is that you can indicate that the variables are private. Private variables can only be used by the member functions of the class. This gives you a much more secure implementation of an ADT than would be obtained by making the variables visible to everybody.

A class is similar in form to a structure. In the class, you list the variables and give prototypes of the member functions. Each member function, however, comes with an implicit parameter: the object that performs the function. So you typically have one less explicit parameter than you would using a structure-based implementation.

Here is an interface, given in file cintstack.h, of a stack of integers ADT. This is a class-based ADT similar to the structure-based ADT IntStack of part 4 of these notes. Notice that the function prototypes are inside the class definition, and that they have one less parameter (the stack) that in the IntStack ADT.

Interface for class CIntStack
// File: cintstack.h
//
// This file provides for stacks of integers.  
// A stack provides for inserting values onto 
// the top and removing them from the top.  
// (It is last-in-first-out.)  
//
// When a stack is created, it is empty.
// Operations are as follows.
//
// s.isEmpty() Returns 1 just when stack s 
//             is empty.
// s.Empty()   Makes s an empty stack.
// s.Push(k)   Adds k to the top of stack s.
// s.Pop()     Removes the top of stack s and 
//             returns it.  If stack s is 
//             empty, then s.Pop() returns 
//             0 and leaves stack s empty.

#ifndef CINTSTACK_H
#define CINTSTACK_H
#include <stdio.h>

class CIntStack {
 private:
  int top, size;
  int* content;
  void GrowStack();

 public:
  CIntStack()
  {
    top      = 0;
    size     = 0;
    content  = NULL;
  }

  ~CIntStack()    // Destructor
  {
    if(content != NULL) {
      delete[] content;
    }
  }

  CIntStack(const CIntStack& otherst);  
    // Copy constructor

  void Push(int k);
  int  Pop();
  bool isEmpty() const;
  void Empty();
};

#endif

The missing parameter, the stack that is performing the operation, is implicitly of type CIntStack&. In the case of function isEmpty, the missing parameter is indicated to have the const attribute by placing const after the prototype.

To use this class, we use object notation. Here is an example. Compare it to the example for the structure-based implementation IntStack. Line 

  CIntStack st;
creates a CIntStack object called st. This is where the class CIntStack is used like a factory.

Using the class
// File cstacktest.cpp
//

#include <stdio.h>
#include "cintstack.h"

int main()
{
  CIntStack st;

  st.Push(2);
  st.Push(3);
  int a = st.Pop();
  int b = st.Pop();
  if(st.isEmpty()) {
    printf("I got a = %d, b = %d.\n", 
           a, b);
    printf("Should get a = 3, b = 2.\n");
  }
  else {
    printf("Hey!  The stack should"
           " be empty.\n");
    printf("By the way, I got a = %d,"
           " b = %d\n", a, b);
  }
  st.Empty();
  return 0;
}

If function main had attempted to use st.top, the compiler would have flagged the use as an error, since the top variable is private to the class, and so cannot be used by functions that are not members of the class.

The class implementation

To implement a class, you must implement each of its member functions. You must indicate, in each function definition, that your are creating a member function of this class. You do that by adding the class name, followed by ::, to the function name. For example, to define function Empty in class CIntStack, you define CIntStack::Empty.

Inside the definition of a member function, you can refer to the object that is performing the method by pointer value this. That is, this is the name of the implicit parameter. For class CIntStack, this has type CIntStack*. You can refer to the variables of this, and ask this to perform methods, without explicitly writing this. For example, top abbreviates this->top and Push(2) abbreviates this->Push(2).

Here is an implementation of class CIntStack. Compare it to file intstack.cpp.

Class CIntStack implementation
// File: cintstack.cpp
//
#include "cintstack.h"
#inlcude <memory.h>

///////////////////////////////////////
// A stack is represented as follows.
// There are three variables, 'top', 'size' 
// and 'content'.  Variable 'content' points 
// to an array of 'size' integers.  'top' 
// tells how many of those integers are
// actually in the stack, and is one 
// greater than the index of the top of 
// the stack.  (So the bottom is at index 0.)
//
// Initially, 'content' is a null pointer, 
// and 'size' is 0.  When data is put into 
// the stack, the array is allocated to
// hold the data.  If that array fills up, 
// a new, larger, array is allocated.
/////////////////////////////////////////////


/////////////////////////////////////////////
// s.isEmpty() returns TRUE just when stack 
// s is empty.
////////////////////////////////////////////

bool CIntStack::isEmpty() const
{
  return top == 0;
}

//////////////////////////////////
// s.Empty() makes stack s empty.
//////////////////////////////////

void CIntStack::Empty()
{
  top  = 0;
  size = 0;
  if(content != NULL) delete[] content;
  else content = NULL;
}

////////////////////////////////////
// s.Pop() removes the top integer 
// from stack s, and returns it.  
// If s is empty, then 0 is returned,
// and s is not changed.
////////////////////////////////////

int CIntStack::Pop()
{
  if(top > 0) {
    return content[--top];
  }
  else {
    return 0;
  }
}

////////////////////////////////////
// s.Push(x) puts x onto the top of 
// stack s.
////////////////////////////////////

void CIntStack::Push(int x)
{
  //----------------------------
  // If the array is too small,
  // then make it bigger.
  //----------------------------

  if(top == size) GrowStack();

  //--------------------
  // Now do the push.
  //--------------------

  content[top++] = x;
}

///////////////////////////
// Make a copy of a stack.
///////////////////////////

CIntStack::CIntStack(const CIntStack& otherst)
{
  size = otherst.size;
  top  = otherst.top;
  if(top == 0) content = NULL;
  else {
    content = new int[size];
    memcpy(content, otherst.content, 
           top*sizeof(int));
  }
}

/////////////////////////////////////
// Growstack:
// allocate a new content array that 
// is twice as large, and copy the 
// previous content
// into the new array.  However, make 
// sure that the size is at least 4.
//(Doubling 0 yields 0, and we
// would never create any space if 
// we start with none.)
////////////////////////////////////////////

void CIntStack::GrowStack()
{
  int  newsize = 2*size;
  if(newsize < 4) newsize = 4;
  int* newcontent = new int[newsize];
  int i;

  if(NULL == newcontent) {
    abort("IntStack overflow");
  }

  for(i = 0; i < size; i++) {
    newcontent[i] = content[i];
  }
  delete[] content;
  content = newcontent;
  size    = newsize;
}

More on constructors

Constructors are used for initialization of objects, and always have the same name as the class. When you define a constructor, you do not give a return type.

Constructors are often written inside the class itself. But you may write them in the .cpp file if you like. A constructor for class Queue is called Queue::Queue in the .cpp file.

There are a few technical problems associated with constructors that are dealt with here.

Initializing instance variables

If you do not call a constructor on the instance variables in an object, they are, by default, initialized using the constructor for their own class that has no parameters. For example, the Queue class above uses this fact to ensure that the two stacks are initialized to empty stacks.

Sometimes, you want to use other constructors for instance variables. There is a special syntax in C++ for doing that. Here is an example that uses this syntax. Suppose that class LimitedStack provides stacks of fixed size, and provides a constructor that gives the desired size.

class DemoConstructors {
  private:
    int count;
    LimitedStack st;

  public:
    DemoConstructors(int countInit, 
                     int sizeInit)
      : count(countInit),
        st(sizeInit)
    {
    }
  ...
};

The variables to be initialized follow the colon, with their parameters but not their types. They are separated by commas.

Copy constructors

When a copy of an object is made, a default copying method is normally used. The default copier

simply copies all of the variables in the object. That is often not what is desired. Imagine, for example, that you are implementing a linked list. To copy the list, you really need to copy all of the cells of the list. The default copier does not do that.

C++ allows you to write your own copy constructor. The copy constructor for a class called Raven has prototype 

  Raven(const Raven&);
If you define such a constructor, then it will be used instead of the default constructor to do copying. It is used to initialize the copy, with its parameter being a reference to the object that is being copied. All copying is done using this constructor, whether it is a copy at an assignment, or due to passing an object as a value parameter to a function, or any other reason.

Class CIntStack contains an example of a copy constructor. If, instead, class CIntStack had used the default copier, you would find that the copy and the copied stack both contain pointers to the same content array. This is not a good idea, since a push to one of the stacks will modify what is in the other. Class CIntStack should really be provided with a copy constructor, so that each stack has its own array.

Another example

A queue also supports insertion and removal, but it is first-in-first-out. This example implements queues using stacks to help. So it both implements an ADT and uses another ADT. This example also uses a private function, Normalize.

Queues
// File: queue.h

///////////////////////////////////////////
// This file implements queues of integers.  
// A queue supports operations that add 
// items to the back of the queue and remove
// them from the front.
//
// When you create a queue using
//
//  Queue q;
//
// the queue is initially empty.  
// Operations are
//
//  q.isEmpty()  Returns TRUE if q is empty.
//  q.Empty()    Makes q empty.
//  q.Insert(k)  Adds k to the back of q.
//  q.Remove()   Removes an item from the 
//               front of q and returns it.
//               If q is empty, then 0 is 
//               returned, and q remains 
//               empty.
///////////////////////////////////////////

#ifndef QUEUE_H
#define QUEUE_H
#include "cintstack.h"

class Queue {
 private:
  CIntStack forwardStack, backwardStack;
  void Normalize();

 public:
  Queue();
  Queue(const Queue& otherq);
  bool isEmpty() const;
  void Empty();
  void Insert(int);
  int  Remove();
};
#endif

// File: queue.cpp

//////////////////////////////////////
// A queue is represented by a pair 
// of stacks, called forwardStack and 
// backwardStack.
//  
// The contents of the queue consists 
// of the contents of forwardStack 
// (in forward, or downward, order) 
// followed by the contents of 
// backwardStack (in backward, or
// upwards, order).  For example, if
// the contents of forwardStack
// and backwardStack, in top-to-bottom 
// order, are
//
//  forwardStack:  2 5
//  backwardStack: 9 2 6
//
// then the queue contains 2 5 6 2 9, 
// in front-to-back order.  The next 
// value to be removed from the queue 
// is the 2.
//
// To remove the front of the queue, 
// we just pop a value from forwardStack.
//
// To insert a value at the back of the 
// queue, we just push a value onto 
// backwardStack.
//
// There is an important catch.  What 
// happens when forwardStack becomes empty?  
// Then there is nothing to pop from 
// forwardStack.  But there is an easy 
// solution to this:
// 
//  Whenever forwardStack becomes empty, 
//  and backwardStack is not empty, we 
//  remove the items from backwardStack 
//  and push them onto forwardStack.  
//
// For example, if forwardStack and 
// backwardStack contain
//
//  forwardStack:  
//  backwardStack: 9 2 6
//
// then before doing a remove, we must 
// replace this by
//
//  forwardStack:  6 2 9
//  backwardStack:
//
// which represents the same queue, but 
// is now ready for a removal of the 
// 6 by popping forwardStack.
//
// Say that a queue representation is in 
// normal form if 
// it is not the case that forwardStack is 
// empty but backwardStack is empty.  We 
// will always keep the queue
// representation in normal form.
//
// If a queue representation is in 
// normal form, then the queue is empty 
// just when forwardStack is empty.
////////////////////////////////////////

#include "cintstack.h"
#include "queue.h"

/////////////////////////////////////
// q.isEmpty() returns TRUE just when
// q is an empty queue.
/////////////////////////////////////

bool Queue::isEmpty() const
{
  return forwardStack.isEmpty();
}

/////////////////////////////////
// q.Empty() makes queue q empty.
/////////////////////////////////

void Queue::Empty()
{
  forwardStack.Empty();
  backwardStack.Empty();
}

/////////////////////////////////
// q.Insert(k) adds k to the back
// of queue q.
/////////////////////////////////

void Queue::Insert(int k)
{
  backwardStack.Push(k);
  Normalize();
}

///////////////////////////////////////
// q.Remove() removes a value from 
// the front of queue q and returns it.
// If q is emtpy, then 0 is returned,
// and q is left empty.
///////////////////////////////////////

int Queue::Remove()
{
  if(!isEmpty()) {
    int result = forwardStack.Pop();
    Normalize();
    return result;
  }
  else return 0;
}

/////////////////////////////////////////
// Copy constructor
/////////////////////////////////////////

Queue::Queue(const Queue& otherq)
  : forwardStack(), 
    backwardStack()
{
}

/////////////////////////////////////////
// q.Normalize() puts the representation 
// of queue q in normal form, if it is 
// not already in normal form.
/////////////////////////////////////////

void Queue::Normalize()
{
  if(forwardStack.isEmpty() && 
     !backwardStack.isEmpty()) {
    while(!backwardStack.isEmpty()) {
      forwardStack.Push(backwardStack.Pop());
    }
  }
}

Class methods and variables

When you declare a variable or function in a class, you normally intend to describe a feature of the objects that the class produces. The objects of a class are sometimes called instances of the class, so these variables and functions are called instance variables and instance functions, or instance methods.

It is possible to create variables and functions that are associated with the class itself, not with the objects. A class variable is shared by all objects, as is a class function. To declare a class variable or function, precede it by the modifier static. For example, 

class MyClass {
 private:
  static int count;
  ...
};
creates a class MyClass that has a class variable called count. Use class variables and methods whenever you want to think of the class itself as a special object, and to give it attributes, or when you need a variable that is shared by the instances of a class.

Prev