mi29.htm

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

<UL><PRE>char&amp; String::operator[](int index)
{
  // if we're sharing a value with other String objects,
  // break off a separate copy of the value for ourselves
  if (value-&gt;refCount &gt; 1) {
    --value-&gt;refCount;                    // decrement current value's
                                          // refCount, because we won't
                                          // be using that value any more
<A NAME="19235"></A>
    value =                               // make a copy of the
      new StringValue(value-&gt;data);       // value for ourselves
  }
<A NAME="16540"></A>
  // return a reference to a character inside our
  // unshared StringValue object
  return value-&gt;data[index];
}
</PRE>
</UL>

<P><A NAME="dingp43"></A><A NAME="84730"></A>
This idea &#151; that of sharing a value with other objects until we have to write on our own copy of the value &#151; has a long and distinguished history in Computer Science, especially in operating systems, where processes are routinely allowed to share pages until they want to modify data on their own copy of a page. The technique is common enough to have a name: <I>copy-on-write</I>. It's a specific example of a more general approach to efficiency, that of lazy evaluation (see <a href="./MI17_FR.HTM#41011" TARGET="_top">Item 17</A>).<SCRIPT>create_link(43);</SCRIPT>
</P>

<P><A NAME="dingp44"></A><FONT ID="mhtitle">Pointers, References, and Copy-on-Write</FONT><SCRIPT>create_link(44);</SCRIPT>
</P>

<P><A NAME="dingp45"></A><A NAME="16606"></A>
This implementation of copy-on-write allows us to preserve both efficiency and correctness &#151; almost. There is one lingering problem. Consider this <NOBR>code:<SCRIPT>create_link(45);</SCRIPT>
</NOBR></P><A NAME="16609"></A>
<UL><PRE>String s1 = "Hello";
</PRE>
</UL><A NAME="16610"></A>
<UL><PRE>char *p = &amp;s1[1];
</PRE>
</UL><P><A NAME="dingp46"></A><A NAME="16621"></A>
Our data structure at this point looks like <NOBR>this:<SCRIPT>create_link(46);</SCRIPT>
</NOBR></P>

<SPAN ID="Image7of1" STYLE="position: absolute; z-index:1; visibility: hidden"><IMG SRC="./IMAGES/GRAPHICS/DIAGRAMS/I_191A1.GIF" BORDER=0></SPAN>
<SPAN ID="Image7of2" STYLE="position: absolute; z-index:1; visibility: hidden"><IMG SRC="./IMAGES/GRAPHICS/DIAGRAMS/I_191A2.GIF" BORDER=0></SPAN>
<SPAN ID="Image7of3" STYLE="position: absolute; z-index:1; visibility: hidden"><IMG SRC="./IMAGES/GRAPHICS/DIAGRAMS/I_191A3.GIF" BORDER=0></SPAN>
<SPAN ID="Image7of4" STYLE="position: absolute; z-index:1; visibility: hidden"><IMG SRC="./IMAGES/GRAPHICS/DIAGRAMS/I_191A4.GIF" BORDER=0></SPAN>
<SPAN ID="Image7of5" STYLE="position: absolute; z-index:1; visibility: hidden"><IMG SRC="./IMAGES/GRAPHICS/DIAGRAMS/I_191A5.GIF" BORDER=0></SPAN>

<SPAN ID="Image7of6" STYLE="position: relative; z-index:1; visibility: hidden"><IMG SRC="./IMAGES/GRAPHICS/DIAGRAMS/I_191A5.GIF" BORDER=0></SPAN>

<P><A NAME="dingp47"></A><A NAME="16695"></A>
Now consider an additional <NOBR>statement:<SCRIPT>create_link(47);</SCRIPT>
</NOBR></P><A NAME="16611"></A>
<UL><PRE>String s2 = s1;
</PRE>
</UL>
<P><A NAME="dingp48"></A><A NAME="16700"></A>
<A NAME="p192"></A>The <CODE>String</CODE> copy constructor will make <CODE>s2</CODE> share <CODE>s1</CODE>'s <CODE>StringValue</CODE>, so the resulting data structure will be this <NOBR>one:<SCRIPT>create_link(48);</SCRIPT>
</NOBR></P>

<SPAN ID="Image8of1" STYLE="position: absolute; z-index:1; visibility: hidden"><IMG SRC="./IMAGES/GRAPHICS/DIAGRAMS/I_192A1.GIF" BORDER=0></SPAN>
<SPAN ID="Image8of2" STYLE="position: absolute; z-index:1; visibility: hidden"><IMG SRC="./IMAGES/GRAPHICS/DIAGRAMS/I_192A2.GIF" BORDER=0></SPAN>
<SPAN ID="Image8of3" STYLE="position: absolute; z-index:1; visibility: hidden"><IMG SRC="./IMAGES/GRAPHICS/DIAGRAMS/I_192A3.GIF" BORDER=0></SPAN>
<SPAN ID="Image8of4" STYLE="position: absolute; z-index:1; visibility: hidden"><IMG SRC="./IMAGES/GRAPHICS/DIAGRAMS/I_192A4.GIF" BORDER=0></SPAN>
<SPAN ID="Image8of5" STYLE="position: absolute; z-index:1; visibility: hidden"><IMG SRC="./IMAGES/GRAPHICS/DIAGRAMS/I_192A5.GIF" BORDER=0></SPAN>

<SPAN ID="Image8of6" STYLE="position: relative; z-index:1; visibility: hidden"><IMG SRC="./IMAGES/GRAPHICS/DIAGRAMS/I_192A5.GIF" BORDER=0></SPAN>

<P><A NAME="dingp49"></A><A NAME="16742"></A>
The implications of a statement such as the following, then, are not pleasant to <NOBR>contemplate:<SCRIPT>create_link(49);</SCRIPT>
</NOBR></P><A NAME="16612"></A>
<UL><PRE>*p = 'x';                     // modifies both s1 and s2!
</PRE>
</UL>
<P><A NAME="dingp50"></A><A NAME="16466"></A>
There is no way the <CODE>String</CODE> copy constructor can detect this problem, because it has no way to know that a pointer into <CODE>s1</CODE>'s <CODE>StringValue</CODE> object exists. And this problem isn't limited to pointers: it would exist if someone had saved a <I>reference</I> to the result of a call to <CODE>String</CODE>'s non-<CODE>const</CODE> <CODE>operator[]</CODE>.<SCRIPT>create_link(50);</SCRIPT>
</P>
<P><A NAME="dingp51"></A><A NAME="16743"></A>
There are at least three ways of dealing with this problem. The first is to ignore it, to pretend it doesn't exist. This approach turns out to be distressingly common in class libraries that implement reference-counted strings. If you have access to a reference-counted string, try the above example and see if you're distressed, too. If you're not sure if you have access to a reference-counted string, try the example anyway. Through the wonder of encapsulation, you may be using such a type without knowing <NOBR>it.<SCRIPT>create_link(51);</SCRIPT>
</NOBR></P>
<P><A NAME="dingp52"></A><A NAME="16758"></A>
Not all implementations ignore such problems. A slightly more sophisticated way of dealing with such difficulties is to define them out of existence. Implementations adopting this strategy typically put something in their documentation that says, more or less, "Don't do that. If you do, results are undefined." If you then do it anyway &#151; wittingly or no &#151; and complain about the results, they respond, "Well, we <I>told</I> you not to do that." Such implementations are often efficient, but they leave much to be desired in the usability <NOBR>department.<SCRIPT>create_link(52);</SCRIPT>
</NOBR></P>
<P><A NAME="dingp53"></A><A NAME="63841"></A>
There is a third solution, and that's to eliminate the problem. It's not difficult to implement, but it can reduce the amount of value sharing between objects. Its essence is this: add a flag to each <CODE>StringValue</CODE> object indicating whether that object is shareable. Turn the flag on initially (the object is shareable), but turn it off whenever the non-<CODE>const</CODE> <CODE>operator[]</CODE> is invoked on the value represented by that object. Once the flag is set to <CODE>false</CODE>, it stays that way forever.<a href="#11827"><sup>10</sup></A><SCRIPT>create_link(53);</SCRIPT>
</P>
<P><A NAME="dingp54"></A><A NAME="16817"></A>
<A NAME="p193"></A>Here's a modified version of <CODE>StringValue</CODE> that includes a shareability <NOBR>flag:<SCRIPT>create_link(54);</SCRIPT>
</NOBR></P><A NAME="16820"></A>
<UL><PRE>class String {
private:
  struct StringValue {
    int refCount;
    bool shareable;                // add this
    char *data;
</PRE>
</UL><A NAME="16821"></A>
<UL><PRE>    StringValue(const char *initValue);
    ~StringValue();
</PRE>
</UL><A NAME="16822"></A>
<UL><PRE>  };
</PRE>
</UL><A NAME="7588"></A>
<UL><PRE>...
</PRE>
</UL><A NAME="7589"></A>
<UL><PRE>};
</PRE>
</UL><A NAME="16825"></A>
<UL><PRE>String::StringValue::StringValue(const char *initValue)
:   refCount(1),
    shareable(true)                // add this
{
  data = new char[strlen(initValue) + 1];
  strcpy(data, initValue);
}
</PRE>
</UL><A NAME="16826"></A>
<UL><PRE>String::StringValue::~StringValue()
{
  delete [] data;
}
</PRE>
</UL>

<P><A NAME="dingp55"></A><A NAME="16818"></A>
As you can see, not much needs to change; the two lines that require modification are flagged with comments. Of course, <CODE>String</CODE>'s member functions must be updated to take the <CODE>shareable</CODE> field into account. Here's how the copy constructor would do <NOBR>that:<SCRIPT>create_link(55);</SCRIPT>
</NOBR></P><A NAME="16861"></A>
<UL><PRE>String::String(const String&amp; rhs)
{
  if (rhs.value-&gt;shareable) {
    value = rhs.value;
    ++value-&gt;refCount;
  }
</PRE>
</UL><A NAME="16864"></A>
<UL><PRE>  else {
    value = new StringValue(rhs.value-&gt;data);
  }
}
</PRE>
</UL>
<P><A NAME="dingp56"></A><A NAME="16859"></A>
All the other <CODE>String</CODE> member functions would have to check the <CODE>shareable</CODE> field in an analogous fashion. The non-<CODE>const</CODE> version of <CODE>operator[]</CODE> would be the only function to set the <CODE>shareable</CODE> flag to <CODE>false</CODE>:<SCRIPT>create_link(56);</SCRIPT>
</P><A NAME="52505"></A>
<UL><PRE><A NAME="p194"></A>char&amp; String::operator[](int index)
{
  if (value-&gt;refCount &gt; 1) {
    --value-&gt;refCount;
    value = new StringValue(value-&gt;data);
  }
</PRE>
</UL><A NAME="52518"></A>
<UL><PRE>  value-&gt;shareable = false;           // add this
</PRE>
</UL><A NAME="52507"></A>
<UL><PRE>  return value-&gt;data[index];
}
</PRE>
</UL>
<P><A NAME="dingp57"></A><A NAME="52500"></A>
If you use the proxy class technique of <a href="./MI30_FR.HTM#6074" TARGET="_top">Item 30</A> to distinguish read usage from write usage in <CODE>operator[]</CODE>, you can usually reduce the number of <CODE>StringValue</CODE> objects that must be marked <NOBR>unshareable.<SCRIPT>create_link(57);</SCRIPT>
</NOBR></P>

<P><A NAME="dingp58"></A><FONT ID="mhtitle">A Reference-Counting Base Class</FONT><SCRIPT>create_link(58);</SCRIPT>
</P>

<P><A NAME="dingp59"></A><A NAME="16087"></A>
Reference counting is useful for more than just strings. Any class in which different objects may have values in common is a legitimate candidate for reference counting. Rewriting a class to take advantage of reference counting can be a lot of work, however, and most of us already have more than enough to do. Wouldn't it be nice if we could somehow write (and test and document) the reference counting code in a context-independent manner, then just graft it onto classes when needed? Of course it would. In a curious twist of fate, there's a way to do it (or at least to do most of <NOBR>it).<SCRIPT>create_link(59);</SCRIPT>
</NOBR></P>
<P><A NAME="dingp60"></A><A NAME="16976"></A>
The first step is to create a base class, <CODE>RCObject</CODE>, for reference-counted objects. Any class wishing to take advantage of automatic reference counting must inherit from this class. <CODE>RCObject</CODE> encapsulates the reference count itself, as well as functions for incrementing and decrementing that count. It also contains the code for destroying a value when it is no longer in use, i.e., when its reference count becomes 0. Finally, it contains a field that keeps track of whether this value is shareable, and it provides functions to query this value and set it to false. There is no need for a function to set the shareability field to true, because all values are shareable by default. As noted above, once an object has been tagged unshareable, there is no way to make it shareable <NOBR>again.<SCRIPT>create_link(60);</SCRIPT>
</NOBR></P>
<P><A NAME="dingp61"></A><A NAME="17170"></A>
<CODE>RCObject</CODE>'s class definition looks like <NOBR>this:<SCRIPT>create_link(61);</SCRIPT>
</NOBR></P><A NAME="80769"></A>
<UL><PRE>class RCObject {
public:
  RCObject();
  RCObject(const RCObject&amp; rhs);
  RCObject&amp; operator=(const RCObject&amp; rhs);
  virtual ~RCObject() = 0;
</PRE>
</UL><A NAME="57762"></A>
<UL><PRE><A NAME="p195"></A>  void addReference();
  void removeReference();
</PRE>
</UL><A NAME="57763"></A>
<UL><PRE>void markUnshareable();
bool isShareable() const;
</PRE>
</UL><A NAME="57770"></A>