X the Unknown Becoming an “X'' in an equation.

C++高阶函数（一）

0. 前言

看见了标题不要以为以下的内容是C++的高级话题。这里的``高阶''是与``函数''连在一起作为名词的。高阶函数（high-order functions）有点借用了数学中高阶的概念。当一个函数是以另一个函数作为参数，或者以另一个函数作为返回值的时候（或者两者兼备），就可以称作是高阶函数。举个例说：

typedef int (*int_func)(int);
 
int f(int_func g, int x) {
   return g(x);
}

这里，函数 f 就可以称作是一个高阶函数，因为它以另一个函数（实参 g ）为参数。

高阶函数在函数式编程里面是很普遍，在命令式编程里面可能比较少提到，但对于C++来说，高阶函数已经不是新事物了。很多地方，例如C++的标准库自身，或者C++的巨牛库boost，对在C++中使用高阶函数已经有不同方面的支持。虽然目前还有很多方面我还没有触及到，但为了避免自己没记性忘掉，我还是准备把我不完全的认识先记录下来，日后继续慢慢更新。嗯，期待自己能写出一个系列呢~。

1. 函数的生成

生成函数？

假如现在有一个简单的函数（实际上是函数对象。这里用的是函数的纯抽象概念：只要表现得和函数一样的，都可以叫作``函''。下面的描述，如果不需要严格区分函数和函数对象，那么我一律称作函数），作用是做加法的：

template <class T>
struct x_plus {
   T operator () (T op1, T op2) const {
      return op1+op2;
   }
};

如果有两个int变量x, y，那么

x_plus<int>()(x, y);

得到的结果就是x+y。对于x_plus<int>()来说，它是一个二元函数。

通过把其中一个值变成常量，x_plus<int>()就可以表现像一个一元函数了：

x_plus<int>()(x, 1); //     ---------------     (1)

相当于计算x+1。

函数生成的过程与上面的这个过程是类似的。通过将一个函数的某一个变量绑定为另外一个变量，就可以得到一个新的函数。

然而严格地说，上面的函数调用(1)依旧是二元函数，只不过其中一个参数被固定了。对于一个一元函数，它被期望的调用方式应该是：

_i_am_an_unary_function_(x);

于是，在对于一些需要使用一元函数的场合，x_plus<int>()是无法使用的：

template <class unary_function>
inline int _i_need_an_unary_func (unary_function f, int x) {
   return unary_function(x);
}
 
_i_need_an_unary_func ( x_plus<int>()(x, 1), 10 ); // error

std::bind1st和std::bind2nd

标准库的std::bind1st和std::bind2nd提供了一个解决方案，使得我们可以将x_plus<int>()转化为一个真正的一元函数：

#include<functional>
using namespace std;
 
_i_need_an_unary_func ( bind2nd(x_plus<int>(), 1), 10 ); // ok
_i_need_an_unary_func ( bind2nd(x_plus<int>(), 1), 10 ); // ok

这里的x_plus<>实现于最开始时候定义的有点区别，会在后面说明。

std::bind2nd(x_plus<int>(), 1)和x_plus<int>()(x, 1)的区别在于前者将一个参数绑定到某个已有函数的某个实参上，从而生成一个新的函数，而后者是一个函数调用（而且是不合法的函数调用，这里的 x 会因为未定义而产生编译错误）。所以对于std::bind2nd(x_plus<int>(), 1)，以下的调用是合法的：

bind2nd(x_plus<int>(), 1)(10); // ok, equivalent to function call: x_plus<int>()(10, 1)

std::bind1st和std::bind2nd是类似的，区别在于绑定参数的位置不一样：

bind1st(x_plus<int>(), 1)(10); // => x_plus<int>()(1, 10)
bind2nd(x_plus<int>(), 1)(10); // => x_plus<int>()(10, 1)

因为std::bind1st和std::bind2nd的实现是类似的，我只考虑实现其中一个的基本原理：

bind1st返回的可以是普通函数指针或者函数对象，然而对于返回普通函数指针，实现起来似乎不怎么方便>*<，所以一般都是返回函数对象：

template <class F, class A1>
struct x_bind1st_c {
   x_bind1st_c(const F& _f, A1 _a1) : f(_f), a1(_a1) { }
 
   return_type? operator () (argument_type? a2) const {
      return f(a1, a2);
   }
private:
   F f;
   A1 a1;
};

上面的实现还未完整，但不妨先进行分析。通过x_bind1st_c< x_plus<int>, int >(x_plus<int>(), 1)，就可以产生一个函数对象func。函数对象里面已经定义了operator()(...)的成员，所以可以通过func(x)的方式来调用这个函数对象，达到预期的效果。

实现中还有部分地方没有明确：operator()(...)的返回类型是什么？实参a2的类型又是什么？或许可以假定为与A1相同，但这毕竟没有普适性：要求一个函数的返回值与实参类型相同、所有实参的类型都一样，这样的要求显然不合理。函数需要返回什么值，实参接受什么类型，是被绑定的函数决定的，如此考虑的话，直接从被绑定函数中获取是最好的方法。为了这样，需要对x_plus<>的定义稍微修改一下：

21
22
23
24
25
26
27
28
29
30

template <class T>
struct x_plus {
   typedef T return_type;
   typedef T arg1_type;
   typedef T arg2_type;
 
   T operator () (T op1, T op2) const {
      return op1+op2;
   }
};

然后……重新写一次完整的x_bind1st_c的定义吧：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

template <class F>
struct x_bind1st_c {
   typedef typename F::return_type return_type;
   typedef typename F::arg1_type arg1_type;
   typedef typename F::arg2_type arg2_type;
 
   x_bind1st_c(const F& _f, arg1_type _a1) : f(_f), a1(_a1) { }
 
   return_type operator () (arg2_type a2) const {
      return f(a1, a2);
   }
private:
   F f;
   arg1_type a1;
};

x_bind1st_c是一个类模板，使用的时候必须显式指定模板的参数。可以利用函数模板的自动推导简化使用：

16
17
18
19
20

template <class F>
inline x_bind1st_c<F>
x_bind1st(F f, typename F::arg1_type a1) {
   return x_bind1st_c<F>(f, a1);
}

x_bind1st就这样完成了。（我并没有看过标准库的实现，所以我不保证这就是std::bind1st的实现方式。事实上我觉得标准库应该比我上面简单的实现考虑得更多，比如const和volatile关键字的修饰。不过我觉得基本原理应该是这样的。）

x_bind1st（算是简化+删节版的std::bind1st吧，所以下面把两者合在一起统称bind1st/bind2nd）的实现同时也提示了几点：

1、只能用在接受两个参数的函数对象上。

所以对于非二元的函数对象，无法使用bind1st/bind2nd；而且对于普通的函数，因为缺少return_type、arg1_type和arg2_type的定义，所以也不能直接使用；相同的情况存在于类成员函数指针中，不过成员函数指针的情况有点特殊，下面将会提及。

为了让bind1st/bind2nd可以为普通的函数绑定，标准库定义了一个ptr_fun，用来包装普通函数，使得bind1st/bind2nd可以用在普通函数上；对于类成员函数指针，标准库也定义了mem_fun/mem_fun_ref来包装，使得bind1st/bind2nd可以用在成员函数指针上：

int func1(int op1, int op2) {
   return op1+op2;
}
 
struct X {
   int func2(int op) {
      return op;
   }
};
 
std::bind2nd(std::ptr_fuc(func1), 10)(20);
std::bind1st(std::mem_fun(&X::func2), &x)(10);

成员函数X::func2只接受一个参数似乎和之前的说明矛盾。其实这是因为成员函数需要接受一个额外的参数（this指针的由来）。除去这个额外参数以后，就只能再接收一个了。

2、被绑定的参数只能是兼容于被绑定函数的可接收参数的类型（即存在隐式转换）。

简单的说就是你不能这样调用bind1st/bind2nd来实现生成类似于f(x)=(10+x)+x的函数：

std::bind1st(
   x_plus<int>(),
   std::bind1st(x_plus<int>(), 10)
)(20);

原因很简单，因为经过bind1st/bind2nd后得到的是一个函数。除非原来的函数接受的就是函数类型的参数，否则，由于不存在隐式转换，这样的调用将产生错误。

* 或许可以考虑一下返回的是一个函数指针。但如果返回的是一个函数指针，那么这个函数的定义至少应该类似于：

R bind1st(A2 a2) {
   return &func_to_be_bound(a1_bound, a2);
}

返回值、参数a1和a2的类型先不作考虑。

为了记录func_to_be_bound，bind1st必须定义为一个函数模板。这样的话就要求函数的参数列表中须新增用来接受func_to_be_bound的形参。这样的话又会破环bind1st的接口：

template <class f>
R bind1st(A2 a2, f func_to_be_bound);

另一个可能的形式是这样：

template <class F, F f>
R bind1st(A2 a2) {
   retrun f(a1, a2);
}

这种形式中 f 是一个非类型的模板参数。如果 F 是一个指针类型的话， f 就是一个指针，也能算是整型的非模板参数，所以这样的形式是接受的。问题在于调用须以这样的形式进行：

bind1st(a2_arg);

和之前的bind1st的用法差别甚大。或许可以尝试写一个辅助函数来简化：

template <class F>
R bind1st_aux(F f) {
   return &(bind1st<F, f>);
}

然而这种方式实际使用中会产生编译错误，因为模板的实例化参数使用了函数参数。函数参数的值是在运行期才能决定的，而模板则要求在编译期完成实例化。

而且上面那样的函数模板无法接受非整型的函数对象作为模板参数，除非把函数对象定义为全局变量，并将函数对象的地址作为参数传入。局部变量因为储存在栈区，地址取决于栈的使用状况，故只能在运行期判明，不能用作模板参数（我认为理论上静态变量也是可以的，因为都是储存在静态区，地址是可以在编译期决定的。不过在gcc 3.4.5上只有使用全局对象时编译才能通过）。

暂时能想到的用普通函数指针来实现会存在的问题就这些，似乎对于普通函数指针来说限制是比较多的。如果哪位有用普通函数指针的不错的实现的话，请告诉我吧！

另外，这不知道算不算是函数对象比普通函数要灵活的一个例子呢？

>back<