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