wwwtc6answer.htm

来自「C++builder学习资料C++builder」· HTM 代码 · 共 979 行 · 第 1/3 页

return value is not used, for *any* data type. On some platforms, 
it's even faster for integers. Unless someone overloads the 
prefix operator in a nonsensical way, it's always as fast or faster 
than postfix. 
</P> 
 
<P> 
<TABLE WIDTH="75%"> 
<TR> 
<TD VALIGN="top"> 
<IMG SRC="images/exclamation.gif" ALT="Tip" BORDER=0 HSPACE="0" ALIGN="top" width="32" height="48"> 
</TD> 
<TD valign="top"> 
<b>Tip:</b> 
<hr size = 1> 
Prefer <TT>++i</TT> over <TT>i++</TT> whenever possible. I think the name of 
the language, C++,  is partially to blame for the over use of postfix 
operator. 
<hr size = 1> 
</TD> 
</TR> 
</TABLE> 
 
<P> 
Next, since <TT>v</TT> is a const reference, it must use a <TT>const_iterator</TT> or 
it will not compile.  For read-only operations, using <TT>const_iterator</TT> is 
always the best choice.  Const is a safety measure.  Most 
professionals use safety equipment:  football players wear pads, 
doctors wear latex gloves, and (good) computer programmers use const 
whenever possible.  After all, it's crazy to enter a construction 
yard without a hard-hat. 
</P> 
<P> 
Now for the main point of this exercise. This question was designed to point 
out that the standard library supplies a great deal of functionality 
that many people do not use. Consider the <TT>count_if()</TT> algorithm to 
implement this function, since it does what the programmer wants, 
straight out of the box. 
</P> 
<P> 
<TABLE WIDTH="75%"> 
<TR> 
<TD VALIGN="top"> 
<IMG SRC="images/exclamation.gif" ALT="Tip" BORDER=0 HSPACE="0" ALIGN="top" width="32" height="48"> 
</TD> 
<TD valign="top"> 
<b>Tip:</b> 
<hr size = 1> 
Use the standard library as often as possible. If you don't know what's in the standard library, it's worth 
the time to learn.  The upfront cost of learning what is available 
is more than paid for when you can actually make use of the standard 
library.  It's tested, efficient, correct, and standardized. 
<hr size = 1> 
</TD> 
</TR> 
</TABLE> 
 
<P> 
A better way to have written this function, then would be to use the 
standard library algorithm <TT>count_if()</TT>. 
</P> 
<pre>
<font color="navy">// count all a's in the range that are &quot;special&quot;</font>
<b>extern</b> <b>bool</b> is_special_value<b>(</b>A <b>*</b><b>)</b><b>;</b>

<b>int</b> count_special_values<b>(</b><b>)</b>
<b>{</b>
  <b>return</b> std<b>:</b><b>:</b>count_if<b>(</b>v<b>.</b>begin<b>(</b><b>)</b><b>,</b> v<b>.</b>end<b>(</b><b>)</b><b>,</b> is_special_value<b>)</b><b>;</b>
<b>}</b>
</pre> 
<P> 
What are the chances of this new version being buggy?  Practically 
zero.  What are the chances of accidentally using an inefficient 
operation?  Practically zero, since you write no code.  Of course, 
the existence of <TT>count_if()</TT> almost eliminates the need for 
<TT>count_special_values()</TT> altogether. 
</P> 
 
<P> 
<TABLE WIDTH="75%"> 
<TR> 
<TD VALIGN="top"> 
<IMG SRC="images/exclamation.gif" ALT="Tip" BORDER=0 HSPACE="0" ALIGN="top" width="32" height="48"> 
</TD> 
<TD valign="top"> 
<b>Tip:</b> 
<hr size = 1> 
Avoid writing home-brew algorithms whenever possible because doing 
so will often turn out to be a waste of your time. 
<hr size = 1> 
</TD> 
</TR> 
</TABLE> 
 
 
 
<P> 
<B>Question #6:</B> 
</P> 
<pre>
<font color="navy">// erase all members of v1</font>
<b>void</b> f<b>(</b><b>)</b>
<b>{</b>
  V<b>:</b><b>:</b>iterator i<b>;</b>
  V<b>:</b><b>:</b>iterator end <b>=</b> v1<b>.</b>end<b>(</b><b>)</b><b>;</b>
  <b>for</b> <b>(</b>i<b>=</b> v1<b>.</b>begin<b>(</b><b>)</b><b>;</b> i <b>!=</b> end<b>;</b> <b>++</b>i<b>)</b>
  <b>{</b>
    v1<b>.</b>erase<b>(</b>i<b>)</b><b>;</b>
  <b>}</b>
<b>}</b>
</pre> 
<P> 
What's wrong with the assumptions in this code?  How can this be made 
more efficient? 
</P> 
<P> 
<B>Answer #6:</B> 
</P> 
<P> 
First and foremost, <TT>i</TT> is an iterator into a vector <TT>v</TT>, but after you 
erase an element the iterator becomes invalid. 
</p> 
<P> 
When a vector removes an element, it moves everything around, and the 
old iterators are pointing to the wrong things, possibly to the 
wrong memory entirely. Do not use invalid iterators, they are some 
of the toughest bugs to track down! 
</P> 
<P> 
We could replace the body of <TT>f()</TT> with this: 
</P> 
<pre>
<b>void</b> f<b>(</b><b>)</b>
<b>{</b>
  <b>int</b> size <b>=</b> v1<b>.</b>size<b>(</b><b>)</b><b>;</b>
  <b>for</b> <b>(</b><b>int</b> ii <b>=</b> <font color="blue">0</font><b>;</b> ii &lt; size<b>;</b> <b>++</b>ii<b>)</b>
  <b>{</b>
    v1<b>.</b>erase<b>(</b>v1<b>.</b>begin<b>(</b><b>)</b><b>)</b><b>;</b>
  <b>}</b>
<b>}</b>
</pre> 
<P> 
This is now correct, but is extremely slow. The vector must shift 
all elements after the removed element to fill in the "hole". 
Therefore, it must shift <TT>N</TT> elements <TT>N</TT> times, making this 
an <TT>N^2</TT> algorithm. 
</P> 
<P> 
Can we do better?  Yes. 
</P> 
<P> 
One might try a more efficient algorithm: instead of removing the head 
of the vector, remove the tail. Then nothing needs shifting because 
its only the tail that is removed, thus no holes are introduced into 
the vector. 
</p> 
<pre>
<b>void</b> f<b>(</b><b>)</b>
<b>{</b>
  <b>int</b> size <b>=</b> v1<b>.</b>size<b>(</b><b>)</b><b>;</b>
  <b>for</b> <b>(</b>size_t ii <b>=</b> <font color="blue">0</font><b>;</b> ii &lt; size<b>;</b> <b>++</b>ii<b>)</b>
  <b>{</b>
    v1<b>.</b>erase<b>(</b>v1<b>.</b>end<b>(</b><b>)</b><b>)</b><b>;</b>
  <b>}</b>
<b>}</b>
</pre> 
<P> 
Unfortunately, it is undefined to remove <TT>end()</TT> from a sequence, since 
<TT>end()</TT> is not referring to an actual element in the container.  We 
could do this instead: 
<pre>
<b>void</b> f<b>(</b><b>)</b>
<b>{</b>
  size_t size <b>=</b> v1<b>.</b>size<b>(</b><b>)</b><b>;</b>
  <b>for</b> <b>(</b>size_t ii <b>=</b> <font color="blue">0</font><b>;</b> ii &lt; size<b>;</b> <b>++</b>ii<b>)</b>
  <b>{</b>
    v1<b>.</b>erase<b>(</b><b>--</b>v1<b>.</b>end<b>(</b><b>)</b><b>)</b><b>;</b>
  <b>}</b>
<b>}</b>
</pre> 
<P> 
It may seem strange to decrement end, but for bidirectional iterator 
it's ok, since we did test that the container is not empty.  However, 
this still creates a temporary iterator and then modifies it for each 
iteration through the loop. A more efficient way would be to call 
<TT>pop_back()</TT>. 
<pre>
<b>void</b> f<b>(</b><b>)</b>
<b>{</b>
  size_t size <b>=</b> v1<b>.</b>size<b>(</b><b>)</b><b>;</b>
  <b>for</b> <b>(</b>size_t ii <b>=</b> <font color="blue">0</font><b>;</b> ii &lt; size<b>;</b> <b>++</b>ii<b>)</b>
  <b>{</b>
    v1<b>.</b>pop_back<b>(</b><b>)</b><b>;</b>
  <b>}</b>
<b>}</b>
</pre> 
<P> 
The above algorithm operates in linear time. Again I ask, is there a 
better way? Again the answer is "yes". 
</p> 
<P> 
The solution is to use the right operation. All containers have a 
<TT>clear()</TT> method that efficiently removes all elements. <TT>clear()</TT> must 
also be linear, but the constant overhead is certainly smaller than 
for the code in the above implementation of <TT>f()</TT>. 
</P> 
<P> 
In situations like this, there is absolutely zero benefit to rolling 
your own code. Let the library do the work, it knows the best way to 
operate on itself. 
</P> 
<pre>
<b>void</b> f<b>(</b><b>)</b>
<b>{</b>
  v1<b>.</b>clear<b>(</b><b>)</b><b>;</b>
<b>}</b>
</pre> 
<P> 
Now the question of the century: Why does <TT>f()</TT> exist at all, if 
clearing <TT>v1</TT> is all we want to accomplish? If there are no other 
preconditions, and no other post conditions, calling <TT>f()</TT> has a price 
of an extra function call, without ANY benefits of being an extra 
function.  It requires more documentation, more testing, and adds 
complexity.  Without other benefits, in this case, it is better to 
just call <TT>clear()</TT> directly. 
</P> 
 
<P> 
<B>Question #7:</B> 
</P> 
<pre>
<font color="navy">// remove even-valued entries from the list</font>
<b>typedef</b> std<b>:</b><b>:</b>list&lt;A<b>*</b><b>&gt;</b> List<b>;</b>

<b>void</b> f<b>(</b>List <b>&amp;</b> lst<b>)</b>
<b>{</b>
  <font color="navy">// now operate on the list</font>
  List<b>:</b><b>:</b>iterator i <b>=</b> lst<b>.</b>begin<b>(</b><b>)</b><b>;</b>
  <b>while</b> <b>(</b>i <b>!=</b> lst<b>.</b>end<b>(</b><b>)</b><b>)</b>
  <b>{</b>
   <b>if</b> <b>(</b><b>(</b><b>*</b>i<b>)</b><b>-&gt;</b>is_even<b>(</b><b>)</b><b>)</b>
   <b>{</b>
     lst<b>.</b>erase<b>(</b>i<b>)</b><b>;</b>
   <b>}</b>
   <b>++</b>i<b>;</b>
  <b>}</b>
<b>}</b>
</pre> 
<P> 
What common mistake is the programmer making? 
</P> 
<P> 
<B>Answer #7:</B> 
</P> 
<P> 
Again we have iterator invalidation.  After <TT>i</TT> is erased from the list, 
it becomes invalid.  But later, that invalid iterator is incremented, 
resulting in undefined behavior. 
</P> 
<P> 
But this item highlights a special case: that the <TT>std::list</TT> collection 
guarantees that insertions and removals of elements only affect the 
specific element being removed or added, and do NOT affect other 
elements, nor do they invalidate iterators referring to other elements. 
</P> 
<P> 
With that in mind, we can rewrite the above loop to be correct. 
</P> 
<pre>
<font color="navy">//</font>
<font color="navy">//  Correct implementation</font>
<font color="navy">//</font>
<b>void</b> f<b>(</b>List <b>&amp;</b> lst<b>)</b>
<b>{</b>
  <font color="navy">// now operate on the list</font>
  List<b>:</b><b>:</b>iterator i <b>=</b> lst<b>.</b>begin<b>(</b><b>)</b><b>;</b>
  <b>while</b> <b>(</b>i <b>!=</b> lst<b>.</b>end<b>(</b><b>)</b><b>)</b>
  <b>{</b>
   <b>if</b> <b>(</b><b>(</b><b>*</b>i<b>)</b><b>-&gt;</b>is_even<b>(</b><b>)</b><b>)</b>
   <b>{</b>
     lst<b>.</b>erase<b>(</b>i<b>++</b><b>)</b><b>;</b>
   <b>}</b>
   <b>else</b>
   <b>{</b>
     <b>++</b>i<b>;</b>
   <b>}</b>
  <b>}</b>
<b>}</b>
</pre> 
<P> 
The "trick" (if you consider it one) is to postfix-increment the 
iterator in the call to <TT>erase()</TT>, or prefix increment it otherwise. 
Why does this work?  Remember how postfix increment works:  It 
creates a temporary copy of the iterator, increments the real 
iterator, and returns the temporary.  Since it is done in that exact 
order, the temporary is a valid iterator when we increment.  The 
real iterator is safely advanced to the next node, and then the 
temporary is returned to the <TT>erase()</TT> function, which then removes 
that element that our iterator USED to point to.  Since lists only 
invalidate iterators that point to the element when it's deleted, 
the real iterator is already on the next node before the old element 
<TT>i</TT> referred to is removed. 
</P> 
<P> 
Also, you will notice that in the correct implementation above, the 
increment of <TT>i</TT> is moved into an <TT>else</TT> block.  This way, if <TT>*i</TT> is 
even, we don't increment twice. 
</P> 
<pre>
<font color="navy">//</font>
<font color="navy">// incorrect implementation</font>
<font color="navy">//</font>
<b>void</b> f<b>(</b>List <b>&amp;</b> lst<b>)</b>
<b>{</b>
  <font color="navy">// now operate on the list</font>
  List<b>:</b><b>:</b>iterator i <b>=</b> lst<b>.</b>begin<b>(</b><b>)</b><b>;</b>
  <b>while</b> <b>(</b>i <b>!=</b> lst<b>.</b>end<b>(</b><b>)</b><b>)</b>
  <b>{</b>
   <b>if</b> <b>(</b><b>(</b><b>*</b>i<b>)</b><b>-&gt;</b>is_even<b>(</b><b>)</b><b>)</b>
   <b>{</b>
     lst<b>.</b>erase<b>(</b>i<b>++</b><b>)</b><b>;</b>
   <b>}</b>
   <b>++</b>i<b>;</b>  <font color="navy">// PROBLEM: i may be twice incremented</font>
  <b>}</b>
<b>}</b>
</pre>