📄 item_084.htm
字号:
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>84. </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></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>parameter-binder</span><span style='font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"'>和简单的函数对象（例如：</span><span
lang=EN-US>bind2nd</span><span style='font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"'>，</span><span
lang=EN-US>plus</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>）拼凑到一起，这样通常会降低清晰性。另外还可以试试</span><span
lang=EN-US>[Boost]</span><span style='font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"'>的</span><span
lang=EN-US>Lambda</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>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>STL</span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>的程序趋向于有更少的显式的循环，低层的无语义的循环被更高层的，定义得更好的抽象操作替代，这些操作可以传达更多的语义信息。与“处理每个元素”的基于循环的（不理智的）思路相比，最好是转向</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>Observer</span><span style='font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"'>”。与此类似，我们说“</span><span
lang=EN-US>Bridge</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>”，“</span><span lang=EN-US>Factory</span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>”，以及“</span><span lang=EN-US>Visitor</span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>”。我们共有的模式词汇表提升了讨论的层次，效率，以及正确性。有了算法，我们同样不说“对某区间中的每个元素执行某操作，然后把结果写到某处”，我们说</span><span
lang=EN-US>transform</span><span style='font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"'>。与此类似，我们说</span><span
lang=EN-US>for_each</span><span style='font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"'>，</span> <span
lang=EN-US>replace_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>partition</span><span style='font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"'>。算法和设计模式一样，本身就是文档。在提供与循环的目的有关的内在语义信息方面，赤裸裸的</span><span
lang=EN-US>for</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>和</span><span lang=EN-US>while</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>83</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>和</span><span lang=EN-US>99</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>[Sutter00]</span><span style='font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"'>和</span><span
lang=EN-US>[Meyers01]</span><span style='font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"'>）。它们会避免一些次要，却不必要的的低效处理，比如重复计算</span><span
lang=EN-US>container.end()</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>STL</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>[Boost]</span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>的</span><span lang=EN-US>lambda</span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>函数。</span><span lang=EN-US>Lambda</span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>函数是用来解决算法的最大缺点，即可读性，的重要工具：它们会替你编写函数对象，把实际的代码留在调用点（</span><span
lang=EN-US>call point</span><span style='font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"'>）。没有</span><span
lang=EN-US>lambda</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>函数，你的选择要么是使用函数对象（然而即使是一个简单的循环体也得放在另一个单独的地方，这样就远离了调用点），要么是使用标准的</span><span
lang=EN-US>binder</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>和函数对象，比如</span><span lang=EN-US>bind2nd</span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>和</span><span lang=EN-US>plus</span><span style='font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>（这些在使用时既冗长，又容易混淆，也很难结合在一起，因为一些基本操作如</span><span
lang=EN-US>compose</span><span style='font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"'>并不是标准的一部分；不过一定要好好看一下</span><span
lang=EN-US>[C++TR104] bind</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></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>[Meyers01]</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>Example 1: Transforming a deque. After
working through several incorrect iterations that ran afoul of iterator
invalidation issues (e.g., see Item 83), we finally come up with the following
correct handwritten loop for adding 41 to every element of data, an array of
doubles, and placing the result at the beginning of d, a deque<double>:</span></p>
<p class=MsoNormal><i style='mso-bidi-font-style:normal'><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>示例</span><span lang=EN-US>1</span></i><i style='mso-bidi-font-style:
normal'><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>：变换一个</span><span lang=EN-US>deque</span></i><i
style='mso-bidi-font-style:normal'><span style='font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"'>。</span></i><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>经过数次与无效迭代器问题的纠缠（例如：参见第</span><span lang=EN-US>83</span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>条），我们最后得到了以下手工编写的正确循环，用来给</span><span lang=EN-US>data</span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>的每个元素加</span><span lang=EN-US>41</span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>，</span><span lang=EN-US>data</span><span style='font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>是一个</span><span
lang=EN-US>double</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>的数组，然后把结果放在</span><span lang=EN-US>deque<double>
d</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 style='margin-left:36.0pt'><span lang=EN-US>deque<double>::iterator
current = d.begin();</span></p>
<p class=MsoNormal style='margin-left:36.0pt'><span lang=EN-US><o:p> </o:p></span></p>
<p class=MsoNormal style='margin-left:36.0pt'><span lang=EN-US>for( size_t i =
0; i < max; ++i ) {</span></p>
<p class=MsoNormal style='margin-left:36.0pt;tab-stops:270.0pt'><span
lang=EN-US><span style='mso-spacerun:yes'> </span>current = d.insert(
current, data[i] + 41 );<span style='mso-tab-count:1'> </span><i
style='mso-bidi-font-style:normal'>// </i></span><i style='mso-bidi-font-style:
normal'><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>为了保证</span><span lang=EN-US>current</span></i><i
style='mso-bidi-font-style:normal'><span style='font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"'>是有效的，</span><span
lang=EN-US><o:p></o:p></span></i></p>
<p class=MsoNormal style='margin-left:36.0pt;tab-stops:270.0pt'><i
style='mso-bidi-font-style:normal'><span lang=EN-US><span style='mso-tab-count:
1'> </span>//
</span></i><i style='mso-bidi-font-style:normal'><span style='font-family:宋体;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>必须非常小心</span><span
lang=EN-US>…</span></i></p>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -