《Effective STL》

haoji

解释了当不是这样时，事情是如何被破坏的。）他们假设operator+是加法（除了string，但是使用“+”表示
字符串的连接已经有悠久的历史了），operator-是减法，operator==作比较。而且他们假设使用less等价于使
用operator<。
operator<不仅是实现less的默认方式，它还是程序员希望less做的。让less做除operator<以外的事情是对程序员
预期的无故破坏。它与所被称为“最小惊讶的原则”相反。它是冷淡的。它是低劣的。它是坏的。你不该那
么做。
特别是当没有理由时。在STL中没有一个用到less的地方你不能指定一个不同的比较类型。回到我们原先以最
高速度排序的multiset<Widget>的例子，我们要得到希望的结果所需的所有事情就是建立一个叫做除了less以
外的几乎任何名字的仿函数类来对我们感兴趣的东西进行比较。嗨，这里有一个例子：
struct MaxSpeedCompare:
public binary_function<Widget, Widget, bool> {
bool operator()(const Widget& lhs, const Widget& rhs) const
{
return lhs.maxSpeed() < rhs.maxSpeed();
}
};
要创造我们的multiset，我们使用MaxSpeedCompare作为比较类型，因此避免了默认比较类型的使用（当然也
就是less<Widget>）：
multiset<Widget, MaxSpeedCompare> widgets;
这条代码确切地说出了它的意思。它建立了一个Widget的multiset，按照仿函数类MaxSpeedCompare所定义方
法排序。
对比这个：
multiset<Widget> widgets;
这个表示widgets是一个以默认方式排序的Widget的multiset。在技术上，那表示它使用了less<Widget>，但是实
际上每人都要假设那真的意味着它是按operator<来排序。
不要通过把less的定义当儿戏来误导那些程序员。如果你使用less（明确或者隐含），保证它表示operator<。
如果你想要使用一些其他标准排序对象，建立一个特殊的不叫做less的仿函数类。它真的很简单。

haoji

Center of STL Study
——最优秀的STL学习网站
使用STL编程
总结由容器、迭代器、算法和函数对象组成的STL是个惯例，但使用STL编程远不止那些。运用STL编程要知
道什么时候使用循环，什么时候使用算法，什么时候使用容器成员函数。要知道equal_range什么时候是比
lower_bound更好的搜索方式，要知道lower_bound什么时候比find更优越，要知道find什么时候击败
equal_range。要知道怎么通过用仿函数替代做同一件事的函数以改进算法性能。要知道怎么避免不可移植或
不能理解的代码。甚至要知道怎么读懂用上千个字符表示的编译器错误信息。要知道STL文档、STL扩展甚至
完整的STL实现的因特网资源。
是的，使用STL编程需要知道很多东西。本章将给你很多你需要的这些知识。

haoji

Center of STL Study
——最优秀的STL学习网站
条款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(),

haoji

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它们，并努力编码使得绝大部分编译器都可以通过将计算结果提到循环外
（译注：频度优化的一种）来避免重复计算。然而，经验表明，这样的实现不是总可以成功的，而且当不成
功时，对重复计算的避免足以让算法比手写的循环具有性能优势。
但这只是影响效率的次要因素。第一个主要影响因素是库的实现者可以利用他们知道容器的具体实现的优

haoji

势，用库的使用者无法采用的方式来优化遍历。比如，在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 + 41); // 在d的前端插入data+41
} // 这段代码有一个bug！

haoji

这可以执行，只要你能满意于插入的元素于在data中对应的元素是反序的。因为每次的插入点都是d.begin()，
最后一个被插入的元素将位于deque的前端！
如果这不是你想要的（还是承认吧，它肯定不是），你可能想这样修改：
deque<double>::iterator insertLocation = d.begin(); // 记下d的
// 起始迭代器
for (size_t i = 0; i < numDoubles; ++i) { // 在insertLocation
d.insert(insertLocation++, data + 41); // 插入data+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 + 41); // 以保证迭代器有效
++insertLocation; // 然后递增它
}
这样的代码确实完成了你相要的功能，但回想一下费了多大劲才达到这一步！和调用算法transform对比一
下：
// 把所有元素从data拷贝到d的前端
// 每个增加上41
transform(data, data + numDoubles,
inserter(d, d.begin()),
bind2nd(plus<double>(), 41));

haoji

这个“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算法的等价版本。
我很希望故事就此结束，因为我认为这个收尾很有说服力的。唉，有句老话叫好事多磨。算法的名字比光溜

haoji

溜的循环有意义多了，这是事实，但使用循环更能让人明白加诸于迭代器上的操作。举例来说，假设想要找
出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是否在保存的值之间
{

haoji

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(),

haoji

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]