6lib.html

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

<p>I added the <var>Upcase</var> method to demonstrate what happens when a string is modified.

<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>void StringVal::Upcase ()
{
    if (_buf)
    {
        int len = strlen (_buf);
        for (int i = 0; i &lt; len; ++i)
            _buf [i] = toupper (_buf [i]);
    }
}
</pre>
    </td></tr>
</table>
<!-- End Code -->

<p>In particular, we can create two copies of the same string and, when we <var>Upcase</var> one of them, the other should remain unchanged. 

<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>StringVal str1 ("foo");
StringVal str2 (str1); // copy
str2.Upcase ();
cout &lt;&lt; str1.c_str () &lt;&lt; endl;
cout &lt;&lt; str2.c_str () &lt;&lt; endl;</pre>
    </td></tr>
</table>
<!-- End Code -->
<p>Semantically, this is how we want our string to behave. Performance-wise, we might not be too happy with this implementation. Consider, as an exercise, how many memory allocations and string copies are made when, for instance, a <var>StringVal</var> is returned by value:
<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>StringVal ByValue ()
{
    StringVal ret ("foo");
    return ret;
}

StringVal str;
str = ByValue ();</pre>
    </td></tr>
</table>
<!-- End Code -->

<p>To save on allocating and copying, we might consider a scheme where multiple copies of the same string would internally share the same representation object--they'd have a pointer to the same buffer. But then the question of ownership arises. Who's supposed to delete the buffer? We have to somehow keep track of how many shared owners of the buffer there are at any point in time. Then, when the last owner disappears, we should delete the buffer. 

<p><img src="image63.gif" tppabs="http://www.relisoft.com/book/tech/images/image63.gif" width=187 height=137 border=0 alt="Shared Representation">
<p class=caption>Multiple object sharing the same reference-counted representation.

<p>The best way to implement it is to divide the responsibilities between two classes of objects. One class encapsulates the reference counted shared object--in our case this object will also hold the string buffer. The other class deals with the ownership issues--it increments and decrements the shared object's reference count--in our case this will be the "string" object. When it discovers that the reference count of the shared object has gone down to zero (nobody else references this object) it deletes it. 
<p>You might think of reference count as a type of resource--it is acquired by incrementing it and it must subsequently be released by decrementing it. Like any other resource, it has to be encapsulated. Our "string" object will be such an encapsulator. In fact, since reference count is a common type of resource, we will build the equivalent of a smart pointer to deal with reference counted objects. 


<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>template &lt;class T&gt;
class RefPtr
{
public:
    RefPtr (RefPtr&lt;T&gt; const &amp; p)
    {
        _p = p._p;
        _p-&gt;IncRefCount ();
    }
    ~RefPtr ()
    {
        Release ();
    }
    RefPtr const &amp; operator= (RefPtr const &amp; p)
    {
        if (this != &amp;p)
        {
            Release ();
            _p = p._p;
            _p-&gt;IncRefCount ();
        }
        return *this;
    }
protected:
    RefPtr (T * p) : _p (p) {}
    void Release ()
    {
        if (_p-&gt;DecRefCount () == 0)
            delete _p;
    }

    T * _p;
};</pre>
    </td></tr>
</table>
<!-- End Code -->

<p>Notice that the reference-counted type <var>T</var> must provide at least two methods, <var>IncRefCount</var> and <var>DecRefCount</var>. We also tacitly assume that it is created with a reference count of one, before being passed to the protected constructor of <var>RefPtr</var>.

<p>Although it's not absolutely necessary, we might want the type <var>T</var> to be a descendant of a base class that implements reference counting interface.
<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>class RefCounted
{
public:
    RefCounted () : _count (1) {}
    int GetRefCount () const { return _count; }
    void IncRefCount () <font color="red">const</font> { _count++; }
    int DecRefCount () <font color="red">const</font> { return --_count; }
private:
    <font color="red">mutable</font> int _count;
};</pre>
    </td></tr>
</table>
<!-- End Code -->

<p>Notice one interesting detail, the methods <var>IncRefCount</var> and <var>DecRefCount</var> are declared <var>const</var>, even though they modify the object's data. You can do that, without the compiler raising an eyebrow, if you declare the relevant data member <var>mutable</var>. We do want these methods to be <var>const</var> (or at least one of them, <var>IncRefCount</var>) because they are called on <var>const</var> objects in <var>RefPtr</var>. Both the copy constructor and the assignment operator take <var>const</var> references to their arguments, but they modify their reference counts. We decided not to consider the updating of the reference count a "modification" of the object. It will make even more sense when we get to the copy-on-write implementation.

<p>Just for the demonstration purposes, let's create a reference-counted string representation using our original <var>StringVal</var>. Normally, one would do it more efficiently, by combining the reference count with the string buffer.

<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>class StringRep: public RefCounted
{
public:
    StringRep (char const * cstr)
        :_string (cstr)
    {}
    char const * c_str () const { return _string.c_str (); }
    void Upcase ()
    {
        _string.Upcase ();
    }
private:
    StringVal _string;
};
</pre>
    </td></tr>
</table>
<!-- End Code -->

<p>Our actual string class is built on the base of <var>RefPtr</var> which internally represents string data with <var>StringRep</var>.

<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>class StringRef: public RefPtr&lt;StringRep&gt;
{
public:
    StringRef (char const * cstr)
        : RefPtr&lt;StringRep&gt; (new StringRep (cstr))
    {}
    StringRef (StringRef const &amp; str)
        : RefPtr&lt;StringRep&gt; (str)
    {}
    char const * c_str () const { return _p->c_str (); }
    void Upcase ()
    {
        _p->Upcase ();
    }
};
</pre>
    </td></tr>
</table>
<!-- End Code -->

<p>Other than in the special C-string-taking constructor, there is no copying of data. The copy constructor just increments the reference count of the string-representation object. So does the (inherited) assignment operator. Consequently, "copying" and passing a <var>StringRef</var> by value is relatively cheap. There is only one tiny problem with this implementation. After you call <var>Upcase</var> on one of the copies of a <var>StringRef</var>, all other copies change to upper case.

<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>StringRef strOriginal ("text");
StringRef strCopy (strOriginal);
strCopy.Upcase ();
// The original will be upper-cased!
cout &lt;&lt; "The original: " &lt;&lt; strOriginal.c_str () &lt;&lt; endl;</pre>
    </td></tr>
</table>
<!-- End Code -->

<p>There is, however, a way to have a cake and eat it, too. It's called copy-on-write, or COW for short. The idea is to share a single representation between multiple copies, as long as they don't want to make any modifications. Every modifying method would have to make sure that its modifications are not shared. It would check the reference count of its representation and, if it's greater than one, make a private copy. This way, the copying is delayed as long as possible. Passing by value is as cheap as in the case of shared representation, but modifications are no longer shared between copies.

<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>class StringCow: public RefPtr&lt;StringRep&gt;
{
public:
    StringCow (char const * cstr)
        : RefPtr&lt;StringRep&gt; (new StringRep (cstr))
    {}
    StringCow (StringCow const & str)
        : RefPtr&lt;StringRep&gt; (str)
    {}
    char const * c_str () const { return _p-&gt;c_str (); }
    void Upcase ()
    {
        Cow ();
        _p-&gt;Upcase ();      
    }
private:
    void Cow ()
    {
        if (_p-&gt;GetRefCount () &gt 1)
        {
            // clone it
            StringRep * rep = new StringRep (_p-&gt;c_str ());
            Release ();
            _p = rep;
        }
    }
};</pre>
    </td></tr>
</table>
<!-- End Code -->

<p>The beauty of this implementation is that, from the point of view of the user, <var>StringCow</var> behaves exactly like <var>StringVal</var>, down to the const-reference-taking copy constructor and assignment operator. Except that, when it comes to passing around by value, its performance is superior.
<p>There is a good chance that your standard library implements <var>string</var> using some version of copy-on-write. 

<h3>End of Restrictions</h3>

<p>Now that we are no longer scared of passing strings by value, we might try some more code improvements. For instance, we can replace this awkward piece of code:

<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>int Scanner::GetSymbolName (char * strOut, int lenBuf)
{
    assert (lenBuf &gt; maxSymLen);
    assert (_lenSymbol &lt; lenBuf);

    strncpy (strOut, &amp;_buf [_iSymbol], _lenSymbol);
    strOut [_lenSymbol] = 0;
    return _lenSymbol;
}
</pre>
    </td></tr>
</table>
<!-- End Code -->

<p>When you use strings, you don't have to worry about sending in appropriately sized buffers. You let the callee create a string of the correct size and return it by value.

<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>std::string Scanner::GetSymbolName ()
{
    return std::string (&amp;_buf [_iSymbol], _lenSymbol);
}
</pre>
    </td></tr>
</table>
<!-- End Code -->

<p>And that's what it looks like on the receiving side. 

<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>std::string strSymbol = _scanner.GetSymbolName ();
int id = _symTab.Find (strSymbol);
...
cerr &lt;&lt; "Unknown function \"";
cerr &lt;&lt; strSymbol &lt;&lt; "\"" &lt;&lt; endl;

</pre>
    </td></tr>
</table>
<!-- End Code -->
Notice that the string <var>strSymbol</var> is a local variable with limited scope. It will disappear when the flow of control leaves the scope and it will deallocate whatever resources it owns (or at least it will decrement their reference count).

<p>By the way, as you can see, a string may be sent to the standard output (or standard error) and it will be printed just like a c-string. Actually, it gets even better than that. You can read text from the standard input directly into a string. The beauty of it is that, because a string can dynamically resize itself, there is practically no restriction on the size of acceptable text. The string will accommodate as much text as the user wishes to type into it. Of course, there has to be a way terminate the string. Normally, the standard input will stop filling a string once it encounters any whitespace character. That means you may read one word at a time with simple code like this:

<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>std::string str;
std::cin &gt;&gt; str;</pre>
    </td></tr>
</table>
<!-- End Code -->

<p>In our program, we have a slightly different requirement. We want to be able to read one line at a time. The standard library has an appropriate function to do that, so let's just use it directly in <var>main</var>.

<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>cerr &lt;&lt; "&gt; ";  // prompt
std::string str;
std::<span class="red">getline</span> (cin, str);
Scanner scanner (str);
</pre>
    </td></tr>
</table>
<!-- End Code -->

<!-- Sidebar -->
<table width="100%" border=0 cellpadding=5><tr>