dhb's Blog HomeArchivesTagsCategoriesSite Log
Lambda函数与std::function
|C++
字数总计: 5.3k|阅读时长: 19 分钟

Lambda函数可以说是C++ 11中加入的最重要的特性之一了。Lambda（也称作匿名函数），提供了一种在代码中很方便地定义函数的方法。这种写法能让我们写出非常简洁的语句，比如[]{}()也许就是C++中最简洁的表达式了。

Lambda语法回顾

Lambda的语法也很简单，其形式大致为[](){}，包含3个部分。

  • []中的内容为捕获列表
  • ()中的内容为参数列表
  • {}为函数体

当参数列表为空时，()部分可以省略，也就是说，C++中最简单的Lambda函数是[]{}，这是一个无输入无返回值无语句的空函数。

一个纯粹的函数是不带有任何变化信息的，就仿佛数学意义上的函数——放回值仅由参数值决定，除此之外什么都不做。但很多时候我们需要函数能访问和修改一些外部的数据，或者说需要有相应的上下文。函数体与上下文的整体就称作闭包（closure），它在Lambda中是通过捕获外部变量实现的。

捕获列表[]中放置所有在函数体中用到的外部变量：

1
2
3
int i = 0, j = 1;
auto f = [i, &j](int a, float b){ ++j; cout << i << ", " << a << ", " << b << endl; };
f(1, 2.0f);

比如上面这个例子，就捕获了i，j两个变量，其中i是值捕获，j是引用捕获。

当捕获的变量较多时，C++还提供了一种指定默认捕获的简便写法：

  • [=]指出默认为值捕获
  • [&]指出默认为引用捕获

指定默认捕获之外，其他特定变量的捕获方式加在捕获列表之后即可。比如下面这个例子指定默认为值捕获，j为引用捕获：

1
auto f = [=, &j](int a, float b){ ++j; cout << i << ", " << a << ", " << b << endl; };

你可能会想，怎么只有两种捕获方式呢？C++的移动语义用到捕获里面呢？

C++ 11 中确实只有这两种方式，但是 C++ 14 的出现解决了这个问题：C++14 允许捕获对象由任意表达式初始化。这就说明可以用下面的方式实现移动捕获：

1
2
std::unique_ptr<int> ptr(new int(10));
auto f = [value = std::move(ptr)] { return *value; };

需要特别说明的一点是，值引用捕获的变量默认是const的，如果要在函数体内修改，需要给lambda加上mutable修饰符：

1
auto f = [=](int a) mutable { cout << i++ << ", " << a << endl; };

值捕获对象的生命周期与lambda本体的生命周期相同，而引用捕获则需要注意调用lambda函数时捕获对象仍在生命周期内。通过捕获不同的对象，lambda函数实现了闭包的效果，比如下面的代码就构造了一个斐波那契数列生成器（generator）：

1
2
3
4
5
6
7
8
9
10
11
auto make_fib = [] {
        auto a = 1, b = 1;
        return [=]() mutable {
            auto ret = a; a = b; b += ret;
            return ret;
        };
    };

auto fib = make_fib();
for (int i = 0; i < 9; i++)
    cout << fib() << ' ';

上面的写法中，我们均没有指明lambda的返回类型是什么，这时C++会将返回类型当作auto，自动帮我们推导。如果要明确指出返回类型，可以像下面这样：

1
auto f = []() -> double { return 5; };

在C++中表示函数

函数动态调用，就是把函数存在“变量”里面，调用的时候根据变量值的不同调用相应的函数。要实现这个我们至少需要做两部分事：

  1. 构造并储存函数到变量中
  2. 调用一个变量中存有的函数

如果实现了这两点，我们便认为函数是一等公民：函数的地位与其他的基础类型一样，可以储存在变量中，可以作为参数传递，可以像其他变量一样随意构造。在函数式语言和许多的动态类型脚本语言（JS，Lua等）中，函数均是一等公民。C++中，函数并不是原生的一等公民（直到Lambda的出现改善了这一点），但 C++也提供了不少语言机制让我们实现函数作为一等公民的类似效果。

关于第一点，C++中要表示可以调用的函数（callable），主要有三种方式：

  1. 函数指针
  2. 函数对象（functor，或function object）
  3. Lambda

函数指针是从C语言中基础而来的写法，它可以指向任意同签名的函数：

1
2
3
int add(int a, int b) { return a + b; }
int(*f)(int,int) = add;
int r = f(1, 2);

这里的f就是指向add函数的函数指针。由于f实际上是一个指针，而指针的值可以指向任何同类型签名的函数，指针也能很方便的作为参数传入任意函数。

函数对象是一个定义了operator()运算符重载的对象。

1
2
3
4
5
struct Functor {
	int operator()(int a, int b) { return a + b; }
};
auto f = Functor();
int r = f(1, 2);

函数对象只声明了一个可调用的函数，并不具备动态调用的能力——因为两个不同函数对象的类型不同，不能相互赋值。解决方案有两种，一种是通过模版在编译期决定调用对象；另一种是通过面向对象中的多态在运行期决定调用对象：在基类中声明函数签名，并在该基类的不同派生类中实现对应的方法。比如：

1
2
3
4
5
6
7
8
9
struct FunctorBase {
	virtual int operator()(int a, int b) = 0;
};
struct Functor1 : FunctorBase {
	int operator()(int a, int b) { return a + b; }
};
struct Functor2 : FunctorBase {
	int operator()(int a, int b) { return a - b; }
};

在C++中，多态一般是由**虚表(virtual table)**实现的，这样实现的动态调用，其实是借助了虚表。

Lambda在上面已经介绍过了，在C++中lambda相当于函数对象的语法糖：它能自动帮你捕获变量。也就是说，下面这个lambda函数：

1
auto f = [=, &j](int a, float b){ ++j; cout << i << ", " << a << ", " << b << endl; };

其实与这个函数对象的功能相同：

1
2
3
4
5
6
7
8
struct F {
    F(int i, int &j) : i(i), j(j) {};
	void operator()(int a, float b) { ++j; cout << i << ", " << a << ", " << b << endl; }
private:
    int i;
    int &j;
};
const auto f = F()

Lambda其实相当于const类型的函数对象，所以修改捕获值时要加mutable修饰符。这个函数对象的类型是实现定义的，编译器会生成一个相应的类型。因此在将lambda赋值给一个变量时，变量类型只能为auto，因为没法确定lambda的类型。

Lambda对象也有相应的大小。由这种等价而来的函数对象，可以很轻易地发现lambda对象的占用空间来自其捕获的对象。比如在64位系统下就有如下的结果：

1
2
3
4
char a[10];
auto f = [](){};	// sizeof(f) == 1
auto g = [&a](){};	// sizeof(g) == 8
auto h = [a](){};	// sizeof(h) == 10

可以看到，空lambda的大小为1字节，与空对象的大小为1字节是对应的。如果有捕获的对象，捕获对象占多大空间，lambda就有多大。

由于lambda的类型是编译器定的，即使是两个函数签名相同的lambda变量也不能相互赋值：

1
2
auto f = [](){ cout << "f"; };
f = [](){ cout << "g"; };		// 错误

不过在捕获列表为空时，我们可以将lambda赋值给相同函数签名的函数指针：

1
int(*f)(int,int) = [](int a, int b){ return a + b; };

既然同函数签名也不能互相赋值，说明Lambda本身不具备动态调用的能力。而由于类型不确定的原因，它也不能利用到面向对象中多态的解决方案，要把lambda函数作为参数传如其他地方中，只能通过模版在编译器解决。在编译期解决调用的好处就是编译器可以很好得将较小的函数体内联进调用函数的地方。比如下面第一种搜索的写法就比用函数指针的第二种写法要快的多，原因正是因为编译器进行了函数内联，从而更好的优化：

1
2
3
4
5
6
7
8
9
10
11
12
// 第一种 - 模版内联
bool first_search (std::vector<int> &vec, int val) {
  auto bigger = [](int a, int b){ return a > b; };
  auto rng = std::equal_range (vec.begin(), vec.end(), val, bigger);
  return rng.first != rng.second;
}

// 第二种 - 函数指针
int bigger (const void *a, const void *b) { return *(int*)b - *(int*)a; }
bool second_search (std::vector<int> &vec, int val) {
  return bsearch (&val, vec.data(), vec.size(), sizeof(int), bigger);
}

虽然编译期决定调用能产生高效的代码，但我们有时只能运行期才能决定调用哪个函数。那怎么样让lambda函数能够在运行期动态地决定调用对象是谁呢？这就需要说到C++11中与lambda同时引入的std::function了。

函数容器——std::function

上面，我们解决了储存函数的问题，现在要来看看动态调用的问题了。

首先，动态调用可以发生在两个阶段：编译期和运行期。

编译期的调用主要由模版实现，比如在std::sort中传入比较函数。

运行期的调用则会稍微麻烦一些，目前我们已知有两种方式：

  1. 函数指针
  2. 面向对象的多态

多态要求函数体实现在一个继承类中，这有时并不太好实现，比如就没有办法让int这样的基础类型继承（要搞也只能像Java中的Integer类做一个装包，但是没有必要）。函数指针虽然没有这个问题，但它本质是无状态的，不方便实现像闭包这样的东西。

有没有一种好的解决方案呢？有。C++11中加入的std::function正好解决了这个问题。它是一种通用的函数容器，不管是函数指针、函数对象、还是lambda函数，只要它们的函数签名对的上，都可以存在里面，而且可以很方便的复制、传递、调用：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void func() {
	cout << "func()" << endl;
}

struct Functor {
	void operator()() { cout << "functor" << endl; }
};

int main() {
	std::function<void()> f;
	f = func;
	f();

	f = Functor();
	f();
	
	f = [](){ cout << "lambda" << endl; };
	f();
}

std::function在被赋值到一个具体的函数前，是空的状态，如果这时调用f()，会得到std::bad_function_call异常。

std::function的动态调用是用多态实现的（在后面会细说），说明f中至少含有一个虚表指针。此外，正如lambda函数要分配储存上下文的空间，std::function也需要给上下文分配空间。这个空间是随着捕获内容的大小而变化的，我们可能猜测该空间分配在堆上，正如std::string那样。如果我们去取上面这个f变量的大小，会发现sizeof(std::function<void()>) == 32，它实际的大小显然比只存一个虚表指针加上堆空间指针要多的多。事实上，在目前的三大主流编译器（gcc, clang, msvc）的实现中，均采用了一个如std::string中的小对象优化机制(SBO, Small Buffer Optimization)：较小的上下文储存在栈上。我们可以hook掉分配内存的函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 替换掉全局的new与delete
void* operator new(std::size_t n) {
	cout << "Allocating " << n << " bytes" << endl;
	return malloc(n);
}
void operator delete(void* p) noexcept { free(p); }

int main() {
	char a1[16];
	auto lambda1 = [a1](){};
	cout << "lambda1 size: " << sizeof(lambda1) << endl;
	std::function<void()> f1 = lambda1;

	char a2[17];
	auto lambda2 = [a2](){}; 
	cout << "lambda2 size: " << sizeof(lambda2) << endl;
	std::function<void()> f2 = lambda2;
}
1
2
3
lambda1 size: 16
lambda2 size: 17
Allocating 17 bytes

从运行结果可以看出，16字节一下的上下文保存在栈中，超过16字节的话则会保存在堆中。

实现一个简陋的std::function

之前我提到了std::function用了多态来实现运行期的动态调用，但具体是怎么实现的呢？直接做一个不就知道了:D（这一部分主要参考了这篇文章）

在cppreference上找到std::function的定义大致如下：

1
2
3
4
5
6
7
template <class>
class function; /* undefined */

template <class Result, class... Args>
class function<Result(Args...)> {
    // ...
}

第二个类定义是第一个的偏特化（partial specialization），模版匹配时会将第一个模版尝试匹配在第二个模版上，这样就能将函数类型中的返回值与参数分离出来。如果我们只将其声明成这样：

1
2
3
4
template <class Result, class... Args>
class function {
    // ...
}

那使用时就只能写成这一种形式：std::function<int, int, float>，而不是我们比较习惯的这种格式：std::function<int(int, float)>。

之前我们说过，std::function的动态函数调用是通过多态实现的。要实现多态调用，首先要定义一个基类ICallable：

1
2
3
4
struct ICallable {
    virtual ~ICallable()                = default;
    virtual Result Invoke(Args... args) = 0;
};

基类主要定义了一个Invoke虚方法来实现函数调用。接下来是派生类CallableT，这里将实际存放的函数类型定义为一个模版参数，从而实现对多种函数表示的支持：

1
2
3
4
5
6
7
template <typename T> struct CallableT : ICallable {
    CallableT(const T &t) : t(t) {}
    ~CallableT() override = default;
    Result Invoke(Args... args) override { return t(args...); }
private:
    T t;
};

CallableT类实际上用到了一个C++中的惯用技巧——类型擦除(Type Erasure)。类型擦除让我们能够将一个不管是什么类型的对象“包”进我们的类中，并让我们之后能调用它。每当CallableT被实例化，都伴随着创建了一个新的虚表(vtable)，辅以多态，我们就能动态地调用到各种不同形式的函数。STL中的std::function、std::any都用到了这个技巧。

有了这两个类的帮助，function类就很好实现了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
template <typename, std::size_t BufferSize = 32> class function; /* undefined */

template <typename Result, typename... Args, std::size_t BufferSize>
class function<Result(Args...), BufferSize> {
public:
    function() = default;

    template <typename T> function &operator=(T &&t) {
        static_assert(sizeof(CallableT<T>) <= sizeof(storage), "function is too large for buffer");
        callable.reset(new (storage) CallableT<T>(t));
        return *this;
    }

    template <> function &operator=<std::nullptr_t>(std::nullptr_t &&t) {
        callable.reset(nullptr);
        return *this;
    }

    Result operator()(Args... args) const {
        assert(callable);
        return callable->Invoke(args...);
    }

private:
    // ICallable 代码 ...
    // CallableT 代码 ...

    struct Deleter {
        void operator()(ICallable *callable) { callable->~ICallable(); }
    };

    char                                storage[BufferSize];
    std::unique_ptr<ICallable, Deleter> callable;
};

这里我没有采用动态内存分配的方式，而是直接在栈上分配了BufferSize字节大小的storage（毕竟调用new的开销比直接在栈上分配要大的多），在此储存上下文。BufferSize的大小由模版值确定，默认为32。

operator=函数的参数类型是一个模版参数，以支持赋值任意的函数形式。其中判断了赋值的函数上下文是否能够储存下，如果是，直接在storage中构造对象。这里还特化了赋值nullptr的情况。

而operator()函数则更加直接，里面调用了基类的虚函数Invoke，在这里调用在虚函数表中找到实际的函数。由于函数可能为空，需要用assert验证其为非空。

简单测试一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void func() {
    std::cout << "func" << std::endl;
}

struct functor {
    void operator()() { std::cout << "functor" << std::endl; }
};

int main() {
    function<void()> f;
    std::cout << "sizeof function<void()>: " << sizeof(f);
    f = func;
    f();
    f = functor();
    f();
    f = [] { std::cout << "lambda" << std::endl; };
    f();
}
1
2
3
4
sizeof function<void()>: 40
func
functor
lambda

动态函数储存是没有问题了，但这个function对象占用了40个字节的大小…实际能存多大的上下文呢？简单测试一下，发现上下文最大能存24个字节的大小，而分配的storage大小是32字节，另外8字节显然被用作了虚表指针。也就是说，这个对象有16个字节是不能用于储存上下文的，能不能进一步优化一下呢？

稍微分析一下就能发现，上面的实现额外储存了一个基类指针，然而基类地址已知，这个指针并没有起到什么作用，唯一的作用就是表示对象是否为空。另一方面，可以用函数指针本身为空来表示对象为空。然而，虚表指针我们无法修改，也就不能将其置空。不过，可以用一种实例化的特殊CallableT来表示function为“空”的这种情况。

简单修改下function的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
template <typename Result, typename... Args, std::size_t BufferSize>
class function<Result(Args...), BufferSize> {
public:
    function() { new (storage) CallableT<std::nullptr_t>(nullptr); }
    ~function() { ((ICallable *)storage)->~ICallable(); }

    template <typename T> function(T &&t) { operator=(std::forward<T>(t)); }

    template <typename T> function &operator=(T &&t) {
        static_assert(sizeof(CallableT<T>) <= sizeof(storage), "function is too large for buffer");
        ((ICallable *)storage)->~ICallable();
        new (storage) CallableT<T>(t);
        return *this;
    }

    Result operator()(Args... args) const {
        return ((ICallable *)storage)->Invoke(args...);
    }

private:
    // ICallable 代码 ...
    // CallableT 代码 ...

    template <> class CallableT<std::nullptr_t> : public ICallable {
    public:
        CallableT(const std::nullptr_t &t) {}
        ~CallableT() override = default;

        Result Invoke(Args... args) override { throw std::bad_function_call(); }
    };

    char storage[BufferSize];
};

PS：上面的代码在Clang和MSVC测试通过，但GCC报错。原因是C++标准要求特化必须在命名空间里做，而Clang和MSVC放宽了这个限制。如果要在GCC上编译，需要做一些workaround（如dummy template argument），这里鉴于篇幅省略…

基本思路是用以std::nullptr_t实例化一个CallableT，用来表示function为空的情况。这种实现也可以去除Invoke调用时判断为空的分支。细节这里就不再说了，代码已经比较清楚了。

修改之后，这个function类已经能做到只用8字节作为虚表指针，剩下的空间用作储存上下文了，比之前节省了8字节的空间呢 😄

不过，如果用它去存一个没有上下文的函数，我们发现BufferSize至少是16字节，而不是预计的8字节。这里被神秘地拿去的8字节来自于CallableT中储存的t，如果函数的上下文为0字节，这里的t应该也是0字节。但是，C++中是不允许存在大小0字节的对象的（不然怎么取地址啊）。于是t的大小就被当作了1字节，再加上内存对齐的影响，最小的BufferSize就应该是16字节啦。

目前function看起来已经能用了，但我们还忽略了一个“小”问题：

1
2
3
function<void()> f2;
f2 = f;
f2();

上面的语句能成功通过编译，我们可能认为编译器为function对象自动创建了自己的复制赋值函数。但真的是这样吗？如果我们在function的Invoke中加上一句输出：

1
2
3
4
Result operator()(Args... args) const {
    std::cout << "Invoked" << std::endl;
    return ((ICallable *)storage)->Invoke(args...);
}

并运行下面的代码：

1
2
3
4
5
6
7
8
9
10
int main() {
    static_function<void()> f;
    int i = 0;
    f = [=]() mutable { std::cout << ++i << std::endl; };
    f();

    static_function<void()> f2;
    f2 = f;
    f2();
}
1
2
3
4
5
Invoked
1
Invoked
Invoked
2

可以看到调用f2()时触发了两次Invoke，显然不是我们想要的情况。可以看出，这是因为f2将f当成了一个普通的函数对象，并调用了我们编写的模版版本的赋值函数。每复制一次，都相当于将f的函数包了一层。

要解决这个问题，只要让编译器在这种情况下不要调用我们编写的模版赋值函数，或者说，让我们编写的模版版本的赋值函数只能用于赋值对象为函数类型的情况，这就需要给模版加上限制。C++中提供了一种实用的机制：SFINAE(Substitution Failure Is Not An Error)，“替换失败不是错误”，它是意思就是，当一个模版匹配失败时并不直接报错，而是当它不存在。通过在模版参数列表中加入匹配条件，就可以对模版的适用范围加以限制，将一些重载函数的选项剔除。具体实现这里就不再细说了（要把SFINAE说清楚可能就要一整篇文章了），读者可以自己实现。

参考

  1. https://shaharmike.com/cpp/naive-std-function/

  2. https://shaharmike.com/cpp/lambdas-and-functions/

文章作者: dhbloo
文章链接: https://dhbloo.github.io/2019/11/04/Cpp-Function/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 dhb's Blog！
C++