📄 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 + -