Copyright © 2016-2024
Robert W. Hasker

Note 9: Inheritance

A Review of Types in Programming Languages

Why is understanding types important to understanding a programming language?
What are the three views of types
- internal: sequence of bits - how it's formed
- all data is numeric: mathematical view, allows logical reasoning about code
- mental models for programmers: abstract data type; data + (legal) operations
When is each relevant?
Knowing these: useful for understanding what language designers are describing...
Today: building on the ADT view: adding inheritance to C++
- Strong overlap with Java
- Some details are different, but the underlying principles are the same
- We will also investigate more detail on programming with classess
  - issues that are valid for both C++ and Java
  - the Java developer might be more successful in ignoring them

Inheritance, virtual methods

See sample Time class for basic inheritance
override: declare that you are overriding a method, like @override in Java
- That is, ensures the new method does redefine some method in the base class
virtual: enables inheritance polymorphism
- These are often called virtual functions
- It supports inheritance polymorphism
  - Example: a graphics image with squares, circles, etc: applying a draw operation to each would require making the draw method be virtual (in C++)
- subclass methods must have the same argument types, return type
- we say the subclass methods override the base class ones
Java: all methods are virtual
C++: can control which are virtual - desired because virtual methods do have overhead

what is the practical reason for inheritance?

    Time *submissions[20] = { new Time(10, 22),
                              new Time(13, 45),
                              new MilTime(13, 18),
                              new MilTime(23, 0),
                              new MilTime(5, 10),
                              new Time(1, 15)
                            };

    ...

    for(int i = 0; submissions[i] != nullptr; ++i) {
      submissions[i]->print(cout);
      cout << endl;
    }

": public" in the class header: means derived from
- If use ": private", then base class public methods are private in subclass
- This is never a good idea - why use inheritance if not going to follow the interface defined by the base class?
  - If pass the object to to a function that takes the base class as an argument, that function can still access those base class operations that we tried to hide!

Suppose we have public class Firefly extends Insect (in Java)

[In what order are the constructors called?]
These rules are the same in C++
[How are arguments to Insect's constructor specified?]

C++ version:

    class Insect {
    public:
      Insect(std::string species);
    };

    class Firefly : public Insect {
    public:
      Firefly(std::string species) : Insect(species) {
        // note: no super in C++
        // more code
      }
    };

Declaration vs. definition for classes
- Important for header files!
- Definition of a class:
```
        class A {
        public:
          int f();
        private:
          int num;
        };
```
  - That is, all data and prototypes for all methods
  - Method implementations can be separate (as discussed earlier)
  - Can also declare classes: class A;
  - Recall: declarations just say something exists, definitions give actual (computable) values

More on Pointers and Classes

Issue: if we create an instance of a class with new, it stays on the heap until the program exits
Review: todo lists
Question: when done with a todo item, how do we return its space to the (available) heap?

Fix: use delete to "undo" allocating the space:

        Task *todo = new Task("eat", 0.75);
        // code to process the item
        delete todo;

Returns the space allocated for the task to the heap - available for the next new operation

This does not change todo:

        delete todo;
        cout << todo->description();  // dangling pointer reference!
                                               // (random result)

Common practice, set todo to point to nothing:
```
        delete todo;
        todo = nullptr;
```
so later references to todo will cause run-time errors.
Note: if x is a nullptr,
```
        delete x;
```
is perfectly fine - it does nothing

Basic principle: a delete for every new

Suppose we have:

        TaskList *items = new TaskList();
        items->add(new Task("sleep", 8.0));
        items->add(new Task("eat breakfast", 0.25));
        items->add(new Task("learn something", 6.0));
        ...
        delete items;

Issue: all of the tasks on the list are still allocated

Fix: add a destructor to TaskList:

        class TaskList {
        ...
        public:
           ~TaskList() {
              for(int i = 0; i < count; ++i)
                delete todo[i];
           }

Now deleting the TaskList also deletes any tasks currently on the list

Warning: the following code is very dangerous:

        TaskList *items = new TaskList();
        Task *x = new Task("do something", 1.0);
        items->add(x);
        delete items;
        delete x;               // breaks the heap!

But Consider

    class Student {
      string name;
      string address;
      double total_grade_points, total_credits;
      Schedule *schedule;
    public:
      Student() : schedule{new Schedule},
                  total_grade_points{0.0},
                  total_credits{0.0},
                  name(""),
                  address("") 
      { }
      virtual ~Student() { delete schedule; }
      double gpa() const { return total_grade_points / total_credits; }
      virtual void add(Course *new_course);
    };

    class SpecialStudent : public Student {
      Certificate *cert;
    public:
      SpecialStudent() : cert{new Certificate} { }
      ~SpecialStudent() { delete cert; }
      void add(Course *new_course); ...
    };

When allocate a Student object, also allocate a Schedule object
delete student; - works, but doesn't reclaim the space for the schedule
- Every new must have a corresponding delete
- (Or the object must be able to exist until the end of the application)
Solution: add a "destructor":
```
    ~Student() { delete schedule; }
```
Note: add is virtual; can be redefined in subclasses

If add is virtual, then ~Student must be:

    virtual ~Student() { delete schedule; }

Destructor is called when exit scope as well:

    void doSomethingNice() {
      Student *someStudent = new SpecialStudent();
      ...
      delete someStudent;
    }

Abstract classes

    class AbstractContainer {
    public:
      virtual double& operator[](int index) = 0;
      virtual int size() = 0;
      virtual ~AbstractContainer() { }
    };

The = 0 syntax means the method is abstract or pure virtual
- These methods must be redefined - cannot create an object of type AbstractContainer
- All methods must be defined or get linker errors
  - Linker will say something like "unresolved symbol"
  - a class is abstract if it has at least one pure virtual method
- C++ has no special keyword for "all pure virtual"
- Thus the equivalent of a Java interface class is an all pure virtual class
Adding an implementation: simple_vector.h

Returning double& in operator[] means we can assign as well as use the value

Consider the code

   void swapFirstLast(AbstractContainer &nums) {
     int last_index = nums.size() - 1;
     assert(last_index > 0); // last_index can be 0!
     double save = nums[0];
     nums[0] = nums[last_index];
     nums[last_index] = save;
   }

and the call

        FixedVector xs;
        ...
        // first shall be last, last shall be first:
        swapFirstLast(xs);

How does this work?

note nums passed by reference to swapFirstLast

What would this call look like if inlined (ignoring the if statements checking indices against _size):

        AbstractContainer &nums = xs;
        int last_index = nums._size - 1;
        assert(last_index > 0);
        double *p_start = &nums.elements[0];
        double *p_end   = &nums.elements[last_index];
        double save = *p_start;
        *p_start = *p_end;
        *p_end = save;

so return by reference is the same as having a "hidden" pointer

Another example:

Code: train.h, train.cpp

How does C++ support inheritance?

Suppose we have the Python code
```
        x.do_something()
```
Question: how do we find the code to execute for do_something?
- Naive solution: x is class Derived, so see if do_something is in Derived
- If it isn't, look at the next class "up"; repeat
- That is, linear search for methods: slow as continental drift
- Implementations will optimize this, but always have some search over a collection

C++ solution: virtual function table or vtable

Start with the observation that the name of a function is a pointer to it:

        long fact(int n) { return n <= 0 ? 1 : n * fact(n - 1); }
        long pow2(int n) { return n <= 0 ? 1 : 2 * pow2(n - 1); }


        long (number_cruncher*)(int);
        if ( x > 0 )
           number_cruncher = pow2;
        else
           number_cruncher = fact;
        cout << (*number_cruncher)(x); // either pow2(x) or fact(x)

Vtable = an array of function pointers
The array stores the addresses of all virtual functions
Each object: must track what vtable to use

Consider

        class X {
        public:
          void a();
          virtual void b();
          virtual void c();
        };

        class Y : public X {
        public:
          void b() override;
          void d();
          virtual void e();
        };

Using these:

        X *something = new X(), *other = new Y();

[Draw something, other with vtable entry

vtable for X:

        +-------------------+
        |  &X::b  |  &X::c  |
        +-------------------+

a not in the table since it's not virtual

vtable for Y:

        +-----------------------------+
        |  &Y::b  |  &X::c  |  &Y::e  |
        +-----------------------------+

b, c always at slots 0, 1
"new" virtual functions in later slots

How to execute other->b?
How to execute other->c?
What happens if execute something->e?
- That's why
```
        Y *confused = new X(); 
```
  isn't just a "little" illegal!!

Larger example: See virtual function tables in train.s, starting at line 771
- (it's not clear if the 0, constructor are in the virtual function table; this may be additional information and the table might start at a constant offset from the first label
Result of using vtable: calling inherited methods requires a bit of extra code - must index the vtable array
- However: it is just a constant time operation - no method lookup
- virtual methods have a bit of overhead, but not much
Experiments: OO programs can run faster on many problems than non-OO programs because the non-OO versions need large if statements that are less efficient

Multiple Inheritance

See multiple_inheritance.cpp in sample code directory
[build with g++ multiple_inheritance.cpp]
Note problem: two ways to define Person
Known as the diamond problem
[rebuild with g++ -Wall multiple_inheritance.cpp]
Can be fixed, not covered here

Revisited Container

Recall FixedVector; consider when destructor called:
Usage:
```
    {
      int n; 
      cin >> n;
      FixedVector xs(n);
      ...        
      xs[1] = 23.4;             // this works because [] returns double&
      xs[0] = xs[1] / 2.0;
      ...
      {
        FixedVector ys(n * 2);
        ...
      } // ys destroyed here
      ...
    } // xs destroyed here
```
- In general: destructor called at end of lifetime (usually, when leave scope)
- if a class has a virtual function, the destructor must be virtual
  - Compiler will give warning if it is not virtual.
  - Deleting the object invokes the destructor of the derived class, that destructor will cause the base class destructor to execute
- Constructors cannot be virtual - it makes no sense
- What would happen if you made the constructor =0?
- For those who have had SWE 2410, Design and Cloud Patterns: How would you make a singleton object in C++?
Resource Acquisition Is Initialization (RAII):
- no naked new operations associated with stack-allocated objects
- move resource management into well-behaved abstractions
- If you move new, delete follows
- Applies to objects without identity; if an object should have just one instance (a bank account, a student object, an object representing a building in a city), use pointers
Initialization
- Add constructor FixedVector(std::initializer_list<double>)
  - initializer_list is an STL type known to the compiler
  - This allows FixedVector v1 = {1, 2, 3, 4, 5};
  - We won't cover the details on this.

Using Abstract Classes

Suppose we have a really large vector: megavector.h

Initialize container to a sequence:

    void initializeUpSequence(AbstractContainer *container,
                              double start, double step) {
      double value = start;
      for(int ix = 0; ix < container->size(); ++ix) {
        (*container)[ix] = value;
        value += step;
      }
    }

    ...
    AbstractContainer *some_numbers = new MegaVector();
    initializeUpSequence(some_numbers, 1.0, 0.1);
    double sum = 0.0;
    for(int i = 0; i < some_numbers->size(); ++i)
      sum += (*some_numbers)[i];

Note: initializeUpSequence cannot be
```
    void initializeUpSequence(AbstractContainer container,
                              double start, double step);
```
(with no *)
- Get a copy of the container without the parts that make it a sequence
- This creates an instance of an AbstractContainer, something C++ does not allow

But can use references:

    void initializeUpSequence(AbstractContainer &container,
                              double start, double step);

Win: cannot call initializeUpSequence(nullptr, 1, 2);
- That is, cannot pass nullptr to a reference

Pass-by-reference and Containers

Consider what happens when we pass a container by value:

    double first_and_last(MegaVector nums) {
      double sum = nums[0] + nums[nums.size() - 1];
      return sum;
    }

What is the big-O of

    MegaVector xs;
    ...
    double s = first_and_last(xs);

Better:

    double first_and_last(MegaVector &nums) {
      double sum = nums[0] + nums[nums.size() - 1];
      return sum;
    }

Issue: no protection against accidental changes:

    double sum = (nums[0] = 0.0) + nums[nums.size() - 1];

Better:

    double first_and_last(const MegaVector &nums) {
      double sum = nums[0] + nums[nums.size() - 1];
      return sum;
    }

However, need to revise class with const methods: revised_vector.h

Other examples of using const&
- Overloading < on students:
```
    bool operator<(const Student &a, const Student &b) {
      return a.name() < b.name();
    }
```
  - Avoid copying whole Student object just to compare names

Practical application: pass std::string by const reference:

        char firstInitial(const std::string &name) {
            return toupper(name[0]);
        }

Namespaces

Section 7.17
Another way to control scope (where an identifier is visible)
- Issue: two programmers could easily make a class Point with different purposes
- namespace: a way to (say) ensure the point used for the UI is different than the point used for calculating distances between GPS coordinates

declaring namespaces:

   namespace myNames
   {
      void getData(int&);
   };
   namespace yourNames
   {
      void getData(int&);
   };

For example, file iostream

        namespace std {
           class istream { ... };
           istream cin;

           class ostream { ... };
           ostream cout;
        };

and file string:

        namespace std {
           class string { ... };
        };

hence the need for using namespace std or std::cin, std::string

definitions:

   namespace myNames
   {
      void getData(int &x) { ... }
   };
   void yourNames::getData(int &y) {...}

calling methods:

   int i;
   myNames::getData(i);
   yourNames::getData(i);

using function:
```
    using myNames::getData;
```
All calls to getData now refer to myNames implicitly
using namespace:
```
    using namespace myNames;
```
for easy access to everything
string, cin, cout are all names in namespace std
- Private versions of these would be silly!
- If code compiles with either a::f or b::f and correctness depends on which one you use, reconsider your naming scheme!
- Stack overflow: "using namespace" is bad
- Stroustrup: uses using clauses everywhere!

Design principles for separate compilation

class/module xyz: xyz.h and xyz.cpp
- If have multiple classes that are closely related, will put them into a single .h file rather than one class per file
ensure xyz.h can be included multiple times
- ... using the #ifndef/#define/#endif
- Often known as "#ifdef magic"
xyz.h must be complete: if it refers to something in another header, include that header
- Or, do not even include the header: if just have X* data, can simply write
```
        class X;
```
  to declare that X is a class.
Do not put "using namespace std;" in a .h file
- use std::string whenever refer to standard classes
- This ensures client code can chose whether or not to use namespace std
First line of code in xyz.cpp: #include "xyz.h"
- makes sure xyz.h is complete
- generally include system libraries last - helps identify errors sooner rather than later

Review

override keyword
inheritance, virtual methods
declarations vs. definitions for classes
delete
abstract classes, pure virtual methods, pure virtual class
virtual function tables: vtables
more on containers
- when destructor called for locally allocated data
- RAII: Resource Acquisition Is Initialization
  - Avoiding having to use new, delete for "simple", stack-allocated objects
- Pass-by-reference with containers; using const& parameters
namespaces and the scope resolution operator
separate compilation
organizing #includes

Review

Consider the code

        class X {
        public:
          X();
          void update();
          void print() const;
        };

Which of the following are legal?
- void f(X a) { a.update(); }
- void g(X *b) { b->update(); }
- void h(X* c) { c->update(); }
- void i(X &d) { d.update(); }
- void j(const X &e) { e.update(); }
- void k(const X &u) { u.print(); }
- void l(X &v) { v.print(); }

Copyright © 2016-2024 Robert W. Hasker

Note 9: Inheritance

A Review of Types in Programming Languages

Inheritance, virtual methods

More on Pointers and Classes

Abstract classes

How does C++ support inheritance?

Multiple Inheritance

Revisited Container

Using Abstract Classes

Pass-by-reference and Containers

Namespaces

Design principles for separate compilation

Review

Review

Copyright © 2016-2024
Robert W. Hasker