Computer Science II -- Week 12
Introduction
Note that the links from this page are to handouts that will be distributed the night of class. Only print out those handouts if you could not attend class.
Main topics this week:
Consider a drawing program. This program will allow the user to draw many types of shapes: rectangles, squares, triangles, circles, etc. As part of making sure we have a good design, we write a simple program to draw rectangles. That works well, so we decide to add squares.
We recognize that squares are just a rectangle where the width and the height must be the same. It seems like there should be some way of reusing all that code we wrote for the rectangle.
Here's what the rectangle class might look like:
class Rectangle
{
public:
Rectangle ();
~Rectangle ();draw ();
void setX (int);
void setY (int);
void setWidth (int);
void setHeight (int);private:
int x, y, width, height;
};
One way of reusing the rectangle code in a square class is called containment. This is also sometimes called a "HasA" relationship.
Containment means that one of the private data members of the square class is a rectangle.
class Square
{
public:
Square ();
~Square ();draw ();
void setX (int);
void setY (int);
void setWidth (int);
void setHeight (int);private:
Rectangle rect;
};
The public methods of square would simple call the public methods of rectangle to do the work.
This approach has a couple of disadvantages:
- If we add public methods to rectangle, we also need to add public methods to square.
- It just doesn't make sense. A square doesn't contain a rectangle, a square is a rectangle.
A better approach is to model an "IsA" relationship, where one object really is a specialized type of another object. The way we implement IsA relationships in C++ is through inheritance.
Syntax for inheritance:
class Square:public Rectangle
{
};
This syntax allows the square to inherit (use) all the public methods of rectangle. Without any more code at all, we can use Square anywhere that we could have used Rectangle.
void main ()
{
Square aSquare;aSquare.setWidth (5);
}
Even though we have no code in the Square class, we can call setWidth because Square inherits that method from Rectangle.
Terminology:
Base class
Derived class
To make our Square class behave like a square, we need to make sure that the height and width are always the same. We do this by overriding some of the Rectangle methods. Overriding is when you have a method in a derived class that has the same signature as a method in a base class.
class Square:public Rectangle
{
public:
void setWidth (int);
void setHeight (int);
};
Now, when we call setWidth on Square, we no longer call the Rectangle setWidth function, but we call the Square setWidth function.
When you override a function, you provide a new implementation for that function
void Square::setWidth (int value)
{
width = value;
height = value;
}void Square::setHeight (int value)
{
setWidth (value);
}
But we have a problem with this. The data members in Rectangle are private, which means that Square can't see them. So the lines in setWidth that assign to width and height would give a compile error.
C++ provides two solutions to this problem.
1) Protected access
If you make the Rectangle data members protected instead of private, then derived classes will be able to see them. Protected access means that the data member or method is private to the rest of the world but public for derived classes.
class Rectangle
{
public:
draw ();void setX (int);
void setY (int);
void setWidth (int);
void setHeight (int);protected:
int x, y, width, height;
};
This would allow the code in Square::setWidth to modify width and height.
2) Calling base class functions
The Square class, instead of trying to access Rectangle data members directly, can access them through the public methods provided by Rectangle. For example, to set the width Square could call the Rectangle setWidth function.
Since Square also has a setWidth function, a special syntax is needed to tell the compiler which setWidth function to call.
void Square::setWidth (int value)
{
Rectangle::setWidth (value);
Rectangle::setHeight (value);
}
In general, if a derived class wants to call a base class public function, the following form is used:
BaseClassName::FunctionName (parameters)
So now we have a Square class that reuses a Rectangle class through inheritance. But we're not quite done with Square and Rectangle yet.
Let's look at what we have to do to our drawing program to add squares. We probably have a vector of Rectangles that the user has drawn, and we probably have a draw routine that will draw all the Rectangles in the vector. The prototype for the draw routine would look like this:
void draw (const vector<Rectangle> &);
Now we want to add squares. It would make sense add a vector of Squares and send that vector into the draw routine too.
void draw (const vector<Rectangle> &, const vector<Square> &);
That doesn't seem too bad, but what about when we want to add circles. Or triangles. Or ellipses. Our draw routine is taking a lot of parameters by the time we finally get all our shapes into the program, and everytime we add a shape we need to do all of the following:
- Add a vector for storing the shape
- Add that vector to any functions that deal with all shapes (for example, draw)
- Add code that knows how to interact with the user to create the new type of shape
- Go to every place in the code that deals with specific types of shapes and add our new type of shape to it (there will probably be switch statements based on the type of shape throughout the program)
That's a lot of work to add new shapes.
Luckily, there's a better way. C++ provides a mechanism called polymorphism.
Polymorphism has two key parts:
1) In C++, a pointer or a reference to a base class may actually point to an instance of a derived class.
This is an important concept. The following code is perfectly legal in C++:
Rectangle *ptr = new Square ();
ptr->setX (5);
This is important because it allows us to write our drawing program more generically. Instead of passing around two vectors, one for Rectangles and one for Shapes, we can just pass around one vector. This single vector will contain pointers to Rectangles. The draw prototype would look like this:
void draw (const vector<Rectangle *> &);
The draw routine would work with these pointers as if they pointer to Rectangles. But in fact they may point to either Rectangles or Squares.
But we still have a problem. Which setWidth function (Square or Rectangle) gets called when we do this:
Rectangle *ptr = new Square ();
ptr->setWidth (5);
2) Virtual functions allow C++ to figure out what function to call at run-time
Normally C++ figures out what function to call when the code is compiled. This is called compile-time, or static, binding. This is fine for most cases.
Sometimes, though, as in the Square::setWidth case, the compiler doesn't have enough information to make the right decision. The compiler knows the type of the pointer, which is Rectangle. Left to itself, the compiler will call the Rectangle::setWidth function, which will bypass all of our specialized code in Square::setWidth.
The virtual keyword on a function in a base class tells the compiler to use run-time, or dynamic, binding. This means that the compiler won't try to figure out what function to call at compile time, but will postpone the decision until the program is actually running.
class Rectangle
{
public:
virtual draw ();virtual void setX (int);
virtual void setY (int);
virtual void setWidth (int);
virtual void setHeight (int);private:
int x, y, width, height;
};
Now when we do this:
Rectangle *ptr = new Square ();
ptr->setWidth (5);
The Square::setWidth function is called. Let's look at the process C++ uses to figure out which function to call at run-time.
All of this only works if a class function is being called through a pointer or a reference to a class. When we have a pointer or a reference to a class, we have two data types involved.
Rectangle *ptr = new Square ();
The first data type is the type of the pointer or reference. In this case, Rectangle. The second data type is the type of the instance of the class, in this case Square.
ptr->setWidth (5);
When you try to call a function through the pointer or reference, the first thing C++ does is to check the class header for the type of pointer, to see if the function being called has the virtual keyword.
If the function does not have the virtual keyword, then the function is called on whatever class the pointer is a type of. In the above example, if setWidth was not virtual, then the Rectangle::setWidth function would have been called. If a function is not virtual, then this is compile-time binding. The compiler knows enough to decide what function gets called at compile time.
If the function is virtual, then C++ needs to figure out what function to call. It starts at the type of the instance being pointed to (in the above example, Square), and checks to see if Square has overriden the setWidth function. If so, Square::setWidth is called. If not, then C++ goes to Square's base class to see if there's a setWidth there. If so, that's the function that is called. If not, C++ goes to the base class of Square's base class to see if there's a setWidth there. This will happen until C++ finds a setWidth function.
In general, the most derived class that overrides that function will be called.
What happens when we delete the Square instance we allocated?
Rectangle *ptr = new Square ();
delete ptr;
Which destructor gets called? ~Rectangle () or ~Square () ? Work through it based on the above rules.
If the wrong destructor gets called, we might leak memory. Say the Square class allocates memory dynamically in its constructor. If the Square destructor isn't called, that memory will never be deleted.
A good practice is to make destructors virtual in all classes that will be base classes.
Note that if you make the destructors virtual so that the Square destructor is called, C++ takes care of calling the Rectangle destructor for you after the Square destructor is called. This makes sure that all the base classes have a chance to clean up their memory, too.
Constructors in derived classes
Constructors are special in derived classes. Everytime you create an instance of a derived class, all the base classes have their constructors called before the derived class constructor is called. This allows the base classes to allocate anything they need to allocate.
But which base class constructor is called? Unless you tell C++ otherwise, the default base class constructor will be called, no matter which derived class constructor is called.
How do you tell C++ to call a different base class constructor? Use the initializer list!
Square::Square ()
: Rectangle (5)
{
}
This tells C++ that every time the default Square constructor is called, the Rectangle constructor that takes an int should be called (and 5 will be passed in). So you can use the initializer list to pass values to base class constructors. These calls to base class constructors can be mixed into the initializer list with data member initializations, but the base class constructor calls are always performed before any data member initialization.
Polymorphism is important because it allows us to program for a general case, and to use derived classes to change behavior without making any changes in our main program.
An abstract data type is a description of the public interface of a data type. This reveals only the public interface to the outside world, and hides all of the implementation.
For example, in C++ an abstract data type description of the Foo class might be:
class Foo
{
public:
void setData (int);
int getData () const;
};
If we could somehow use this as our class, without having to list private data members, then anyone who used the Foo class would not need to know anything about the private data members. If I later changed the data type of private data members, but kept the public interface the same, nobody who used the Foo class would need to change.
In C++, we do this by creating an Abstract Base Class. An Abstract Base Class is a C++ version of an Abstract Data Type. An Abstract Base Class version of Foo would look like this:
class Foo
{
public:
virtual void setData (int) = 0;
virtual int getData () const = 0;
};
The notation following each function prototype (= 0) makes each of the functions a "pure virtual function". This means that you are not going to provide an implementation for these functions for the Foo class.
One practical result of this is that if I try to create an instance of Foo, the compiler will not allow it. That's because the compiler doesn't know how to perform the setData and getData calls.
In order to use Foo, we need to derive a class from Foo that provides the implementation of the pure virtual functions:
class FooDerived:public Foo
{
public:
FooDerived ();virtual void setData (int);
virtual int getData () const;
};
You do write the implementation for these methods. Now someone can use the Foo class like this:
Foo *ptr = new FooDerived ();
After this, they just use the ptr as if it pointed to a Foo instance. Virtual functions ensure that the right functions get called.
Abstract Base Classes are useful as the ultimate base class of several derived classes. For example, in our drawing program, we want to be able to draw more than just Rectangles and Squares. Other types of shapes are not Rectangles, so we cannot use Rectangle as our ultimate base class. Instead we would create an Abstract Base Class called Shape, and use it as the data type for our vectors. From Shape we would have all the other data type derived. Shape would contain all the methods that are in common to all shapes, but since Shape doesn't know how to do anything, those functions would be pure virtual functions.