这篇文章是关于如何巧妙地运用模板在C++中复现boost::lambda库。

引言

在2011年，lambda表达式正式进入C++11标准，成为了语法级别的组件。而本文所涉及的C++函数编程，是指在C++11标准前，借助函数调用运算符重载实现的一种编程范式。

boost库里的函数式编程库颇为丰富，其中尤以lambda和Phoenix两个库著名。在此，我们就以boost::lambda作为典型案例，分析C++的函数式编程。在接下来的文章里，我将首先概述函数式编程（第2章），接着分析boost::lambda的应用（第3章）和实现（第4章），最后给出自己改进版的实现（第5章），分析其安全、性能和灵活性。在本文的最后，我将对C++的函数式编程进行一个总结（第6章）。

在这里，我假定读者拥有一定的模板编程技能。对于函数对象、匿名函数等相关概念已经有很多了解的读者可以跳过第2章。

声明：所有的代码都通过了gcc 6.1.1和clang 3.8.0的测试，visual studio 2015的编译器对于部分代码可能会出现错误。

C++的函数式编程

函数对象

借助运算符重载，我们可以构建出函数对象。该技术很早就出现在了C++的标准库里，标准库functional集中地提供了各种各样的函数对象。接下来我以LLVM头文件（这里我对LLVM的代码进行了简化，以增加可读性）作为示例。标准库在头文件functional里定义了std::less，其可能的实现如下：

template <class T>
struct less {
    bool operator()(const T &lhs, const T &rhs) const {
        return lhs < rhs;
    }
};

因而标准库algorithm里面只带2个参数的std::sort就可以采用如下的实现：

template <class RandomAccessIterator>
inline void sort(RandomAccessIterator first, RandomAccessIterator last) {
    sort(first, last, less<typename iterator_traits<RandomAccessIterator>::value_type>());
}

在这里我们通过标准库iterator中的std::iterator_traits进行类型推断得到其迭代器所指的值类型，进而得到可以用于小于比较的函数对象，将之传递给了拥有3个参数的std::sort函数（第3个参数是一个用于比较的函数对象）。

当然，我们惊喜的发现函数对象的语法是和函数指针相互兼容的，考虑带3个参数的std::sort函数的声明，大致是这个样子的：

template <class RandomAccessIterator, class Compare>
inline void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

假设RandomAccessIterator迭代器其所指的类型叫T，而我们定义了函数bool compareFunc(const T &lhs, const T &rhs)用于比较，当我们调用sort(first, last, compareFunc)时，模板形参Compare的值为bool (const T &lhs, const T &rhs)是一种函数类型，又由于当函数类型作为函数形参的类型时会自动转换为函数指针类型，所以函数形参comp的真实类型为bool (*)(const T &lhs, const T &rhs)，而函数形参comp的值为&compareFun。这里，我们看到C++对于旧有的C语言的相关概念惊人的抽象和兼容能力，数组抽象为了容器（序列容器），指针抽象为了迭代器，而函数指针抽象为了函数对象。

接下来我们分析一下性能，先丢结论，函数对象的性能可能高于函数指针。虽然sort函数多传进去一个参数，但由于该参数实际不占任何空间，实际编译后不会存在一个空对象被压入栈的指令。又由于类模板成员函数的内联展开，原来定义对于std::less对象的函数调用运算符会在sort函数内展开成一个小于比较的表达式，相较于函数指针，减少了一次函数调用的开销。所以函数对象在空间开销上不差于函数指针，在性能开销上可能优于函数指针。

匿名函数

脱离C++，所谓匿名函数，就是一个不具有名字的函数。这种函数通常很小，其定义处就是其使用处。考虑C++98，就其语法层面，匿名函数是不直接支持的，但其实通过函数对象，我们可以构建出类似的语法。考虑上面第3行代码，我们希望最后的代码长成这个样子：

sort(first, last, _1 < _2);

形式上，_1 < _2就像是定义了一个匿名函数，并将这个函数作为...