有效使用 Lambda 表达式和 std::function [翻译]

翻译自 Dr. Dobb's 的一篇关于 C++11 的 lambda 表达式, 闭包 和 std::function 的文章

原文: Efficient Use of Lambda Expressions and std::function
作者: Cassio Neri
译文: 有效使用 Lambda 表达式和 std::function
译者: Breaker <breaker.zy_AT_gmail>

译文

---

有效使用 Lambda 表达式和 std::function

函数对象和 std::function 在各个库中实现各不同。C++11 的 lambda 表达式使它们更有效地被使用

函数对象类，即实现 operator() 的类，多年来被 C++ 程序员所熟知，它们被用做 STL 算法中的谓词 (predicate)。然而，实现简单的函数对象类是一件繁琐的事情，如：

假设 v 是 int 为元素的 STL 容器，我们要计算其中有多少元素是指定整数 n 的倍数。STL 的方式如下：

std::count_if(v.begin(), v.end(), is_multiple_of(n));

is_multiple_of 定义如下：

class is_multiple_of {
public:
    typedef bool result_type;   // 虽然无严格要求, 但建议定义这两个 typedef
    typedef int argument_type;  // 讨论 std::reference_wrapper 时会说明原因
    is_multiple_of(int n) : n(n) {}
    bool operator()(int i) const { return i%n == 0; }
private:
  const int n;
};

这些冗长的代码让很多程序员宁愿写自己的循环，也不愿使用 std::count_if，如此一来，他们也丢掉了编译优化的机会

lambda 表达式 使创建这种简单的函数对象类更加方便。Boost 中的两个库 Boost.Lambda 和最近的 Boost.Phoenix，均提供了很好的 lambda 概念的实现，以提高 C++03 的语言表达能力，并且 C++ 标准委员会已决定在 C++11 中加入 lambda 表达式的语言支持。使用这些新特性后，之前的例子变为：

std::count_if(v.begin(), v.end(), [n](int i){return i%n == 0;});

上面的 lambda 表达式 [n](int i){return i%n == 0;} 会让编译器产生一个类似 is_multiple_of 的未命名函数对象类，并且具有以下优点：

1. 它简约而不冗长
2. 它不会为临时的使用而引入新的名字，所以不导致名字污染
3. 通常（这个例子还看不出来），函数对象类名不如它的实际代码的表达能力强，把代码放到更靠近调用它的地方将提高代码清晰度

闭包类型

在前面的例子中，我们的函数对象类名为 is_multiple_of，而由编译器自动生成的函数对象类有不同的名字，并且只有编译器知道这个类型名字，可以认为它是一个未命名类型。为了阐述，它叫做 闭包类型 (closure type)，而由 lambda 表达式产生的临时对象叫做 闭包对象。类型的匿名性并不影响 std::count_if 的调用，因为它是一个函数模板，它会进行参数类型推导

将函数改写为模板，可以让它接受 lambda 表达式作为参数。例如，一个科学计算库实现一个根查找器 (root-finder)，比如一个接受函数对象 f，并返回满足 f(x) = 0 的 double 值 x 的 root-finder 函数，可以实现为函数模板：

template <class T>
double find_root(T const& f);

但是，一些少许而周知的 C++ 模板缺点让上面代码并不很合意：模板代码必须写在头文件中，这会增加编译时间，并且函数模板不能为 virtual

find_root 可以写为非模板函数吗？如果可以，它将具有怎样的原型 (signature)

double find_root(??? const& f);

参数类型推导并不是 C++11 引入的新事物，相比之下，新的标准将引入两个关键字，auto 和 decltype，以支持类型推导（注：auto 也是 C++03 的关键字，但意义不同）。如果要命名闭包对象，可以如下例：

auto f = [](double x){ return x * x - 0.5; };

另外，可以为闭包类型定义别名，如下：

typedef decltype(f) function_t;

但是不幸地是，function_t 只能在 lambda 表达式所在的同一作用域中定义，即其它地方是不可见的，故它也不能用来定义 find_root 的原型

下面来看另一个重要的东西 std::function

std::function 及其开销

另一个选择是 Boost 的 std::function，它实现了一套类型消除机制 (type erasure)，可以统一处理不同的函数对象类型。它的前辈 boost::function 可以追溯到 2001 年，并在 2005 年引入为 TR1 的 std::tr1::function。现在，它是 C++11 的一部分，并且放入 std 名字空间中

下面看下 std::function 和相关类的三种不同实现：Boost, Microsoft C++ Standard library (MSLIB), GNU Standard C++ Library (libstdc++, 本文称 GCCLIB)。除非另行说明，这里提到的库类型和函数都属于 std 名字空间，虽然 Boost 不是。使用两个编译器：Microsoft Visual Studio 2010 (MSVC), GNU Compiler Collection 4.5.3 (GCC) 带 -std=c++0x 选项，对上述各自库和 Boost 进行编译。使用 std::function 后，find_root 声明变为：

double find_root(std::function<double(double)> const& f);

通常 std::function<R(T1, T2, ..., TN)> 是一个函数对象类，它包装其它任意的函数对象，被包装的函数对象具有类型为 T1, ..., TN 的 N 个参数，并且返回一个可转换到 R 类型的值。std::function 使用 模板转换构造函数 接收被包装的函数对象，特别是，闭包类型可以隐式地转换为 std::function。但是，在构造 std::function 时存在两个隐藏的，但也可预防的开销：

第一个开销，std::function 构造函数按值传递函数对象，这意味着进行拷贝。进一步，构造函数会将这个拷贝转发到一系列辅助函数上，而其中大多数也是按值传递，这意味着更多的拷贝。例如，MSLIB 和 GCCLIB 会做 4 次拷贝，而 Boost 则会做 7 次。不过，大量的拷贝还不是性能损害的元凶

第二个问题和函数对象的大小有关。std::function 的三个库实现都采用了标准建议的小对象优化技术 (small object optimization)，以避免动态内存分配。通常，它们使用一个数据成员存储被包装函数对象的拷贝。但是，因为被包装对象的大小是在 std::function 构造时确定，（被包装对象较大时）成员存储可能不足以容纳其拷贝。这时，将调用 new（除非自定义分配器）在堆上创建拷贝，只在数据成员中保存拷贝的指针。超出就分配堆存储的准确大小，依赖于具体平台和内存对齐，对于一般平台的 MSLIB, GCCLIB 和 Boost 的最好情况，分别是 12 bytes, 16 bytes 和 24 bytes

提高 std::function 的性能

为了解决上述性能问题，应该避免使用拷贝和大对象，直接的想法是用引用代替拷贝。但是，这通常很难，因为我们有时需要 std::function 比它的原始被包装函数对象有更长的生存期

这是个老问题，STL 算法按值传递函数对象参数时，就存在此问题。Boost 很早就提供了一种解决方法，现在被 C++11 采用。类模板 std::reference_wrapper 包装一个对象的引用，并提供到被包装类型的自动类型转换，这使得 std::reference_wrapper 可用在很多需要被包装类型的地方。std::reference_wrapper 和引用的大小相同，即它很小。另外，有两个函数模板 std::ref 和 std::cref，分别用来简化非 const 和 const 的 std::reference_wrappers 的创建（就像用 std::make_pair 简化 std::pairs 的创建）

再看下第一个例子：为了避免 is_multiple_of 的多次拷贝（虽然它很小，没有大的开销），可使用如下：

std::count_if(v.begin(), v.end(), std::cref(is_multiple_of(n)));

同样的思路，应用在 lambda 表达式时如下：

std::count_if(v.begin(), v.end(), std::cref([n](int i){return i%n == 0;}

不幸地是，这里的情况有些复杂，并且依赖编译器和库实现：

• 两个编译器下的 Boost（将 std::cref 变为 boost::cref）: 均无法工作，因为 boost::reference_wrapper<T> 不是一个函数对象

• MSLIB: 无法工作，但未来会支持。实际上，MSLIB 为了操作函数对象的返回类型，使用了 TR1 中的 std::result_of，它依赖含 result_type 成员的函数对象类型，其中 result_type 是用作 operator() 返回类型的 typedef。注意，手工的 is_multiple_of 类已包含这个类型成员，但 C++11 的闭包类型却没有。C++11 中已经改变 std::result_of，它以 decltype 的方式定义。我们现在处于过渡期，MSLIB 仍然遵循 TR1，但 下一版 MSLIB 应该会遵循 C++11

• GCCLIB: 可以工作

另外，按照 C++11，由 lambda 表达式产生的函数对象类不能适配 (adaptable)（译注：参考 STL 谓词适配），即它们没有 STL 适配器 (adaptor) 需要的特定类型成员，所以下面代码是非法的：

std::not1([n](int i){ return i%n == 0; });

这个例子中，std::not1 需要 argument_type 成员类型。注意，手工的 is_multiple_of 类中已定义了它

当使用 std::function 时，上面的 std::reference_wrapper 问题有些小变化。按照定义，std::function 只包装函数对象，因此，当它的构造函数接收std::reference_wrapper<T> 类型的对象时，它假定 T 是一个函数对象类并相应工作。例如，下面代码对于 Boost 和 GCCLIB 是合法的，而目前对 MSLIB 尚不合法（下一版应该可以）：

std::function<bool(int)> f(std::cref([n](int i) {return i%n == 0));
std::count_if(v.begin(), v.end(), f);

值得一提的是，std::function 包装的一元和二元函数对象类可以适配，它们可以传递给 STL 适配器，如 std::not1

总结一下：如果你不想使用堆存储（和自定义分配器），可以选择 Boost 和 GCCLIB；如果考虑移植性，则应该使用 Boost；对于使用 MSVCLIB 的开发者，直到下一版之前，性能问题都会存在；对于那些不想等待的人，这里有一个可移植的变通方法（GCC 和 MSVC 都可工作）

思路很简单：保持小的闭包类型。闭包对象的大小依赖于 lambda 表达式捕获的变量（译注：参考闭包概念, upvalue），即 [] 中的东西。如之前的 lambda 表达式：

[n](int i){ return i%n == 0; };

这里捕获的变量是 n，所以闭包类型有一个 int 数据成员保存 n 的拷贝。放入 [] 中的标识符越多，闭包类型的尺寸就会越大。如果 [] 中所有标识符的合计尺寸很小，比如一个 int 或 double 的大小，那么便不会使用堆存储

一种保持小尺寸的方法是，创建一个只包含引用的 struct，其中的引用指向之前放入 [] 中的所有标识符，然后只将 struct 的引用放入 []。随后，可以在 lambda 表达式体内使用 struct 的成员。例如，下面 lambda 表达式：

double a;
double b;
// ...
[a, b](double x){ return a * x + b; };

将产生至少 2 * sizeof(double) = 16 bytes 的闭包类型，足以让 MSLIB 使用堆存储。将其改变如下：

double a;
double b;
// ...
struct {
    const double& a;
    const double& b;
} p = { a, b };
[&p](double x){ return p.a * x + p.b; };

这时，只有指向 p 的引用被捕获，这对于 MSLIB, GCC 和 Boost 都不会使用堆存储

最后的忠告是，标准中说，闭包类型实现可以使用不同的大小和字节对齐。这表示以上的变通方法也可能不奏效。准确地说，以上代码仍合法，但如果对象变大，也可能使用堆存储。还好，MSVC 和 GCC 都不如此

[END]