C++实现匿名函数递归:std::function、Y Combinator and Deducing This

这周写到递归的快速排序时突然发现：我不懂如何去用匿名函数去递归自身，因为正常的lambda就不支持：

//this is a wrong code phase
std::vector<int> nums{9,5,2,7,1,2,3};
auto quick_sort = [&nums](int low, int high)
{
    if(low < high){
        int pivot = sort_paticial(low,high);
        quick_sort(low, pivot-1);
        quick_sort(pivot+1, high);  //wrong
    }
};

当然C++委员会也意识到这个问题，在C++ 11我们有std::function，C++ 14有Y组合子，C++ 23有Deducing this，籍此机会详细记录一下。

方案1（C++11）：std::function封装

对大部分编译器匿名函数不支持在捕获列表直接捕获自身，但是如果加上std::function的可调用封装是允许的，因此能直接写成：

std::function<void(int,int)> quick_sort = [&sort, &quick_sort](int low, int high){
    if(low < high){
        int pivot = sort(low, high);
        quick_sort(low,pivot-1);
        quick_sort(pivot+1, high);   //ok
    }
};

这种方案在简单浅层递归能够使用，但是在大规模计算需要深层递归情况下，性能会急剧下降，这样的性能下降来自于std::function的局限：

无法内联优化：对递归的普通函数或者匿名函数，提升性能的关键是内联技术，即将函数调用直接替换为函数体代码，而std::function需要通过函数指针或者虚函数表指针来确认具体函数，发起间接调用，程序需要先访问std::function指针再跳转到表达式位置执行调用；除了内存寻址更多，间接调用还会破坏CPU分支预测器(Branch Predictor), 造成CPU流水线停顿，影响性能；

内存擦除技术导致必然产生虚函数表：因为std::function允许包装裸函数指针、匿名函数、普通函数、成员函数等对象，其实现就是通过内存擦除实现，简单而言分为三层：

// 抽象基类，用于统一接口
class InvokerBase {
public:
    virtual ~InvokerBase() = default;
    virtual void invoke(int arg) = 0; // 统一的调用接口
};

template <typename F>
class Invoker : public InvokerBase {
    F callable; // 保存具体的可调用对象（如 Lambda、函数指针等）
public:
    Invoker(F f) : callable(f) {}
    
    // 实现基类的虚函数，在内部调用真正的对象
    void invoke(int arg) override {
        callable(arg);     //我们自己的函数实现
    }
};

class MyFunction {
    // 只持有基类指针，具体类型（F）被“擦除”了
    std::unique_ptr<InvokerBase> invoker; 

public:
    // 模板构造函数：可以接受任何可调用对象 F
    template <typename F>
    MyFunction(F f) {
        // 在堆上创建具体的派生类，但用基类指针指向它
        invoker = std::make_unique<Invoker<F>>(f); 
    }

    // 重载调用运算符
    void operator()(int arg) {
        if (invoker) {
            invoker->invoke(arg); // 通过虚函数多态调用
        }
    }
};

所以std::function被调用(MyFunction被调用)，需要在父类对象的虚函数表找到子函数指针；此外，每次std::function对象(MyFunction对象)被创建，会产生new基类构造，实际std::function使用了SSO(小对象优化)，当字节小于16或者32字节时直接在本地缓冲栈区分配内存，但如果匿名函数捕获的变量过多，仍然会产生堆内存分配。

方案2（C++14/C++17/C++20）：Y组合子(Y Combinator)

综上，Y组合子是大多数编译器能接受，且性能瓶颈较高的方法。Y组合子是函数式编程(functional programming)的重要部分，涉及到的理论也比较复杂，例如λ演算等，在这里贴两个优质文章和专栏：

比较学术，笔者水平太低暂不引入。

回到实现上，通过一个Y包装器，接收匿名函数对象，传入该对象作为参数并且调用函数对象，如下：

auto Y = [](auto f) {
    return [f = std::move(f)](auto&& ...args){
        return f(f, std::forward<decltype(args)>(args)...);
    };
};

auto quick_sort = Y([&nums, &sort](auto& self, int low, int high)->void {
    if(low < high) {
        int pivot = sort(low, high);
        self(self, low, pivot - 1);
        self(self, pivot + 1, high);
    }
});

//调用：
quick_sort(0, static_cast<int>(num.size()));

此处注意匿名函数的返回值需要显式指明，因为Y组合子接收的仍然是一个匿名函数对象，这个对象的类型定义应该是完备的, 否则在递归时无法确认当前的函数类型；

也可见，显式写出Y组合子允许调用函数时无需传入自身，C++ 14也支持更简化的写法：

auto quick_sort = [&num,&sort_partition](auto&&self, int low, int high)->void{
    if(low < high){
        int pivot = sort_partition(low, high);
        self(self, low,pivot-1);
        self(self, pivot+1, high);
    }
};
//调用时：需要传递自己或者其他递归函数
quick_sort(quick_sort, 0,num.size()-1);

方案3（C++23）：Deducing this(this推断)

Deducing this不是专门用于解决匿名函数递归的，但是它将this变成了一个可推导参数，意味着匿名函数可以不经过Y组合子包装也能将自身作为参数，既不用手动定义Y组合子，也无需调用时显式调用自身，以下：

auto quick_sort = [&num,&sort_partition](this auto& self,int low, int high)->void{
    if(low < high){
        int pivot = sort_partition(low, high);
        self(low,pivot-1);
        self(pivot+1, high);
    }
};

quick_sort(0, static_cast<int>(num.size()));

关于C++ 23的deducing this特性，我们在下一篇文章会结合C++ 23的相关提案具体陈述，本文暂不展开。