📄 item_46.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>条款46：考虑使用函数对象代替函数作算法的参数</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>条款46：考虑使用函数对象代替函数作算法的参数</h2> <p>一个关于用高级语言编程的抱怨是抽象层次越高，产生的代码效率就越低。事实上，Alexander Stepanov（STL的发明者）有一次作了一组小测试，试图测量出相对C，C++的“抽象惩罚”。其中，测试结果显示基本上操作包含一个double的类产生的代码效率比对应的直接操作一个double的代码低。因此你可能会奇怪地发现把STL函数对象——化装成函数的对象——传递给算法所产生的代码一般比传递真的函数高效。</p> <p>比如，假设你需要以降序排序一个double的vector。最直接的STL方式是通过sort算法和greater<double>类型的函数对象：</p> <pre>vector<double> v;...sort(v.begin(), v.end(), greater<double>());</pre> <p>如果你注意了抽象惩罚，你可能决定避开函数对象而使用真的函数，一个不光是真的，而且是内联的函数：</p> <pre>inlinebool doubleGreater(double d1, double d2){ return dl > d2;}...sort(v.begin(), v.end(), doubleGreater);</pre> <p>有趣的是，如果你比较了两个sort调用（一个使用greater<double>，一个使用doubleGreater）的性能，你基本上可以明确地知道使用greater<double>的那个更快。实际来说，我在四个不同的STL平台上测量了对一百万个double的vector的两个sort调用，每个都设为针对速度优化，使用greater<double>的版本每次都比较快。最差的情况下，快50%，最好的快了160%。抽象惩罚真多啊。</p> <p>这个行为的解释很简单：内联。如果一个函数对象的operator()函数被声明为内联（不管显式地通过inline或者隐式地通过定义在它的类定义中），编译器就可以获得那个函数的函数体，而且大部分编译器喜欢在调用算法的模板实例化时内联那个函数。在上面的例子中，greater<double>::operator()是一个内联函数，所以编译器在实例化sort时内联展开它。结果，sort没有包含一次函数调用，而且编译器可以对这个没有调用操作的代码进行其他情况下不经常进行的优化。（内联和编译器优化之间交互的讨论，参见《Effective C++》的条款33和Bulka与Mayhew的《Efficient C++》<a href="bibliography.html#bi10">[10]</a>的第8-10章。<span>) </span></p> <p>使用doubleGreater调用sort的情况则不同。要知道有什么不同，我们必须知道不可能把一个函数作为参数传给另一个函数。当我们试图把一个函数作为参数时，编译器默默地把函数转化为一个指向那个函数的<em>指针</em>，而那个指针是我们真正传递的。因此，这个调用</p> <pre>sort(v.begin(), v.end(), doubleGreater);</pre> <p>不是真的把doubleGreater传给sort，它传了一个doubleGreater的指针。当sort模板实例化时，这是产生函数的声明：</p> <pre>void sort(vector<double>::iterator first, // 区间起点 vector<double>::iterator last, // 区间终点 bool (*comp)(double, double)); // 比较函数</pre> <p>因为comp是一个指向函数的指针，每次在sort中用到时，编译器产生一个间接函数调用——通过指针调用。大部分编译器不会试图去内联通过函数指针调用的函数，甚至，正如本例中，那个函数已经声明为inline而且这个优化看起来很直接。为什么不？可能因为编译器厂商从来没有觉得值得实现这个优化。你得稍微同情一下编译器厂商。他们有很多需求，而他们不能做每一件事。你的需要并不能让他们实现那个优化。</p> <p>把函数指针作为参数会抑制内联的事实解释了一个长期使用C的程序员经常发现却难以相信的现象：在速度上，C++的sort实际上总是使C的qsort感到窘迫。当然，C++有函数、实例化的类模板和看起来很有趣的operator()函数需要调用，而C只是进行简单的函数调用，但所有的C++“开销”都在编译期被吸收。在运行期，sort内联调用它的比较函数（假设比较函数已经被声明为inline而且它的函数体在编译期可以得到）而qsort通过一个指针调用它的比较函数。结果是sort运行得更快。在我的测试的一百万个double的vector上，它快670%，但不要光相信我的话，亲自试试。很容易证实当比较函数对象和真的函数作为算法的参数时，那是一个纯红利。</p><p>还有另一个使用函数对象代替函数作为算法参数的理由，而它与效率无关。它涉及到让你的程序可以编译。对于任何理由，STL平台经常完全拒绝有效代码，即使编译器或库或两者都没问题。比如，一个广泛使用的STL平台拒绝了下面（有效的）代码来从cout打印出set中每个字符串的长度：</p> <pre>set<string> s;...transform(s.begin(), s.end(), ostream_iterator<string::size_type>(cout, "\n"), mem_fun_ref(&string::size));</pre> <p>这个问题的原因是这个特定的STL平台在处理const成员函数时有bug（比如string::size）。一个变通方法是改用函数对象：</p> <pre>struct StringSize: public unary_function<string, string::size_type>{ // 参见<a href="item_40.html">条款40</a> string::size_type operator()(const string& s) const { return s.size(); }};transform(s.begin(), s.end(), ostream_iterator<string::size_type>(cout, "\n"), StringSize());</pre> <p>解决这问题的还有其他变通办法，但这个不仅在我知道的每个STL平台都可以编译。而且它简化了string::size的内联调用，那是几乎不会在上面把mem_fun_ref(&string::size)传给transform的代码中发生的事情。换句话说，仿函数类StringSize的创造不仅避开了编译器一致性问题，而且可能会带来性能提升。</p><p>另一个用函数对象代替函数的原因是它们可以帮助你避免细微的语言陷阱。有时候，看起来合理代码被编译器由于合法性的原因——但很模糊——而拒绝。有很多这样的情况，比如，当一个函数模板实例化的名字不等价于函数名。这是一种这样的情况：</p><pre>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){ transform( begin1, end1, begin2, ostream_iterator<typename iterator_traits <lnputIter1>::value_type> (s, "\n"), average<typename iteraror_traits <InputIter1>::value_type> // 有错？ );}</pre> <p>很多编译器接受这段代码，但是C++标准倾向于禁止它。理由是理论上有可能存在另一带有一个类型参数的函数模板叫做average。如果有，表达式average<typename iterator_traits<lnputIter1>::value_type>将是模棱两可的，因为它不清楚将实例化哪个模板。在这个特殊的例子里，不存在模棱两可，但是无论如何，有些编译器会拒绝这段代码，而且那么做是允许的。没有关系。解决这个问题的方法是依靠一个函数对象：</p><pre>template<typename FPType>struct Average: public binary_function<FPType, FPType, FPType>{ // 参见<a href="item_40.html">条款40</a>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>() );}</pre> <p>每个编译器都会接受这条修正的代码。而且在transform里调用Average::operator()符合内联的条件，有些事情对于实例化上面的average不成立，因为averate是一个函数模板，不是函数<em>对象</em>。</p><p>把函数对象作为算法的参数所带来的不仅是巨大的效率提升。在让你的代码可以编译方面，它们也更稳健。当然，真函数很有用，但是当涉及有效的STL编程时，函数对象经常更有用。</p></body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -