sea_9743.htm

来自「C++标准库 C++标准库 C++标准库 C++标准库」· HTM 代码 · 共 262 行 · 第 1/2 页

   char * where = search(base, base + strlen(base), 
         text, text + strlen(text));

   if (*where != '\0')
      cout << "substring position: " << where - base << endl;
   else
      cout << "substring does not occur in text" << endl;
}
</PRE>
<P>Note that this algorithm, unlike many that manipulate two sequences, uses a starting and ending iterator pair for both sequences, not just the first sequence.</P>
<P>Like the algorithms <SAMP>equal()</SAMP> and <SAMP>mismatch(),</SAMP> an alternative version of <SAMP>search()</SAMP> takes an optional binary predicate that is used to compare elements from the two sequences.</P>
<PRE></PRE>

<A NAME="13.3.5"><H3>13.3.5 Find the last occurrence of a Sub-sequence </H3></A>
<A NAME="idx139"><!></A>
<P>The algorithm <SAMP>find_end()</SAMP> is used to locate the beginning of a the last occurrence of a particular sub-sequence within a larger sequence.  The easiest example to understand is the problem of looking for a particular substring within a larger string, although the algorithm can be generalized to other uses.  The arguments are assumed to have at least the capabilities of forward iterators.</P>
<PRE>ForwardIterator find_end 
   (ForwardIterator first1, ForwardIterator last1, 
   ForwardIterator first2, ForwardIterator last2 
   [, BinaryPredicate ]);
</PRE>

<A HREF="sidebar1.htm#sidebar61"><IMG SRC="images/note.gif" BORDER=0> <STRONG>Speed of Find_end</STRONG></A>

<P>Suppose, for example, that we wish to discover the location of the last occurrence of the string <SAMP>"le"</SAMP> in the string <SAMP>"The road less traveled".</SAMP>  The solution to this problem is shown in the example program.  If no appropriate match is found, the value returned is the past-the-end iterator for the first sequence.</P>
<PRE>void find_end_example ()
      // illustrate the use of the find_end algorithm
{
   char * base = "The road less traveled";
   char * text = "le";

   char * where = find(base, base + strlen(base), 
         text, text + strlen(text));

   if (*where != '\0')
      cout &#60;&#60; "substring position: " &#60;&#60; where - base &#60;&#60; endl;
   else
      cout &#60;&#60; "substring does not occur in text" &#60;&#60; endl;
}
</PRE>
<P>Note that this algorithm, unlike many that manipulate two sequences, uses a starting and ending iterator pair for both sequences, not just the first sequence.</P>
<P>Like the algorithms <SAMP>find_first_of()</SAMP> and <SAMP>search(),</SAMP> an alternative version of <SAMP>find_end()</SAMP> takes an optional binary predicate that is used to compare elements from the two sequences.</P>
<PRE></PRE>

<A NAME="13.3.6"><H3>13.3.6 Locate Maximum or Minimum Element</H3></A>
<A NAME="idx140"><!></A>
<P>The functions <SAMP>max()</SAMP> and <SAMP>min()</SAMP> can be used to find the maximum and minimum of a pair of values.  These can optionally take a third argument that defines the comparison function to use in place of the less-than operator (operator <SAMP>&#60;</SAMP>).  The arguments are values, not iterators:</P>
<PRE>template &#60;class T> 
   const T&#38; max(const T&#38; a, const T&#38; b [, Compare ] );
template &#60;class T> 
   const T&#38; min(const T&#38; a, const T&#38; b [, Compare ] );
</PRE>
<A NAME="idx141"><!></A>
<P>The maximum and minimum functions are generalized to entire sequences by the generic algorithms <SAMP>max_element()</SAMP> and <SAMP>min_element().</SAMP> For these functions the arguments are input iterators.</P>
<PRE>ForwardIterator max_element (ForwardIterator first, 
      ForwardIterator last [, Compare ] );
ForwardIterator min_element (ForwardIterator first, 
      ForwardIterator last [, Compare ] );
</PRE>

<A HREF="sidebar1.htm#sidebar62"><IMG SRC="images/note.gif" BORDER=0> <STRONG>Largest and Smallest Elements of a Set</STRONG></A>

<P>These algorithms return an iterator that denotes the largest or smallest of the values in a sequence, respectively.  Should more than one value satisfy the requirement, the result yielded is the first satisfactory value.  Both algorithms can optionally take a third argument, which is the function to be used as the comparison operator in place of the default operator.</P>
<P>The example program illustrates several uses of these algorithms.  The function named <SAMP>split()</SAMP> used to divide a string into words in the string example is described in <A HREF="ane_8974.htm">Section 12.3</A>.  The function <SAMP>randomInteger() </SAMP>is described in <A HREF="var_0565.htm#2.2.5">Section 2.2.5</A>.</P>
<PRE>void max_min_example ()
   // illustrate use of max_element and min_element algorithms
{
   // make a vector of random numbers between 0 and 99
   vector&#60;int> numbers(25);
   for (int i = 0; i &#60; 25; i++)
      numbers[i] = randomInteger(100);

   // print the maximum
   vector&#60;int>::iterator max = 
      max_element(numbers.begin(), numbers.end());
   cout &#60;&#60; "largest value was " &#60;&#60; * max &#60;&#60; endl;

   // example using strings
   string text = 
      "It was the best of times, it was the worst of times.";
   list&#60;string> words;
   split (text, " .,!:;", words);
   cout &#60;&#60; "The smallest word is " 
         &#60;&#60; * min_element(words.begin(), words.end())
         &#60;&#60; " and the largest word is "
         &#60;&#60; * max_element(words.begin(), words.end())
         &#60;&#60; endl;
}
</PRE>

<A NAME="13.3.7"><H3>13.3.7 Locate the First Mismatched Elements in Parallel Sequences</H3></A>
<A NAME="idx142"><!></A>
<P>The name <SAMP>mismatch()</SAMP>  might lead you to think this algorithm was the inverse of the <SAMP>equal()</SAMP> algorithm, which determines if two sequences are equal (see <A HREF="sca_1926.htm#13.6.4">Section 13.6.4</A>).  Instead, the <SAMP>mismatch()</SAMP> algorithm returns a <B><I>pair</I></B> of iterators that together indicate the first positions where two parallel sequences have differing elements.  (The structure <A HREF="../stdlibcr/pai_5818.htm"><B><I>pair</I></B></A> is described in Section 9.1).  The second sequence is denoted only by a starting position, without an ending position.  It is assumed (but not checked) that the second sequence contains at least as many elements as the first.  The arguments and return type for <SAMP>mismatch()</SAMP> can be described as follows:</P>
<PRE>pair&#60;InputIterator, InputIterator> mismatch 
   (InputIterator first1, InputIterator last1, 
      InputIterator first2 [, BinaryPredicate ] );</PRE>
<P>The elements of the two sequences are examined in parallel, element by element.  When a mismatch is found, that is, a point where the two sequences differ, then a <B><I>pair</I></B> containing iterators denoting the locations of the two differing elements is constructed and returned.  If the first sequence becomes exhausted before discovering any mismatched elements, then the resulting pair contains the ending value for the first sequence, and the last value examined in the second sequence.  (The second sequence need not yet be exhausted).</P>
<P>The example program illustrates the use of this procedure.  The function <SAMP>mismatch_test()</SAMP> takes as arguments two string values.  These are lexicographically compared and a message printed indicating their relative ordering. (This is similar to the analysis performed by the <SAMP>lexicographic_compare()</SAMP> algorithm, although that function simply returns a boolean value.) Because the <SAMP>mismatch()</SAMP> algorithm assumes the second sequence is at least as long as the first, a comparison of the two string lengths is performed first, and the arguments are reversed if the second string is shorter than the first.  After the call on <SAMP>mismatch()</SAMP> the elements of the resulting pair are separated into their component parts.  These parts are then tested to determine the appropriate ordering.</P>
<PRE>   void mismatch_test (char * a, char * b)
          // illustrate the use of the mismatch algorithm
   {
      pair&#60;char *, char *> differPositions(0, 0);
      char * aDiffPosition;
      char * bDiffPosition;
      if (strlen(a) &#60; strlen(b)) {
         // make sure longer string is second
         differPositions = mismatch(a, a + strlen(a), b);
         aDiffPosition = differPositions.first;
         bDiffPosition = differPositions.second;
         }
      else {
         differPositions = mismatch(b, b + strlen(b), a);
         // note following reverse ordering
         aDiffPosition = differPositions.second;
         bDiffPosition = differPositions.first;
         }</PRE><PRE>      // compare resulting values
      cout &#60;&#60; "string " &#60;&#60; a;
      if (*aDiffPosition == *bDiffPosition)
         cout &#60;&#60; " is equal to ";
      else if (*aDiffPosition &#60; *bDiffPosition)
         cout &#60;&#60; " is less than ";
      else
         cout &#60;&#60; " is greater than ";
      cout &#60;&#60; b &#60;&#60; endl;
   }
</PRE><P>A second form of the <SAMP>mismatch()</SAMP> algorithm is similar to the one illustrated, except it accepts a binary predicate as a fourth argument.  This binary function is used to compare elements, in place of the <SAMP>==</SAMP> operator.</P>

<HR>
<A HREF="ini_5794.htm"><IMG SRC="images/prev.gif"></A> <A HREF="booktoc1.htm"><IMG SRC="images/toc.gif"></A><A HREF="tindex1.htm"><IMG SRC="images/tindex.gif"></A><A HREF="inp_4704.htm"><IMG SRC="images/next.gif"></A><P>&copy;Copyright 1996, Rogue Wave Software, Inc.</P>
</BODY></HTML>