📄 item_085.htm
字号:
{mso-list-id:1852142267;
mso-list-type:hybrid;
mso-list-template-ids:2025458442 1525840168 67698691 67698693 67698689 67698691 67698693 67698689 67698691 67698693;}
@list l2:level1
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:36.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Symbol;
color:windowtext;}
@list l3
{mso-list-id:1891922128;
mso-list-template-ids:1133777540;}
@list l3:level1
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:36.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
ol
{margin-bottom:0cm;}
ul
{margin-bottom:0cm;}
-->
</style>
<!--[if gte mso 10]>
<style>
/* Style Definitions */
table.MsoNormalTable
{mso-style-name:"Table Normal";
mso-tstyle-rowband-size:0;
mso-tstyle-colband-size:0;
mso-style-noshow:yes;
mso-style-parent:"";
mso-padding-alt:0cm 5.4pt 0cm 5.4pt;
mso-para-margin:0cm;
mso-para-margin-bottom:.0001pt;
mso-pagination:widow-orphan;
font-size:10.0pt;
font-family:"Times New Roman";
mso-ansi-language:#0400;
mso-fareast-language:#0400;
mso-bidi-language:#0400;}
</style>
<![endif]--><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="2050"/>
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1"/>
</o:shapelayout></xml><![endif]-->
</head>
<body lang=ZH-CN link=blue vlink=purple style='tab-interval:36.0pt'>
<div class=Section1>
<h3><span lang=EN-US>85. </span><span style='font-family:宋体;mso-ascii-font-family:
Arial;mso-hansi-font-family:Arial'>使用正确的</span><span lang=EN-US>STL</span><span
style='font-family:宋体;mso-ascii-font-family:Arial;mso-hansi-font-family:Arial'>查找算法。</span></h3>
<p class=MsoNormal><span lang=EN-US><o:p> </o:p></span></p>
<p class=MsoNormal><b style='mso-bidi-font-weight:normal'><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>摘要</span></b></p>
<p class=MsoNormal><span lang=EN-US><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>查找“不多不少”——正确的查找可能是</span><span
lang=EN-US>STL</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>（比光速要慢），即便不是的话，它也已经相当快了：本条适用于在一个区间内查找一个特定的值，或者该值在区间内的位置（如果存在的话）。要查找一个无序区间，请使用</span><span
lang=EN-US>find/find_if</span><span style='font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"'>或</span><span
lang=EN-US>count/count_if</span><span style='font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"'>。要查找一个有序区间，请使用</span><span
lang=EN-US>lower_bound</span><span style='font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"'>，</span><span
lang=EN-US>upper_bound</span><span style='font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"'>，</span><span
lang=EN-US>equal_range</span><span style='font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"'>，或（极少数情况下）</span><span
lang=EN-US>binary_search</span><span style='font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"'>。（虽然</span><span
lang=EN-US>binary_search</span><span style='font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"'>的名字听起来很通用，但它通常并不是正确的选择。）</span></p>
<p class=MsoNormal><span lang=EN-US><o:p> </o:p></span></p>
<p class=MsoNormal><b style='mso-bidi-font-weight:normal'><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>讨论</span><a name=ch75index09></a><a name=ch75index08></a><a
name=ch75lev1sec2></a><span lang=EN-US><o:p></o:p></span></b></p>
<p class=MsoNormal><span lang=EN-US><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>对无序区间来说，</span><span lang=EN-US>find/find_if</span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>和</span><span lang=EN-US>count/count_if</span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>可以分别在线性时间内告诉你某元素是否在某区间中，以及该元素在区间中的位置。请注意在一般情况下</span><span
lang=EN-US>find/find_if</span><span style='font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"'>的效率更高，因为它们可以在找到匹配的元素时终止查找。</span></p>
<p class=MsoNormal><span lang=EN-US><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>对有序区间来说，最好是使用四个二元查找算法，</span><span
lang=EN-US>binary_search</span><span style='font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"'>，</span><span
lang=EN-US>lower_bound</span><span style='font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"'>，</span><span
lang=EN-US>upper_bound</span><span style='font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"'>，以及</span><span
lang=EN-US>equal_range</span><span style='font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"'>，它们都占用对数时间。唉，虽然</span><span
lang=EN-US>binary_search</span><span style='font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"'>的名字很好，但它几乎没什么用，因为它只返回一个布尔值来表示有没有找到匹配的元素。通常你会用</span><span
lang=EN-US>lower_bound</span><span style='font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"'>或</span><span
lang=EN-US>upper_bound</span><span style='font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"'>——或</span><span
lang=EN-US>equal_range</span><span style='font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"'>，它可以同时给你</span><span
lang=EN-US>lower_bound</span><span style='font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"'>和</span><span
lang=EN-US>upper_bound</span><span style='font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"'>的结果（但并非以两倍的开销）。</span></p>
<p class=MsoNormal><span lang=EN-US><o:p> </o:p></span></p>
<p class=MsoNormal><span lang=EN-US>lower_bound</span><span style='font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>返回一个迭代器，指向第一个匹配（如果存在的话），或是它应该在的位置（如果不存在的话）；如果要在有序容器的正确位置插入新的值，那么后一种情况很有用。</span><span
lang=EN-US>upper_bound</span><span style='font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"'>返回一个迭代器，指向最后一个匹配的下一个元素（如果存在的话），这正是下一个等价元素（</span><span
lang=EN-US>equivalent element</span><span style='font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"'>）可以被添加的位置；如果要在有序容器的正确位置插入新的值，同时让等价元素保持它们在插入时的顺序不变，那么这是很有用的。</span></p>
<p class=MsoNormal><span lang=EN-US><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>对有序区间来说，最好是把</span><span lang=EN-US>p
= equal_range( first, last, value ); distance( p.first, p.second );</span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>当作</span><span lang=EN-US>count( first, last, value );</span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>的快速版本使用。</span></p>
<p class=MsoNormal><span lang=EN-US><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>如果正在查找一个有序容器，那么最好是使用算法的同名成员函数，而不要使用非成员函数。通常成员函数版本的效率更高，其中包括成员函数版本的</span><span
lang=EN-US>count</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>可以在对数时间内完成（因此没有必要再先后调用</span><span
lang=EN-US>equal_range</span><span style='font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"'>和</span><span
lang=EN-US>distance</span><span style='font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"'>来代替成员函数</span><span
lang=EN-US>count</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>，对非成员函数</span><span lang=EN-US>count</span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>而言这是有必要的）。</span></p>
</div>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -