?? csdn技術中心 cuj：標準庫：標準庫中的搜索算法.htm
字號:
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT size=3><FONT face=宋體><SPAN
style="mso-tab-count: 1">
</SPAN>可能直接將id傳給lower_bound()嗎？也許，通過傳入一個異質比較函數，它接受一個X和一個id？這個問題沒有一個簡單的答案。C++標準沒有完全說清楚是否允許這樣的異質比較函數；依我之見，對標準的最自然的讀解是不允許。在現今的實踐中，異質比較函數在一些實作上可行，而在另外一些上不行。另一方面，C++標準化委員會認為這是一個缺陷，并且在未來版本的標準將明確是否允許異質比較函數[注4]。</FONT></FONT></SPAN></P>
<H3 style="MARGIN: auto 0cm"><FONT face=宋體>總結</FONT></H3>
<P class=MsoPlainText
style="MARGIN: 0cm 0cm 0pt; TEXT-INDENT: 21pt"><SPAN
lang=EN-US><FONT face=宋體
size=3>C++運行庫還提供了其它一些形式的搜索算法。使用find()和lower_bound()，搜索只限于單個元素，但標準運行庫還提供了serach()，它尋找整個子區間。比如，你可以在一個字符串中搜索一個單詞：</FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體 size=3>std::string the =
"the";</FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體 size=3>std::string::iterator
i</FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT size=3><FONT face=宋體><SPAN
style="mso-spacerun: yes"> </SPAN>= std::search(s.begin(),
s.end(),</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT size=3><FONT face=宋體><SPAN
style="mso-spacerun: yes">
</SPAN>the.begin(), the.end());</FONT></FONT></SPAN></P>
<P class=MsoPlainText
style="MARGIN: 0cm 0cm 0pt; TEXT-INDENT: 21pt"><FONT size=3><FONT
face=宋體>返回值，<SPAN
lang=EN-US>i，將指向“the”在s中第一次出現的開始處－－或，和往常一樣，如果“the”不存在將返回s.end()。還有一個變種以從尾部開始搜索：</SPAN></FONT></FONT></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體 size=3>std::find_end(s.begin(),
s.end(),</FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT size=3><FONT face=宋體><SPAN
style="mso-spacerun: yes">
</SPAN>the.begin(), the.end());</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT size=3><FONT face=宋體><SPAN
style="mso-tab-count: 1">
</SPAN>它返回一個iterator，指向“the”最后出現處的開始，而不是第一個。(如果你認為這很奇怪，search的逆向變種叫find_end()而不是search_end()，那么你并不孤獨。)</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT size=3><FONT face=宋體><SPAN
style="mso-tab-count: 1">
</SPAN>搜索可以被封裝入數據結構。最明顯地，標準運行庫的關聯容器，set、multiset、map和multimap，被特別設計為根據key進行搜索將很高效[注5]。運行庫的string類也提供了許多搜索用的成員函數：find()、rfind()、find_first_of()、find_last_of()、find_first_not_of()和find_last_not_of()。我建議避免使用它們。我發現這些特殊的成員函數難以記憶，因為它們擁有如此多的形式，并且接口形式與運行庫的其它部分不同；無論如何，他們不會提供任何不能從find()、find_if()、search()得到的功能。</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT size=3><FONT face=宋體><SPAN
style="mso-tab-count: 1">
</SPAN>但是，如果你仍然認為看到了一些重要的省略，你是正確的！我沒有提到hash表，因為標準運行庫中沒有hash表。我提到了search()的子區間匹配，但那當然只是模式匹配的一個特例－－標準運行庫中沒有正則表達式搜索或任何類似的東西。</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><FONT size=3><FONT
face=宋體><SPAN lang=EN-US><SPAN
style="mso-tab-count: 1">
</SPAN>C++標準化委員會剛剛開始考慮對標準運行庫擴充，而hash表和正則表達式是未來版本的標準的優先候選者。如果你認為標準運行庫缺少了什么，并且你想提交一份提議，那么現在是你應該開始準備時候了。</SPAN><SPAN
lang=EN-US style="mso-hansi-font-family: 宋體"><SPAN
style="mso-tab-count: 1">
</SPAN><o:p></o:p></SPAN></FONT></FONT></P>
<H3 style="MARGIN: auto 0cm"><FONT face=宋體>注<SPAN
lang=EN-US><o:p></o:p></SPAN></FONT></H3>
<P class=MsoNormal style="MARGIN: 0cm 0cm 0pt"><SPAN lang=EN-US
style="FONT-FAMILY: 宋體"><FONT size=3>[1] See Table 72 in the C++
Standard. Some of the other search algorithms, which I discuss
later, rely on the stronger <I>Forward Iterator</I>
requirements.<o:p></o:p></FONT></SPAN></P>
<P class=MsoNormal style="MARGIN: 0cm 0cm 0pt"><SPAN lang=EN-US
style="FONT-FAMILY: 宋體"><FONT size=3>[2] See, for example,
<</FONT><A href="http://www.sgi.com/tech/stl"><FONT
size=3>www.sgi.com/tech/stl</FONT></A><FONT
size=3>>.<o:p></o:p></FONT></SPAN></P>
<P class=MsoNormal style="MARGIN: 0cm 0cm 0pt"><SPAN lang=EN-US
style="FONT-FAMILY: 宋體"><FONT size=3>[3] See “Algorithm Q,” in §6.1
of D. E. Knuth, <I>The Art of Computer Programming, vol. 2, Sorting
and Searching</I>, Second Edition (Addison-Wesley,
1998).<o:p></o:p></FONT></SPAN></P>
<P class=MsoNormal style="MARGIN: 0cm 0cm 0pt"><SPAN lang=EN-US
style="FONT-FAMILY: 宋體"><FONT size=3>[4] See <</FONT><A
href="http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-active.html#270"><FONT
size=3>http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-active.html#270</FONT></A><FONT
size=3>>. Dave Abrahams had the insight that enabled the proposed
resolution to this issue. He pointed out that it’s possible to think
of binary searches not in terms of sorting and comparisons, but in
terms of partitioning: we’re given a range with the property that
all elements before a certain point satisfy a condition and all
elements after it fail to satisfy the condition, and we’re looking
for the transition point.<o:p></o:p></FONT></SPAN></P>
<P class=MsoNormal style="MARGIN: 0cm 0cm 0pt"><SPAN lang=EN-US
style="FONT-FAMILY: 宋體"><FONT size=3>[5] But these containers aren’t
the most efficient choice as often as one might think. See my
earlier column “Why You Shouldn’t Use set — and What You Should Use
Instead,” <I>C++ Report</I>, April 2000.
<o:p></o:p></FONT></SPAN></P>
<P class=MsoNormal style="MARGIN: 0cm 0cm 0pt"><SPAN lang=EN-US
style="FONT-FAMILY: 宋體"><FONT
size=3> <o:p></o:p></FONT></SPAN></P></SPAN><BR>
<DIV
style="FONT-SIZE: 14px; LINE-HEIGHT: 25px"><STRONG>作者Blog：</STRONG><A
id=ArticleContent1_ArticleContent1_AuthorBlogLink
href="http://blog.csdn.net/taodm/"
target=_blank>http://blog.csdn.net/taodm/</A></DIV>
<DIV
style="FONT-SIZE: 14px; COLOR: #900; LINE-HEIGHT: 25px"><STRONG>相關文章</STRONG></DIV>
<TABLE id=ArticleContent1_ArticleContent1_RelatedArticles
style="BORDER-COLLAPSE: collapse" cellSpacing=0 border=0>
<TBODY>
<TR>
<TD><A
href="http://dev.csdn.net/article/18/article/26/26838.shtm">Loki庫讀解
STATIC_CHECK擴展：可放在任何地方的STATIC_CHECK，編譯期打印出類型的大小</A> </TD></TR>
<TR>
<TD><A
href="http://dev.csdn.net/article/18/article/26/26574.shtm">Loki庫讀解-擴展TypeList：Typelist生成器、MaxSizeOf</A>
</TD></TR>
<TR>
<TD><A
href="http://dev.csdn.net/article/18/article/18/18446.shtm">CUJ：高效使用標準庫：顯式函數模板參數申明與STL</A>
</TD></TR>
<TR>
<TD><A
href="http://dev.csdn.net/article/18/article/18/18362.shtm">CUJ：高效使用標準庫：STL中的unary
predicate</A> </TD></TR>
<TR>
<TD><A
href="http://dev.csdn.net/article/18/article/18/18258.shtm">CUJ：高效使用標準庫：for_each()
vs. transform()</A> </TD></TR></TBODY></TABLE></TD></TR></TBODY></TABLE><A
name=#Comment></A>
<TABLE cellPadding=0 width="100%" border=0>
<TBODY>
<TR>
<TD>
<TABLE cellSpacing=0 cellPadding=0 width="100%" align=center
bgColor=#006699 border=0>
<TBODY>
<TR bgColor=#006699>
<TD id=white align=middle width=556 bgColor=#006699><FONT
color=#ffffff>對該文的評論</FONT> </TD></TR></TBODY></TABLE>
<DIV align=right><A id=CommnetList1_CommnetList1_Morelink
href="http://comment.csdn.net/Comment.aspx?c=2&s=18031">【評論】</A>
<A id=CommnetList1_CommnetList1_Hyperlink1
href="javascript:window.close();">【關閉】</A>
</DIV><BR></TD></TR></TBODY></TABLE></TD></TR></TBODY></TABLE></FORM><!-- 版權 -->
<HR align=center width=770 noShade SIZE=1>
<TABLE cellSpacing=0 cellPadding=0 width=500 align=center border=0>
<TBODY>
<TR>
<TD vAlign=bottom align=middle height=10><A
href="http://www.csdn.net/intro/intro.asp?id=2">網站簡介</A> - <A
href="http://www.csdn.net/intro/intro.asp?id=5">廣告服務</A> - <A
href="http://www.csdn.net/map/map.shtm">網站地圖</A> - <A
href="http://www.csdn.net/help/help.asp">幫助信息</A> - <A
href="http://www.csdn.net/intro/intro.asp?id=2">聯系方式</A> - <A
href="http://www.csdn.net/english">English</A> </TD>
<TD align=middle rowSpan=3><A
href="http://www.hd315.gov.cn/beian/view.asp?bianhao=010202001032100010"><IMG
height=48 src="CSDN技術中心 CUJ：標準庫：標準庫中的搜索算法.files/biaoshi.gif" width=40
border=0></A></TD></TR>
<TR>
<TD vAlign=top align=middle>北京百聯美達美數碼科技有限公司 版權所有 京ICP證020026號</TD></TR>
<TR align=middle>
<TD vAlign=top><FONT face=Verdana>Copyright © CSDN.NET, Inc. All Rights
Reserved</FONT></TD></TR>
<TR>
<TD height=15></TD></TR></TBODY></TABLE><!-- /版權 -->
<SCRIPT>
document.write("<img src=http://count.csdn.net/count/pageview1.asp?columnid=4&itemid=11 border=0 width=0 height=0>");
</SCRIPT>
</BODY></HTML>
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -