Summary

Today's lab session covers class inheritance and the use of abstract classes. Of special importance are the details concerning creation, destruction and copying of objects within class hierarchies. Along the way you will learn a small & handy C++11 feature. The main exercise builds upon the function-plotter exercise you did last week.

Class inheritance

Designing class hierarchies by deriving concrete classes from more abstract ones is one of the most essential features of object-oriented programming languages; also C++. A point worth noting is that the concept of deriving classes predates the introduction of C++ by roughly 15 years. By no means is C++ a purely object-oriented language, nor is it the most elegant implementation of the principles. Being a very popular general purpose language, C++ has many of the features that allow for an object-oriented approach of designs. Keep in mind though, that there are many other languages that are "more object-oriented" than C++. Do some reading if you're interested in some more details. Since the lab sessions are all about practical examples, we'll jump right into the syntax of deriving a class Derived from another class Base:

class Base {
    public:
        void foo();
};

class Derived : public Base {
    public:
        void bar();
};

In this simple case, the UML diagram (generated from the above code snippet with Doxygen by the way) looks like: Objects of the Derived class have two members: foo (derived from Base) and bar (defined in Derived). Therefore, the following is valid:

Derived d;
d.foo();
d.bar();

More generally: a member of a derived class can use the public and protected members of its base class as if they were declared in the derived class.

Note the public inheritance. This means that all access modifiers (public, private and protected) of the Base class members stay the same in Derived. This is the most common scenario we'll encounter. Two other possibilities are:

• protected: public members of Base become protected in Derived
• private: all members from Base become private in Derived

Constructors & destructors

If Base has constructors, they must be invoked in Derived. This invocation can be implicit (i.e., automatic) in the case of a default constructor. On the other hand, if Base's constructor needs arguments, it must be called explicitly. This can be summarized as: constructors are never inherited. Also, you can't directly initialize members of Base in the constructor of Derived; even if they're not private (assignment works though).

Base.h:

class Base {
    public:
        Base(int a);
};

Base.cpp:

Base::Base(int a) {
    ...
}

Derived.h:

class Derived : public Base {
    public:
        Derived(int a, int b);
};

Derived.cpp:

Derived::Derived(int a, int b)
    : Base(a) { // <- EXPLICIT call to Base's non-default constructor
    ...
}

The order in which objects are created can be summarized as:

• Objects are constructed bottom-up: base class, members, derived class
• Objects are destroyed top down: derived class, members, base class
• Members & base classes are constructed in order of declaration
• Members & base classes are destroyed in reverse order of declaration

C++11 additions

The above is not 100% true anymore. Please learn about constructor inheritance here and here to see what's been added to C++11 to ease object creation for inherited classes.

Suppose the following scenario:

Base.h:

class Base {
    public:
        Base(int a);
};

Base.cpp:

Base::Base(int a) {
    cout << "Base constructor, a = " << a << endl;
}

Derived.h:

class Derived : public Base {
};

main.cpp:

// -- SNIP --

Derived d(1);

// -- SNAP --

My g++ fails with error: no matching function for call to 'Derived::Derived(int)'. C++11 provides a way to fix this. Read the above Wikipedia article and make the example work! In both articles, another interesting C++11 feature is discussed: constructor delegation. Which part of the following snippet relate to constructor inheritance and which part to constructor delegation?

class Base {
public:
    Base(int n) : number(n) {};
private:
    int number;
};

class Derived: public Base {
public:
    using Base::Base;
    Derived() : Derived(5) {};
};

Making copies of objects

Suppose you're doing this:

Derived d;
Base b = d;

or an assignment like:

Derived d;
Base b;
b = d;

The result is that b only knows about Base properties of d. All the rest is not copied. This is called slicing. There's an interesting consequence of how constructors are handled in class hierarchies when you're making copies of objects. Consider:

Base.h:

class Base {
    public:
        Base();
        Base(const Base&);
};

Base.cpp:

Base::Base() {
    cout << "Base::Base()" << endl;
}

Base::Base(const Base&) {
    cout << "Base::Base(const Base&)" << endl;
}

Derived.h:

class Derived : public Base {
    public:
        Derived();
        Derived(const Derived&);
};

Derived.cpp:

Derived::Derived() {
    cout << "Derived::Derived()" << endl;
}

Derived::Derived(const Derived&) {
    cout << "Derived::Derived(const Derived&)" << endl;
}

What's the output when I do:

Derived d;
Derived d_copy(d);

Do you think what you see is the expected behaviour? If not, what's wrong, and how should you fix it? Check if the assignment operator operator= is similar in how the above situation is handled.

Pointers / references

Contrary to the above, when passing around pointers or references to objects, no copies are involved, nor is there any slicing (i.e., no information is lost). For example:

Derived* d_ptr = new Derived;
Base* b_ptr = d_ptr;

Now b_ptr pretends to be a pointer to Base but is actually pointing to a Derived object. This brings us to the important subject of virtual functions.

Virtual functions

Referring to Derived objects through a pointer / reference to Base allows using polymorphic method calls. Try this example:

Base.h:

class Base {
    public:
        virtual void print_info();
};

Base.cpp:

void Base::print_info() {
    cout << "Base::print_info()" << endl;
}

Derived.h:

class Derived : public Base {
    public:
        virtual void print_info(); // NOTE: 'virtual' is optional here, 'override' might be better.
};

Derived.cpp:

void Derived::print_info() {
    cout << "Derived::print_info()" << endl;
}

Note that the keyword virtual only appears in the class definition (.h file); NOT in the definition of its methods (.cpp file)!

Now, different print_info methods will be called depending on object's type:

Base* b_ptr = new Base;
Derived* d_ptr = new Derived;
Base* b_ptr2 = new Derived;
Base& b_ref = *d_ptr;

b_ptr->print_info();    // Base::print_info()
d_ptr->print_info();    // Derived::print_info()
b_ptr2->print_info();   // Derived::print_info() !!!
b_ref.print_info();     // Derived::print_info() !!!

In all cases the object's dynamic type determines which method is called. The dynamic type is the type of the object pointed to at runtime (remember that a pointer to a Base object can actually point to a Derived object).

The C++ FAQ lite has a whole section on virtual functions. Especially the part on how virtual functions work internally is interesting if you want a deeper knowledge of C++!

Abstract classes

A slight downside to virtual functions as defined above is that you are required to implement all methods, even if they really don't do anything useful yet, as might be the case in the Base class. More often than not a base class specifies how derived classes should look like (i.e., the interface). The consequence is that many of the base class methods end up having an empty body.

class TheAnswer {
    public:
        virtual int get() {
            // The base class represents a concept that is too general to
            // decide what exectly should be returned. However, the get()
            // method needs to be implemented or the code won't compile.
            // If you turn on all warnings in gcc with -Wall, you'll even
            // get:
            //  warning: no return statement in function returning non-void
            // but you don't know what to return!
            // Surely there must be a better way to handle this...
        }
};

class TheAnswerToLifeTheUniverseAndEverything : public TheAnswer {
    public:
        virtual int get() {
            return 42;
        }
};

The solution to the above problem is declaring TheAnswer::get() to be a pure virtual function. A pure virtual function has no definition, only a zero-initializer:

class TheAnswer {
    public:
        // We don't need to make up answers just to please the compiler!
        virtual int get() = 0;
}

As you might have guessed, it now doesn't make any sense to create objects of the type TheAnswer since they don't know how to behave if you call their get() method. Any attempt to compile this:

TheAnswer a;

Indeed gives:

error: cannot declare variable 'a' to be of abstract type 'TheAnswer'
note:  because the following virtual functions are pure within 'TheAnswer':
note:   virtual int TheAnswer::get() = 0;

As GCC's error message hints, we'll call TheAnswer an abstract base class. Read C++ FAQ's section on abstract base classes now.

Notes

• A pure virtual function that is not defined in a derived class remains a pure virtual function. Therefore, the derived class remains an abstract class.
• This way, layers of abstraction can be stacked together.
• Abstract classes represent abstract concepts and work as interfaces for its derived classes to enforce a certain structure.
• A pure virtual function may be defined in the base class if its functionality is used frequently in most of the derived classes. The zero-initializer still ensures the abstract behaviour of the base class.

Run-time type information

(often abbreviated as RTTI)

In the context of class hierarchies three different types of casts can be performed between pointers (or references) to objects of different types:

• upcast: from Derived* to Base*
• downcast: from Base* to Derived*
• crosscast: from a Base1* to a Base2 (only for multiple inheritance)

Upcast

"Whatever points to an object of the Derived class, must also point to a Base":

Derived* d_ptr = new Derived;
Base* b_ptr = d_ptr;

Downcast

"If you've got a pointer to a Base object, you can't assume it's pointing to a Derived object". Unless you know for sure, in which case you can use a dynamic_cast:

Base* b_ptr = new Derived;
Derived* d_ptr = dynamic_cast<Derived*>(b_ptr);

Note that the use of dynamic_cast is often frowned upon, as this usually means you applied polymorphism incorrectly. Look at the concept of duck typing and the Liskov substitution principle for when to correctly apply inheritance. An alternative to downcasting can be a double dispatch, potentially in combination with the visitor pattern. Also, have a look at some discussions about the use of dynamic_cast, for instance here or here.

Crosscast

Google exercise: look it up!

Notes

RTTI deals with the case in which the correctness of the type conversion cannot be determined by the compiler at compile-time and must be postponed until run-time. The primary purpose of the dynamic_cast operator is to perform type-safe downcasts. If the conversion fails, a null pointer is returned. In the case of references, a bad_cast exception is thrown.

You can use it for checking the exact type of a polymorphic object:

// Both Derived1 and Derived2 are subclasses of Base
void f(Base* b_ptr) {
    if (Derived1* d1_ptr = dynamic_cast<Derived1*>(b_ptr)) {
        d1_ptr->derived1Method();
    } else if (Derived2* d2_ptr = dynamic_cast<Derived2*>(b_ptr)) {
        d2_ptr->derived2Method();
    } else {
        b_ptr->baseMethod();
    }
}

Exercises

Plotting polynomials, part 2

Last week, you designed a Plotter class for plotting general functions that evaluated a polynomial in an interval between a and b and printed those values. This week you'll create a concrete implementation of a plotter class that uses the SFML library for graphical output.

• Start by subclassing Plotter with a class PlotterSFML. The constructor of PlotterSFML should take care of setting up the graphical context. Its destructor should handle the clean-up.

• The plot(const Polynomial &polynomial, double a, double b, unsigned int n) method does all the work of evaluating the function f in n points equally spaced in the interval [a,b] and plotting it on the screen.

• You'll also need to perform a coordinate transformation to map the [a,b] and [f(a),f(b)] intervals on the available window width and height.

• Make sure the Plotter base class is abstract by declaring Plotter::plot(...) pure virtual.

• You will need to do some research on how to use SFML; this tutorial is a decent starting point. For drawing the function f as a set of subsequent points connected by lines I suggest you use sf::LinesStrip, see here.

Using SFML with CMake

CMake does not know where or how to find SFML by default. You'll have to instruct it where to look for SFML. CMake comes bundled with a variety of Find<WhateverLibrary>.cmake scripts that are used for discovering components required for compilation. Luckily, FindSFML.cmake is included in the current CMake distribution, but for older versions you might have to manually include it inside a cmake/Modules folder as part of your project.

You can instruct CMake to look for the SFML library using FIND_PACKAGE(SFML COMPONENTS system window graphics). Next, we need to make sure the compiler knows where to find the SFML header files that we include in our code, by using INCLUDE_DIRECTORIES(${SFML_INCLUDE_DIR}).

Finally, CMake needs to instruct the linker to link our compiled binary to the SFML libraries, which is done using TARGET_LINK_LIBRARIES(plotter ${SFML_LIBRARIES}).

Start with the following

CMAKE_MINIMUM_REQUIRED(VERSION 2.8.12)
PROJECT(PlottingPolynomials)
ADD_EXECUTABLE(plot src/Plotter.cpp src/Polynomial.cpp src/main.cpp)

And the code:

// Polynomial.h
#ifndef POLYNOMIAL_H
#define POLYNOMIAL_H

#include <vector>
#include <ostream>

class Polynomial {
    public:
        /**
         * Creates a polynomial with coefficients from coeff.
         * Coefficients are ordered from x^0 to x^n.
         */
        Polynomial(std::vector<double> coeff);

        /**
         * Evaluates the polynomial in a point x using a naive method.
         */
        double apply(double x) const;

        /**
         * Evaluates the polynomial in a point x using Horner's method.
         */
        double eval_horner(double x) const;

        /**
         * Returns the first derivative of a polynomial as a new Polynomial.
         */
        Polynomial derive() const;

        /**
         * Unary - operator.
         */
        Polynomial operator-() const;

        /**
         * Binary + operator.
         */
        Polynomial operator+(const Polynomial& that) const;

        /**
         * Binary - operator.
         */
        Polynomial operator-(const Polynomial& that) const;

        /**
         * Binary * operator.
         */
        Polynomial operator*(const Polynomial& that) const;

        /**
         * += operator
         */
        Polynomial& operator+=(const Polynomial& that);

        /**
         * -= operator
         */
        Polynomial& operator-=(const Polynomial& that);

        /**
         * *= operator
         */
        Polynomial& operator*=(const Polynomial& that);

        // Make sure ostream::operator<< has access to Polynomial's internals
        friend std::ostream& operator<<(std::ostream& out, const Polynomial& p);

    private:
        std::vector<double> m_coeff;    /// Polynomial's coefficients
};

#endif /* POLYNOMIAL_H */

// Polynomial.cpp
#include "Polynomial.h"
#include <iostream>
#include <iomanip> // For std::setw()

Polynomial::Polynomial(std::vector<double> coeff)
    : m_coeff(coeff) {
}

double Polynomial::apply(double x) const {
    double x_pow = 1.0;
    double result = 0.0;
    for (double a : this->m_coeff) {
        result += a * x_pow;
        x_pow *= x;
    }
    return result;
}

double Polynomial::eval_horner(double x) const {
    double result = 0.0;
    for (auto it = m_coeff.crbegin(); it != m_coeff.crend(); ++it) {
        result *= x;
        result += *it;
    }
    return result;
}

Polynomial Polynomial::derive() const {
    std::vector<double> d_coeff(m_coeff);
    unsigned int n = 0;
    for (double& a : d_coeff) {
        a *= (n++);
    }
    return Polynomial(d_coeff);
}

Polynomial Polynomial::operator-() const {
    Polynomial result(*this);
    for (double& a : result.m_coeff) {
        a = -a;
    }
    return result;
}

Polynomial Polynomial::operator+(const Polynomial& that) const {
    // Sizes of both polynomial's coefficient vectors
    size_t this_n = this->m_coeff.size();
    size_t that_n = that.m_coeff.size();

    // a are the coefficients of the polynomial with the largest degree
    const std::vector<double>& a = this_n > that_n ? this->m_coeff : that.m_coeff;

    // b are the coefficients of the polynomial with the smallest degree
    const std::vector<double>& b = this_n > that_n ? that.m_coeff : this->m_coeff;

    // Create result with coefficients from a (higher degree poly.)
    Polynomial result(a);
    // ... and add up coefficients from b (smaller degree poly.)
    for (size_t i = 0; i < b.size(); ++i) {
        result.m_coeff.at(i) += b.at(i);
    }

    return result;
}

Polynomial Polynomial::operator-(const Polynomial& that) const {
    return (*this) + (-that);
}

Polynomial Polynomial::operator*(const Polynomial& that) const {
    size_t a_n = this->m_coeff.size();
    size_t b_n = that.m_coeff.size();

    Polynomial result(std::vector<double>(a_n + b_n - 1));
    for (size_t i = 0; i < a_n; ++i) {
        for (size_t j = 0; j < b_n; ++j) {
            result.m_coeff.at(i + j) += this->m_coeff.at(i) * that.m_coeff.at(j);
        }
    }

    return result;
}

Polynomial& Polynomial::operator+=(const Polynomial& that) {
    *this = (*this) + that;
    return *this;
}

Polynomial& Polynomial::operator-=(const Polynomial& that) {
    *this = (*this) - that;
    return *this;
}

Polynomial& Polynomial::operator*=(const Polynomial& that) {
    *this = (*this) * that;
    return *this;
}


std::ostream& operator<<(std::ostream& out, const Polynomial& p) {
    out << "Polynomial coeff. (increasing order): ";
    for (double a : p.m_coeff) {
        out << std::setw(4) << a;
    }
    return out;
}

// Plotter.h
#ifndef PLOTTER_H
#define PLOTTER_H

#include <functional>
#include "Polynomial.h"

class Plotter {
    public:
        /**
         * f: double -> double function
         * a: left point of [a,b]
         * b: right point of [a,b]
         * n: number of points in [a,b]; including a & b
         */
        static void plot(const Polynomial &polynomial, double a, double b, unsigned int n);
    private:
};

#endif /* PLOTTER_H */

// Plotter.cpp
#include "Plotter.h"
#include "Polynomial.h"
#include <iostream>
#include <vector>

void Plotter::plot(const Polynomial &polynomial, double a, double b, unsigned int n) {
    // The 1D grid to use for plotting & evaluation of f(x)
    std::vector<double> x(n);
    // Evaluated values of f in all grid points x
    std::vector<double> fx(n);
    // Distance between subsequent grid points
    const double h = (b - a) / (n - 1);

    size_t i = 0;
    for (double& x_i : x) {
        x_i = a + i * h;
        fx.at(i) = polynomial.apply(x_i);
        std::cout << x_i << " -> " << fx.at(i) << std::endl;
        ++i;
    }
}

// main.cpp
#include "Polynomial.h"
#include "Plotter.h"

int main() {
    Polynomial a{{3, 2, 1}};
    Plotter::plot(a, -20, 20, 200);
}

The final CMakeLists.txt file could look like this:

CMAKE_MINIMUM_REQUIRED(VERSION 2.8.12)
PROJECT(Plotter)
IF (CMAKE_INSTALL_PREFIX_INITIALIZED_TO_DEFAULT)
    SET (CMAKE_INSTALL_PREFIX "${CMAKE_BINARY_DIR}/installed" CACHE PATH "default install path" FORCE)
ENDIF()

# Look for SFML >= 2.0, with the specific subcomponents listed below
FIND_PACKAGE(SFML 2 COMPONENTS system window graphics)

# The source files to compile
SET(SRC src/Plotter.cpp src/PlotterSFML.cpp src/Polynomial.cpp src/main.cpp)

# Add include dirs for SFML
INCLUDE_DIRECTORIES(${SFML_INCLUDE_DIR})

# The program we're compiling with the sources set above
ADD_EXECUTABLE(plotter ${SRC})

# Link target to SFML libs
TARGET_LINK_LIBRARIES(plotter sfml-system sfml-graphics sfml-window)

# Install our executable to the CMAKE_INSTALL_PREFIX/bin
INSTALL(TARGETS plotter DESTINATION bin)

Virtual destructors

Write a simple program to show why destructors should always be declared virtual in the context of derived classes.

Start from the following code:

#include <iostream>

class Base {
public:
    Base(int value) : m_value(new int(value)) {}
    ~Base() {
        std::cout << "Base::~Base called" << std::endl;
        delete m_value;
    }
private:
    int *m_value;
};

class Derived : public Base {
public:
    Derived(int base_value, int derived_value) : Base(base_value), m_derived_value(new int(derived_value)) {}
    ~Derived() {
        std::cout << "Derived::~Derived called, ";
        delete m_derived_value;
    }
private:
    int *m_derived_value;
};

int main() {
    // your code here.
    return 0;
}