?? csdn技術中心 cuj：標準庫：標準庫中的搜索算法.htm
字號:
style="FONT-FAMILY: 宋體"><A
href="http://www.cuj.com/experts/1911/austern.htm?topic=experts"><FONT
size=3>http://www.cuj.com/experts/1911/austern.htm?topic=experts</FONT></A><o:p></o:p></SPAN></P>
<P class=MsoNormal style="MARGIN: 0cm 0cm 0pt; TEXT-ALIGN: center"
align=center><SPAN lang=EN-US style="FONT-FAMILY: 宋體"><FONT
size=3> <o:p></o:p></FONT></SPAN></P>
<P class=MsoNormal style="MARGIN: 0cm 0cm 0pt"><FONT size=3><SPAN
lang=EN-US>The genius as well as the oversights in the design of the
Standard C++ library surface in a simple discussion of its linear
and binary search algorithms. </SPAN><SPAN lang=EN-US
style="FONT-SIZE: 12pt; FONT-FAMILY: 宋體; mso-font-kerning: 0pt"><o:p></o:p></SPAN></FONT></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體
size=3>--------------------------------------------------------------------------------</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>如果你儲存著一系列的元素，或許原因理由之一是因此你能夠在它里面找到些對象。在一個集合中找到一個特別的條目是個很重要的問題；所有的書都會寫到它。不奇怪，標準C++運行庫提供了許多不同的搜索技術。</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>在
C++運行庫中，指明一個集合的常用方法是通過iterator指示出區間。區間可以被寫為[first,
last)，此處，*first是區間內的第一個元素而last則指向最后一個元素的下一個。本文展示了我們如何考慮一個通用問題：給定一個區間和一個準則，找到指向第一個滿足準則的元素的iterator。因為我們將區間表示為不對稱的形式，于是避開了一個特殊情況：搜索失敗可以返回last，沒有任何元素的區間可以寫為[i,
i)。</FONT></FONT></SPAN></P>
<H3 style="MARGIN: auto 0cm"><FONT face=宋體>線性搜索和它的變種</FONT></H3>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體><FONT size=3><SPAN
style="mso-tab-count: 1">
</SPAN>最簡單的搜索是線性搜索，或，如Knuth所稱呼的，順序搜索：依次查看每個元素，檢查它是否為我們正在搜索的那個。如果區間中有N個元素，最壞的情況就需要N次比較。</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體><FONT size=3><SPAN
style="mso-tab-count: 1">
</SPAN>標準運行庫提供了線性搜索的一些版本；兩個最重要的版本是find()
(它接受一個區間和值x，并查找等價于x的元素)和find_if()(接受一個區間和判決條件p，并查找滿足p的元素)。線性搜索的其它版本是find_first_of()(接受兩個區間，[first1,last1)和[first2,last2)
，并在[first1, last1)中查找第一個等價于[first2,
last2)中任何一個元素的元素]和adjacent_find()(接受單一區間，并查找第一個等價于其后繼元素的元素)。</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體><FONT size=3><SPAN
style="mso-tab-count: 1">
</SPAN>舉例來說，假如，v是一個int的vector。你能用下面的代碼查找第一個0：</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體 size=3>vector<int>::iterator i
=</FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體><FONT size=3><SPAN
style="mso-spacerun: yes"> </SPAN>find(v.begin(), v.end(),
0);</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體><FONT size=3><SPAN
style="mso-tab-count: 1">
</SPAN>你也能這樣查找第一個非0值：</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體 size=3>vector<int>::iterator i
=</FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體><FONT size=3><SPAN
style="mso-spacerun: yes"> </SPAN>find_if(v.begin(),
v.end(),</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體><FONT size=3><SPAN
style="mso-spacerun: yes">
</SPAN>not1(bind2nd(equal_to<int>(),</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體><FONT size=3><SPAN
style="mso-spacerun: yes">
</SPAN>0)));</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體><FONT size=3><SPAN
style="mso-tab-count: 1">
</SPAN>你能這樣查找第一個小質數：</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體 size=3>A[4] = { 2, 3, 5, 7
};</FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體 size=3>vector<int>::iterator i
=</FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體><FONT size=3><SPAN
style="mso-spacerun: yes"> </SPAN>find_first_of(v.begin(),
v.end(),</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體><FONT size=3><SPAN
style="mso-spacerun: yes">
</SPAN>A+0, A+4);</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體><FONT size=3><SPAN
style="mso-tab-count: 1">
</SPAN>你能這樣找到第一個重復對：</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體 size=3>vector<int>::iterator i
=</FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體><FONT size=3><SPAN
style="mso-spacerun: yes"> </SPAN>adjacent_find(v.begin(),
v.end());</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體><FONT size=3><SPAN
style="mso-tab-count: 1">
</SPAN>沒有任何獨立版本以對區間進行逆向搜索，因為你不需要：你能用一個簡單的iterator
adaptor來達到相同的效果。比如，在v中找到最后一個0，可以這么寫：</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體 size=3>vector<int>::reverse_iterator
i =</FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體><FONT size=3><SPAN
style="mso-spacerun: yes"> </SPAN>find(v.rbegin(), v.rend(),
0);</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體><FONT size=3><SPAN
style="mso-tab-count: 1">
</SPAN>線性搜索是一個簡單的算法，它的實現看起來沒什么可討論的。許多書(包括我的)展示了std::find()的一個簡單的實現：</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體 size=3>template <class InIter, class
T></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體 size=3>InIter find(InIter first, InIter
last,</FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體><FONT size=3><SPAN
style="mso-spacerun: yes">
</SPAN>const T& val)</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體 size=3>{</FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體><FONT size=3><SPAN
style="mso-spacerun: yes"> </SPAN>while (first != last
&& !</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體><FONT size=3><SPAN
style="mso-spacerun: yes"> </SPAN>(*first ==
val))</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體><FONT size=3><SPAN
style="mso-spacerun: yes">
</SPAN>++first;</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體><FONT size=3><SPAN
style="mso-spacerun: yes"> </SPAN>return
first;</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體 size=3>}</FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體><FONT size=3><SPAN
style="mso-tab-count: 1">
</SPAN>這的確是線性搜索算法的一個忠實的實現，滿足C++標準的需求；第一個模板參數的名字，InIter，意味著實參只需要是非常弱的Input
Iterator[注1]。它看起來可能是如此的簡單，以致于還不如在代碼中直接手寫出來。雖然如此，還是有一個令人懊惱的問題：這個實現沒有達到它應該的效率。循環條件很復雜，需要為取得的每個元素作兩個測試。有條件的分支昂貴的，并且復雜的循環條件不會得到與簡單的循環條件同樣程度的優化。</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體><FONT size=3><SPAN
style="mso-tab-count: 1">
</SPAN>問題的答案之一，并是被某些標準運行庫的實作所采用[注2]，是“解開”循環，每次檢查4個元素。這是比較復雜的解決方法，因為find()然后必須處理殘余元素（區間不會總是4的倍數?。?，以及它還需要find()基于Iterator的種類進行分解－－“解開”只能工作于Random
Access Iterator指示的區間，對一般情況還是需要使用老的實現。但是，“解開”是有效果的：它將對每個元素的測試的數目從2降到
1.25。它是標準庫的實現人員不需要改動任何接口就能采用的技術。</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><FONT size=3><SPAN
lang=EN-US><FONT face=宋體><SPAN
style="mso-tab-count: 1">
</SPAN>你將會在講述算法的常見書籍中看到一個不同的答案。需要對每個元素作兩次測試的原因是，如果到達區間結束還沒有找到所要找的元素，我們必須承認已經失敗。但是如果我們碰巧所要查找的元素總是存在，搜索絕不會失敗時，會怎么樣？在那種情況下，為區間結束作的測試是多余的；會沒有任何的理由認為搜索算法應該首先掌握區間結束的信息（there
wouldn</FONT></SPAN><SPAN lang=EN-US
style="FONT-FAMILY: 'Courier New'; mso-ascii-font-family: 宋體">’</SPAN><SPAN
lang=EN-US><FONT face=宋體>t be any reason for the search algorithm to
keep track of the end of the range in the first
place）。取代std::find()，我們可以如下實現線性搜索算法：</FONT></SPAN></FONT></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體 size=3>template <class InIter, class
T></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體 size=3>InIter</FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -