ch06.htm

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

  Set a break point on that line and run to the break point. Stepping in takes 
  you to the constructor of the <tt>Node</tt> object:</p>
<pre>
<tt> Node::Node(char c):</tt>
<tt>myChar,nextNode(0)</tt>
<tt>{</tt>
<tt>}</tt>
</pre>
<p>This does nothing but initialize the member variables. We now have a node whose 
  <tt>myChar</tt> character variable contains <tt>'a'</tt> and whose <tt>nextNode</tt> 
  pointer is <tt>NULL</tt>.</p>
<p>Returning to <tt>main()</tt>, we step into the call to </p>
<pre>
<tt>     head.Insert('b');</tt>
</pre>
<p>Step into this code from Listing 6.2, which is once again reproduced for your 
  convenience:</p>
<pre>
<tt>36:  void Node::Insert(char theChar)</tt>
<tt>37:  {</tt>
<tt>38:      if ( ! nextNode )</tt>
<tt>39:          nextNode = new Node(theChar);</tt>
<tt>40:      else</tt>
<tt>41:          nextNode-&gt;Insert(theChar);</tt>
<tt>42:  }</tt>
</pre>
<p>On line 38 we test to see whether <tt>nextNode</tt> is <tt>NULL</tt>. In this 
  case it is, so we must create a new node. The last time we created a node, we 
  simply declared it and passed in the value to store (<tt>'a'</tt>). This time 
  we do something different, calling the <tt>new</tt> operator. Why?</p>
<p>Until now, all the objects you've created were created on the stack. The stack, 
  you'll remember, is where all local variables are stored, along with the parameters 
  to function calls. To understand why creating your new node object on the stack 
  won't work, we need to talk a bit more about what the stack is and how it works. 
  <a name="_Toc445687420"></a></p>
<h2> <a name="Heading8">Excursion: Understanding the Stack</a></h2>
<p>The stack is a special area of memory that is allocated for your program to 
  hold the data required by each of the functions in your program. It is called 
  a stack because it is a <i>last-in, first-out</i> (LIFO) queue, much like a 
  stack of dishes at a cafeteria (see Figure 6.6).</p>
<p><b>Figure 6.6 </b><i>A LIFO stack.</i></p>
<p>LIFO means that whatever is added to the stack last will be the first thing 
  that is taken off. Other queues are more like a line at a theater, which is 
  called <i>first in, first out </i>(<i>FIFO</i>): The first one on line is the 
  first one off.</p>
<blockquote>
  <hr>
  <p><strong> </strong> <b>LIFO</b>--Last in, first out, like plates on a stack</p>
  <p> <b>FIFO</b>--First in, first out, like people on line to buy tickets at 
    a theater</p>
  <p> Interestingly, most airplanes board and unboard coach like a FIFO stack. 
    The people at the rear of the plane are the first to board and the last to 
    get off. Of course, first class is a FIFO structure--first class passengers 
    are the first ones in and the first ones out.</p>
  <hr>
</blockquote>
<p>When data is pushed onto the stack, the stack grows; as data is popped off 
  the stack, the stack shrinks. It isn't possible to pop a dish off the stack 
  without first popping off all the dishes placed on after that dish, and it isn't 
  possible to pop data off a stack without first popping all the data added above 
  your data.</p>
<p>A stack of dishes is a fine analogy as far as it goes, but it is fundamentally 
  wrong. A more accurate mental picture is of a series of cubbyholes, aligned 
  top to bottom. The top of the stack is whatever cubby the stack pointer happens 
  to be pointing to. The <i>stack pointer</i> is just a pointer whose job is to 
  keep track of the top of the stack.</p>
<blockquote>
  <hr>
  <p><b>stack</b> <b>pointer</b>--A pointer that keeps track of the top of the 
    stack</p>
  <hr>
</blockquote>
<p>Each of the cubbies has a sequential address, and one of those addresses is 
  kept in the stack pointer register. Everything below that magic address, known 
  as the top of the stack, is considered to be on the stack. Everything above 
  the top of the stack is considered to be off the stack, and therefore invalid. 
  Figure 6.7 illustrates this idea.</p>
<p><b>Figure 6.7 </b><i>The instruction pointer.</i></p>
<p>When data is put on the stack, it is placed into a cubby above the stack pointer, 
  and then the stack pointer is moved up to indicate that the new data is now 
  on the stack.</p>
<p>When data is popped off the stack, all that really happens is that the address 
  of the stack pointer is changed because it moves down the stack. Figure 6.8 
  makes this rule clear.</p>
<p><b>Figure 6.8 </b><tt><b><a name="_Toc445687421"></a> </b></tt><i>Moving the 
  stack pointer.</i></p>
<h2> <a name="Heading9">The Stack and Functions</a></h2>
<p>Here's what happens when a program that is running on a PC under DOS branches 
  to a function:</p>
<p>
<dl> 
  <dt>
  <dd> 
    <p><b>1.</b> The address in the instruction pointer is incremented to the 
      next instruction past the function call. That address is then placed on 
      the stack, and it will be the return address when the function returns.</p>
  <dt>
  <dd> 
    <p><b>2.</b> Room is made on the stack for the return type you've declared. 
      On a system with two-byte integers, if the return type is declared to be 
      <tt>int</tt>, another two bytes are added to the stack, but no value is 
      placed in these bytes.</p>
  <dt>
  <dd> 
    <p><b>3.</b> The address of the called function, which is kept in a special 
      area of memory that is set aside for that purpose, is loaded into the instruction 
      pointer, so the next instruction executed will be in the called function.</p>
  <dt>
  <dd> 
    <p><b>4. </b>The current top of the stack is noted and is held in a special 
      pointer called the <i>stack frame</i>. Everything that is added to the stack 
      from now until the function returns is considered local to the function.</p>
  <dt>
  <dd> 
    <p><b>5.</b> All the arguments to the function are placed on the stack.</p>
  <dt>
  <dd> 
    <p><b>6.</b> The instruction that is now in the instruction pointer executes, 
      thus executing the first instruction in the function.</p>
  <dt>
  <dd> 
    <p><b>7.</b> Local variables are pushed onto the stack as they are defined.</p>
  <dt>
  <dd> 
    <p><b>8.</b> When the function is ready to return, the return value is placed 
      in the area of the stack that is reserved at step 2.</p>
  <dt>
  <dd> 
    <p><b>9.</b> The stack is then popped all the way up to the stack frame pointer, 
      which effectively throws away all the local variables and the arguments 
      to the function.</p>
  <dt>
  <dd> 
    <p><b>10.</b> The return value is popped off the stack and assigned as the 
      value of the function call itself.</p>
  <dt>
  <dd> 
    <p><b>11. </b>The address that is stashed away in step 1 is retrieved and 
      put into the instruction pointer.</p>
  <dt>
  <dd> 
    <p><b>12. </b>The program resumes immediately after the function call, with 
      the value of the function retrieved. 
  </dl>
<p></p>
<p>Some of the details of this process change from compiler to compiler, or between 
  computers, but the essential ideas are consistent across environments. In general, 
  when you call a function, the return address and parameters are put on the stack. 
  During the life of the function, local variables are added to the stack. When 
  the function returns, these are all removed by popping the stack.</p>
<p>For our purposes, the most important thing to note about this process is that 
  when a function returns, all the local variables are popped off the stack and 
  destroyed.</p>
<p>As was described previously, if we create the new node in <tt>InsertNode</tt> 
  on the stack, when the function returns, that node is destroyed. Let's try it. 
  We'll just change <tt>Insert</tt> to create a local node, and we'll stash away 
  the address of that local <tt>Node</tt> in <tt>nextNode</tt>. Listing 6.6 illustrates 
  the change.</p>
<blockquote>
  <hr>
  <p><strong>WARNING: </strong> These changes compile and link, but will crash 
    when you run the program.</p>
  <hr>
</blockquote>
<h4> Listing 6.6 Local Nodes</h4>
<pre>
<tt>0:  void Node::Insert(char theChar)</tt>
<tt>1:  {</tt>
<tt>2:      if ( ! nextNode )</tt>
<tt>3:      {</tt>
<tt>4:          Node localNode(theChar);</tt>
<tt>5:          nextNode = &amp;localNode;</tt>
<tt>6:      }</tt>
<tt>7:      else</tt>
<tt>8:          nextNode-&gt;Insert(theChar);</tt>
<tt>9:</tt>
</pre>
<p>When I run this program, it quickly crashes. Here's what happens: When we create 
  the head <tt>Node</tt>, its <tt>nextNode</tt> pointer is null. When we call 
  <tt>Insert()</tt> on the head node, the <tt>if</tt> statement returns <tt>true</tt>, 
  and we enter the body of the <tt>if</tt> statement on line 4. We create a <tt>localNode</tt> 
  object and assign its address to <tt>nextNode</tt>. We then return from <tt>Insert</tt>. 
  At that moment, the stack unwinds, and the local node we created is destroyed. 
</p>
<p>Now, all that happens when that local node is destroyed is that its destructor 
  runs and the memory is marked as reusable. Sometime later, we might assign that 
  memory to a different object. Still later, we might use the <tt>nextNode</tt> 
  pointer and <i>bang!</i> the program crashes. <a name="_Toc445687423"></a></p>
<h2> <a name="Heading10">Using new</a></h2>
<p>This is a classic example of when you need to create an object on the heap. 
  Objects that are created on the heap are <i>not</i> destroyed when the function 
  returns. They live on until you delete them explicitly, which is just what we 
  need.</p>
<p>Unlike objects on the stack, objects on the heap are unnamed. You create an 
  object on the heap using the <tt>new</tt> operator, and what you get back from 
  <tt>new</tt> is an address, which you must assign to a pointer so that you can 
  manipulate (and later delete) that object.</p>
<p>Let's look again at <tt>Insert()</tt> from Listing 6.2:</p>
<pre>
<tt>36:  void Node::Insert(char theChar)</tt>
<tt>37:  {</tt>
<tt>38:      if ( ! nextNode )</tt>
<tt>39:          nextNode = new Node(theChar);</tt>
<tt>40:      else</tt>
<tt>41:          nextNode-&gt;Insert(theChar);</tt>
<tt>42:  }</tt>
</pre>
<p>The logic of this code is that we test to see whether the <tt>nextNode</tt> 
  pointer is pointing to an object on line 38; if it is not, we create a new object 
  on the heap and assign its address to <tt>nextNode</tt>.</p>
<p>When we create the new object, we call <tt>new</tt>, followed by the type of 
  the object we are creating (<tt>Node</tt>) and any parameters we need to send 
  to the constructor (in this case, <tt>theChar</tt>).</p>
<p>If this object does point to another node, we invoke <tt>Insert</tt> on that 
  object, passing along the character we're trying to solve. Eventually we reach 
  the end of the list--a node that does not point to any other node--and we can 
  create a new node and tag it to the end of the list. <a name="_Toc445687424"></a></p>
<h3> <a name="Heading11">new and delete</a></h3>
<p>Many details are involved in using <tt>new</tt> effectively, which we'll discuss 
  as we come to them. There is one, however, that I want to discuss immediately. 
  When you create an object on the heap using <tt>new</tt>, you own that object, 
  and you must clean it up when you are done with it. If you create an object 
  on the heap and then lose the pointer, that object continues to use up memory 
  until your program ends, but you can't access that memory.</p>
<p>When you have an object that you can't access anymore but that continues to 
  consume memory, we say it has <i>leaked out</i> of the program. Memory leaks 
  are of significant concern to C++ programmers. You solve memory leaks by the 
  judicious application of <tt>delete()</tt>. We see this in the destructor in 
  Listing 6.2, copied here:</p>
<pre>
<tt>10:  Node::~Node()</tt>
<tt>11:  {</tt>
<tt>12:      if ( nextNode )</tt>
<tt>13:          delete nextNode;</tt>
<tt>14:  }</tt>
</pre>
<p>When we are ready to destroy the linked list, we call <tt>delete</tt> on the 
  head node (implicitly by returning from the function in which the head node 
  was created on the stack, or explicitly if the head node was created on the 
  heap). The destructor examines its own <tt>nextNode</tt>, and if the <tt>nextNode</tt> 
  pointer is not null, the destructor deletes the node to which it points. This 
  mechanism knocks down all the dominoes, each object deleting the next object 
  as part of its own sequence of destruction.</p>
<p>Let's modify <tt>main()</tt> to create the head node on the heap, and we'll 
  delete it explicitly when we're done with the list. To make all this clear, 
  we'll add printouts to the constructors and destructors to see our progress. 
  Listing 6.7 is the entire program, which we'll walk through in some detail.</p>
<h4> Listing 6.7a Node.h</h4>
<pre>
<tt>1:    class Node</tt>
<tt>2:    {</tt>
<tt>3:    public:</tt>
<tt>4:        Node(char c);</tt>
<tt>5:        ~Node();</tt>
<tt>6:    </tt>
<tt>7:        void    Display        ()            const;</tt>
<tt>8:        int        HowMany        (char c)    const;</tt>
<tt>9:        void    Insert        (char c);</tt>
<tt>10:    </tt>
<tt>11:    private:</tt>
<tt>12:        char    myChar;</tt>
<tt>13:        Node *    nextNode;</tt>
<tt>14:    };</tt>
</pre>
<h4> Listing 6.7b[em]Node.cpp</h4>
<pre>
<tt>15:    #include &lt;iostream.h&gt;</tt>