Polymorphism

Forms of Polymorphism

In C++, there are three forms of polymorphism:

Overloading: the same function name may be overloaded, using different signatures (also known as ad hoc polymorphism)
Parameterized Polymorphism: (see later, class templates)
Pure Polymorphism: selection of a function at run time, based on the class type and its position in an inheritance hierarchy.

Here we are concerned with pure polymorphism.

What’s the Problem we’re Solving?

Imagine that we have a Fruit class, and two classes, Kiwi and Kumquat, derived from it:

//
//  Fruits.h
//  Polymorphism
//
//  Created by Bryan Higgs on 8/28/24.
//

#ifndef Fruits_h
#define Fruits_h

//  fruits.h
class Fruit
{
public:
  const char *Type() const
  { return "Fruit"; }
};

class Kiwi : public Fruit
{
public:
  const char *Type() const
  { return "Kiwi"; }
};

class Kumquat : public Fruit
{
public:
  const char *Type() const
  { return "Kumquat"; }
};

#endif /* Fruits_h */

Assume we wish to represent a collection of Fruits using a linked list:

//
//  FruitList.h
//  Polymorphism
//
//  Created by Bryan Higgs on 8/28/24.
//

#ifndef FruitList_h
#define FruitList_h

#include "Fruits.h"

class FruitList
{
public:
  FruitList(Fruit *fruit, FruitList *list = 0)
    : m_elem(fruit), m_next(list)  // add to front of list
  {}
  ~FruitList();

  void Print() const;  // Print out list contents
private:
  FruitList  *m_next;  // next FruitList in list
  Fruit      *m_elem;  // ptr to current fruit
};

#endif /* FruitList_h */

//
//  FruitList.cpp
//  Polymorphism
//
//  Created by Bryan Higgs on 8/28/24.
//

#include <iostream>
#include "FruitList.h"

FruitList::~FruitList()
{
  // Clean up...
}

void FruitList::Print() const
{
  for (const FruitList *ptr = this;
       ptr != 0;
       ptr = ptr->m_next
      )
  {
    std::cout << ptr->m_elem->Type()
              << std::endl;
  }
}

And we have a program to test this out:

//
//  main.cpp
//  Polymorphism
//
//  Created by Bryan Higgs on 8/28/24.
//

#include <iostream>
#include "FruitList.h"

int main(int argc, const char * argv[]) 
{
  FruitList *list = new FruitList(new Fruit, 0);
                       // A lone Fruit entry
  list = new FruitList(new Kiwi, list);
                       // Kiwi -> Fruit
  list = new FruitList(new Kumquat, list);
                       // Kumquat -> Kiwi -> Fruit
  list->Print();
  return 0;
}

We expect the output to reflect the specific kinds of Fruit we have in the list.

But the program outputs:

Fruit
Fruit
Fruit
Program ended with exit code: 0

What’s wrong?

The Solution: virtual Functions

The problem is that the compiler took us literally when we said, in the FruitList class:

Fruit *elem;

We need some way of telling the compiler that this means “Pointer to a Fruit, or anything derived from Fruit“, so that it can invoke the proper Type() member function at run time.

Enter virtual functions:

We simply add the keyword virtual in front of the Type() function:

//
//  Fruits.h
//  Polymorphism
//
//  Created by Bryan Higgs on 8/28/24.
//

#ifndef Fruits_h
#define Fruits_h

//  fruits.h
class Fruit
{
public:
  virtual const char *Type() const
  { return "Fruit"; }
};

class Kiwi : public Fruit
{
public:
  virtual const char *Type() const
  { return "Kiwi"; }
};

class Kumquat : public Fruit
{
public:
  virtual const char *Type() const
  { return "Kumquat"; }
};

#endif /* Fruits_h */

… and the program now works as we expected:

Kumquat
Kiwi
Fruit
Program ended with exit code: 0

What happened?

The code in the Print() member function:

ptr->elem->Type()

now determines the type of *elem at run time, and from it figures out which Type() function to invoke.

A class that declares or inherits a virtual function is called a Polymorphic Class.

The virtual keyword can be used when declaring overriding functions in a derived class, but it is unnecessary; overrides of virtual functions are always virtual.

Another Example: Vector & BoundedVector

Remember our old standby, the Vector class, and its derivative, BoundedVector?

We had some code that looked like:

//
//  main.cpp
//  Polymorphic Vector
//
//  Created by Bryan Higgs on 8/28/24.
//

#include <iostream>
#include "BoundedVector.h"

int main(int argc, const char * argv[])
{
  Vector         values(6);
  BoundedVector  bvalues(-5, 3);

  for (int i = 0; i < values.getElementCount(); i++)
  {
    values[i] = i;
  }
  std::cout << "Vector contents: " << std::endl;
  for (int i = 0; i < values.getElementCount(); i++)
  {
    std::cout << "[" << i << "] = "
              << values[i] << std::endl;
  }

  for (int i = bvalues.LowBound(); i <= bvalues.HighBound(); i++)
  {
    bvalues[i] = i*i;
  }
  std::cout << "BoundedVector contents: " << std::endl;
  for (int i = bvalues.LowBound(); i <= bvalues.HighBound(); i++)
  {
    std::cout << "[" << i << "] = "
              << bvalues[i] << std::endl;
  }

  return 0;
}

which produced output like this:

Vector contents: 
[0] = 0
[1] = 1
[2] = 2
[3] = 3
[4] = 4
[5] = 5
BoundedVector contents: 
[-5] = 25
[-4] = 16
[-3] = 9
[-2] = 4
[-1] = 1
[0] = 0
[1] = 1
[2] = 4
[3] = 9
Program ended with exit code: 0

Imagine we wanted to reduce some of the redundant code, to

//
//  main.cpp
//  Polymorphic Vector
//
//  Created by Bryan Higgs on 8/28/24.
//

#include <iostream>
#include "BoundedVector.h"

void Print(const Vector &v, int low, int high)
{
  for (int i = low; i <= high; i++)
    std::cout << "[" << i << "] = " << v[i] << std::endl;
}

int main(int argc, const char * argv[])
{
  Vector         values(6);
  BoundedVector  bvalues(-5, 3);

  for (int i = 0; i < values.getElementCount(); i++)
  {
    values[i] = i;
  }
  std::cout << "Vector contents: " << std::endl;
  Print(values, 0, values.getElementCount() - 1);

  for (int i = bvalues.LowBound(); i <= bvalues.HighBound(); i++)
  {
    bvalues[i] = i*i;
  }
  std::cout << "BoundedVector contents: " << std::endl;
  Print(bvalues, bvalues.LowBound(), bvalues.HighBound());

  return 0;
}

and to cause everything to compile, I had to change one small thing here:

//
//  Vector.h
//  Polymorphic Vector
//
//  Created by Bryan Higgs on 8/28/24.
//

#ifndef Vector_h
#define Vector_h

class Vector // A vector of ints
{
public:
  // Constructors & destructors
  // Default constructor
  explicit Vector(const int elements = 10);
  // Copy constructor
  Vector(const Vector &source);
  // Destructor
  ~Vector() { delete [] m_p; }

  int getElementCount() { return m_elems; }
  
  // Subscript operator overload
  int &operator[](int i) const;
  
private:
  int *m_p;    // Ptr to array
  int  m_elems;  // Alloc. count
};

#endif /* Vector_h */

… and:

//
//  Vector.cpp
//  Polymorphic Vector
//
//  Created by Bryan Higgs on 8/28/24.
//

#include <iostream>
#include <assert.h>
#include "Vector.h"

Vector::Vector(const int elements)
{
  // Allocate space for elements
  m_p = new int[m_elems = elements];
  // Set all elements to 0
  for (int i = 0; i < m_elems; i++)
    m_p[i] = 0;
}

// Copy Constructor
Vector::Vector(const Vector &source)
{
  // Allocate space for elements
  m_p = new int[m_elems = source.m_elems];
  // Copy values from source elements
  for (int i = 0; i < m_elems; i++)
    m_p[i] = source.m_p[i];
}

int &Vector::operator[](int i) const
{
  // Do bounds checking...
  assert( (i >= 0) && (i < m_elems) );

  // We're within bounds
  return m_p[i];
}

… and:

//
//  BoundedVector.h
//  Polymorphic Vector
//
//  Created by Bryan Higgs on 8/28/24.
//

#ifndef BoundedVector_h
#define BoundedVector_h

#include "Vector.h"

class BoundedVector : public Vector
{
public:
  // Constructor
  BoundedVector(int low, int high);
  
  int LowBound() { return m_low; }
  int HighBound() { return m_high; }
  int &operator[](int i) const
  { return Vector::operator[](i - m_low); }
private:
  int    m_low;  // Low bound
  int    m_high; // High bound
};

#endif /* BoundedVector_h */

… and:

//
//  BoundedVector.cpp
//  Polymorphic Vector
//
//  Created by Bryan Higgs on 8/28/24.
//

#include <iostream>
#include "BoundedVector.h"

// Constructor
BoundedVector::BoundedVector(int low, int high)
  : Vector((high - low) + 1),  // NOTE!
    m_low(low), m_high(high)
{
  if (low > high)      // Check the bounds
  {
    std::cerr << "\nLow bound " << low
              << " greater than high bound"
              << high << std::endl;
    exit(0);      // Abrupt exit!
  }
}

So, when we run the program, now we get:

Vector contents: 
[0] = 0
[1] = 1
[2] = 2
[3] = 3
[4] = 4
[5] = 5
BoundedVector contents: 
[-5] = Assertion failed: ((i >= 0) && (i < m_elems)), function operator[], file Vector.cpp, line 34.

In other words, the Print() function called by the main program worked for the Vector, but failed for the BoundedVector.

Why? How would you fix it?

Hint: Adding a single word to the declaration for a member function in the Vector class will fix it.

Another Important Case

Let’s go back to the Fruits example, and make some modifications. Let’s change the FruitList class so that its destructor cleans up the list and its fruits:

Let’s change the FruitList class, so that its destructor cleans up the list and its Fruits:

//
//  FruitList.cpp
//  Polymorphism
//
//  Created by Bryan Higgs on 8/28/24.
//

#include <iostream>
#include "FruitList.h"

FruitList::~FruitList()
{
  delete m_elem;  // delete this one's fruit
  if (m_next != 0)
    delete m_next;  // delete next in list
        // How does this work?
}


void FruitList::Print() const
{
  for (const FruitList *ptr = this;
       ptr != 0;
       ptr = ptr->m_next
      )
  {
    std::cout << ptr->m_elem->Type()
              << std::endl;
  }
}

We also add some explicit destructors for Fruit, Kiwi, and Kumquat, so we can instrument them with output:

//
//  Fruits.h
//  Polymorphism
//
//  Created by Bryan Higgs on 8/28/24.
//

#ifndef Fruits_h
#define Fruits_h

//  fruits.h
class Fruit
{
public:
  ~Fruit();
  virtual const char *Type() const
  { return "Fruit"; }
};

class Kiwi : public Fruit
{
public:  
  ~Kiwi();
  virtual const char *Type() const
  { return "Kiwi"; }
};

class Kumquat : public Fruit
{
public:
  ~Kumquat();
  virtual const char *Type() const
  { return "Kumquat"; }
};

#endif /* Fruits_h */

//
//  Fruits.cpp
//  Polymorphism
//
//  Created by Bryan Higgs on 8/28/24.
//

#include <iostream>
#include "Fruits.h"

Fruit::~Fruit()
{
    std::cout << "In ~Fruit()" << std::endl;
}

Kiwi::~Kiwi()
{
    std::cout << "In ~Kiwi()" << std::endl;
}

Kumquat::~Kumquat()
{
    std::cout << "In ~Kumquat()" << std::endl;
}

Finally, we add a line of code to the main program, so that the program cleans up after itself by deleting the allocated list:

//
//  main.cpp
//  Polymorphism
//
//  Created by Bryan Higgs on 8/28/24.
//

#include <iostream>
#include "FruitList.h"

int main(int argc, const char * argv[]) 
{
  FruitList *list = new FruitList(new Fruit, 0);
                       // A lone Fruit entry
  list = new FruitList(new Kiwi, list);
                       // Kiwi -> Fruit
  list = new FruitList(new Kumquat, list);
                       // Kumquat -> Kiwi -> Fruit
  list->Print();
  delete list; // delete allocated list
  
  return 0;
}

But the program now outputs the following:

Kumquat
Kiwi
Fruit
In ~Fruit()
In ~Fruit()
In ~Fruit()
Program ended with exit code: 0

What’s wrong?

How would you fix it?

Hint: Again, adding a single keyword to a single declaration of a member function produces the correct output:
Kumquat
Kiwi
Fruit
In ~Kumquat()
In ~Fruit()
In ~Kiwi()
In ~Fruit()
In ~Fruit()
Program ended with exit code: 0

Invoking the virtual Mechanism

When a virtual member function is invoked like this:

void Mumble()
{
  Fruit f;
  cout << "Type = " << f.Type() << endl;
}

then the Fruit::Type() function is always invoked (i.e. non-virtual).

However, when it is invoked like this:

void Sub(Fruit &f)
{
  cout << "Type = " << f.Type() << endl;
}

void Mumble()
{
  Kiwi  k;
  Fruit *f = &k;
  cout << "Type = " << f->Type() << endl;
  Sub(k);
}

then the virtual mechanism is used.

Summary of virtual Functions

A function is virtual if it is declared virtual, or if there is a base class function with the same signature that is virtual.

The signature match must be exact
In addition, the return type must also match
- if the return type is a pointer or reference to a class, then special rules apply

The virtual mechanism only works through pointers or references.

A virtual function must be a non-static member function of its class.

If a virtual function is defined in a base class, but is not defined in a derived class, then the base class function is the one used.

Only the base class needs to specify a member function be virtual.

A member function of the same signature in a derived class will automatically become virtual.
It is a good idea, however, to repeat the virtual keyword in derived class member functions.

Remember:

Overloaded operators that are member functions are no different from any other kind of member functions: they may need to be virtual, also.
A base class destructor needs to be virtual. Forget this at your peril!

virtual Function Caveats

If a member function in a base class is not overridden in the derived class and a function with the same name but different arguments is declared in the derived class, the function in the base class is hidden.

For example:

class Airplane
{
public:
	// ...
	void Steer(int degrees);
};

class AutoPilot
{
public:
	AutoPilot();
	// ...
};

class Airliner : public Airplane
{
public:
	// ...
	void Steer(AutoPilot &);	
		// hides Airplane::Steer(int)
};

Virtual functions work differently than you might expect in constructors and destructors:

//
//  main.cpp
//  Virtual Function Caveats
//
//  Created by Bryan Higgs on 8/28/24.
//

#include <iostream>

class Base
{
public:
  Base() { InConstr(); }
  ~Base() { InDestr(); }
  virtual void InConstr() const
  { std::cout << "In Base::Base()" << std::endl; }
  virtual void InDestr() const
  { std::cout << "In Base::~Base()" << std::endl; }
};

class Derived : public Base
{
public:
  virtual void InConstr() const
  { std::cout << "In Derived::Derived()" << std::endl; }
  virtual void InDestr() const
  { std::cout << "In Derived::~Derived()" << std::endl; }
};

int main()
{
  Base b;
  Derived d;
  
  return 0;
}

This program outputs:

In Base::Base()
In Base::Base()
In Base::~Base()
In Base::~Base()
Program ended with exit code: 0

When the Base constructor executes, the Derived class data members haven’t yet been initialized.
When the Base destructor executes, the Derived class data members have already been destroyed.

Abstract Base Classes

Sometimes we know the interface to some functionality, but we don’t know the implementation of that interface for every class in a hierarchy. For example, say we have a base class Shape that ‘represents’ different shapes which we will implement as derived classes. We know that every actual Shape that we can implement must have a draw() method, but Shape is too abstract a concept for us to be able to specify the implementation for it.

An abstract base class is a class that can be used only as a base class for some other class.

No instances of an abstract base class may be created, except as objects representing a base class of a class derived from it.

A class is abstract if it has at least one pure virtual function:

class Fruit
{
public:
	virtual const char *Type() const = 0;
	// Make Fruit an abstract base class
	// (it's too generic to be instantiated here)
}

whether that be directly, or through inheritance.

The ‘= 0‘ is known as a pure-specifier, and appears either immediately after the declarator for the virtual function.

So, let’s look at our previous Fruits example:

First, we make the Fruit::Type() method be pure virtual, and comment out the Kiwi::Type() method, to show the results:

//
//  Fruits.h
//  Abstract Base Classes
//
//  Created by Bryan Higgs on 8/29/24.
//

#ifndef Fruits_h
#define Fruits_h

class Fruit
{
public:
  virtual const char *Type() const = 0; // Pure virtual
};

class Kiwi : public Fruit
{
public:
  /* Intentionally omitted for exposition
  virtual const char *Type() const
  { return "Kiwi"; }
  */
};

class Kumquat : public Fruit
{
public:
  virtual const char *Type() const
  { return "Kumquat"; }
};

#endif /* Fruits_h */

The other files, Fruits.cpp, FruitList.h, FruitList.cpp, and main.cpp have no changes.

But main.cpp no longer compiles:

//
//  main.cpp
//  Abstract Base Classes
//
//  Created by Bryan Higgs on 8/29/24.
//

#include "FruitList.h"

int main(int argc, const char * argv[]) 
{
  FruitList *list = new FruitList(new Fruit, 0);
      // ERROR: Cannot instantiate Fruit
  list = new FruitList(new Kiwi, list);
      // ERROR: Cannot instantiate Kiwi
  list = new FruitList(new Kumquat, list);
      // No problem with Kumquat
  list->Print();
  return 0;
}

main.cpp:12:39 Allocating an object of abstract class type ‘Fruit’
Unimplemented pure virtual method ‘Type’ in ‘Fruit’

main.cpp:14:28 Allocating an object of abstract class type ‘Kiwi’
Unimplemented pure virtual method ‘Type’ in ‘Kiwi’

In the case of Fruit, this is goodness — class Fruit is too generic to be instantiated.

In the case of Kiwi, this is a way of discovering an omission in the class.

An abstract base class may not be used as:

a parameter type
a function return type
the type of an explicit conversion

However, pointers and references to an abstract base class may be declared. In fact, this is how they are typically used.

Defining and Enforcing an Interface

A very useful application of an abstract base class is to define and enforce a common interface that all classes derived from it must supply.

For example:

typedef int Operate(void *context, Containee &);

class Container
{
public:
	virtual void add(Containee &) = 0;
	virtual void remove(Containee &) = 0;
	virtual int  forAll(void *context,
			                Operate *func) = 0;
};

class Set : public Container ( ... }; 

class List : public Container { ... };

class Dictionary : public Container { ... };

The Role of a Base Class Virtual Function

A base class virtual function can:

Be non-pure virtual
- Useful when the base class provides a commonly used implementation.
- Derived classes may choose to use it, or provide their own.
Be pure virtual with no implementation
- Derived classes must provide their own implementation. There is no ‘default’.
Be pure virtual with an implementation
- Derived classes must provide their own implementation.
- The base class implementation may supply a ‘default’ behaviour; derived classes may choose to use it or augment it (by making an explicit call to the base implementation), or may completely override it.

Polymorphic Constructors?

It seems reasonable to ask:

“If we have polymorphic destructors, what about polymorphic constructors?”

A good question! In fact, C++ does not support polymorphic constructors. You have to resort to the use of a Factory Method.

A Factory Method is an implementation of the Factory pattern, as defined in the ‘Gang of Four’ Patterns book…

The ‘Gang of Four’ Patterns Book

Design Patterns: Elements of Reusable Object-Oriented Software

Erich Gamma, Richard Helm, Ralph Johnson, John M. Vlissides,

ISBN-10 ‏ : ‎ 0201633612
ISBN-13 ‏ : ‎ 978-0201633610
Publisher: Addison Wesley Professional

Highly recommended!

Summary

Well, we’ve covered a fair bit of ground:

Virtual functions
Virtual destructors
Abstract base classes
Interfaces
Virtual constructors; Factory patterns

There’s still much more to learn…

Onward!