CS 218 - Object Oriented Programming with C++

Chapter 12 - Classes and Data Abstraction


This chapter introduces the student to classes. Objectives important to this chapter:

  1. What classes are
  2. Scopes of classes
  3. Constructors and destructors
  4. Abstract data types
  5. Using classes and ADTs
  6. Information hiding

A class is something new, but it relates to things we have discussed before. An arrary is a data structure of variables, and all the variables are of the same type. A struct is a data structure which can hold several data types. A class is like a structure, in that it must be declared and defined to have a certain shape and size. A class has members, like a struct. What is different is that members of a class can be data holders, and other members of that class can be functions. (Actually, in C++, a struct can have members that are functions as well, but this is not commonly done.)

Declaring a class:

	class Circle

In other words, let there be a class called Circle. The name is followed by a definition:

		void SetRadius(void);
		void GetRadius(void);
		void CalculateArea(void);
		int radius;
		int color;

This looks weird. The public and private sections are meant to show you that there are some parts of the class that will interface with the world and some that will not. Members that are public may be called or accessed by code in the program. Members that are private may only be called or accessed by code in the class itself. The C++ Tutorial site offers this discussion of the concept:

  • private members of a class are accessible only from within other members of the same class or from their friends. (More about that later...)
  • protected members are accessible from members of their same class and from their friends, but also from members of their derived classes.
  • Finally, public members are accessible from anywhere where the object is visible.

There are four public members declared in this example, the second and third being standard looking function prototypes. These functions will be defined very soon in the program.

The first and fourth members are odd. The first is the prototype for the constructor function for the class. Essentially, it is a requirement that it be there, shaped like this, in order for the class to work. It is what allows the computer to create an instance of the class. Note that type keywords were not used with it. A keyword is never used for the return type, but variables and keywords may be used in the parentheses. (I'll show you in a few lines.)

The fourth member of the class is the prototype for the destructor function for the class (also called the deconstructor function). You should be aware that C and C++ are memory efficient languages. Think of the destructor function as being necessary to clean up memory after we are done using an instance of a class. Type keywords are not used with the destructor function prototype, either.

Note that the constructor function of a class is the first public member declared and the destructor function for the class is the last public member declared. This would be true even if this class had data members as well as member functions in the public section. (Yes, I know, the syntax for this makes no sense. Remember, the poor creatures who created this thought in UNIX...) The constructor function has the same name as the class, and the destructor function has the same name, preceded by a tilde. Constructor and destructor functions have no types: they return nothing. Unlike other functions, the have no type specifier, not even void.

The author of our old text, having bewildered you with the above, then switches gears and confuses you with a change in syntax for his code. As he likes to precede the name of an integer variable with an i, a character variable with a c, and so on , he tells us to precede the name of a class with a capital C. You don't have to do this, but it is consistent with his style. Likewise, when he includes data members, he precedes their names with m_, regardless of their type. (Well, there goes the consistency. It could be worse. I have seen people preface a Visual Basic variable with several characters, to note its type, scope, location, etc. You start to wonder if they are being paid by the keypress...)

The code changes to look like this:

	class CCircle
		CCircle( int r ); //Constructor
		void SetRadius( int r );
		void DisplayArea(void);
		~CCircle();  //Destructor
		float CalculateArea(void);
		int m_Radius;
		int m_Color;

Since we changed the name of the class (added the prefixed C), we had to change the names of the constructor and destructor functions as well. He could have done this the first time, but he wanted to warm up to his notation standard. Now, the constructor is meant to receive a variable to tell it how big the circle we are making will be. The return type is still not mentioned and should not be.

The first thing the program does after the class declaration is to define the class functions. His constructor function does not do much, just assigns the value of the integer passed to it to the m_Radius member.

// The Constructor function
CCircle::CCircle(int r)
	// set the radius
	m_Radius = r;

He does not use the dot operator because it happens internally, and the function assumes that the named variable (m_Radius) is a member of the class. The use of the double colon tells the compiler that this function (named to the right of the double colon) is a member of the named class (named to the left of the double colon). Without this notation, the compiler might think that this was simply an external function, available to any other function in the program.

Defining destructor functions is easy. You don't put anything in them, you just let C++ worry about it. It is required, however, that this worthless looking code be in the program.

// The Destructor function

A class can have more than one constructor function, but it can have only one destructor function.

There are more functions that need to be added to this program. When it runs, the main function creates an instance called MyCircle and passes a value to it. The class code receives the value and places it in the m_Radius member of MyCircle. Then the program would call the DisplayArea member of MyCircle. This is allowed because this is a public member function. DisplayArea calls CalculateArea which is not defined above, but is mentioned in the private section of the class. DisplayArea is allowed to call CalculateArea because it happens internally in the class. If the program code (main function) had tried to call the CalculateArea member directly, it would have failed because that member is private to the class. This may seem silly, since all the code is in one program anyway. The concept is meant to apply to larger projects that use multiple files.

This distinction is important when you consider another version of the program. In it, the author creates a header file containing the definition of the CCircle class. Including this header allows a new C++ program to use the class, without rewriting the whole thing over again. (Aren't headers wonderful?) The header file that holds the specific code for a class can be called a specification file. Using headers this way can provide a means to hide code from programmers and users, preventing them from changing code that is supposed to be standardized for a project.

Now, the source code for the class is not readily available to the programmer. This is more like our usual programming habits, taking advantage of existing work. ("If I have seen farther than others, it is because I have stood on the shoulders of giants." -- Isaac Newton) This is one of the major features of object oriented programming. If we create a useful object, save it in a header so it can be reused in other programs.

The text offers more terminology:

  • accessor function - a member function that reads, but does not change the value of member variables
  • mutator function - a member function that can change the values of member variables

An Abstract Data Type (ADT) packages methods and data representations together in a way that is problem-oriented rather than language-oriented. Your text explains that it is just a logical representation of the data type you are creating.

One kind of ADT is a linked list. A linked list is a list in which each item contains information describing where to find the next item in the list. In a linked-list implementation, each link is called a node. Within each node there is a pointer which points to the address of the next node.

An ADT specifies two types of information: a set of properties and a set of operations. With a linked list, the type property is to hold a sequence of items. The set of operations include:

  • Initialize list to empty
  • Determine if list is empty
  • Determine if list is full
  • Determine number of items in list
  • Add item to end of list
  • Traverse list, processing each item in the list.

The three step process in creating an ADT moves from the general to the concrete. The steps are:

  1. Provide an abstract description of the type's properties and of the operations you can perform on the type.
  2. Develop a programming interface that implements the ADT.
  3. Write code to implement the interface.

Building the interface generally involves creating some general type, such as type Item, as in:

	#define TSIZE 45
	struct film
	char title[TSIZE];
	int rating;
	typedef struct film Item;

This defines Item and allows the programmer to store data of this type.

A queue is a first in, first out (FIFO) data form. With this ADT, the operations include:

  • Initialize queue to empty
  • Determine whether queue is empty
  • Determine whether queue is full
  • Determine number of items in the queue
  • Add item to rear of queue
  • Remove and recover item from front of queue

A primary difference between a linked list Node and a queue Node is as follows:

	typedef struct node
	Item item;
	struct node * next;
	} NODE;
	typedef struct queue
	Node * front;
	Node * rear;
	int items;
	} Queue;

With a linked list a single pointer points to the next node. With a queue, two pointers are needed to point to the front and rear nodes.

Comparing a linked list to an array leads to the following advantages for a linked list: Size is determined during run time, and inserting and deleting nodes is quick. The disadvantages include lack of direct support by C and no random user access.

With a linked list, a search must be performed sequentially. A binary search ADT avoids this. This type of search begins in the middle of an ordered list and performs a binary search strategy.

Each node in a binary tree ADT contains two pointers to other nodes, called child nodes. The properties of a binary tree ADT are several and include:

  • A tree is either an empty set of nodes or a set of nodes with one node designated as the root.
  • Each node has exactly two trees, called subtrees, descending from it.
  • Each subtree is itself a binary tree, which include the possibility of an empty tree.
  • A binary search tree is an ordered binary tree in which each node contains an item, in which all items in the left subtree precede the root item and in which the root item precedes all items in the right subtree.

The operations of a binary tree are also several and include:

  • Determine if the tree is empty
  • Determine if the tree is full
  • Determine the number of items in the tree
  • Add an item to the tree
  • Remove an item from the tree
  • Search the tree for an item
  • Visit each item in the tree

A binary tree is efficient only if it is balanced. Trees built as balanced trees are called AVL trees.