《Effective STL》

haoji

Center of STL Study
——最优秀的STL学习网站
条款46：考虑使用函数对象代替函数作算法的参数
一个关于用高级语言编程的抱怨是抽象层次越高，产生的代码效率就越低。事实上，Alexander Stepanov
（STL的发明者）有一次作了一组小测试，试图测量出相对C，C++的“抽象惩罚”。其中，测试结果显示基
本上操作包含一个double的类产生的代码效率比对应的直接操作一个double的代码低。因此你可能会奇怪地
发现把STL函数对象——化装成函数的对象——传递给算法所产生的代码一般比传递真的函数高效。
比如，假设你需要以降序排序一个double的vector。最直接的STL方式是通过sort算法和greater<double>类型的
函数对象：
vector<double> v;
...
sort(v.begin(), v.end(), greater<double>());
如果你注意了抽象惩罚，你可能决定避开函数对象而使用真的函数，一个不光是真的，而且是内联的函数：
inline
bool doubleGreater(double d1, double d2)
{
return dl > d2;
}
...
sort(v.begin(), v.end(), doubleGreater);
有趣的是，如果你比较了两个sort调用（一个使用greater<double>，一个使用doubleGreater）的性能，你基本
上可以明确地知道使用greater<double>的那个更快。实际来说，我在四个不同的STL平台上测量了对一百万个
double的vector的两个sort调用，每个都设为针对速度优化，使用greater<double>的版本每次都比较快。最差的
情况下，快50%，最好的快了160%。抽象惩罚真多啊。
这个行为的解释很简单：内联。如果一个函数对象的operator()函数被声明为内联（不管显式地通过inline或者
隐式地通过定义在它的类定义中），编译器就可以获得那个函数的函数体，而且大部分编译器喜欢在调用算
法的模板实例化时内联那个函数。在上面的例子中，greater<double>:perator()是一个内联函数，所以编译器
在实例化sort时内联展开它。结果，sort没有包含一次函数调用，而且编译器可以对这个没有调用操作的代码

haoji

进行其他情况下不经常进行的优化。（内联和编译器优化之间交互的讨论，参见《Effective C++》的条款33和
Bulka与Mayhew的《Efficient C++》[10]的第8-10章。)
使用doubleGreater调用sort的情况则不同。要知道有什么不同，我们必须知道不可能把一个函数作为参数传给
另一个函数。当我们试图把一个函数作为参数时，编译器默默地把函数转化为一个指向那个函数的指针，而
那个指针是我们真正传递的。因此，这个调用
sort(v.begin(), v.end(), doubleGreater);
不是真的把doubleGreater传给sort，它传了一个doubleGreater的指针。当sort模板实例化时，这是产生函数的声
明：
void sort(vector<double>::iterator first, // 区间起点
vector<double>::iterator last, // 区间终点
bool (*comp)(double, double)); // 比较函数
因为comp是一个指向函数的指针，每次在sort中用到时，编译器产生一个间接函数调用——通过指针调用。
大部分编译器不会试图去内联通过函数指针调用的函数，甚至，正如本例中，那个函数已经声明为inline而且
这个优化看起来很直接。为什么不？可能因为编译器厂商从来没有觉得值得实现这个优化。你得稍微同情一
下编译器厂商。他们有很多需求，而他们不能做每一件事。你的需要并不能让他们实现那个优化。
把函数指针作为参数会抑制内联的事实解释了一个长期使用C的程序员经常发现却难以相信的现象：在速度
上，C++的sort实际上总是使C的qsort感到窘迫。当然，C++有函数、实例化的类模板和看起来很有趣的
operator()函数需要调用，而C只是进行简单的函数调用，但所有的C++“开销”都在编译期被吸收。在运行
期，sort内联调用它的比较函数（假设比较函数已经被声明为inline而且它的函数体在编译期可以得到）而
qsort通过一个指针调用它的比较函数。结果是sort运行得更快。在我的测试的一百万个double的vector上，它
快670%，但不要光相信我的话，亲自试试。很容易证实当比较函数对象和真的函数作为算法的参数时，那是
一个纯红利。
还有另一个使用函数对象代替函数作为算法参数的理由，而它与效率无关。它涉及到让你的程序可以编译。
对于任何理由，STL平台经常完全拒绝有效代码，即使编译器或库或两者都没问题。比如，一个广泛使用的
STL平台拒绝了下面（有效的）代码来从cout打印出set中每个字符串的长度：
set<string> s;
...
transform(s.begin(), s.end(),
ostream_iterator<string::size_type>(cout, "\n"),

haoji

mem_fun_ref(&string::size));
这个问题的原因是这个特定的STL平台在处理const成员函数时有bug（比如string::size）。一个变通方法是改用
函数对象：
struct StringSize:
public unary_function<string, string::size_type>{ // 参见条款40
string::size_type operator()(const string& s) const
{
return s.size();
}
};
transform(s.begin(), s.end(),
ostream_iterator<string::size_type>(cout, "\n"),
StringSize());
解决这问题的还有其他变通办法，但这个不仅在我知道的每个STL平台都可以编译。而且它简化了string::size
的内联调用，那是几乎不会在上面把mem_fun_ref(&string::size)传给transform的代码中发生的事情。换句话
说，仿函数类StringSize的创造不仅避开了编译器一致性问题，而且可能会带来性能提升。
另一个用函数对象代替函数的原因是它们可以帮助你避免细微的语言陷阱。有时候，看起来合理代码被编译
器由于合法性的原因——但很模糊——而拒绝。有很多这样的情况，比如，当一个函数模板实例化的名字不
等价于函数名。这是一种这样的情况：
template<typename FPType> // 返回两个
FPTypeaverage(FPType val1, FPType val2) // 浮点数的平均值
{
return (val1 + val2) / 2;
}
template<typename InputIter1,
typename InputIter2>
void writeAverages(InputIter1 begin1, // 把两个序列的
InputIter1 end1, // 成对的平均值
InputIter2 begin2, // 写入一个流
ostream& s)

haoji

{
transform(
begin1, end1, begin2,
ostream_iterator<typename iterator_traits
<lnputIter1>::value_type> (s, "\n",
average<typename iteraror_traits
<InputIter1>::value_type> // 有错？
);
}
很多编译器接受这段代码，但是C++标准倾向于禁止它。理由是理论上有可能存在另一带有一个类型参数的
函数模板叫做average。如果有，表达式average<typename iterator_traits<lnputIter1>::value_type>将是模棱两可
的，因为它不清楚将实例化哪个模板。在这个特殊的例子里，不存在模棱两可，但是无论如何，有些编译器
会拒绝这段代码，而且那么做是允许的。没有关系。解决这个问题的方法是依靠一个函数对象：
template<typename FPType>
struct Average:
public binary_function<FPType, FPType, FPType>{ // 参见条款40
FPType operator()(FPType val1. FPType val2) const
{
return average(val 1 , val2);
}
template<typename InputIter1, typename InputIter2>
void writeAverages(lnputIter1 begin1, InputIter1 end1,
InputIter2 begin2, ostream& s)
{
transform(
begin1, end1, begin2,
ostream_iterator<typename iterator_traits<lnputIter1>
::value_type>(s, "\n",
Average<typename iterator_traits<InputIter1>
::value_type>()
);
}
每个编译器都会接受这条修正的代码。而且在transform里调用Average:perator()符合内联的条件，有些事情
对于实例化上面的average不成立，因为averate是一个函数模板，不是函数对象。

haoji

把函数对象作为算法的参数所带来的不仅是巨大的效率提升。在让你的代码可以编译方面，它们也更稳健。
当然，真函数很有用，但是当涉及有效的STL编程时，函数对象经常更有用。

haoji

Center of STL Study
——最优秀的STL学习网站
条款47：避免产生只写代码
假设你有一个vector<int>，你想去掉vector中值小于x而出现在至少和y一样大的最后一个元素之后的所有元
素。下面代码立刻出现在你脑中吗？
vector<int> v;
int x, y;
...
v.erase(
remove_if(find_if(v.rbegin(), v.rend(),
bind2nd(greater_equal<int>(), y)).base(),
v.end(),
bind2nd(less<int>(), x)),
v.end());
一条语句就完成了工作。清楚并直接了当。没问题。对吗？
好，让我们先退回一步。对你来说它是合理的、好维护的代码？“不！”大部分C++程序员惊叫，他们的声
音中充满了害怕和讨厌。“是！”他们中的一部分显然高兴地说。但那儿有一个问题。一个程序员很有表现
力的方法是另一个程序员的噩梦。
正如我所见，有上面代码涉及到两个问题。首先，它是函数调用的鼠巢。要知道我是什么意思，这里有一个
相同的语句，但所有的函数名都替换为fn，每个n对应一个函数：
v.f1(f2(f3(v.f4(), v.f5(), f6(f7(), y)),.f8(), v.f9(), f6(f10(), x)), v.f9());
这看起来不自然地复杂，因为我去掉了出现在原例中的缩进，但我想它可以很明白的表示了如果一条语句使
用了12次函数调用，分别调用了10个不同的函数，那会被大部分C++程序开发人员认为很过分。但曾经用过
比如Scheme的函数式语言（functional language）的程序员可能感觉不同，而我的经验是大多数看到原来的代
码而没有感到惊讶的程序员有一个很强的函数式语言背景。大部分C++程序员缺乏这样的背景，所以除非你
的同事精通深度嵌套（nest）的函数调用的方法，类似上面erase调用的代码几乎可以肯定会打败下一个想要
弄明白你写的代码的人。

haoji

这段代码的第二个缺点是需要很多STL背景才能明白它。它使用了不常见的_if形式的find和remove，它使用了
逆向迭代器（参见条款26），它把reverse_iterator转换为iterator（参见条款28），它使用了bind2nd，它建立了
匿名函数对象而且它使用了erase-remove惯用法（参见条款32）。有经验的STL程序员可以轻易地吞下那些组
合，但更多C++开发者在一口吃掉之前会一遍一遍看。如果你的同事对在一条语句中使用erase、remove_if、
find_if、base和bind2ndSTL的这种方法都很熟悉，那可能很好，但如果你想让你的代码易于被主流背景更多的
C++程序员了解，我鼓励你把它分解为易于消化的块。
这是一种你可以使用的方法。（注释不光为了本书。我也会把它们放入代码。）
typedef vector<int>::iterator VecIntIter;
// 把rangeBegin初始化为指向最后一个
// 出现一个大于等于y的值后面的元素。
// 如果没有那样的值，
// 把rangeBegin初始化为v.begin()。如果那个值的
// 最后一次出现是v中的最后一个元素，
// 就把rangeBegin初始化为v.end()。
VecIntIter rangeBegin = find_if(v.rbegin(), v.rend(),
bind2nd(greater_equal<int>(), y)).base();
// 从rangeBegin到v.end()，删除所有小于x的值
v.erase(remove_if(rangeBegin, v.end(), bind2nd(less<int>(), x)), v.end());
这仍然可能把一些人弄糊涂，因为它依赖于对erase-remove惯用法的了解，但在代码的注释和一本好的STL参
考（比如，Josuttis的《The C++ Standard Library》[3]或SGI的STL网站[21])之间，每个C++程序员应该可以不太
困难地指出它作了什么。
当转换代码时，要注意我并没有放弃算法并试图自己写的循环。条款43解释了为什么那一般是一个劣等的选
择，它的论点在这里。当写源代码时，目标是写出对编译器和人都有意义的代码，并提供可接受的性能。算
法基本上总是最好地达到那个目标的方式。但是，条款43也解释了增加算法的时候会自然导致增加嵌套函数
调用并大量使用绑定器和其他仿函数适配器。再看看本条款开头的问题描述：
假设你有一个vector<int>，你想去掉vector中值小于x而出现在至少和y一样大的最后一个元素
之后的所有元素。
一个方案的轮廓跳入脑中：

haoji

● 找到vector中一个值的最后一次出现需要用逆向迭代器调用find或find_if的某种形式。
● 去掉元素需要调用erase或erase-remove惯用法。
把这两个想法加在一起，你可以得到这个伪代码，其中“something”表示一个用于还没有填充的代码的占位
符：
v.erase(remove_if(find_if(v.rbegin(), v.rend(), something).base(),
v.end(),
something)),
v.end());
一旦你完成了这个，确定something就不是很难了，下一个事情你是知道的，你有原例中的代码。那是为什么
这种语句一般被称为“只写（write-only）”代码。当你写代码时，它似乎很直截了当，因为它是一些基本想
法（也就是，erase-remove惯用法加上使用逆向迭代器调用find的想法）的自然产物。但是，读者们很难把最
后的产物分解回它基于的想法。这就被称为只写代码：很容易写，但很难读和理解。
代码是否是只写依赖于读它的人。正如我提到的，有些C++程序员不反感本条款中的代码。如果这是你工作
环境的典型而且你希望它在未来也典型，那就自由释放出你最多的高级STL编程爱好。但是，如果你的同时
不适应函数式编程风格而且STL经验很少，收回你的野心，写一些接近我前面演示的两条语句的方法的东
西。
代码的读比写更经常，这是软件工程的真理。也就是说软件的维护比开发花费多得多的时间。不能读和理解
的软件不能被维护，不能维护的软件几乎没有不值得拥有。你用STL越多，你会感到它越来越舒适，而且你
会越来越多的使用嵌套函数调用和即时（on the fly）建立函数对象。这没有什么错的，但永远记住你今天写
的代码会被某个人——也可能是你——在未来的某一天读到。为那天做准备吧。
当然，使用STL，好好使用，有效使用。但避免产生只写代码。最后，这样的代码完全不高效。

haoji

Center of STL Study
——最优秀的STL学习网站
条款48：总是#include适当的头文件
STL编程的次要麻烦之一是虽然可以很容易地建立可以在一个平台上编译的软件，但在其它平台上则需要附
加的#include指示。这个烦恼来自一个事实：C++标准（不像C标准）未能指定哪一个标准头文件必须或者可
能被其他标准头文件#include。由于有了这样的灵活性，不同的实现就会选择去做不同的东西。
这在实践中意味着什么？我可以给你一些的概念。我使用了五个STL平台（咱们叫它们A、B、C、D和E），
花了一些时间在它们上测试了一些小程序来看看我可以在忽略哪个标准头文件的情况下仍然成功编译。这间
接地告诉我哪个头文件#include了其他的。这是我所发现的：
● 对于A和C，<vector> #includes <string>.
● 对于C，<algorithm> #includes <string>.
● 对于C和D, <iostream> #includes <iterator>.
● 对于D, <iostream> #includes <string> and <vector>.
● 对于D和E, <string> #includes <algorithm>.
● 对于所有的五个实现，<set> #includes <functional>.
除了<set> #include <functional>外，我无法使缺少头文件的程序通过实现B。按照Murphy定律，你总是会在像
A、C、D或E那样的平台上开发，然后移植到像B那样的平台，尤其是当移植的压力很大而且完成的时间很紧
的情况下。
但是请别指责你将要移植的编译器或库实现。如果你缺少了需要的头文件，这就是你的过错。无论何时你引
用了std名字空间里的元素，你就应该对#include合适的头文件负责。如果你遗漏了它们，你的代码也可能编
译，但你仍然缺少了必要的头文件，而其他STL平台可能正好会抵制你的代码。
要帮你记起需要的东西，关于在每个标准STL相关的头文件中都有什么，这里有一个快速概要：
● 几乎所有的容器都在同名的头文件里，比如，vector在<vector>中声明，list在<list>中声明等。例外的
是<set>和<map>。<set>声明了set和multiset，<map>声明了map和multimap。
● 除了四个算法外，所有的算法都在<algorithm>中声明。例外的是accumulate（参见条款37）、
inner_product、adjacent_difference和partial_sum。这些算法在<numeric>中声明。
● 特殊的迭代器，包括istream_iterators和istreambuf_iterators（参见条款29），在<iterator>中声明。
● 标准仿函数（比如less<T>）和仿函数适配器（比如not1、bind2nd）在<functional>中声明。

haoji

无论何时你使用了一个头文件中的任意组件，就要确定提供了相应的#include指示，就算你的开发平台允许你
不用它也能通过编译。当你发现移植到一个不同的平台时这么做可以减少压力，你的勤奋将因而得到回报。