sutter.htm

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

<P><A NAME="dingp76"></A><FONT ID="aititle">An Improved <CODE>Stack</CODE></FONT><SCRIPT>create_link(76);</SCRIPT>
</P>

<P><A NAME="dingp77"></A>One way to greatly simplify an exception-safe container like <CODE>Stack</CODE> is to use better encapsulation. Specifically, we'd like to encapsulate the basic memory management work. Most of the care we  had to take while writing our original exception-safe <CODE>Stack</CODE> was needed just to get the basic memory allocation right, so let's introduce a simple helper class to put all of that work in one <NOBR>place:<SCRIPT>create_link(77);</SCRIPT>
</NOBR></P>
<A NAME="AUTO00107"></A>

<UL><PRE>template &lt;class T&gt; class StackImpl {
/*????*/:
  StackImpl(size_t size=0)
  : v_( static_cast&lt;T*&gt;               // see <SCRIPT>sendmetoo(2,77216,'M');</SCRIPT>
ONMOUSEOVER = "self.status = 'Item M2'; return true" ONMOUSEOUT = "self.status = self.defaultStatus">Item M2</A> for info on static_cast
    ( size == 0
    ? 0
    : ::operator new(sizeof(T)*size) ) ),
    vsize_(size),
    vused_(0)
  { }
  ~StackImpl() {
    destroy( v_, v_+vused_ );         // this can't throw
    ::operator delete( v_ );
  }
  void Swap(StackImpl& other) throw() {
    swap(v_, other.v_);
    swap(vsize_, other.vsize_);
    swap(vused_, other.vused_);
  }
  T*     v_;                          // ptr to a memory area big
  size_t vsize_;                      //  enough for `vsize_' T's
  size_t vused_;                      // # of T's actually in use
};</PRE>
</UL>

<P><A NAME="dingp78"></A>There's nothing magical going on here: <CODE>StackImpl</CODE> is responsible for simple raw memory management and final cleanup, so any class that uses it won't have to worry about those details. We won't spend much time analyzing why this class is fully exception-safe (works properly in the presence of exceptions) and exception- neutral (propagates all exceptions to the caller), because the reasons are pretty much the same as those we dissected in detail <NOBR>above.<SCRIPT>create_link(78);</SCRIPT>
</NOBR></P>

<P><A NAME="dingp79"></A><A NAME="AUTO00037"></A>Note that <CODE>StackImpl</CODE> has all of the original <CODE>Stack</CODE>'s data members, so that we've essentially moved the original<CODE> Stack</CODE>'s representation entirely into <CODE>StackImpl</CODE>. <CODE>StackImpl</CODE> also has a helper function named <CODE>Swap</CODE>, which exchanges the guts of our <CODE>StackImpl</CODE> object with those of another <CODE>StackImpl</CODE>.<SCRIPT>create_link(79);</SCRIPT>
</P>

<P><A NAME="dingp80"></A><A NAME="AUTO00038"></A>Before reading on, stop and think about this class and consider: What access specifier would you write in place of the comment "<CODE>/*????*/</CODE>"? And how exactly might you use a class like this to simplify <CODE>Stack</CODE>? (Hint: The name <CODE>StackImpl</CODE> itself hints at some kind of &quot;implemented-in-terms-of&quot; relationship, and there are two main ways to write that kind of relationship in C++ &#151; see Items <SCRIPT>sendmetoo(40,7424,'E');</SCRIPT> ONMOUSEOVER = "self.status = 'E40'; return true" ONMOUSEOUT = "self.status = self.defaultStatus">E40</A> and <SCRIPT>sendmetoo(42,21052,'E');</SCRIPT> ONMOUSEOVER = "self.status = 'Item E42'; return true" ONMOUSEOUT = "self.status = self.defaultStatus">Item E42</A>.)<SCRIPT>create_link(80);</SCRIPT>
</P>

<P><A NAME="dingp81"></A><FONT ID="aititle">Technique 1: Private Base Class</FONT><SCRIPT>create_link(81);</SCRIPT>
</P>

<P><A NAME="dingp82"></A>The missing <CODE>/*????*/</CODE> access specifier must be either <CODE>protected</CODE> or <CODE>public</CODE>. (If it were <CODE>private</CODE>, no one could use the class.) First, consider what happens if we make it <CODE>protected</CODE>.<SCRIPT>create_link(82);</SCRIPT>
</P>

<P><A NAME="dingp83"></A><A NAME="AUTO00039"></A>Using <CODE>protected</CODE> means that <CODE>StackImpl</CODE> is intended to be used as a private base class. So <CODE>Stack</CODE> will be &quot;implemented in terms of&quot; <CODE>StackImpl</CODE>, which is what private inheritance means (see <SCRIPT>sendmetoo(42,21052,'E');</SCRIPT> ONMOUSEOVER = "self.status = 'Item E42'; return true" ONMOUSEOUT = "self.status = self.defaultStatus">Item E42</A>), and we have a clear division of responsibilities: the <CODE>StackImpl</CODE> base class will take care of managing the memory buffer and destroying all remaining <CODE>T</CODE> objects during <CODE>Stack</CODE> destruction, while the <CODE>Stack</CODE> derived class will take care of constructing all <CODE>T</CODE> objects within the raw memory. The raw memory management takes place pretty much entirely outside <CODE>Stack</CODE> itself, because for example the initial allocation must fully succeed before any <CODE>Stack</CODE> constructor can even be called. So far, so <NOBR>good.<SCRIPT>create_link(83);</SCRIPT>
</NOBR></P>

<P><A NAME="dingp84"></A><A NAME="AUTO00040"></A>Using the private base class method, our <CODE>Stack</CODE> class will look something like this (the code is shown inlined for <NOBR>brevity):<SCRIPT>create_link(84);</SCRIPT>
</NOBR></P>
<A NAME="AUTO00108"></A>

<UL><PRE>template &lt;class T&gt;
class Stack : private StackImpl&lt;T&gt; {
public:
  Stack(size_t size=0) : StackImpl&lt;T&gt;(size) { }</PRE>
</UL>

<P><A NAME="dingp85"></A><CODE>Stack</CODE>'s default constructor simply calls the default constructor of <CODE>StackImpl</CODE>, which just sets the stack's state to empty and optionally performs an initial allocation. The only operation here which might throw is the <CODE>new</CODE> done in <CODE>StackImpl</CODE>'s constructor, and that's unimportant when considering <CODE>Stack</CODE>'s own exception safety; if it does happen, we won't enter the <CODE>Stack</CODE> constructor and there will never have been a <CODE>Stack</CODE> object at all, so any initial allocation failures in the base class don't affect <CODE>Stack</CODE>.<SCRIPT>create_link(85);</SCRIPT>
</P>

<P><A NAME="dingp86"></A><A NAME="AUTO00041"></A>Note that we slightly changed <CODE>Stack</CODE>'s original constructor interface to allow a starting 'hint' at the amount of memory to allocate. We'll make use of this in a minute when we write the <CODE>Push</CODE> <NOBR>function.<SCRIPT>create_link(86);</SCRIPT>
</NOBR></P>

<P><A NAME="dingp87"></A><A NAME="AUTO00042"></A>We don't need to provide a <CODE>Stack</CODE> destructor. The default compiler-generated <CODE>Stack</CODE> destructor is fine, because it just calls the <CODE>StackImpl</CODE> destructor to destroy any objects that were constructed and actually free the <NOBR>memory.<SCRIPT>create_link(87);</SCRIPT>
</NOBR></P>
<A NAME="AUTO00109"></A>

<UL><PRE>Stack(const Stack& other)
  : StackImpl&lt;T&gt;(other.vused_)
{
  while( vused_ &lt; other.vused_ ) {
  construct( v_+vused_,                // see <A HREF="#side1" ONMOUSEOVER = "self.status = 'Sidebar 1'; return true" ONMOUSEOUT = "self.status = self.defaultStatus">Sidebar 1</A> for
         other.v_[vused_] );           // info on construct
  ++vused_;
  }
}</PRE>
</UL>

<P><A NAME="dingp88"></A>Copy construction now becomes efficient and elegant. The worst that can happen here is that a <CODE>T</CODE> constructor could fail, in which case the <CODE>StackImpl</CODE> destructor will correctly destroy exactly as many objects as were successfully created and then deallocate the raw memory. One big benefit derived from <CODE>StackImpl</CODE> is that we could add as many more constructors as we want without putting cleanup code inside each <NOBR>one.<SCRIPT>create_link(88);</SCRIPT>
</NOBR></P>
<A NAME="AUTO00110"></A>

<UL><PRE>
Stack& operator=(const Stack& other) {
  Stack temp(other);      // does all the work
  Swap( temp );           // this can't throw &#151; see <A HREF="#side1" ONMOUSEOVER = "self.status = 'Sidebar 1'; return true" ONMOUSEOUT = "self.status = self.defaultStatus">Sidebar 1</A>
                          // for info on swap
  return *this;
}</PRE>
</UL>

<P><A NAME="dingp89"></A>Copy assignment is even more elegant, if a little subtle: we construct a temporary object from <CODE>other</CODE>, then call <CODE>Swap</CODE> to swap our own guts with temp's, and finally when temp goes out of scope and destroys itself it automatically cleans up our old guts in the process, leaving us with the new state. Also, when <CODE>operator=</CODE> is made exception-safe like this, a side effect is that it usually also automatically handles self-assignment (e.g., <CODE>Stack s; s = s;</CODE>) correctly without further work. (Because self- assignment is exceedingly rare, I omitted the traditional &quot;<CODE>if( this != &other )</CODE>&quot; test which has its own subtle problems. See <FONT COLOR="#FF0000" SIZE="-2"><B>&deg;</B></FONT><A HREF="http://www.awl.com/cseng/cgi-bin/cdquery.pl?name=guru"
    ONMOUSEOVER = "self.status = 'Guru of the Week #11'; return true" ONMOUSEOUT = "self.status = self.defaultStatus" TARGET="_top">Guru of the Week #11</A> for all the gory <NOBR>details.)<SCRIPT>create_link(89);</SCRIPT>
</NOBR></P>

<P><A NAME="dingp90"></A><A NAME="AUTO00043"></A>Note that because all the real work is done while constructing <CODE>temp</CODE>, any exceptions that might be thrown (either by memory allocation or <CODE>T</CODE> copy construction) can't affect the state of our object. Also, there won't be any memory leaks or other problems from the <CODE>temp</CODE> object because the Stack copy constructor is already fully exception-neutral. Once all the work is done, we simply swap our object's internal representation with <CODE>temp</CODE>'s, which cannot throw (because <CODE>Swap</CODE> has a <CODE>throw()</CODE> exception specification, and because it does nothing but copy built-ins), and we're <NOBR>done.<SCRIPT>create_link(90);</SCRIPT>
</NOBR></P>

<P><A NAME="dingp91"></A><A NAME="AUTO00044"></A>Note how much more elegant this is than the exception-safe copy assignment we implemented earlier! This version also requires much less care to ensure that it's been made properly <NOBR>exception-safe.<SCRIPT>create_link(91);</SCRIPT>
</NOBR></P>
<A NAME="AUTO00111"></A>

<UL><PRE>size_t Count() const {
  return vused_;
}</PRE>
</UL>

<P><A NAME="dingp92"></A>Yes, <CODE>Count</CODE> is still the easiest member function to <NOBR>write.<SCRIPT>create_link(92);</SCRIPT>
</NOBR></P>
<A NAME="AUTO00112"></A>

<UL><PRE>void Push( const T& t ) {
  if( vused_ == vsize_ ) { // grow if necessary
    Stack temp( vsize_*2+1 );
    while( temp.Count() &lt; vused_ ) {
      temp.Push( v_[temp.Count()] );
    }
    temp.Push( t );
    Swap( temp );
  } else {
    construct( v_+vused_, t );
    ++vused_;
  }
}</PRE>
</UL>

<P><A NAME="dingp93"></A>First, consider the simple <CODE>else</CODE> case: If we already have room for the new object, we attempt to construct it. If the construction succeeds, we update our <CODE>vused_</CODE> count. This is safe and <NOBR>straightforward.<SCRIPT>create_link(93);</SCRIPT>
</NOBR></P>

<P><A NAME="dingp94"></A><A NAME="AUTO00045"></A>Otherwise, like last time, if we don't have enough room for the new element we trigger a reallocation. In this case, we simply construct a temporary <CODE>Stack</CODE> object, push the <CODE>new</CODE> element onto that, and finally swap out our original guts to it to ensure they're disposed of in a tidy <NOBR>fashion.<SCRIPT>create_link(94);</SCRIPT>
</NOBR></P>

<P><A NAME="dingp95"></A><A NAME="AUTO00046"></A>But is this exception-safe? Yes. <NOBR>Consider:<SCRIPT>create_link(95);</SCRIPT>
</NOBR></P>
<OL>
<A NAME="dingp96"></A><LI> If the construction of temp fails, our state is unchanged and no resources have been leaked, so that's fine.<SCRIPT>create_link(96);</SCRIPT>

<A NAME="AUTO00047"></A>
<A NAME="dingp97"></A><LI> If any part of the loading of temp's contents (including the new object's copy construction) fails by throwing an exception, temp is properly cleaned up when its destructor is called as temp goes out of scope.<SCRIPT>create_link(97);</SCRIPT>

<A NAME="AUTO00048"></A>
<A NAME="dingp98"></A><LI> In no case do we alter our state until all the work has already been completed successfully.<SCRIPT>create_link(98);</SCRIPT>


</OL>

<P><A NAME="dingp99"></A><A NAME="AUTO00049"></A>Note that this provides the strong commit-or-rollback guarantee, because the <CODE>Swap</CODE> is performed only if the entire reallocate-and-push operation succeeds. If we were supporting iterators into this container, for instance, they would never be invalidated (by a possible internal grow operation) if the insertion is not completely <NOBR>successful.<SCRIPT>create_link(99);</SCRIPT>
</NOBR></P>
<A NAME="AUTO00113"></A>