mi35.htm

Effective & MoreEfective C++ 英文版

  return begin;
}
</PRE>
</UL><A NAME="10045"></A>

<P><A NAME="dingp32"></A>
This function looks for <CODE>value</CODE> in the range between <CODE>begin</CODE> and <CODE>end</CODE> (excluding <CODE>end &#151; end </CODE>points to one beyond the end of the array) and returns a pointer to the first occurrence of <CODE>value</CODE> in the array; if none is found, it returns <CODE>end</CODE>.<SCRIPT>create_link(32);</SCRIPT>
</P><A NAME="86224"></A>
<P><A NAME="dingp33"></A>
Returning <CODE>end</CODE> seems like a funny way to signal a fruitless search. Wouldn't 0 (the null pointer) be better? Certainly null seems more natural, but that doesn't make it "better." The <CODE>find</CODE> function must return some distinctive pointer value to indicate the search failed, and for this purpose, the <CODE>end</CODE> pointer is as good as the null pointer. In addition, as we'll soon see, the <CODE>end</CODE> pointer generalizes to other types of containers better than the null <NOBR>pointer.<SCRIPT>create_link(33);</SCRIPT>
</NOBR></P><A NAME="47983"></A>
<P><A NAME="dingp34"></A>
Frankly, this is probably not the way you'd write the <CODE>find</CODE> function, but it's not unreasonable, and it generalizes astonishingly well. If you followed this simple example, you have mastered most of the ideas on which the STL is <NOBR>founded.<SCRIPT>create_link(34);</SCRIPT>
</NOBR></P><A NAME="47987"></A>
<P><A NAME="dingp35"></A>
You could use the <CODE>find</CODE> function like <NOBR>this:<SCRIPT>create_link(35);</SCRIPT>
</NOBR></P>

<A NAME="47988"></A>
<UL><PRE>int values[50];
<A NAME="76772"></A>
...
<A NAME="76773"></A>
int *firstFive = find(values,        // search the range
                      values+50,     // values[0] - values[49]
                      5);            // for the value 5
<A NAME="47993"></A>
if (firstFive != values+50) {        // did the search succeed?
<A NAME="47997"></A>
  ...                                // yes
<A NAME="48000"></A>
}
else {
  ...                                // no, the search failed
}
</PRE>
</UL><A NAME="47992"></A>

<P><A NAME="dingp36"></A>
You can also use <CODE>find</CODE> to search subranges of the <NOBR>array:<SCRIPT>create_link(36);</SCRIPT>
</NOBR></P>

<A NAME="48005"></A><UL><PRE><A NAME="p282"></A>
int *firstFive = find(values,        // search the range
                      values+10,     // values[0] - values[9]
                      5);            // for the value 5
<A NAME="48020"></A>
int age = 36;
<A NAME="76770"></A>
...
<A NAME="76777"></A>
int *firstValue = find(values+10,    // search the range
                       values+20,    // values[10] - values[19]
                       age);         // for the value in age
</PRE>
</UL><A NAME="76778"></A>

<P><A NAME="dingp37"></A>
There's nothing inherent in the <CODE>find</CODE> function that limits its applicability to arrays of <CODE>int</CODE>s, so it should really be a <NOBR>template:<SCRIPT>create_link(37);</SCRIPT>
</NOBR></P>

<A NAME="48079"></A>
<UL><PRE>template&lt;class T&gt;
T * find(T *begin, T *end, const T&amp; value)
{
  while (begin != end &amp;&amp; *begin != value) ++begin;
  return begin;
}
</PRE>
</UL><A NAME="48026"></A>

<P><A NAME="dingp38"></A>
In the transformation to a template, notice how we switched from pass-by-value for <CODE>value</CODE> to pass-by-reference-to-<CODE>const</CODE>. That's because now that we're passing arbitrary types around, we have to worry about the cost of pass-by-value. Each by-value parameter costs us a call to the parameter's constructor and destructor every time the function is invoked. We avoid these costs by using pass-by-reference, which involves no object construction or destruction (see <a href="../EC/EI22_FR.HTM#6133" TARGET="_top">Item E22</A>).<SCRIPT>create_link(38);</SCRIPT>
</P><A NAME="48094"></A>

<P><A NAME="dingp39"></A>
This template is nice, but it can be generalized further. Look at the operations on <CODE>begin</CODE> and <CODE>end</CODE>. The only ones used are comparison for inequality, dereferencing, prefix increment (see <a href="./MI6_FR.HTM#5262" TARGET="_top">Item 6</A>), and copying (for the function's return value &#151; see <a href="./MI19_FR.HTM#41177" TARGET="_top">Item 19</A>). These are all operations we can overload, so why limit <CODE>find</CODE> to using pointers? Why not allow any object that supports these operations to be used in addition to pointers? Doing so would free the <CODE>find</CODE> function from the built-in meaning of pointer operations. For example, we could define a pointer-like object for a linked list whose prefix increment operator moved us to the next element in the <NOBR>list.<SCRIPT>create_link(39);</SCRIPT>
</NOBR></P><A NAME="48124"></A>

<P><A NAME="dingp40"></A>
This is the concept behind STL <I>iterators</I>. Iterators are pointer-like objects designed for use with STL containers. They are first cousins to the smart pointers of <a href="./MI28_FR.HTM#61766" TARGET="_top">Item 28</A>, but smart pointers tend to be more ambitious in what they do than do STL iterators. From a technical viewpoint, however, they are implemented using the same <NOBR>techniques.<SCRIPT>create_link(40);</SCRIPT>
</NOBR></P><A NAME="48137"></A>

<P><A NAME="dingp41"></A>
Embracing the notion of iterators as pointer-like objects, we can replace the pointers in <CODE>find</CODE> with iterators, thus rewriting <CODE>find</CODE> like <NOBR>this:<SCRIPT>create_link(41);</SCRIPT>
</NOBR></P>

<A NAME="48066"></A>
<UL><PRE><A NAME="p283"></A>template&lt;class Iterator, class T&gt;
Iterator find(Iterator begin, Iterator end, const T&amp; value)
{
  while (begin != end &amp;&amp; *begin != value) ++begin;
  return begin;
}</PRE>
</UL><A NAME="47920"></A>

<P><A NAME="dingp42"></A>
Congratulations! You have just written part of the Standard Template Library. The STL contains dozens of algorithms that work with containers and iterators, and <CODE>find</CODE> is one of <NOBR>them.<SCRIPT>create_link(42);</SCRIPT>
</NOBR></P><A NAME="49909"></A>

<P><A NAME="dingp43"></A>
Containers in STL include <CODE>bitset</CODE>, <CODE>vector</CODE>, <CODE>list</CODE>, <CODE>deque</CODE>, <CODE>queue</CODE>, <CODE>priority_queue</CODE>, <CODE>stack</CODE>, <CODE>set</CODE>, and <CODE>map</CODE>, and you can apply <CODE>find</CODE> to <i>any </i>of these container <NOBR>types:<SCRIPT>create_link(43);</SCRIPT>
</NOBR></P>

<A NAME="48195"></A><UL><PRE>
list&lt;char&gt; charList;                  // create STL list object
                                      // for holding chars
...
<A NAME="48199"></A>
// find the first occurrence of 'x' in charList
list&lt;char&gt;::iterator it = find(charList.begin(),
                               charList.end(),
                               'x');</PRE>
</UL>
<A NAME="48210"></A>

<P><A NAME="dingp44"></A>
"Whoa!", I hear you cry, "This doesn't look <I>anything</I> like it did in the array examples above!" Ah, but it does; you just have to know what to look <NOBR>for.<SCRIPT>create_link(44);</SCRIPT>
</NOBR></P><A NAME="48223"></A>
<P><A NAME="dingp45"></A>
To call <CODE>find</CODE> for a <CODE>list</CODE> object, you need to come up with iterators that point to the first element of the list and to one past the last element of the list. Without some help from the <CODE>list</CODE> class, this is a difficult task, because you have no idea how a <CODE>list</CODE> is implemented. Fortunately, <CODE>list</CODE> (like all STL containers) obliges by providing the member functions <CODE>begin</CODE> and <CODE>end</CODE>. These member functions return the iterators you need, and it is those iterators that are passed into the first two parameters of <CODE>find</CODE> <NOBR>above.<SCRIPT>create_link(45);</SCRIPT>
</NOBR></P><A NAME="48224"></A>
<P><A NAME="dingp46"></A>
When <CODE>find</CODE> is finished, it returns an iterator object that points to the found element (if there is one) or to <CODE>charList.end()</CODE> (if there's not). Because you know nothing about how <CODE>list</CODE> is implemented, you also know nothing about how iterators into <CODE>list</CODE>s are implemented. How, then, are you to know what type of object is returned by <CODE>find</CODE>? Again, the <CODE>list</CODE> class, like all STL containers, comes to the rescue: it provides a typedef, <CODE>iterator</CODE>, that is the type of iterators into <CODE>list</CODE>s. Since <CODE>charList</CODE> is a <CODE>list</CODE> of <CODE>char</CODE>s, the type of an iterator into such a list is <CODE>list&lt;char&gt;</CODE>::<CODE>iterator</CODE>, and that's what's used in the example above. (Each STL container class actually defines two iterator types, <CODE>iterator</CODE> and <CODE>const_iterator</CODE>. The former acts like a normal pointer, the latter like a pointer-to-<CODE>const</CODE>.)<SCRIPT>create_link(46);</SCRIPT>
</P><A NAME="48247"></A>
<A NAME="p284"></A>
<P><A NAME="dingp47"></A>
Exactly the same approach can be used with the other STL containers. Furthermore, C++ pointers <I>are</I> STL iterators, so the original array examples work with the STL <CODE>find</CODE> function, <NOBR>too:<SCRIPT>create_link(47);</SCRIPT>
</NOBR></P>

<A NAME="48344"></A>
<UL>
  <PRE>int values[50];
<A NAME="76781"></A>
...
<A NAME="76782"></A>
int *firstFive = find(values, values+50, 5);       // fine, calls
                                                   // STL find
</PRE>
</UL>
<A NAME="48258"></A>

<P><A NAME="dingp48"></A>
At its core, STL is very simple. It is just a collection of class and function templates that adhere to a set of conventions. The STL collection classes provide functions like <CODE>begin</CODE> and <CODE>end</CODE> that return iterator objects of types defined by the classes. The STL algorithm functions move through collections of objects by using iterator objects over STL collections. STL iterators act like pointers. That's really all there is to it. There's no big inheritance hierarchy, no virtual functions, none of that stuff. Just some class and function templates and a set of conventions to which they all <NOBR>subscribe.<SCRIPT>create_link(48);</SCRIPT>
</NOBR></P><A NAME="47914"></A>

<P><A NAME="dingp49"></A>
Which leads to another revelation: STL is extensible. You can add your own collections, algorithms, and iterators to the STL family. As long as you follow the STL conventions, the standard STL collections will work with your algorithms and your collections will work with the standard STL algorithms. Of course, your templates won't be part of the standard C++ library, but they'll be built on the same principles and will be just as <NOBR>reusable.<SCRIPT>create_link(49);</SCRIPT>
</NOBR></P><A NAME="48313"></A>

<P><A NAME="dingp50"></A>
There is much more to the C++ library than I've described here. Before you can use the library effectively, you must learn more about it than I've had room to summarize, and before you can write your own STL-compliant templates, you must learn more about the conventions of the STL. The standard C++ library is far richer than the C library, and the time you take to familiarize yourself with it is time well spent (see also <a href="../EC/EI49_FR.HTM#8392" TARGET="_top">Item E49</A>). Furthermore, the design principles embodied by the library &#151; those of generality, extensibility, customizability, efficiency, and reusability &#151; are well worth learning in their own right. By studying the standard C++ library, you not only increase your knowledge of the ready-made components available for use in your software, you learn how to apply the features of C++ more effectively, and you gain insight into how to design better libraries of your <NOBR>own.<SCRIPT>create_link(50);</SCRIPT>
</NOBR></P><A NAME="2472"></A>

<DIV ALIGN="CENTER"><FONT SIZE="-1">Back to <A HREF="./MI34_FR.HTM" TARGET="_top">Item  34: Understand how to combine C++ and C in the same program</A> &nbsp;&nbsp;<BR>&nbsp;&nbsp;Continue to <A HREF="./MIREADFR.HTM" TARGET="_top">Recommended Reading</A></FONT></DIV>
</BODY>
</HTML>