sea_9743.htm
来自「C++标准库 C++标准库 C++标准库 C++标准库」· HTM 代码 · 共 262 行 · 第 1/2 页
HTM
262 行
<HTML><HEAD><TITLE>13.3 Searching Operations</TITLE></HEAD><BODY><A HREF="ug1.htm"><IMG SRC="images/banner.gif"></A><BR><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><BR><STRONG>Click on the banner to return to the user guide home page.</STRONG><H2>13.3 Searching Operations</H2><A NAME="idx134"><!></A><P>The next category of algorithms we will describe are those that are used to locate elements within a sequence that satisfy certain properties. Most commonly the result of a search is then used as an argument to a further operation, such as a <SAMP>copy </SAMP>(<A HREF="inp_4704.htm#13.4.4">Section 13.4.4</A>), a <SAMP>partition</SAMP> (Section 13.2.2) or an <SAMP>in-place merge</SAMP> (Section 13.4.6.)</P><A HREF="sidebar1.htm#sidebar56"><IMG SRC="images/note.gif" BORDER=0> <STRONG>Obtaining the Source</STRONG></A><P>The searching routines described in this section return an iterator that identifies the first element that satisfies the search condition. It is common to store this value in an iterator variable, as follows:</P><PRE> list<int>::iterator where; where = find(aList.begin(), aList.end(), 7);</PRE><P>If you want to locate <I>all</I> the elements that satisfy the search conditions you must write a loop. In that loop, the value yielded by a previous search is first advanced (since otherwise the value yielded by the previous search would once again be returned), and the resulting value is used as a starting point for the new search. For example, the following loop from the <SAMP>adjacent_find()</SAMP> example program (<A HREF="sea_9743.htm#13.3.2">Section 13.3.2</A>) will print the value of all repeated characters in a string argument.</P><A HREF="sidebar1.htm#sidebar57"><IMG SRC="images/note.gif" BORDER=0> <STRONG>Check Search Results</STRONG></A><PRE> while ((where = adjacent_find(where, stop)) != stop) { cout << "double " << *where << " in position " << where - start << endl; ++where; }</PRE><P>Many of the searching algorithms have an optional argument that can specify a function to be used to compare elements, in place of the equality operator for the container element type (operator <SAMP>==</SAMP>). In the descriptions of the algorithms we write these optional arguments inside a square bracket, to indicate they need not be specified if the standard equality operator is acceptable.</P><A NAME="13.3.1"><H3>13.3.1 Find an Element Satisfying a Condition</H3></A><A NAME="idx135"><!></A><P>There are two algorithms, <SAMP>find()</SAMP> and <SAMP>find_if(),</SAMP> that are used to find the first element that satisfies a condition. The declarations of these two algorithms are as follows:</P><PRE>InputIterator find_if (InputIterator first, InputIterator last, Predicate);InputIterator find (InputIterator first, InputIterator last, const T&);</PRE><P>The algorithm <SAMP>find_if()</SAMP> takes as argument a predicate function, which can be any function that returns a boolean value (see <A HREF="pre_1157.htm">Section 3.2</A>). The <SAMP>find_if()</SAMP> algorithm returns a new iterator that designates the first element in the sequence that satisfies the predicate. The second argument, the past-the-end iterator, is returned if no element is found that matches the requirement. Because the resulting value is an iterator, the dereference operator (the <SAMP>*</SAMP> operator) must be used to obtain the matching value. This is illustrated in the example program.</P><P>The second form of the algorithm, <SAMP>find(),</SAMP> replaces the predicate function with a specific value, and returns the first element in the sequence that tests equal to this value, using the appropriate equality operator (the <SAMP>==</SAMP> operator) for the given data type.</P><A HREF="sidebar1.htm#sidebar58"><IMG SRC="images/note.gif" BORDER=0> <STRONG>Searching Sets and Maps</STRONG></A><P>The following example program illustrates the use of these algorithms:</P><PRE>void find_test () // illustrate the use of the find algorithm{ int vintageYears[] = {1967, 1972, 1974, 1980, 1995}; int * start = vintageYears; int * stop = start + 5; int * where = find_if (start, stop, isLeapYear); if (where != stop) cout << "first vintage leap year is " << *where << endl; else cout << "no vintage leap years" << endl;</PRE><PRE> where = find(start, stop, 1995); if (where != stop) cout << "1995 is position " << where - start << " in sequence" << endl; else cout "1995 does not occur in sequence" << endl;}</PRE><A NAME="13.3.2"><H3>13.3.2 Find Consecutive Duplicate Elements</H3></A><A NAME="idx136"><!></A><P>The <SAMP>adjacent_find()</SAMP> algorithm is used to discover the first element in a sequence equal to the next immediately following element. For example, if a sequence contained the values 1 4 2 5 6 6 7 5, the algorithm would return an iterator corresponding to the first 6 value. If no value satisfying the condition is found, then the end-of-sequence iterator is returned. The declaration of the algorithm is as follows:</P><PRE>ForwardIterator adjacent_find (ForwardIterator first, ForwardIterator last [, BinaryPredicate ] );</PRE><P>The first two arguments specify the sequence to be examined. The optional third argument must be a binary predicate (a binary function returning a boolean value). If present, the binary function is used to test adjacent elements, otherwise the equality operator (operator <SAMP>==</SAMP>) is used.</P><P>The example program searches a text string for adjacent letters. In the example text these are found in positions 5, 7, 9, 21 and 37. The increment is necessary inside the loop in order to avoid the same position being discovered repeatedly.</P><PRE>void adjacent_find_example () // illustrate the use of the adjacent_find instruction{ char * text = "The bookkeeper carefully opened the door."; char * start = text; char * stop = text + strlen(text); char * where = start; cout << "In the text: " << text << endl; while ((where = adjacent_find(where, stop)) != stop) { cout << "double " << *where << " in position " << where - start << endl; ++where; }}</PRE><A NAME="13.3.3"><H3>13.3.3 Find the first occurrence of any value from a sequence</H3></A><A NAME="idx137"><!></A><P>The algorithm <SAMP>find_first_of()</SAMP> is used to find the first occurrence of some element from one sequence that is also contained in another sequence. </P><PRE>ForwardIterator1 find_first_of (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2 [, BinaryPredicate pred ] );</PRE><P>The algorithm returns a new iterator that designates the first element found in <SAMP>[first1,last1)</SAMP> that is also contained in <SAMP>[first2,last2)</SAMP>. If no match is found then the second argument is returned . Because the resulting value is an iterator, the dereference operator (the <SAMP>*</SAMP> operator) must be used to obtain the matching value. This is illustrated in the example program.</P><A HREF="sidebar1.htm#sidebar59"><IMG SRC="images/note.gif" BORDER=0> <STRONG>Searching Sets and Maps</STRONG></A><P>The following example program illustrates the use of this algorithm:</P><PRE>void find_test () // illustrate the use of the find algorithm{ int vintageYears[] = {1967, 1972, 1974, 1980, 1995}; int requestedYears[] = [1923, 1970, 1980, 1974 }; int * start = vintageYears; int * stop = start + 5; int * where = find_first_of (start, stop, requestedyears,requestedyears+4 ); if (where != stop) cout << "first requested vintage year is " << *where << endl; else cout << "no requested vintage years" << endl;</PRE><PRE>}// The output would indicate 1974.</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>find_first_of()</SAMP> takes an optional binary predicate that is used to compare elements from the two sequences.</P><PRE></PRE><A NAME="13.3.4"><H3>13.3.4 Find a Sub-sequence within a Sequence</H3></A><A NAME="idx138"><!></A><P>The algorithms <SAMP>search()</SAMP> and <SAMP>search_n()</SAMP> are used to locate the beginning 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 search (ForwardIterator first1, ForwardIterator last1, ForwardIterator first2, ForwardIterator last2 [, BinaryPredicate ]);</PRE><A HREF="sidebar1.htm#sidebar60"><IMG SRC="images/note.gif" BORDER=0> <STRONG>Speed of Search</STRONG></A><P>Suppose, for example, that we wish to discover the location of the string <SAMP>"ration"</SAMP> in the string <SAMP>"dreams and aspirations".</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 search_example () // illustrate the use of the search algorithm{ char * base = "dreams and aspirations"; char * text = "ration";⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?