4limit.html

C ++ in action

        return _aStatus.InRange (id)) &&
               _aStatus [id] != stNotInit;
    }
    double Value (int id) const
    {
        assert (id >= 0);
        assert (IsInit (id));
        return _aCell [id];
    }
    void SetValue (int id, double val)
    {
        assert (id >= 0);
        if (_aCell.InRange (id))
        {
            _aCell [id] = val;
            _aStatus [id] = stInit;
        }
        else
        {
            AddValue (id, val);
        }
    }

    void AddValue (int id, double val)
    {
        assert (id >= 0);
        _aCell.Add (id, val);
        _aStatus.Add (id, stInit);
    }
private:
    DynArray<double>           _aCell;
    DynArray<unsigned char>    _aStatus;
};</pre>
    </td></tr>
</table>
<!-- End Code -->

<P>In the preamble to the constructor of <var>Store</var> we construct the dynamic arrays. The memory cells are initialized to zero and the statuses to <var>stNotInit</var>. 
<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>Store::Store (SymbolTable &amp; symTab)
    : _aCell (0.0), _aStatus (stNotInit)
{
    // add predefined constants
    // Note: if more needed, do a more general job
    cerr &lt;&lt; "e = " &lt;&lt; exp (1) &lt;&lt; endl;
    int id = symTab.ForceAdd ("e");
    AddValue (id, exp (1));
    cerr &lt;&lt; "pi = " &lt;&lt; 2 * acos (0.0) &lt;&lt; endl;
    id = symTab.ForceAdd ("pi");
    AddValue (id, 2 * acos (0.0));
}</pre>
    </td></tr>
</table>
<!-- End Code -->

<P>Finally, our getting rid of built in limitations is reflected in some nice simplifications in <var>main</var>. We no longer need to pass size arguments to the constructors.
<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>int main ()
{
    ...
    SymbolTable symTab;
    Function::Table funTab (symTab);
    Store store (symTab);
    ...
}
</pre>
    </td></tr>
</table>
<!-- End Code -->

<h3>Standard Vector</h3>

</td></tr>
<tr>
<td class=margin valign=top>
<a href="source/calc4.zip">
<img src="../images/brace.gif" width=16 height=16 border=1 alt="Download!"><br>source</a>
</td>
<td>
<p>Now that you know how a dynamic array works, it's time to introduce the most useful member of the Standard Library, the <var>vector</var>. The <var>vector</var> is all that you might expect from a dynamic array and more. Without further ado, let's quickly substitute all the occurrences of <var>DynArray</var> with <var>std::vector</var> (yes, it's a member of the <var>std</var> namespace), making sure we include the appropriate header:
<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>#include &lt;vector&gt;</pre>
    </td></tr>
</table>
<!-- End Code -->

<p>Let's start with <var>MultiNode</var> and its two dynamic arrays.

<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>std::vector&lt;Node*&gt; _aChild;
std::vector&lt;bool&gt;  _aIsPositive;
</pre>
    </td></tr>
</table>
<!-- End Code -->
<p>Before our code can compile, we have to make a few adjustments. For instance, <var>std::vector</var> doesn't have the <var>Add</var> method. We can, however, append new elements by calling <var>push_back</var>, which has the side effect of growing the array if necessary. (Notice, by the way, the particular naming convention of the stadard library. All names are lower case with underscores for word separators. You'll have no problems distinguishing them from our own names.)

<p>Another thing, there seems to be no simple way of providing the default values for the elements of a vector. Fortunately, the standard library uses default constructors to fill empty spaces in vectors and other containers. It so happens that C++ provides default constructors for all built-in types. For instance, the default value for an <var>int</var> or a pointer is zero, for a <var>bool</var>, <var>false</var>, etc. Try it!
<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>int i = int ();
bool b = bool ();
typedef void * voidptr;
void * p = voidptr ();
cout &lt;&lt; "int " &lt;&lt; i &lt;&lt; ", bool " &lt;&lt; b ", pointer " &lt;&lt; p &lt;&lt; endl;
</pre>
    </td></tr>
</table>
<!-- End Code -->
<p>It turns out that the introduction of std::vector further simplified our implementation of class <var>MultiNode</var>:

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

<p>I have eliminated the member variable <var>_iCur</var> as it's no longer needed. We can quickly find out how many children there are by calling the vector's <var>size ()</var> method. However, if all we need is to iterate over the elements of a vector (like we do in the destructor of <var>MultiNode</var>) there is a better, more "standard," way: We can use an iterator.

<p>If you think of a vector as an array, an iterator is like a pointer. Remember when I told you that it's better to use an index rather than a pointer to access elements of an array? With vectors it's sort of the opposite, at least as far as iteration goes.

<p>You can get an iterator pointing to the beginning of a vector by calling te vector's <var>begin ()</var> method. Similarly, you can get the iterator pointing <i>one beyond the last element</i> of a vector by calling its <var>end ()</var> method. You can move the iterator to point to the next slot of the vector by applying the increment, ++, operator. You can test whether two iterators are equal (point to the same slot in the vector) using the (un-) equality operators. Finally, you can get the value of an element of the vector by dereferencing the iterator using the star (asterisk) operator.
<p>This is what the new destructor of MultiNode looks like:

<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>MultiNode::~MultiNode ()
{
    typedef std::vector&lt;Node *&gt::iterator NodeIter;
    for (NodeIter it = _aChild.begin (); it != _aChild.end (); ++it)
        delete *it;
}
</pre>
    </td></tr>
</table>
<!-- End Code -->

<p>The type "<var>iterator</var>" is internal to the template class <var>vector</var>. That makes for a very unwieldy type name, <var>std::vector&lt;Node *&gt::iterator</var>. It is customary to declare local typedefs for such complex type names.

<p>In case you're wondering, <var>vector::iterator</var> is in all likelihood implemented as a pointer in most versions of the Standard Library. And if, for some reason or another, it's not, you can still do with it virtually anything you can do with a pointer. What's even more important is that you get from it the same kind of performance as from a pointer. You can pass it around just like a poiner. You can return it from a function like a pointer. In fact, performance-wise, there is no difference between the code above and the following:

<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>
Node * aChild [size];
typedef Node ** NodeIter;
for (NodeIter it = aChild; it != aChild + size; ++it)
    delete *it;</pre>
    </td></tr>
</table>
<!-- End Code -->

<p>I want to stress this point, because some programmers might hesitate to use some of the features of the Standard Library for fear of performance degradation. No need to worry--the creators of the Standard Library made it their highest priority not to jeopardize the performance. That's why, for instance, they selected the pointer-like approach to iteration, rather than the, somehow safer, sequencer approach. Pointer-like iteration requires two separate pieces of data--the current position and the end position. A sequencer has access to both. With a sequencer, there is no danger that you might, by mistake, compare the current position in one vector against the end position that belongs to some other vector. In fact, if you are worried about this kind of errors, you might create a sequencer class out of two iterators.

<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>class NodeSeq
{
public:
    NodeSeq (std::vector&lt;Node *&gt; & vec)
        : _cur (vec.begin ()), _end (vec.end ())
    {}
    bool AtEnd () const { return _cur == _end; }
    void Advance () { ++_cur; }
    Node * Get () { return *_cur; }
private:
    std::vector&lt;Node *&gt;::iterator _cur;
    std::vector&lt;Node *&gt;::iterator _end;
};
</pre>
    </td></tr>
</table>
<!-- End Code -->

<p>The only drawback of the sequencer approach is that it's slightly more expensive to pass a sequencer by value than it is to pass an iterator--as you can see a sequencer is usually twice as large than the corresponding iterator. And, as you'll see later, iterators are passed around a lot, once you start using standard algorithms.

<p>Next on our list of dynamic array substitutions is the symbol table with its <var>_aOffStr</var> array. We'll have to re-code the <var>ForceAdd</var> method; incidentally getting rid of the <var>_curId</var> member.
<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>int SymbolTable::ForceAdd (char const * str)
{
    int offset = _bufStr.AddString (str);
    int id = _aOffStr.size ();
    _aOffStr.push_back (offset);
    _htab.Add (str, id);
    return id;
}
</pre>
    </td></tr>
</table>
<!-- End Code -->
<p>As you might remember, we use the current position in the array of offsets as our string id. Again, the <var>size ()</var> method of the vector helps us locate the current end of the vector.
<p>By the way, did you notice that the compiler didn't complain about our initializing the vector in the constructor of <var>SymbolTable</var>? Unlike <var>DynArray</var>, <var>std::vector</var> doesn't take a default element value. However, it has a one-argument constructor that accepts the initial size for the vector.

<p>Finally, let's get rid of the two <var>DynArray</var>s in <var>Store</var>. Here the situation is a bit more tricky. One of the arrays stores enumerated values, for which the compiler doesn't know the default. Instead of coming up with a clever trick, why don't we simply replace this array with a vector of <var>bool</var>. All we ever ask this array is whether a given element has been initialized or not. That's a yes/no question. So here are the new data members of <var>Store</var>:

<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>std::vector&lt;double&gt;  _aCell;
std::vector&lt;bool&gt;    _aIsInit;
</pre>
    </td></tr>
</table>
<!-- End Code -->

<p>Next, we have to substitute all calls to <var>DynArray::InRange</var> with a test against <var>vector::size ()</var>. For instance,

<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>bool IsInit (int id) const
{
    assert (id &gt;= 0);
    return id &lt; _aIsInit.size () &amp;&amp; _aIsInit [id];
}</pre>
    </td></tr>
</table>
<!-- End Code -->
<p>The <var>AddValue</var> method has to be able to insert an item beyond the current end of the vector. The way to do it is to first resize them. The <var>resize</var> method increases the size of the vector and fills the new slots with default values.


<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>void AddValue (int id, double val)
{
    assert (id >= 0);
    _aCell.resize (id + 1);
    _aIsInit.resize (id + 1);
    _aCell [id] = val;
    _aIsInit [id] = true;
}
</pre>
    </td></tr>
</table>
<!-- End Code -->

<p class=summary>To summarize: There is no reason for any program to have unreasonable limitations due to the use of fixed-size arrays. Standard Library vector should be used whenever a resizable array is needed.

    </td>
    </tr>
</table>
<!---- End Main Table --->
</body>
</html>