ch08.htm

C++ From Scratch: An Object-Oriented Approach is designed to walk novice programmers through the ana

  first the constructor for the base class is called, and then the constructor 
  for the derived class is called. Figure 8.2 shows how the <tt>InternalNode</tt> 
  object looks after it is created. Note that the <tt>Node</tt> part of the object 
  is contiguous in memory with the <tt>InternalNode</tt> part.</p>
<p><b>Figure 8.2</b><tt><b> </b></tt><i>The <tt>InternalNode</tt> object after 
  it is created.</i></p>
<p>When a virtual function is created in an object, the object must keep track 
  of that function. Many compilers build a virtual function table, called a <i>v-table</i>. 
  One of these tables is kept for each type, and each object of that type keeps 
  a virtual table pointer (called a <i>vptr</i> or <i>v-pointer</i>) that points 
  to that table. (Although implementations vary, all compilers must accomplish 
  the same thing, so you won't be too wrong with this description.)</p>
<blockquote>
  <hr>
  <p><strong> </strong> <b>v-table</b>--The virtual function table used to achieve 
    polymorphism</p>
  <p> <b>vptr or v-pointer</b>--The Virtual Function Table Pointer, which is provided 
    for every object from a class with at least one virtual method</p>
  <hr>
</blockquote>
<p>Each object's vptr points to the v-table that, in turn, has a pointer to each 
  of the virtual functions. When the <tt>Node</tt> part of the <tt>InternalNode</tt> 
  is created, the vptr is initialized to point to the correct part of the v-table, 
  as shown in Figure 8.3.</p>
<p><b>Figure 8.3</b><tt><b> </b></tt><i>The v-table of a node.</i></p>
<p>When the <tt>InternalNode</tt> constructor is called and the <tt>InternalNode</tt> 
  part of this object is added, the vptr is adjusted to point to the virtual function 
  overrides (if any) in the <tt>InternalNode</tt> object (see Figure 8.4).</p>
<p><b>Figure 8.4</b><tt><b> </b></tt><i>The v-table of a <tt>InternalNode</tt>.</i></p>
<p>When a pointer to a <tt>Node</tt> is used, the vptr continues to point to the 
  correct function, depending on the "real" type of the object. Thus, when <tt>Insert()</tt> 
  is invoked, the correct (<tt>InternalNode</tt>) version of the function is invoked. 
  <a name="_Toc447529664"></a></p>
<h3> <a name="Heading11">Virtual Destructors</a></h3>
<p>It is legal and common to pass a pointer to a derived object when a pointer 
  to a base object is expected. What happens when that pointer to a derived subject 
  is deleted? If the destructor is virtual, as it should be, the right thing happens: 
  The derived class's destructor is called. Because the derived class's destructor 
  automatically invokes the base class's destructor, the entire object is properly 
  destroyed.</p>
<p>The rule of thumb is this: If any of the functions in your class are virtual, 
  the destructor needs to be virtual as well.</p>
<p>The ANSI/ISO standard dictates that you <i>can</i> vary the return type, but 
  few compilers support this. If you change the signature--the name, number, or 
  type of parameters or whether the method is <tt>const</tt>--you are not overriding 
  the method, you are adding a new method.</p>
<p>It is important to note that if you add a new method with the same name as 
  another method in the base class, you hide the base class method and the client 
  can't get to it. Take a look at Listing 8.1, which illustrates this point.</p>
<h4> Listing 8.1 Hiding the Base Class Method</h4>
<pre>
<tt>0:  #include &lt;iostream&gt;</tt>
<tt>1:  using namespace std;</tt>
<tt>2:  </tt>
<tt>3:  class Base</tt>
<tt>4:  {</tt>
<tt>5:  public:</tt>
<tt>6:      Base() { cout &lt;&lt; "Base constructor\n"; }</tt>
<tt>7:      virtual ~Base() { cout &lt;&lt; "Base destructor\n"; }</tt>
<tt>8:      virtual void MethodOne() { cout &lt;&lt; "Base MethodOne\n"; }</tt>
<tt>9:      virtual void MethodTwo() { cout &lt;&lt; "Base MethodTwo\n"; }</tt>
<tt>10:      virtual void MethodThree() </tt>
<tt>11:          { cout &lt;&lt; "Base MethodThree\n"; }</tt>
<tt>12:  private:</tt>
<tt>13:  };</tt>
<tt>14:  </tt>
<tt>15:  class Derived : public Base</tt>
<tt>16:  {</tt>
<tt>17:  public:</tt>
<tt>18:      Derived() { cout &lt;&lt; "Derived constructor\n"; }</tt>
<tt>19:      virtual ~Derived() { cout &lt;&lt; "Derived destructor\n"; }</tt>
<tt>20:      virtual void MethodOne() { cout &lt;&lt; "Derived MethodOne\n"; }</tt>
<tt>21:      virtual void MethodTwo() { cout &lt;&lt; "Derived MethodTwo\n"; }</tt>
<tt>22:      virtual void MethodThree(int myParam) </tt>
<tt>23:          { cout &lt;&lt; "Derived MethodThree\n"; }</tt>
<tt>24:  private:</tt>
<tt>25:  };</tt>
<tt>26:  </tt>
<tt>27:  int main()</tt>
<tt>28:  {</tt>
<tt>29:  </tt>
<tt>30:      Base * pb = new Base;</tt>
<tt>31:      pb-&gt;MethodOne();</tt>
<tt>32:      pb-&gt;MethodTwo();</tt>
<tt>33:      pb-&gt;MethodThree();  </tt>
<tt>34:  //    pb-&gt;MethodThree(5);  </tt>
<tt>35:      delete pb;</tt>
<tt>36:      cout &lt;&lt; endl;</tt>
<tt>37:  </tt>
<tt>38:      Base * pbd = new Derived;</tt>
<tt>39:      pbd-&gt;MethodOne();</tt>
<tt>40:      pbd-&gt;MethodTwo();</tt>
<tt>41:      pbd-&gt;MethodThree();   </tt>
<tt>42:  //    pbd-&gt;MethodThree(5);  </tt>
<tt>43:      delete pbd;</tt>
<tt>44:      cout &lt;&lt; endl;</tt>
<tt>45:  </tt>
<tt>46:      Derived * pd = new Derived;</tt>
<tt>47:      pd-&gt;MethodOne();</tt>
<tt>48:      pd-&gt;MethodTwo();   </tt>
<tt>49:  //    pd-&gt;MethodThree();    </tt>
<tt>50:      pd-&gt;MethodThree(5);  </tt>
<tt>51:      delete pd;</tt>
<tt>52:  </tt>
<tt>53:      return 0;</tt>
<tt>54:  }</tt>
<tt>Base constructor</tt>
<tt>Base MethodOne</tt>
<tt>Base MethodTwo</tt>
<tt>Base MethodThree</tt>
<tt>Base destructor</tt>
<tt>Base constructor</tt>
<tt>Derived constructor</tt>
<tt>Derived MethodOne</tt>
<tt>Derived MethodTwo</tt>
<tt>Base MethodThree</tt>
<tt>Derived destructor</tt>
<tt>Base destructor</tt>
<tt>Base constructor</tt>
<tt>Derived constructor</tt>
<tt>Derived MethodOne</tt>
<tt>Derived MethodTwo</tt>
<tt>Derived MethodThree</tt>
<tt>Derived destructor</tt>
<tt>Base destructor<a name="WhereWasI"></a></tt>
</pre>
<p>In this example, we create a <tt>Base</tt> class and a <tt>Derived</tt> class. 
  The <tt>Base</tt> class declares three methods virtual on lines 8-10, which 
  will be overridden in the <tt>Derived</tt> class.</p>
<p>The overridden <tt>MethodThree</tt> differs from the base class's version in 
  that it takes an extra parameter. This overloads the method (rather than overrides 
  it) and <i>hides</i> the base class method. What is the effect? Let's see. </p>
<p>On line 30 we declare a pointer to a <tt>Base</tt> object, and we use this 
  pointer to invoke <tt>MethodOne</tt>, <tt>MethodTwo,</tt> and both versions 
  of <tt>MethodThree</tt>. The second, shown on line 34, won't compile and so 
  is commented out. It won't compile because <tt>Base</tt> objects know nothing 
  about this overload version.</p>
<p>The output shows that a <tt>Base</tt> constructor is called, followed by the 
  three <tt>Base</tt> methods, ending with a call to the <tt>Base</tt> destructor. 
  Pretty much as we might expect.</p>
<p>On line 38 we declare a pointer to a <tt>Base</tt> and initialize it with a 
  <tt>Derived</tt>. This is the polymorphic form: We assign a specialized object 
  to a pointer to a more general object. We call <tt>MethodOne</tt>, <tt>MethodTwo</tt>, 
  and <tt>MethodThree,</tt> and they compile fine until we try to compile the 
  version that takes an <tt>int</tt>. Because this is a pointer to a <tt>Base</tt>, 
  it can't find this method and won't compile. </p>
<p>Let's look at the output. We see the <tt>Base</tt> constructor, and then the 
  <tt>Derived</tt> constructor. That is how derived objects are constructed: base 
  first. We then see a call to the <tt>Derived MethodOne</tt>. Polymorphism works! 
  Here we have a <tt>Base</tt> pointer, but because we assigned a <tt>Derived</tt> 
  object to it, when we call a virtual method, the right method is called. This 
  is followed by a call to <tt>Derived MethodTwo</tt>, and then to <tt>Base MethodThree</tt>! 
  As far as the <tt>Base</tt> pointer is concerned, <tt>Base MethodThree</tt> 
  has not been overridden, so <tt>Derived</tt> inherits the <tt>Base</tt> method. 
  Finally, the object is destroyed in the reverse order in which it was created.</p>
<p>The final set of code begins on line 46, where we create a <tt>Derived Pointer</tt> 
  and initialize it with a <tt>Derived</tt> object. This time we can't call the 
  version of <tt>MethodThree</tt> that was declared in <tt>Base</tt> because our 
  new <tt>Derived</tt> object hides it. This proves the rule: If you overload 
  a base class in the derived class, you must explicitly implement every version 
  of the method (in this case you'd have to implement the version with no parameters) 
  in the derived class, or it is hidden from your derived objects.</p>
<p>The output reflects the fact that this <tt>Derived</tt> object calls (of course) 
  only derived methods.</p>
<p>To avoid the hiding, we can move the version of the method that takes an integer 
  up into <tt>Base</tt>, or at a minimum we can implement the version with no 
  parameters in the derived class. If we choose the first option, we can use both 
  methods polymorphically. If we choose the latter, at least we can access the 
  base method using a derived object.</p>
<p>We can, actually, overcome many of these problems with a bit more magic. Let's 
  take them in turn. To solve the first problem (shown on line 34), we have only 
  to overload <tt>MethodThree</tt> in <tt>Base</tt>:</p>
<pre>
<tt>3:  class Base</tt>
<tt>4:  {</tt>
<tt>5:  public:</tt>
<tt>6:      Base() { cout &lt;&lt; "Base constructor\n"; }</tt>
<tt>7:      virtual ~Base() { cout &lt;&lt; "Base destructor\n"; }</tt>
<tt>8:      virtual void MethodOne() { cout &lt;&lt; "Base MethodOne\n"; }</tt>
<tt>9:      virtual void MethodTwo() { cout &lt;&lt; "Base MethodTwo\n"; }</tt>
<tt>10:      virtual void MethodThree() </tt>
<tt>11:          { cout &lt;&lt; "Base MethodThree\n"; }</tt>
<tt>        virtual void MethodThree(int param)</tt>
<tt>               { cout &lt;&lt; "Base MethodThree(int)\n"; }</tt>
<tt>12:  private:</tt>
<tt>13:  };</tt>
</pre>
<p>To solve the problem on lines 42 and 49, we need only invoke the base class's 
  method directly:</p>
<pre>
<tt>42:  //    pbd-&gt;Base::MethodThree(5);  </tt>
</pre>
<p>Here we use the <tt>Base</tt> class name, followed by the scoping operator 
  (<tt>::</tt>), to invoke the <tt>Base</tt> version of this method. Hey! Presto! 
  Now we've "unhidden" it, and we can call it.</p>
<h2> <a name="Heading12">Implementing Polymorphism</a></h2>
<p>All this is fine in theory, but it remains highly abstract until you see it 
  implemented in code. Let's take a look at the implementation of the newly object-oriented 
  <tt>LinkedList</tt> (see Listing 8.2).</p>
<h4> Listing 8.2 LinkedList</h4>
<pre>
<tt>0:  #ifndef LINKEDLIST_H</tt>
<tt>1:  #define LINKEDLIST_H</tt>
<tt>2:  </tt>
<tt>3:  #include "DefinedValues.h"</tt>
<tt>4:  </tt>
<tt>5:  class Node  // abstract data type</tt>
<tt>6:  {</tt>
<tt>7:  public:</tt>
<tt>8:       Node(){}</tt>
<tt>9:       virtual ~Node() {}</tt>
<tt>10:       virtual void Display() const { }</tt>
<tt>11:       virtual int HowMany(char c) const = 0;</tt>
<tt>12:       virtual Node * Insert(char theCharacter) = 0;</tt>
<tt>13:       virtual char operator[](int offset) = 0;</tt>
<tt>14:  private:</tt>
<tt>15:  };</tt>
<tt>16:  </tt>
<tt>17:  class InternalNode: public Node</tt>
<tt>18:  {</tt>
<tt>19:  public:</tt>
<tt>20:       InternalNode(char theCharacter, Node * next);</tt>
<tt>21:       virtual ~InternalNode();</tt>
<tt>22:       virtual void Display() const;</tt>
<tt>23:       virtual int HowMany(char c) const;</tt>
<tt>24:       virtual Node * Insert(char theCharacter);</tt>
<tt>25:       virtual char operator[](int offset);</tt>
<tt>26:  </tt>
<tt>27:  private:</tt>
<tt>28:       char myChar; </tt>
<tt>29:       Node * nextNode;</tt>
<tt>30:  };</tt>
<tt>31:  </tt>
<tt>32:  class TailNode : public Node</tt>
<tt>33:  {</tt>
<tt>34:  public:</tt>
<tt>35:       TailNode(){}</tt>
<tt>36:       virtual ~TailNode(){}</tt>
<tt>37:       virtual int HowMany(char c) const;</tt>
<tt>38:       virtual Node * Insert(char theCharacter);</tt>
<tt>39:       virtual char operator[](int offset);</tt>
<tt>40:  </tt>
<tt>41:  private:</tt>
<tt>42:  </tt>
<tt>43:  };</tt>
<tt>44:  </tt>
<tt>45:  class LinkedList : public Node</tt>
<tt>46:  {</tt>
<tt>47:  public:</tt>
<tt>48:       LinkedList();</tt>
<tt>49:       virtual ~LinkedList();</tt>
<tt>50:       virtual void Display() const;</tt>
<tt>51:       virtual int HowMany(char c) const;</tt>
<tt>52:       virtual char operator[](int offset);</tt>
<tt>53:  </tt>
<tt>54:       bool Add(char c);</tt>
<tt>55:       void SetDuplicates(bool dupes);</tt>
<tt>56:  </tt>
<tt>57:  private:</tt>
<tt>58:       Node * Insert(char c);</tt>
<tt>59:       bool duplicates;</tt>
<tt>60:       Node * nextNode;</tt>
<tt>61:  };</tt>
<tt>62:  </tt>
<tt>63: #endif </tt>
</pre>
<p>This analysis begins on line 5 with the declaration of the <tt>Node</tt> class. 
  Note that all the methods, with the exception of the constructor, are virtual.</p>
<p>Constructors cannot be virtual; destructors need to be virtual if any method 
  is virtual; and I've made the rest of the methods virtual because I expect that 
  they can be overridden in at least some of the derived classes.</p>
<p>Note that the first three methods--the constructor, the destructor, and <tt>Display()</tt>--all 
  have inline implementations that do nothing. <tt>HowMany()</tt> (line 11), however, 
  does not have an inline implementation. If you check Listing 8.2, which has 
  the implementation for the classes that are declared in Listing 8.1, you will 
  not find an implementation for <tt>Node::HowMany()</tt>. </p>
<p>That is because <tt>Node::HowMany()</tt> is declared to be a <i>pure</i> virtual 
  function by virtue of the designation at the end of the declaration, <tt>= 0</tt>. 
  This indicates to the compiler that this method <i>must</i> be overridden in 
  the derived class. In fact, it is the presence of one or more pure virtual functions 
  in your class declaration that creates an ADT. To recap: In C++, an abstract 
  data type is created by declaring one or more pure virtual functions in the 
  class.</p>
<blockquote>
  <hr>
  <p><strong> </strong> <b>Pure Virtual Function</b>--A member function that <i>must</i> 
    be overridden in the derived class, and which makes the class in which it 
    is declared an Abstract Data Type. You create a pure virtual function by adding 
    <tt>= 0</tt> to the function declaration.</p>
  <hr>
</blockquote>
<p>The <tt>Node</tt> class is, therefore, an ADT from which you derive the concrete 
  nodes you'll instantiate in the program. Every one of these concrete types must 
  override the <tt>HowMany()</tt> and <tt>Insert()</tt> methods, as well as the 
  offset operator. If a derived type fails to override even one of these methods, 
  it too is abstract, and no objects can be instantiated from it.</p>
<p>On line 17, you see the declaration of the <tt>InternalNode</tt> class, which 
  derives from <tt>Node</tt>. As you can see on lines 23-25, this class does override 
  the three pure virtual functions of <tt>Node</tt>; thus, this is a concrete 
  class from which you can instantiate objects.</p>