STL泛型算法vs.手写的循环
Scott Meyers
准备进行优化？别那么急。Scott正试图让你相信库函数比你自己写的更好。
-------------------------------------------------------------------------------
[这篇文章源自一本即将出版的书。S. Meyers，Effective STL:50 Specific Ways to Improve Your Use of the Standard Template Library，改自Item 26-28（WQ注，CUJ上原文如此，应为Item 43）。 2001 Addison-Wesley。 发行：permission of Pearson Education, Inc]
每个泛型算法接受至少一对选择子，以指示将被操作的元素区间。比如，min_element()寻找出此区间中的最小的值，而accumulate()则对区间内的元素作某种形式的整体求和运算，partition()将区间内的元素分割为满足和不满足某判决条件的两个部分。当泛型算法被执行时，它们必须检查指示给它的区间中的每个元素，并且是按你所期望的方式进行的：从区间的起始点循还到结束点。有一些泛型算法，比如find()和find_if()，可能在遍历完成前就返回了，但即使是这些泛型算法，内部都有着一个循环。毕竟，即使是find()和find_if()也必须在查看过了每个元素后，才能断定它们所寻找的元素不在此区间内。
所以，泛型算法内部是一个循环。此外，STL泛型算法涉及面广泛，这意味着很多你本来要用循环来实现的任务，现在可以改用泛型算法实现了。比如，有一个Widget类，它支持redraw()。
class Widget {
public:
...
void redraw() const;
...
};
并且，你想redraw一个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的地址要舒服多了。但是，这篇文章将说明调用泛型算法更可取。事实上，这篇文章将证明调用泛型算法通常比手写的循环更优越。为什么？
有三个理由:
l 效率：泛型算法通常比循环高效。
l 正确性: 写循环时比调用泛型算法更容易产生错误。
l 可维护性: 与相应的显式循环相比，泛型算法通常使代码更干净、更直观。
文章的以后部分将予以例证。
从效率方面看，泛型算法在3个方面打败了显式循环，两个主要因素，一个次要因素。次要因素是消除了多余的计算。回头看一下我们刚才写的循环：
for (list<Widget>::iterator i =
lw.begin();
i != lw.end();
++i) {
i->redraw();
}
我已经加亮了循环终止测试语句，以强调每次循环，i都要与lw.end()作检查。也就是说，每次的循环，都要调用函数list::end()。但我们不需要调用end()一次以上的，因为我们不准备修改这个list，对end()调用一次就够了。而我们转过来看一下泛型算法，就可以看到只对end()函数作了正确的求值次数：
// this call evaluates lw.end() exactly
// once
for_each(lw.begin(), lw.end(),
mem_fun_ref(&Widget::redraw));
凭心而论，STL的实现者知道begin()和end()(以及类似的函数，比如size())用得很频繁，所以尽可能地实现得最高效。几乎肯定会inline它们，并编码得绝大部分编译器都能避免重复计算（通过将计算结果外提（这种优化手段））。然而，经验表明，这不是总能成功的，而且当不成功时，对重复计算的避免足以让泛型算法比手写的循环具有性能优势。
但这只是影响性能的次要因素。第一个主要影响因素是：库的实现者可以利用他们知道容器的具体实现的优势，用库的使用者无法采用的方式来优化代码。比如，在deque中的元素通常存储在（内部的）一个或多个固定大小的数组上。基于指针的遍历比基于选择子的遍历更快，但只有库的实现者可以使用基于指针的遍历，因为只有他们知道内部数组的大小以及如何从一个数组移向下一个。有一些STL容器和泛型算法的实现版本特别考虑了它们的deque的内部数据结构，而且已经知道，这样的实现比“通常”的实现快20%。
第二个主要因素是，除了最微不足道的算法，所有的STL泛型算法使用的数学算法都比一般的C++程序员能拿得出来的算法更复杂，－－有时会复杂得多得多。不可能超越sort()及其同族泛型算法的(比如，stable_sort()，nth_element()等)；适用于已序区间的搜索算法(比如，binary_search()，lower_bound() 等)相当完美；就算是很平凡的任务，比如从vector、deque或数组中销毁元素，使用erase-remove惯用法都比绝大多数程序员写的循环更高效。
如果效率的因素说服不了你，也许你更愿意接受基于正确性的考虑。写循环时，比较麻烦的事在于确保所使用的选择子(a)有效，并且(b)指向你所期望的地方。举例来说，假设有一个数组，你想获得其中的每一个元素，在上面加41，然后将结果从前端插入一个deque。用循环，你可能这样写：
// C API: this function takes a pointer
// to an array of at most arraySize
// doubles and writes data to it. It
// returns the number of doubles written.
size_t fillArray(double *pArray, size_t arraySize);
// create local array of max possible size
double data[maxNumDoubles];
// create deque, put data into it
deque<double> d;
...
// get array data from API
size_t numDoubles =
fillArray(data, maxNumDoubles);
// for each i in data, insert data[i]+41
// at the front of d; this code has a bug!
for (size_t i = 0; i < numDoubles; ++i) {
d.insert(d.begin(), data[i] + 41);
}
这可以执行，只要你能满意于插入的元素是反序的。因为每次的插入点是d.begin()，最后一个被插入的元素将位于deque的前端！
如果这不是你想要的（还是承认吧，它肯定不是你想要的），你可能想这样修改：
// remember d’s begin iterator
deque<double>::iterator insertLocation = d.begin();
// insert data[i]+41 at insertLocation, then
// increment insertLocation; this code is also buggy!
for (size_t i = 0; i < numDoubles; ++i) {
d.insert(insertLocation++, data[i] + 41);
}
看起来象双赢，它不只是累加了指示插入位置的选择子，还避免了每次对begin()的调用（这消除了影响效率的次要因素）。唉，这种方法陷入了另外一个的问题中：它导致了“未定义”的结果。每次调用deque::insert()，都将导致所有指向deque内部的选择子无效，包括上面的insertLocation。在第一次调用insert()后，insertLocation就变得无效了，后面的循环可以产生任何行为（are allowed to head straight to looneyland）。
注意到这个问题后，你可能会这样做：
deque<double>::iterator insertLocation =
d.begin();
// update insertLocation each time
// insert is called to keep the iterator valid,
// then increment it
for (size_t i = 0; i < numDoubles; ++i) {
insertLocation =
d.insert(insertLocation, data[i] + 41);
++insertLocation;
}
这样的代码确实完成了你相要的功能，但回想一下费了多大劲才达到这一步！和调用泛型算法transform()对比一下：
// copy all elements from data to the
// front of d, adding 41 to each
transform(data, data + numDoubles,
inserter(d, d.begin()),
bind2nd(plus<int>(), 41));
这个“bind2nd(plus<int>(), 41)”可能会花上一些时间才能看明白(尤其是如果不常用STL的bind族的话)，但是与选择子相关的唯有烦扰就是指出源区间的起始点和结束点(而这从不会成为问题)，并确保在目的区间的起始点上使用inserter。实际经验表明，为源区间和目的区间指出正确的初始选择子通常都很容易，至少比确保循环体没有于无意中将需要持续使用的选择子变得无效要容易得多。
因为在使用选择子前，必须时刻关注它们是否被不正确地操纵或变得无效，难以正确实现循环的情况太多了，这个例子只是比较有代表性。假设使用无效的选择子会导致“未定义”的行为，又假设“未定义”的行为在开发和测试期间 has a nasty habit of failing to show itself ，为什么要冒不必要的危险？将选择子扔给泛型算法，让它们去考虑操纵选择子时的各种诡异行为吧。
我已经解释了泛型算法为什么可以比手写的循环更高效，也描述了为什么循环将艰难地穿行于与选择子相关的荆棘丛中，而泛型算法正避免了这一点。运气好的话，你现在已是一个泛型算法的信徒了。然而运气是不足信的，在我休息前，我想更确保些。因此，让我们继续行进到代码清晰性的议题。最后，最好软件是那些最清晰的软件、最好懂的软件、能最被乐意于增强、维护和适用于新的环境的软件。虽然习惯于循环，但泛型算法在这个长期的竞争中具有优势。
关键在于具名词汇的力量。在STL中约有70个泛型算法的名字，总共超过100个不同的函数模板（每个重载都算一个）。每个泛型算法都完成一些精心定义的任务，而且有理由认为专业的C++程序员知道（或应该去看一下）每个泛型算法都完成了什么。因此，当程序员调用transform()时，他们认为对区间内的每个元素都施加了某个函数，而结果将被写到另外一个地方。当程序员调用replace_if()时，他（她）知道区间内满足判定条件的对象都将被修改。当调用partition()时，他（她）明白所有满足判定条件的对象将被聚集在一起。STL泛型算法的名字传达了大量的语义信息，这使得它们比随意的循环清晰多了。
明摆着，泛型算法的名字暗示了其功能。“for”、“while”和“do”却做不到这一点。事实上，这一点对标准C语言或C++语言运行库的所有部件都成立。毫无疑问地，你能自己实现strlen()， memset()或bsearch()，但你不会这么做。为什么不会？因为(1)已经有人帮你实现了它们，因此没必要你自己再做一遍；(2) 名字是标准的，因此，每个人都知道它们做什么用的；和(3)你猜测程序库的实现者知道一些你不知道的关于效率方面的技巧，因此你不愿意错过熟练的程序库实现者可能能提供的优化。正如你不会去写strlen()等函数的自己的版本，同样没道理用循环来实现出已存在的STL泛型算法的等价版本。
我很希望故事就此结束，因为我认为这个收尾很有说服力的。唉，好事多磨（this is a tale that refuses to go gentle into that good night）。 泛型算法的名字比光溜溜的循环有意义多了，这是事实，但使用循环更能让人明白加诸于选择子上的操作。举例来说，假设想要找出vector中第一个比x大又比y小的元素。这是使用循环的实现：
vector<int> v;
int x, y;
...
// iterate from v.begin() until an
// appropriate value is found or
// v.end() is reached
vector<int>::iterator i = v.begin();
for( ; i != v.end(); ++i) {
if (*i > x && *i < y) break;
}
// i now points to the value
// or is the same as v.end()
将同样的逻辑传给find_if()是可能的，但是需要使用一个非标的functor，比如SGI的compose2[注1]：
// find the first value val where the
// "and" of val > x and val < y is true
vector<int> iterator i =
find_if(v.begin(), v.end(),
compose2(logical_and<bool>(),
bind2nd(greater<int>(), x),
bind2nd(less<int>(), y)));
即使没使用非标的元件，许多程序员也会反对说它远不及循环清晰，我也不得不同意这个观点。
find_if()的调用可以不显得那么复杂，只要将测试的逻辑封装入一个独立的functor(也就是申明了operator()成员函数的类)：
template<typename T>
class BetweenValues:
public std::unary_function<T, bool> {
public:
// have the ctor save the
// values to be between
BetweenValues(const T& lowValue,
const T& highValue)
: lowVal(lowValue), highVal(highValue)
{}
// return whether val is
// between the saved values
bool operator()(const T& val) const
{
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申明在这个函数内部，就像这样，
// beginning of function
{
...
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));
...
}
// end of function
你会发现编译不通过，因为模板不能申明在函数内部。如果试图用类代替模板而避开这个问题，
// beginning of function
{
...
class BetweenValues:
public std::unary_function<int, bool> { ... };
vector<int> iterator i =
find_if(v.begin(), v.end(),
BetweenValues(x, y));
...
}
// end of function
你会发现仍然运气不佳，因为定义在函数内部的类是个局部类，而局部类不能绑定在模板的类型参数上(比如find_if()所需要的functor 类型)。很失望吧，functor类和functor类不能被定义在函数内部，不管它实现起来有多方便。
在泛型函数与手写循环的长久较量中，关于代码清晰度的底线是：这完全取决于你想在循环里做的是什么。如果你要做的是泛型算法已经提供了的，或者非常接近于它提供的，调用泛型算法更清晰。如果循环里要做的事非常简单，但调用泛型算法时却要使用bind族和adapter或者独立的functor类，你恐怕还是写循环比较好。最后，如果你在循环里做的事相当长或相当复杂，天平再次倾向于泛型算法。长的、复杂的通常总应该封装入独立的函数。只要将循环体一封装入独立函数，你几乎总能找到方法将这个函数传给一个泛型算法(通常是 for_each())，以使得最终代码直截了当。
如果你同意调用泛型算法通常优于手写循环这个主题，并且，如果你也同意作用于某个区间的成员函数优于循环调用作用于单元素的成员函数[注2]，一个有趣的结论出现了：使用STL容器的C++精致程序中的循环比不使用STL的等价程序少多了。这是好事。只要能用高层次的术语（如insert()、find()和for_each()）取代了低层次的词汇（如for、while和do），我们就提升了软件的抽象层次，并因此使得它更容易实现、文档化、增强，和维护。
注和参考
[1] To learn more about compose2, consult the SGI STL website (<http://www.sgi.com/tech/stl/>) or Matt Austern’s book, Generic Programming and the STL (Addison-Wesley, 1999).
[2] Range member functions are container member functions such as insert, erase, and assign that take two iterators specifying a range to e.g., insert, erase, or assign. A single call to a range member is generally much more efficient than a hand-written loop that does the same thing. For details, consult Item 5 of Effective STL.
