5resource.html

Visual C++ has been one of most effective tool for the large industrial applications. This book is t

        <font color="red">_aChild.push_back (pNode.release ());</font>
        _aIsPositive.push_back (isPositive);
    }
protected: 
    std::vector&lt;Node*&gt; _aChild;
    std::vector&lt;bool&gt;  _aIsPositive;
};</pre>
    </td></tr>
</table>
<!-- End Code -->

<p>Look what happens inside <var>AddChild</var>. We call <var>release</var> on <var>pNode</var> and then immediately call <var>push_back</var> on a vector. We know that <var>push_back</var> might re-allocate the vector's internal array. A re-allocation involves memory allocation which, as we know, might fail. You see the problem? The pointer that we have just released from <var>pNode</var> will be caught naked in the middle of an allocation failure. This pointer will never get a chance to be properly deleted. We have a memory leak!
<p>What is needed here is for the vector to be re-allocated before the pointer is released. We could force the potential reallocation by first calling 
<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>_aChild.reserve (_aChild.size () + 1);</pre>
    </td></tr>
</table>
<!-- End Code -->
But that's an awkward solution (besides, it requires a lot of vigilance on the part of the programmer). So let's rethink the problem. 

<p>The culprit here is the vector of pointers, which has no notion of ownership. Notice that the deallocation of nodes is done not in the vector's destructor but rather in the <var>MultiNode</var>'s destructor. What we need is some type of a vector that really <i>owns</i> the objects stored in it through pointers. 
<p>Could we use a vector of <var>auto_ptr</var>s? 

<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>std::vector&lt;auto_ptr&lt;Node&gt; &gt; _aChild;</pre>
    </td></tr>
</table>
<!-- End Code -->
(Notice the space left between the two greater-than signs. If you remove this space, the compiler will confuse it with the right-shift operator. It's just another quirk of C++ syntax.) When we <var>push_back</var> an <var>auto_ptr</var> on such a vector, the re-allocation will definitely happen before the "transfer" assignment. Morover, we could get rid of the explicit <var>MultiNode</var> destructor, because the vector's destructor will destroy all its <var>auto_ptr</var>s which, in turn, will destroy all the nodes. 
<p>Although in principle this is a valid solution to our problem, in practice it's hardly acceptable. The trouble is that the vector's interface is totally unsuitable for storing objects with weird copy semantics. For instance, on a const vector, the array-access operator returns an object by value. This is fine, except that returning an <var>auto_ptr</var> by value involves a resource transfer. Similarly, if you try to iterate over such a vector, you might get a resource transfer every time you dereference an iterator. Unless you are very careful, you're bound to get some nasty surprizes from a vector of <var>auto_ptr</var>s.

<p>At this point you might expect me to come up with some clever data structure from the standard library. Unfortunately, there are no ownership-aware containers in the standard library, so we'll have to build one ourselves. Fortunately--we have all the necessary tools. So let's start with the interface.

<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>template &lt;class T&gt; 
class auto_vector
{
public:
    explicit auto_vector (size_t capacity = 0);
    ~auto_vector ();
    size_t size () const;
    T const * operator [] (size_t i) const;
    T * operator [] (size_t i);
    void assign (size_t i, auto_ptr&lt;T&gt; &amp; p);
    void assign_direct (size_t i, T * p);
    void push_back (auto_ptr&lt;T&gt; &amp; p);
    auto_ptr&lt;T&gt; pop_back ();
};</pre>
    </td></tr>
</table>
<!-- End Code -->

<p>Notice a rather defensive attitude in this design. I could have provided an array-access operator that would return an lvalue but I decided against it. Instead, if you want to set a value, you have to use one of the <var>assign</var> or <var>assign_direct</var> methods. My philosophy is that resource transfer shouldn't be taken lightly and, besides, it isn't needed all that often--an <var>auto_vector</var> is usually filled using the <var>push_back</var> method.

<p>As far as implementation goes, we can simply use a dynamic array of <var>auto_ptr</var>s.
<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>template &lt;class T&gt;
class auto_vector
{
    ~auto_vector () { delete []_arr; }
private:
    void grow (size_t reqCapacity);

    auto_ptr&lt;T&gt;    *_arr;
    size_t        _capacity;
    size_t        _end;
};</pre>
    </td></tr>
</table>
<!-- End Code -->

<p>The <var>grow</var> method allocates a larger array of <var>auto_ptr&lt;T&gt;</var>, transfers all the items from the old array, swaps it in, and deletes the old array.

<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>template &lt;class T&gt;
void auto_vector&lt;T&gt;::grow (size_t reqCapacity)
{
    size_t newCapacity = 2 * _capacity;
    if (reqCapacity > newCapacity)
        newCapacity = reqCapacity;
    // allocate new array
    auto_ptr&lt;T&gt; * arrNew = new auto_ptr&lt;T&gt; [newCapacity];
    // transfer all entries
    for (size_t i = 0; i &lt; _capacity; ++i)
        arrNew [i] = _arr [i];
    _capacity = newCapacity;
    // free old memory
    delete []_arr;
    // substitute new array for old array
    _arr = arrNew;
}</pre>
    </td></tr>
</table>
<!-- End Code -->
<p>The rest of the implementation of <var>auto_vector</var> is pretty straightforward, since all the complexity of resource management is built into <var>auto_ptr</var>.  For instance, the <var>assign</var> method simply utilizes the overloaded assignment operator to both deallocate the old object and transfer the new object in one simple statement.
<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>void assign (size_t i, auto_ptr&lt;T&gt; &amp; p)
{
    assert (i &lt; _end);
    _arr [i] = p;
}</pre>
    </td></tr>
</table>
<!-- End Code -->
<p>The method <var>assign_direct</var> takes advantage of the <var>reset</var> method of <var>auto_ptr</var>:

<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>void assign_direct (size_t i, T * p)
{
    assert (i &lt; _end);
    _arr [i].reset (ptr);
}</pre>
    </td></tr>
</table>
<!-- End Code -->

<p>The <var>pop_back</var> method returns <var>auto_ptr</var> by value, because it transfers the ownership away from <var>auto_vector</var>.
<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>auto_ptr&lt;T&gt; pop_back ()
{
    assert (_end != 0);
    return _arr [--_end];
}</pre>
    </td></tr>
</table>
<!-- End Code -->

<p>Indexed access to <var>auto_vector</var> is implemented in terms of the <var>get</var> method of <var>auto_ptr</var>, which returns a "weak" pointer.
<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>T * operator [] (size_t i) 
{
    return _arr [i].get (); 
}</pre>
    </td></tr>
</table>
<!-- End Code -->

<p>With the new <var>auto_vector</var> the implementation of <var>MultiNode</var> is not only 100% resource-safe, but also simpler. One more explicit destructor bites the dust!

<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>class MultiNode: public Node
{
public:
    MultiNode (auto_ptr&lt;Node&gt; & pNode)
    {
        AddChild (pNode, true);
    }
    void AddChild (auto_ptr&lt;Node&gt; & pNode, bool isPositive)
    {
        <font color="red">_aChild.push_back (pNode);</font>
        _aIsPositive.push_back (isPositive);
    }
protected: 
    <font color="red">auto_vector&lt;Node&gt;</font>  _aChild;
    std::vector&lt;bool&gt;  _aIsPositive;
};</pre>
    </td></tr>
</table>
<!-- End Code -->

<p>How do we know when we're done? How do we know when our code is completely resource-safe? There is a simple set of tests, at least as far as memory resources are concerned, that will answer this question. We have to search our code for all occurrences of <var>new</var> and <var>release</var> and go through the following series of test:

<ul>
<li>Is this a direct transfer to an <var>auto_ptr</var>? 
<li>Or, are we inside a constructor of an object? Is the result of the call immediately stored within the object, with no exception prone code following it in the constructor?
<li>If so, is there a corresponding <var>delete</var> in the destructor of the object?
<li>Or, are we inside a method that immediately assigns the result of the call to a pointer owned by the object, making sure the previous value is deleted?
</ul>

Notice that all these tests are local. We don't have to follow all possible execution paths--just the close vicinity of the calls, except for the occasional look at some destructors. It can't get any easier than that!

<h3>Iterators</h3>

<p>Like any other standard container, our <var>auto_vector</var> needs iterators. I will not attempt to provide the full set of iterators--it's a tedious work best left to library implementors. All we'll ever need in our calculator is a forward-only constant iterator, so that's what I'll define.

<p>An iterator is an abstraction of a pointer to an element of an array. It is also usually implemented as a pointer. It can be cheaply passed around and copied. Our <var>auto_vector</var> is implemented as an array of <var>auto_ptr</var>, so it's only natural that we should implement its iterator as a pointer to <var>auto_ptr</var>. It will be cheap to create, pass around and copy. Moreover, incrementing such an iterator is as easy as incrementing a pointer. The only thing that prevents us from just <var>typedef</var>ing an <var>auto_vector</var> iterator to a pointer to <var>auto_ptr</var> is its dereferencing behavior. When you dereference a pointer to an <var>auto_ptr</var>, you get an <var>auto_ptr</var> with all its resource-transfer semantics. What we need is an iterator that produces a regular weak pointer upon dereferencing (and in the case of a constant iterator, a weak pointer to <var>const</var>). Operator overloading to the rescue!

<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>template&lt;class T&gt;
class const_auto_iterator: public
    std::iterator&lt;std::forward_iterator_tag, T const *&gt;
{
public:
    const_auto_iterator () : _pp (0) {}
    const_auto_iterator (auto_ptr&lt;T&gt; const * pp) : _pp (pp) {}
    bool operator != (const_auto_iterator&lt;T&gt; const &amp; it) const 
        { return it._pp != _pp; }
    const_auto_iterator operator++ (int) { return _pp++; }
    const_auto_iterator operator++ () { return ++_pp; }
    T const * operator * () { return _pp-&gt;get (); }
    T const * operator-&gt; () { return _pp-&gt;get (); }
private:
    auto_ptr&lt;T&gt; const * _pp;
};</pre>
    </td></tr>
</table>
<!-- End Code -->

<p>First of all, a well-bahaved iterator should inherit from the <var>std::iterator</var> template, so that it can be passed to various standard algorithms. This template is parametrized by an iterator tag (<var>forward_iterator_tag</var> in our case), which specifies the iterators's capabilities; and its value type (pointer to const <var>T</var>, in our case). (Strictly speaking, there is a third parameter, the difference type--the type that you get when you subtract one iterator from another, but this one correctly defaults to <var>ptrdiff_t</var>.)
<p>We have two constructors--one default and one taking a pointer to a const <var>auto_ptr</var>. We have a not-equal operator. We have two increment operators. One of them overloads the post-increment and the other the pre-increment operator. To distinguish between the declarations of these two, you provide a dummy <var>int</var> argument to your declaration of the post-increment operator (yet another quirk of C++ syntax).

<p>
<!-- Sidebar -->
<table width="100%" border=0 cellpaddin