cargill.htm

一个非常适合初学者入门的有关c++的文档

<EM> &nbsp; &nbsp; &lt;outputs&gt; </EM>

<A NAME="AUTO00025"></A><UL><PRE>
17736
</PRE>
</UL>

<P><A NAME="dingp10"></A>The object <CODE>x</CODE> should be made empty, since it is copied from an empty master. However, <CODE>x</CODE> is not empty according to <CODE>x.count()</CODE>; the value <CODE>17736</CODE> appears because <CODE>x.top</CODE> is not set by the copy constructor when copying an empty object. The test that suppresses the copy loop for an empty object also suppresses the setting of <CODE>top</CODE>. The value that <CODE>top</CODE> assumes is determined by the contents of its memory as left by the last <NOBR>occupant.<SCRIPT>create_link(10);</SCRIPT>
</NOBR></P>

<P><A NAME="dingp11"></A><A NAME="AUTO00010"></A>Now consider a similar situation with respect to <NOBR>assignment:<SCRIPT>create_link(11);</SCRIPT>
</NOBR></P>

<A NAME="AUTO00026"></A><UL><PRE>
  Stack&lt;int&gt; a, b;
  a.push(0);
  a = b;
  printf( "%u\n", a.count() );</PRE>
</UL>

<EM> &nbsp; &nbsp; &lt;outputs&gt; </EM>

<A NAME="AUTO00027"></A><UL><PRE>
  1
</PRE>
</UL>

<P><A NAME="dingp12"></A>Again, the object <CODE>a</CODE> should be empty. Again, it isn't. The boundary condition fault seen in the copy constructor also appears in <CODE>operator=</CODE>, so the value of <CODE>a.top</CODE> is not set to the value of <CODE>b.top</CODE>. There is a second bug in <CODE>operator=</CODE>. It does nothing to protect itself against self-assignment, that is, where the left-hand and right-hand sides of the assignment are the same object. Such an assignment would cause <CODE>operator=</CODE> to attempt to access deleted memory, with undefined <NOBR>results.<SCRIPT>create_link(12);</SCRIPT>
</NOBR></P>

<A NAME="AUTO00011"></A>
<P><A NAME="dingp13"></A><FONT ID="aititle">Exceptions Thrown by <CODE>Stack</CODE></FONT><SCRIPT>create_link(13);</SCRIPT>
</P>

<P><A NAME="dingp14"></A>There are five explicit throw sites in <CODE>Stack</CODE>: four report memory exhaustion from <CODE>operator</CODE> <CODE>new</CODE>, and one reports stack underflow on a <CODE>pop</CODE> operation. (<CODE>Stack</CODE> assumes that on memory exhaustion <CODE>operator</CODE> <CODE>new</CODE> returns a null pointer. However, some implementations of <CODE>operator</CODE> <CODE>new</CODE> throw an exception instead. I will probably address exceptions thrown by <CODE>operator</CODE> <CODE>new</CODE> in a later <NOBR>column.)<SCRIPT>create_link(14);</SCRIPT>
</NOBR></P>

<P><A NAME="dingp15"></A><A NAME="AUTO00012"></A>The <CODE>throw</CODE> expressions in the default constructor and copy constructor of <CODE>Stack</CODE> are benign, by and large. When either of these constructors throws an exception, no <CODE>Stack</CODE> object remains and there is little left to say. (The little that does remain is sufficiently subtle that I will defer it to a later column as <NOBR>well.)<SCRIPT>create_link(15);</SCRIPT>
</NOBR></P>

<P><A NAME="dingp16"></A><A NAME="AUTO00013"></A>The <CODE>throw</CODE> from <CODE>push</CODE> is more interesting. Clearly, a <CODE>Stack</CODE> object that <CODE>throws</CODE> from a <CODE>push</CODE> operation has rejected the pushed value. However, when rejecting the operation, in what state should <CODE>push</CODE> leave its object? On <CODE>push</CODE> failure, this stack class takes its object into an inconsistent state, because the increment of <CODE>top</CODE> precedes a check to see that any necessary growth can be accomplished. The <CODE>Stack</CODE> object is in an inconsistent state because the value of <CODE>top</CODE> indicates the presence of an element for which there is no corresponding entry in the allocated <NOBR>array.<SCRIPT>create_link(16);</SCRIPT>
</NOBR></P>

<P><A NAME="dingp17"></A><A NAME="AUTO00014"></A>Of course, the <CODE>Stack</CODE> class might be documented to indicate that a <CODE>throw</CODE> from its <CODE>push</CODE> leaves the object in a state in which further member functions (<CODE>count</CODE>, <CODE>push</CODE> and <CODE>pop</CODE>) can no longer be used. However, it is simpler to correct the code. The <CODE>push</CODE> member function could be modified so that if an exception is thrown, the object is left in the state that it occupied before the <CODE>push</CODE> was attempted. Exceptions do not provide a rationale for an object to enter an inconsistent state, thus requiring clients to know which member functions may be <NOBR>called.<SCRIPT>create_link(17);</SCRIPT>
</NOBR></P>

<P><A NAME="dingp18"></A><A NAME="AUTO00015"></A>A similar problem arises in <CODE>operator=</CODE>, which disposes of the original array before successfully allocating a new one. If <CODE>x</CODE> and <CODE>y</CODE> are <CODE>Stack</CODE> objects and <CODE>x=y</CODE> throws the out-of-memory exception from <CODE>x.operator=</CODE>, the state of <CODE>x</CODE> is inconsistent. The value returned by <CODE>a.count()</CODE> does not reflect the number of elements that can be popped off the stack because the array of stacked elements no longer <NOBR>exists.<SCRIPT>create_link(18);</SCRIPT>
</NOBR></P>

<A NAME="AUTO00016"></A>
<P><A NAME="dingp19"></A><FONT ID="aititle">Exceptions Thrown by <CODE>T</CODE></FONT><SCRIPT>create_link(19);</SCRIPT>
</P>

<P><A NAME="dingp20"></A>The member functions of <CODE>Stack&lt;T&gt;</CODE> create and copy arbitrary <CODE>T</CODE> objects. If <CODE>T</CODE> is a built-in type, such as <CODE>int</CODE> or <CODE>double</CODE>, then operations that copy <CODE>T</CODE> objects do not throw exceptions. However, if <CODE>T</CODE> is another class type there is no such guarantee. The default constructor, copy constructor and assignment operator of <CODE>T</CODE> may throw exceptions just as the corresponding members of <CODE>Stack</CODE> do. Even if our program contains no other classes, client code might instantiate <CODE>Stack&lt;Stack&lt;int&gt; &gt;</CODE>. We must therefore analyze the effect of an operation on a <CODE>T</CODE> object that throws an exception when called from a member function of <CODE>Stack</CODE>.<SCRIPT>create_link(20);</SCRIPT>
</P>

<P><A NAME="dingp21"></A><A NAME="AUTO00017"></A><A NAME="dingp21"></A>The behavior of <CODE>Stack</CODE> should be &quot;exception neutral&quot; with respect to <CODE>T</CODE>. The <CODE>Stack</CODE> class must let exceptions propagate correctly through its member functions without causing a failure of <CODE>Stack</CODE>. This is much easier said than <NOBR>done.<SCRIPT>create_link(21);</SCRIPT>
</NOBR></P>

<P><A NAME="dingp22"></A><A NAME="AUTO00018"></A><A NAME="dingp22"></A>Consider an exception thrown by the assignment operation in the <CODE>for</CODE> loop of the copy <NOBR>constructor:<SCRIPT>create_link(22);</SCRIPT>
</NOBR></P>

<A NAME="AUTO00019"></A>
<A NAME="AUTO00028"></A><UL><PRE>
template &lt;class T&gt;
Stack&lt;T&gt;::Stack(const Stack&lt;T&gt;& s)
{
  v = new T[nelems = s.nelems];        // leak
  if( v == 0 )
    throw &quot;out of memory&quot;;
  if( s.top &gt; -1 ){
    for(top = 0; top &lt;= s.top; top++)
      v[top] = s.v[top];               // throw
    top--;
  }
}</PRE>
</UL>

<P><A NAME="dingp23"></A>Since the copy constructor does not catch it, the exception propagates to the context in which the <CODE>Stack</CODE> object is being created. Because the exception came from a constructor, the creating context assumes that no object has been constructed. The destructor for <CODE>Stack</CODE> does not execute. Therefore, no attempt is made to delete the array of <CODE>T</CODE> objects allocated by the copy constructor. This array has leaked. The memory can never be recovered. Perhaps some programs can tolerate limited memory leaks. Many others cannot. A long-lived system, one that catches and successfully recovers from this exception, may eventually be throttled by the memory leaked in the copy <NOBR>constructor.<SCRIPT>create_link(23);</SCRIPT>
</NOBR></P>

<P><A NAME="dingp24"></A><A NAME="AUTO00020"></A>A second memory leak can be found in <CODE>push</CODE>. An exception thrown from the assignment of <CODE>T</CODE> in the <CODE>for</CODE> loop in <CODE>push</CODE> propagates out of the function, thereby leaking the newly allocated array, to which only <CODE>new_buffer</CODE> <NOBR>points:<SCRIPT>create_link(24);</SCRIPT>
</NOBR></P>

<A NAME="AUTO00029"></A><UL><PRE>
template &lt;class T&gt;
void Stack&lt;T&gt;::push(T element)
{
  top++;
  if( top == nelems-1 ){
    T* new_buffer = new T[nelems+=10]; // leak
    if( new_buffer == 0 )
      throw "out of memory";
    for(int i = 0; i &lt; top; i++)
      new_buffer[i] = v[i];            // throw
    delete [ ] v;
    v = new_buffer;
  }
  v[top] = element;
}</PRE>
</UL>

<P><A NAME="dingp25"></A>The next operation on <CODE>T</CODE> we examine is the copy construction of the <CODE>T</CODE> object returned from <CODE>pop</CODE>:<SCRIPT>create_link(25);</SCRIPT>
</P>

<A NAME="AUTO00030"></A><UL><PRE>
template &lt;class T&gt;
T Stack&lt;T&gt;::pop()
{
  if( top &lt; 0 )
    throw &quot;pop on empty stack&quot;;
  return v[top--];                     // throw
}</PRE>
</UL>

<P><A NAME="dingp26"></A>What happens if the copy construction of this object throws an exception? The <CODE>pop</CODE> operation fails because the object at the top of the stack cannot be copied (not because the stack is empty). Clearly, the caller does not receive a <CODE>T</CODE> object. But what should happen to the state of the stack object on which a <CODE>pop</CODE> operation fails in this way? A simple policy would be that if an operation on a stack throws an exception, the state of the stack is unchanged. A caller that removes the exception's cause can then repeat the <CODE>pop</CODE> operation, perhaps <NOBR>successfully.<SCRIPT>create_link(26);</SCRIPT>
</NOBR></P>

<P><A NAME="dingp27"></A><A NAME="AUTO00021"></A>However, <CODE>pop</CODE> <I>does</I> change the state of the stack when the copy construction of its result fails. The post-decrement of <CODE>top</CODE> appears in an argument expression to the copy constructor for <CODE>T</CODE>. Argument expressions are fully evaluated before their function is called. So <CODE>top</CODE> is decremented <I>before</I> the copy construction. It is therefore impossible for a caller to recover from this exception and repeat the <CODE>pop</CODE> operation to retrieve that element off the <NOBR>stack.<SCRIPT>create_link(27);</SCRIPT>
</NOBR></P>

<P><A NAME="dingp28"></A><A NAME="AUTO00022"></A>Finally, consider an exception thrown by the default constructor for <CODE>T</CODE> during the creation of the dynamic array of <CODE>T</CODE> in <CODE>operator=:</CODE><SCRIPT>create_link(28);</SCRIPT>
</P>

<A NAME="AUTO00031"></A><UL><PRE>
template &lt;class T&gt;
Stack&lt;T&gt;&
Stack&lt;T&gt;::operator=(const Stack&lt;T&gt;& s)
{
  delete [ ] v;                         // v undefined
  v = new T[nelems=s.nelems];           // throw
  if( v == 0 )
    throw "out of memory";
  if( s.top &gt; -1 ){
    for(top = 0; top &lt;= s.top; top++)
      v[top] = s.v[top];
    top--;
  }
  return *this;
}</PRE>
</UL>

<P><A NAME="dingp29"></A>The <CODE>delete</CODE> expression in <CODE>operator=</CODE> deletes the old array for the object on the left-hand side of the assignment. The <CODE>delete</CODE> operator leaves the value of <CODE>v</CODE> undefined. Most implementations leave <CODE>v</CODE> dangling unchanged, still pointing to the old array that has been returned to the heap. Suppose the exception from <CODE>T::T()</CODE> is thrown from within this <NOBR>assignment:<SCRIPT>create_link(29);</SCRIPT>
</NOBR></P>

<A NAME="AUTO00032"></A><UL><PRE>
{
  Stack&lt;Thing&gt; x, y;
  y = x;                               // throw
}                                      // double delete
  </PRE>
</UL>

<P><A NAME="dingp30"></A>As the exception propagates out of <CODE>y.operator=</CODE>, <CODE>y.v</CODE> is left pointing to the deallocated array. When the destructor for <CODE>y</CODE> executes at the end of the block, <CODE>y.v</CODE> still points to the deallocated array. The <CODE>delete</CODE> in the <CODE>Stack</CODE> destructor therefore has undefined results &#151; it is illegal to delete the array <NOBR>twice.<SCRIPT>create_link(30);</SCRIPT>
</NOBR></P>

<P><A NAME="dingp31"></A><FONT ID="aititle">An Invitation</FONT><SCRIPT>create_link(31);</SCRIPT>
</P>

<P><A NAME="dingp32"></A>Regular readers of this column might now expect to see a presentation of my version of <CODE>Stack</CODE>. In this case, I have no code to offer, at least at present. Although I can see how to correct many of the faults in Reed's <CODE>Stack</CODE>, I am not confident that I can produce a exception-correct version. Quite simply, I don't think that I understand all the exception-related interactions against which <CODE>Stack</CODE> must defend itself. Rather, I invite Reed (or anyone else) to publish an exception-correct version of <CODE>Stack</CODE>. This task involves more than just addressing the faults I have enumerated here, because I have chosen not to identify all the problems that I found in <CODE>Stack</CODE>. This omission is intended to encourage others to think exhaustively about the issues, and perhaps uncover situations that I have missed. If I did offer all of my analysis, while there is no guarantee of its completeness, it might discourage others from looking further. I don't know for sure how many bugs must be corrected in <CODE>Stack</CODE> to make it <NOBR>exception-correct.<SCRIPT>create_link(32);</SCRIPT>
</NOBR></P>
</BODY>
</HTML>