📄 item_43.html
字号:
<?xml version="1.0" encoding="gb2312"?><!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><title>条款43：尽量用算法调用代替手写循环</title><meta http-equiv="Content-Type" content="text/html; charset=gb2312" /><link href="css/all.css" rel="stylesheet" type="text/css" /><link rel="stylesheet" href="http://stl.winterxy.com/styles-site.css" type="text/css" /><link rel="alternate" type="application/rss+xml" title="RSS" href="http://stl.winterxy.com/index.rdf" /><link rel="EditURI" type="application/rsd+xml" title="RSD" href="http://stl.winterxy.com/rsd.xml" /></head><body><div id="banner"><h1><a href="http://stl.winterxy.com/" accesskey="1">Center of STL Study</a> </h1><span class="description">——最优秀的STL学习网站<script language="javascript" src="http://www.winterxy.com/cgi-bin/js/webstats.js"></script></span></div><h2>条款43：尽量用算法调用代替手写循环</h2> <p>每个算法接受至少一对用来指示将被操作的对象区间的迭代器。比如，min_element可以找出此区间中的最小的值，而accumulate则对区间内的元素作某种形式的整体求和运算（参见<a href="item_37.html">条款37</a>），partition将区间内的元素分割为满足和不满足某判决条件的两个部分（参见<a href="item_31.html">条款31</a>）。当算法被执行时，它们必须检查指示给它的区间中的每个元素，并且是按你所期望的方式进行的：从区间的起始点循还到结束点。有一些算法，比如find和find_if，可能在遍历完成前就返回了，但即使是这些算法，内部都包含一个循环。毕竟，即使是find和find_if也必须在查看过了每个元素后，才能断定它们所寻找的元素在不在此区间内。</p><p>所以，算法内部是一个循环。此外，STL算法的广泛涉及面意味着很多你本来要用循环来实现的任务，现在可以改用算法来实现了。比如，如果你有一个支持重画的Widget类：</p><pre>class Widget {public: ... void redraw() const; ...};</pre> <p>并且，你想重画一个list中的所有Widget对象，你可能会这样使用这样一个循环：</p><pre>list<Widget> lw;...for (list<Widget>::iterator i = lw.begin(); i != lw.end(); ++i) { i->redraw();}</pre> <p>但是你也可以用for_each算法来完成：</p> <pre>for_each(lw.begin(), lw.end(), mem_fun_ref(&Widget::redraw));</pre> <p>对许多C++程序员而言，使用循环比调用算法的想法自然多了，并且读循环比弄懂mem_fun_ref的意义和取Widget::redraw的地址要舒服多了。但是，本条款将说明调用算法更可取。事实上，本条款将证明调用算法通常比手写的循环更优越。为什么？</p> <p>有三个理由：</p> <ul> <li><strong>效率：</strong>算法通常比程序员产生的循环更高效。</li> <li><strong>正确性：</strong>写循环时比调用算法更容易产生错误。</li> <li><strong>可维护性：</strong>算法通常使代码比相应的显式循环更干净、更直观。</li> </ul> <p>本条款的余下部分将对此予以例证。</p> <p>从效率方面看，算法在三个方面可以打败显式循环，两个主要的，一个次要的。次要的包括消除了多余的计算。回头看一下我们刚才写的循环：</p> <pre>for (list<Widget>::iterator i = lw.begin(); <span class="highlight">i != lw.end();</span> ++i) { i->redraw();}</pre> <p>我已经加亮了循环终止测试语句，以强调每次循环，i都要与lw.end()作检查。也就是说，每次的循环，都要调用函数list::end。但我们不需要调用end()一次以上的，因为我们不准备修改这个list，end调用一次就够了。而我们转过来看一下算法调用，就可以看到只对end作了正确的求值次数：</p><pre>for_each(lw.begin(), lw.end(), // 调用lw.end()求值 mem_fun_ref(&Widget::redraw)); // 只有一次 </pre> <p>公平的说，STL的实现者知道begin和end（以及类似的函数，比如size）用得很频繁，所以他们尽可能把它们实现得最高效。几乎肯定会inline它们，并努力编码使得绝大部分编译器都可以通过将计算结果提到循环外<strong>（译注：频度优化的一种）</strong>来避免重复计算。然而，经验表明，这样的实现不是总可以成功的，而且当不成功时，对重复计算的避免足以让算法比手写的循环具有性能优势。</p> <p>但这只是影响效率的次要因素。第一个主要影响因素是库的实现者可以利用他们知道容器的具体实现的优势，用库的使用者无法采用的方式来优化遍历。比如，在deque中的对象通常存储在（内部的）一个或多个固定大小的数组上。基于指针的遍历比基于迭代器的遍历更快，但只有库的实现者可以使用基于指针的遍历，因为只有他们知道内部数组的大小以及如何从一个数组移向下一个。一些STL容器和算法的实现版本将它们的deque的内部数据结构引入了account，而且已经知道，这样的实现比“通常”的实现快20%。</p><p>这点不是说STL实现这为deque（或者其他特定的容器类型）做了优化，而是实现者对于他们的实现比你知道得更多，而且他们可以把这些知识用在算法实现上。如果你避开了算法调用，而只喜欢自己写循环，你就相当于放弃了得到任何他们所提供的特定实现优点的机会。</p><p>第二个主要的效率因素是，除了最微不足道的STL算法，所有的STL算法使用的计算机科学都比一般的C++程序员能拿得出来的算法复杂——有时候会复杂得多。几乎不可能被打败的sort及其同族算法（比如，stable_sort()，nth_element()等，参见<a href="item_31.html">条款31</a>）；适用于有序区间的搜索算法（比如，binary_search，lower_bound等，参见<a href="item_34.html">条款34</a>和<a href="item_35.html">35</a>）也一样好；就算是很平凡的任务，比如从连续内存容器中除去一些对象，使用erase-remove惯用法都比绝大多数程序员写的循环更高效（参见<a href="item_09.html">条款9</a>）。</p><p>如果算法的效率因素说服不了你，也许你更愿意接受基于正确性的考虑。写循环时，比较麻烦的事在于确保所使用的迭代器（a）有效，并且（b）指向你所期望的地方。举例来说，假设有一个数组（大概是因为遗留的C API——参见<a href="item_16.html">条款16</a>），你想获得其中的每一个元素，把它加上41，然后将结果插入一个deque的前端。用循环，你可能这样写：（这是来自<a href="item_16.html">条款16</a>的一个例子的变体）：</p> <pre>// C API：这个函数的参数是一个能放arraySize// 个double的数组的指针，// 函数向这个数组写入数据。它返回// 写入double的个数size_t fillArray(double *pArray, size_t arraySize);double data[maxNumDoubles]; // 建立本地数组， // 大小是最大可能的大小deque<double> d; // 建立deque，... // 把数据放进去size_t numDoubles = fillArray(data, maxNumDoubles); // 从API获取数组数据for (size_t i = 0; i < numDoubles; ++i) { // 对于每一个数据， d.insert(d.begin(), data[i] + 41); // 在d的前端插入data[i]+41} // 这段代码有一个bug！</pre> <p>这可以执行，只要你能满意于插入的元素于在data中对应的元素是反序的。因为每次的插入点都是d.begin()，最后一个被插入的元素将位于deque的前端！</p> <p>如果这不是你想要的（还是承认吧，它肯定不是），你可能想这样修改：</p> <pre>deque<double>::iterator insertLocation = d.begin(); // 记下d的 // 起始迭代器for (size_t i = 0; i < numDoubles; ++i) { // 在insertLocation d.insert(insertLocation++, data[i] + 41); // 插入data[i]+41，然后} // insertLocation递增； // 这段代码也有bug！</pre> ⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -