Polymorphism

Polymorphism ("one interface, multiple methods"):

Compile-time polymorphism: operator overloading, function overloading.
Run-time polymorphism (dynamic binding): virtual function. This works only when used with pointers and references (the ability of a pointer or a reference of a base class to address any of its derived classes):
- Through the implicit conversion of a derived class pointer, a reference to a pointer or a reference of its public base type.
```
BaseName *pb = new DerivedName("Derived");
pb->Virtual(); // invokes DerivedName::Virtual()
BaseName b = DerivedName("Derived"); // ok, but already sliced
b.Virtual(); // invokes BaseName::Virtual()
```
- Through the virtual function mechanism.
- Through the dynamic_cast and typeid operators.
```
DerivedName *pd = dynamic_cast<DerivedName*>(pb);
```

The division between the public interface and private implementation of a class is referred to as information hiding. Two primary benefits provided:

If the private implementation of the class needs to be modified or extended, only the relatively small number of member functions requiring access to that implementation needs to be modified; the many user programs making use of the class generally do not need to be modified, although they may require recompiliation.
If there is an error in the state of the private class implementation, the amount of program code we need to examine in general is localized to the relatively small number of member functions requiring access to that implementation; the entire program need not be examined.

By declaring member function as virtual, it does not only continue to provide the interface to the class but also the inheritance hierarchy derived from it.

For a call to a nonvirtual function, the compiler selects the function that will be invoked at compile-time. The resolution of a virtual function call is delayed until run-time. At each call point within the executing program, the virtual function instance is selected based on the actual base or derived class type through which the function is being invoked.

The implementation of virtual functions requires that objects carry around with them some additional information that can be used at runtime to determine which virtual functions should be invoked on the object. In most compilers, this extra information takes the form of a pointer called a vptr ("virtual table pointer"). It points to an array of function pointers called a vtbl ("virtual table"); each class with virtual functions has an associated vtbl. When a virtual function is invoked on an object, the actual function called is determined by following the object's vptr to a vtbl and then looking up the appropriate function pointer in the vtbl.

Although declare virtual function inline can avoid function call overhead, compiler will still have to generate an out-of-line copy of the function to entered into the class's vtbl.

Static invocation of a virtual function is done using class scope operator. Override the virtual mechanism often for efficiency or to invoke pure virtual function statically.

BaseName *pb = new DerivedName("Derived");
pb->Virtual(); // invokes DerivedName::Virtual()
pb->BaseName::Virtual(); // resolved at compile-time

Declare a destructor virtual if it is going to used as base class and an object of a derived class may be destroyed through a pointer or reference to this class. It will call the derived class and then base class destructor.

class BaseName {
public:
  virtual ~BaseName(void) {}
};

class DerivedName : BaseName {
public:
  ~DerivedName(void) {} // will call ~BaseName() afterward
};

// usage in application
BaseName *pB = new DerivedName;
// ...
delete pB;	// will call DerivedName destructor

To make a class abstract but don't have any functions that are pure virtual, declare a pure virtual destructor. This class has a pure virtual function, so it's abstract, and it has a virtual destructor, so assured that no destructor problem. There is one twist, however: must provide a definition for the pure virtual destructor as compiler will call it at last. To avoid paying the overhead cost of a call to an empty function, declaring inline.

Unlike the base class constructor, the base class destructor, in general, should not be made protected. Otherwise, derived class destructor is protected when invoked through a base class pointer or reference, therefore cannot invoke in application.

Virtual function in base class constructor or destructor will be invoked as base class, to prevent it access derived class data members which haven't constructed or already destructed. Then the program is likely to crash.

Virtual function is a handy design tool, but can have big performance penalties:

Extra memory accesses
Virtual function dispatch can cause an unpredictable branch -- piplines can grind to a halt (note however, that some architectures have branch caches which can avoid this problem)
Less efficient than non-virtual function because they cannot be optimized by compilers (optimization occurs at compile-time, and virtual functions are resolved at run-time): it prevents inlining, instruction scheduling, data flow analysis, loop unrolling, etc.

When are virtual functions bad?

When the amount of code inside the virtual function is small (e.g. fewer than 25 flops), the overhead will be crucial.
When the virtual function is used frequently (e.g. inside a loop), can be determined with the help of a profiler.

Brittle base class problem

class Shape {
public:	// interface to users of Shapes
  virtual void draw() const;
  virtual void rotate(int degrees);
  // ...
protected: // common data (for implementers of Shapes)
  Point center;
  Color col;
  // ...
};

class Circle : public Shape {
public:	
  void draw() const;
  void rotate(int) { }
  // ...
protected:
  int radius;
  // ...
};

class Triangle : public Shape {
public:	
  void draw() const;
  void rotate(int);
  // ...
protected:
  Point a, b, c;
  // ...
};

The idea is that users manipulate shapes through Shape's public interface, and that implementers of derived classes (such as Circle and Triangle) share aspects of the implementation represented by the protected members. There are three serious problems with this apparently simple idea:

It is not easy to define shared aspects of the implementation that are helpful to all derived classes. For that reason, the set of non-public members is likely to need changes far more often than the public interface. For example, even though "center" is arguably a valid concept for all Shapes, it is a nuisance to have to maintain a point "center" for a Triangle.
The non-public members are likely to depend on implementation details that the users of Shapes would rather not have to depend on. For example, many (most?) code using a Shape will be logically independent of the definition of "Color", yet the presence of Color in the definition of Shape will probably require compilation of header files defining the operating system's notion of color.
When something in the non-public part changes, users of Shape have to recompile - even though only implementers of derived classes have access to the non-public members.

Thus, the presence of "information helpful to implementers" in the base class that also acts as the interface to users is the source of instability in the implementation, spurious recompilation of user code (when implementation information changes) and excess inclusion of header files into user code (because the "information helpful to implementers" needs those headers). The obvious solution is to make pure interfaces and this can decrease build times by orders of magnitudes.

If there really is some information that is common to all derived classes (or simply to several derived classes),

make that information a class and derive the implementation classes from that also (multiple inheritance).

class Shape {
public:	// interface to users of Shapes
  virtual void draw() const = 0;
  virtual void rotate(int degrees) = 0;
  virtual Point center() const = 0;
  // ...
  // no data
};

struct Common {
  Color col;
  // ...
};
		
class Circle : public Shape, protected Common {
public:	
  void draw() const;
  void rotate(int) { }
  Point center() const { return cent; }
  // ...
protected:
  Point cent;
  int radius;
};

class Triangle : public Shape, protected Common {
public:	
  void draw() const;
  void rotate(int);
  Point center() const;
  // ...
protected:
  Point a, b, c;
};

Pimpl idiom: a method of hiding implementation details by moving private members (both data and functions) of a class into an internal private struct (port to protected).

class Shape {
public:	// interface to users of Shapes
  Shape();
  ~Shape();
  virtual void draw() const = 0;
  virtual void rotate(int degrees) = 0;
  virtual Point center() const = 0;
  // ...
protected:
  struct ShapeImpl; // require forward declaration of internal struct
  ShapeImpl *pimpl; //opaque pointer
};

// in file Shape.cpp
struct Shape::ShapeImpl { // common data (for implementers of Shapes)
  Color col;
  // ...
};
// every Shape object allocates its own ShapeImpl object dynamically 
Shape::Shape(): pimpl (new ShapeImpl) {}
Shape::~Shape() { delete pimpl; }

class Circle : public Shape {
public:	
  void draw() const;
  void rotate(int) { }
  Point center() const { return cent; }
  // ...
protected:
  Point cent;
  int radius;
};
// access the ShapeImpl members using the pointer pimpl
void Circle::draw() const
{
  // pimpl->col ...
}

class Triangle : public Shape {
public:	
  void draw() const;
  void rotate(int);
  Point center() const;
  // ...
protected:
  Point a, b, c;
};

Another advantage is data types that are non-public members (for example, std::vector) need no longer be defined in the header file. This means can remove extra includes from header file (only include them in impelmentation file), thus reducing compilation time. But the penalties are:

Each construction and destruction allocates and release memory dynamically.
Pimpled version accesses its hidden data members using a pointer, whereas the non-Pimpled version accesses them directly.

Now can modify implementation without recompiling all source files including the header. It's always best to experiment with a few key-classes (heavily included) in a project and learn how this affects project's build-time.

Example using interface/ abstract base class:

Encapsulates an algorithm from a family
Allows algorithm to vary independently of the client

class DistanceBase {
public:
  virtual DistanceBase* Clone(void) const = 0;
  virtual double Distance(const vnl_vector<double>& v) = 0;

  // to load the NearestNeighbour class from disk need to know what type
  // of DistanceBase was saved
  virtual vcl_string IsDistance(void) const = 0;
  virtual void Write(vsl_b_ostream& bfs) const = 0;
  virtual void Read(vsl_b_istream& bfs) = 0;

protected:
  static vcl_string classname_; // to record name of class
};

// declare and define the vcl_string to hold the class name
vcl_string DistanceBase::classname_ = vcl_string("DistanceBase");

class L1Distance : public DistanceBase {
  virtual DistanceBase* Clone(void) const { return new L1Distance(*this); }
  virtual double Distance(const vnl_vector<double>& v) {
    double sum = 0.0;
    for (int i=0; i<v.size(); i++) sum += vcl_fabs(v);
    return sum;
  }

  vcl_string IsDistance(void) const { return vcl_string("L1Distance"); }
  void Write(vsl_b_ostream& bfs) const {
    vsl_b_write(bfs, IsDistance());
  }
  void Read(vsl_b_istream& bfs) {
    vcl_string name;
    vsl_b_read(bfs, name);
    if (name != IsDistance())
      throw UnmatchedObjectException;
  }
};

class L2Distance : public DistanceBase {
  virtual DistanceBase* Clone(void) const { return new L2Distance(*this); }
  virtual double Distance(const vnl_vector<double>& v) {
    return vcl_sqrt(dot(v,v));
  }

  vcl_string IsDistance(void) const { return vcl_string("L2Distance"); }
  void Write(vsl_b_ostream& bfs) const {
    vsl_b_write(bfs, IsDistance());
  }
  void Read(vsl_b_istream& bfs) {
    vcl_string name;
    vsl_b_read(bfs, name);
    if (name != IsDistance())
      throw UnmatchedObjectException;
  }
};

// client:
class NearestNeighbour {
public:
  // default constructor allow to construct objects with no arguments,
  // then set them up later, but need to check data member is set
  // each time member function access them
  NearestNeighbour(void) { Initialize(); }
  NearestNeighbour(DistanceBase& d) {
    // Keep a copy of an object better than point to the external object
    // such as d_ = &d; The external object must be in scope at all times.
    d_ = d.Clone();
  }
  NearestNeighbour(const NearestNeighbour& original) {
    Initialize();
    *this = original;	// use operator=()
  }
  ~NearestNeighbour(void) { delete d_; }
  NearestNeighbour& operator=(const NearestNeighbour& original) {
    if (this != &original)	// self-test
    {
      delete d_;
      d_ = NULL;
      if (original.d_ != NULL) d_ = original.d_->Clone();
    }
    return *this;
  }

  DistanceBase& GetDistanceBase(void) {
    if (d_ != NULL)
      return *d_;
    else
      throw NotInitializeException;
  }
  int Nearest(const vcl_vector<vnl_vector<double> >& data,
              const vnl_vector<double>& v);	// use d_->Distance(dv)
  void Write(vsl_b_ostream& bfs) const {
    d_->Write(bfs);
    vsl_b_write(bfs, *d_);
  }
  void Read(vsl_b_istream& bfs) {
    d_->Read(bfs);
    delete d_;
    d_ = NULL;
    vsl_b_read(bfs, d_);	// load by pointer
  }

protected:
  // refer pre-declaring class by pointer/reference speed up compilation
  // and reduce dependency
  DistanceBase* d_;

  Initialize(void) {
    d_ = NULL;
  }
};

// usage in application
L1Distance distance1;
L2Distance distance2;
NearestNeighbour nearest1(distance1);	// use L1 metric
NearestNeighbour nearest2(distance2);	// use L2 metric

Index