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: allows redefining method in subclass
  • 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() { 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;
          ...
          // destructor called here
        }
    

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
• 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;
       }
    
    
       ... declare xs to be some class derived from AbstractContainer
       ... and read data into the container
       // first shall be last, last shall be first:
       swapFirstLast(xs);
    

    • nums passed by reference
    • code generated by this: equivalent to returning a pointer and then dereferencing that pointer on each access:

          double* p = &nums[0];
          *p = nums[last_index];
      

• Putting it all together:
• 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 6912
  • (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

Container

• Have already seen containers in previous examples
• from Stroustrup ch. 4, implementing an arbitrary-size vector with destructor: simple_vector.h
  • Note return by reference: double&
  • useful as both an l-value and an r-value
  • r-value: value on the right-hand-side of an assignment - the contents
  • l-value: value on left-hand-side of assignment - the address
• 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);
  

  however, the pointer version makes it more obvious that the object is on the heap

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

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