条款43：尽量用算法调用代替手写循环

优质

小牛编辑

118浏览

2023-12-01

条款43：尽量用算法调用代替手写循环

每个算法接受至少一对用来指示将被操作的对象区间的迭代器。比如，min_element可以找出此区间中的最小的值，而accumulate则对区间内的元素作某种形式的整体求和运算（参见条款37），partition将区间内的元素分割为满足和不满足某判决条件的两个部分（参见条款31）。当算法被执行时，它们必须检查指示给它的区间中的每个元素，并且是按你所期望的方式进行的：从区间的起始点循还到结束点。有一些算法，比如find和find_if，可能在遍历完成前就返回了，但即使是这些算法，内部都包含一个循环。毕竟，即使是find和find_if也必须在查看过了每个元素后，才能断定它们所寻找的元素在不在此区间内。

所以，算法内部是一个循环。此外，STL算法的广泛涉及面意味着很多你本来要用循环来实现的任务，现在可以改用算法来实现了。比如，如果你有一个支持重画的Widget类：

class Widget {
public:
  ...
  void redraw() const;
  ...
};

并且，你想重画一个list中的所有Widget对象，你可能会这样使用这样一个循环：

list<Widget> lw;
...
for (list<Widget>::iterator i = 
		lw.begin();
		i != lw.end(); ++i) {
	i->redraw();
}

但是你也可以用for_each算法来完成：

for_each(lw.begin(), lw.end(),
	mem_fun_ref(&Widget::redraw));

对许多C++程序员而言，使用循环比调用算法的想法自然多了，并且读循环比弄懂mem_fun_ref的意义和取Widget::redraw的地址要舒服多了。但是，本条款将说明调用算法更可取。事实上，本条款将证明调用算法通常比手写的循环更优越。为什么？

有三个理由：

效率：算法通常比程序员产生的循环更高效。
正确性：写循环时比调用算法更容易产生错误。
可维护性：算法通常使代码比相应的显式循环更干净、更直观。

本条款的余下部分将对此予以例证。

从效率方面看，算法在三个方面可以打败显式循环，两个主要的，一个次要的。次要的包括消除了多余的计算。回头看一下我们刚才写的循环：

for (list<Widget>::iterator i = 
		lw.begin();
		i != lw.end();
		++i) {
	i->redraw();
}

我已经加亮了循环终止测试语句，以强调每次循环，i都要与lw.end()作检查。也就是说，每次的循环，都要调用函数list::end。但我们不需要调用end()一次以上的，因为我们不准备修改这个list，end调用一次就够了。而我们转过来看一下算法调用，就可以看到只对end作了正确的求值次数：

for_each(lw.begin(), lw.end(),		// 调用lw.end()求值
         mem_fun_ref(&Widget::redraw));	// 只有一次

公平的说，STL的实现者知道begin和end（以及类似的函数，比如size）用得很频繁，所以他们尽可能把它们实现得最高效。几乎肯定会inline它们，并努力编码使得绝大部分编译器都可以通过将计算结果提到循环外（译注：频度优化的一种）来避免重复计算。然而，经验表明，这样的实现不是总可以成功的，而且当不成功时，对重复计算的避免足以让算法比手写的循环具有性能优势。

但这只是影响效率的次要因素。第一个主要影响因素是库的实现者可以利用他们知道容器的具体实现的优势，用库的使用者无法采用的方式来优化遍历。比如，在deque中的对象通常存储在（内部的）一个或多个固定大小的数组上。基于指针的遍历比基于迭代器的遍历更快，但只有库的实现者可以使用基于指针的遍历，因为只有他们知道内部数组的大小以及如何从一个数组移向下一个。一些STL容器和算法的实现版本将它们的deque的内部数据结构引入了account，而且已经知道，这样的实现比“通常”的实现快20%。

这点不是说STL实现这为deque（或者其他特定的容器类型）做了优化，而是实现者对于他们的实现比你知道得更多，而且他们可以把这些知识用在算法实现上。如果你避开了算法调用，而只喜欢自己写循环，你就相当于放弃了得到任何他们所提供的特定实现优点的机会。

第二个主要的效率因素是，除了最微不足道的STL算法，所有的STL算法使用的计算机科学都比一般的C++程序员能拿得出来的算法复杂——有时候会复杂得多。几乎不可能被打败的sort及其同族算法（比如，stable_sort()，nth_element()等，参见条款31）；适用于有序区间的搜索算法（比如，binary_search，lower_bound等，参见条款34和35）也一样好；就算是很平凡的任务，比如从连续内存容器中除去一些对象，使用erase-remove惯用法都比绝大多数程序员写的循环更高效（参见条款9）。

如果算法的效率因素说服不了你，也许你更愿意接受基于正确性的考虑。写循环时，比较麻烦的事在于确保所使用的迭代器（a）有效，并且（b）指向你所期望的地方。举例来说，假设有一个数组（大概是因为遗留的C API——参见条款16），你想获得其中的每一个元素，把它加上41，然后将结果插入一个deque的前端。用循环，你可能这样写：（这是来自条款16的一个例子的变体）：

// 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！

这可以执行，只要你能满意于插入的元素于在data中对应的元素是反序的。因为每次的插入点都是d.begin()，最后一个被插入的元素将位于deque的前端！

如果这不是你想要的（还是承认吧，它肯定不是），你可能想这样修改：

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！

看起来象双赢，它不只是递增了指示插入位置的，还避免了循环每次对begin的调用；这就像我们前面讨论过的一样，消除了影响效率的次要因素。唉，这种方法陷入了另外一个的问题中：它导致了未定义的结果。每次调用deque::insert，都将导致所有指向deque内部的迭代器无效，包括上面的insertLocation。在第一次调用insert后，insertLocation就无效了，后面的循环迭代器可以直接让人发疯。

注意到这个问题后（可能得到了STLport调试模式的帮助，在条款50描述），你可能会这样做：

deque<double>::iterator insertLocation =
	d.begin();						// 同上

for (size_t i = 0; i < numDoubles; ++i) {			// 每次调用insert后
	insertLocation =					// 都更新insertLocation
		d.insert(insertLocation, data[i] + 41);		// 以保证迭代器有效
	++insertLocation;					// 然后递增它
}

这样的代码确实完成了你相要的功能，但回想一下费了多大劲才达到这一步！和调用算法transform对比一下：

// 把所有元素从data拷贝到d的前端
// 每个增加上41
transform(data, data + numDoubles,
          inserter(d, d.begin()),
          bind2nd(plus<double>(), 41));

这个“bind2nd(plus<double>(), 41)”可能会花上一些时间才能看明白（尤其是如果不常用STL的bind族的话），但是与迭代器相关的唯一烦扰就是指出源区间的起始点和结束点（而这从不会成为问题），并确保在目的区间的起始点上使用inserter（参见条款30）。实际上，为源区间和目的区间指出正确的初始迭代器通常都很容易，至少比确保循环体没有于无意中将需要持续使用的迭代器变得无效要容易得多。

难以正确实现循环的情况太多了，这个例子只是比较有代表性。因为在使用迭代器前，必须时刻关注它们是否被不正确地操纵或变得无效。要看忽略迭代器失效会导致的麻烦的另一个例子，转到条款9，那里描述了手写循环和调用erase只见的微妙之处。假设使用无效的迭代器会导致未定义的行为，又假设未定义的行为在开发和测试期间会有表现出令人讨厌的行为，为什么要冒不必要的危险？将迭代器扔给算法，让它们去考虑操纵迭代器时的各种诡异行为吧。

我已经解释了算法为什么可以比手写的循环更高效，也描述了为什么循环将艰难地穿行于与迭代器相关的荆棘丛中，而算法正避免了这一点。运气好的话，你现在已是一个算法的信徒了。然而运气是变化无常的，在我休息前，我想更确定些。因此，让我们继续行进到代码清晰性的议题。毕竟，最好软件应该是那些最清晰的、最容易懂的、能容易增强、维护和适用于新的环境的软件。虽然循环比较熟悉，但算法在这个长期的竞争中具有优势。

关键在于已知词汇的力量。在STL中约有70个算法的名字——总共超过100个不同的函数模板，每个重载都算一个。每个算法都完成一些精心定义的任务，而且有理由认为专业的C++程序员知道（或应该去看一下）每个算法都完成了什么。因此，当程序员调用transform时，他们认为对区间内的每个元素都施加了某个函数，而结果将被写到另外一个地方。当程序员调用replace_if时，他（她）知道区间内满足判定条件的对象都将被修改。当调用partition时，她（他）明白区间中所有满足判定条件的对象将被聚集在一起（参见条款31）。STL算法的名字传达了大量的语义信息，这使得它们比随机的循环清晰多了。

当你看见for、while或do的时候，你能知道的只是这是一种循环。如果要获得哪怕一点关于这个循环作了什么的信息，你就得审视它。算法则不用。一旦你看见调用一个算法，独一无二的名字勾勒出了它所作所为的轮廓。当然要了解它真正做了什么，你必须检查传给算法的实参，但这一般比去研究一个普通的循环结构要轻松得多。

明摆着，算法的名字暗示了其功能。“for”、“while”和“do”却做不到这一点。事实上，这一点对标准C语言或C++语言运行库的所有组件都成立。毫无疑问地，你能自己实现strlen， memset或bsearch，但你不会这么做。为什么不会？因为（1）已经有人帮你实现了它们，因此没必要你自己再做一遍；（2）名字是标准的，因此，每个人都知道它们做什么用的；和（3）你猜测程序库的实现者知道一些你不知道的关于效率方面的技巧，因此你不愿意错过熟练的程序库实现者可能能提供的优化。正如你不会去写strlen等函数的自己的版本，同样没道理用循环来实现出已存在的STL算法的等价版本。

我很希望故事就此结束，因为我认为这个收尾很有说服力的。唉，有句老话叫好事多磨。算法的名字比光溜溜的循环有意义多了，这是事实，但使用循环更能让人明白加诸于迭代器上的操作。举例来说，假设想要找出vector中第一个比x大又比y小的元素。这是使用循环的实现：

vector<int> v;
int x, y;
...
vector<int>::iterator i = v.begin();	 // 从v.begin()开始迭代，直到
for( ; i != v.end(); ++i) {			// 找到了适当的值或
  if (*i > x && *i < y) break;	// 到v.end()了
}
...						// i现在指向那个值或等于v.end()

将同样的逻辑传给find_if是可能的，但是需要使用一个非标准函数对象适配器，比如SGI的compose2^[1]（参见条款50）：

vector<int>::iterator i =
  find_if(v.begin(), v.end(),			// 查找第一个find the first value val
       compose2(logical_and<bool>(),	// 使val > x
           bind2nd(greater<int>(), x),	// 和val < y都
           bind2nd(less<int>(), y)));	// 为真的值val

即使没使用非标准组件，许多程序员也会反对说它远不及循环清晰，我也不得不同意这个观点（参见条款47）。

find_if的调用可以不显得那么复杂，只要将测试的逻辑封装入一个独立的仿函数类中：

template<typename T>
class BetweenValues: 
public unary_function<T, bool> {		// 参见条款40 
public: 
	BetweenValues(const T& lowValue, 
		const T& highValue)			// 使构造函数保存上下界
		:lowVal(lowValue), highVal(highValue)
	{} 
	bool operator()(const T& val) const	//返回val是否在保存的值之间 
	{
		return val > lowVal && val < highVal;
	}

private: 
	T lowVal; 
	T highVal; 
}; 
...
vector<int>::iterator i = find_if(v.begin(), v.end(), 
				BetweenValues<int>(x, y));

但这种方法有它自己的缺陷。首先，创建BetweenValues模板比写循环体要多出很多工作。就光数一下行数。循环体：1行；BetweenValues模板：24行。太不成比例了。第二，find_if正在找寻是什么的细节被从调用上完全割裂出去了，要想真的明白对find_if的这个调用，还必须得查看BetweenValues的定义，但BetweenValues一定被定义在调用find_if的函数之外。如果试图将BetweenValues声明在这个函数的调用内部，就像这样，

{ // 函数开始

	...
	template <typename T>
	class BetweenValues:
		public std::unary_function<T, bool> { ... };
	vector<int>::iterator i =
		find_if(v.begin(), v.end(),
			BetweenValues<int>(x, y));
	...
} // 函数结束

你会发现这不能编译，因为模板不能声明在函数内部。如果试图把BetweenValues做成一个类而不是模板来避开这个限制：

{ // 函数开始
  ...
  class BetweenValues:
    public std::unary_function<int, bool> { ... };
  vector<int> iterator i =
    find_if(v.begin(), v.end(),
            BetweenValues(x, y));
  ...
} // 函数结束

你会发现仍然运气不佳，因为定义在函数内部的类是个局部类，而局部类不能绑定在模板的类型实参上（比如find_if所需要的仿函数类型）。很失望吧，仿函数类和仿函数类模板不能被定义在函数内部，不管它实现起来有多方便。

在算法调用与手写循环正在进行的较量中，关于代码清晰度的底线是：这完全取决于你想在循环里做的是什么。如果你要做的是算法已经提供了的，或者非常接近于它提供的，调用泛型算法更清晰。如果循环里要做的事非常简单，但调用算法时却需要使用绑定和适配器或者需要独立的仿函数类，你恐怕还是写循环比较好。最后，如果你在循环里做的事相当长或相当复杂，天平再次倾向于算法。因为长的、复杂的通常总应该封装入独立的函数。只要将循环体一封装入独立函数，你几乎总能找到方法将这个函数传给一个算法（通常是for_each），以使得最终代码直截了当。

如果你同意算法调用通常优于手写循环这个条款，并且如果你也同意条款5的区间成员函数优于循环调用单元素的成员函数，一个有趣的结论出现了：使用STL容器的C++精致程序中的循环比不使用STL的等价程序少多了。这是好事。只要能用高层次的术语——如insert、find和for_each，取代了低层次的词汇——如for、while和do，我们就提升了软件的抽象层次，并因此使得它更容易实现、文档化、增强和维护。

^[1]要了解更多关于compose2的信息，请参考SGI的STL网站[21]或Matt Austern的书《Generic Programming and the STL》（Addison-Wesley，1999）[4]