模板(十)：函数对象

发表于
  • STL提供函数对象(function obeject)
    • 提供一种方法，将要调用的函数与准备传递给这个函数的隐式参数捆绑起来

  • 函数对象表示一种操作，通过组合函数对象可以得到复杂的操作

    • 运行时处理大量的循环和条件语句、调用函数的程序块的组合对效率不利

一个例子

  • 标准库包含一个find_if的函数，以一对迭代器和一个判断式(predicate, 生成布尔值的函数)为参数
    • 返回迭代器限定的范围内第一个使判断式得到真值的迭代器的值
1
2
3
bool greater1000(int n) {
    return n > 1000;
}
  • find_if(v.begin(), v.end(), greater1000)返回指向v中第一个大于1000的元素的指针

函数对象和函数对象配接器使得可以不必真正定义一个函数

  • 考虑模板类greater: 充当判断式，接受两个参数，判断第一个参数是否大于第二个
1
2
3
4
bool greater1000(int n) {
    greater<int> gt;
    return gt(n, 1000);
}
  • 标准库一个函数配接器: bind2nd
    • 函数对象f有两个参数，一个值v
    • bind2nd创建一个新的函数对象g，g(x)具有和f(x, v)相同的值

  • bind2nd(gt, 1000)

1
2
3
4
bool greater1000(int n) {
    greater<int> gt;
    return (bind2nd(gt, 1000))(n);
}
  • 用匿名对象greater<int>()取代局部变量gt
1
2
3
bool greater1000(int n) {
    return (bind2nd(greater<int>(), 1000))(n);
}
  • 表达式bind2nd(greater<int>(), 1000)等价于greater1000(n)
    • find_if(v.begin(), v.end(), bind2nd(greater<int>(), x))

  • 原来的greater1000不通用

  • 函数对象配接器解决问题

    • 把信息从使用函数对象的部分通过程序的另一部分(该部分对要传递的信息(如find_if函数体)一无所知)传递到到第三部分中(如与bind2nd有关的判断表达式)
    • 在第三部分中信息被取出来

函数指针

某些编程语言中函数是第一级值(first-class value)
可以将函数作为参数传递，作为值返回，当作表达式的组件使用

  • C++不属于这类语言
    • 函数作为参数时实际上是函数指针
1
2
3
4
void apply(void f(int), int* p, int n) {
    for (int i = 0; i < n; ++i)
        f(p[i]);
}
  • 任何试图声明函数类型的变量都被转换成指向函数的指针声明
  • 所有对函数指针的调用都等价于对这个指针所指向函数的调用
  • 事实上等价于
1
2
3
4
void apply(void (*fp)(int), int* p, int n) {
    for (int i = 0; i < n; ++i)
        (*fp)(p[i]);
}
  • 函数和函数指针的差异
    • 不可能通过操纵函数指针创建指针所指向的对象
    • C++的总存储空间在程序执行前就固定了

  • 无法在程序开始运行后创建新函数

  • 如何写一个C++函数把两个函数组合起来生成第三个函数

1
2
extern int f(int);
extern int g(int);
  • int (*h)(int) = compose(f, g)

  • 对任意整数n，h(n)将会等于f(g(n))

  • C++没有提供直接实现的方法

1
2
3
4
5
6
7
// 无效的代码
int (*compose(int f(int), int g(int)))(int x) {
    int result(int n) {
        return f(g(n));
    }
    return result;
}
  • C++不支持嵌套函数
    • result需要在块作用域内访问f和g
    • 也不能简单地使result全局化: f和g在result中没有定义
1
2
3
4
5
6
7
8
// 这段代码也无效
int result(int n) {
    return f(g(n));
}
int (*compose(int f(int), int g(int)))(int x) {
    return result;
}
  • 假设C++允许嵌套函数，仍然没用
1
2
3
4
5
6
7
8
9
10
// 无效的代码
int (*compose(int f(int), int g(int)))(int x) {
    int (*fp)(int) = f;
    int (*gp)(int) = g;
    int result(int n) {
        return fp(gp(n));
    }
    return result;
}
  • 将f和g的地址复制到两个局部变量中
  • 返回指向result的指针
  • fp和gp是局部变量，compose返回就无效
  • 返回的result试图调用，导致程序运行崩溃

编写compose函数需要常规的基于堆栈的实现外还需要某种自动内存管理
把函数当作第一级值处理的语言通常也支持垃圾回收机制

函数对象

  • 如果compose不能返回一个函数，可以返回一个行为和函数类似的类对象

  • 函数对象

    • 包含operator()成员函数的类
    • 可以把类对象当作函数使用
1
2
3
4
5
6
7
8
9
10
class F {
public:
    int operator()(int);
    // ...
};
int main() {
    F f;
    int n = f(42);
}
  • 通过这种技巧可以组合函数
1
2
3
4
5
6
7
8
9
10
11
class Intcomp {
puclic:
    Intcomp(int (*f0)(int), int (*g0)(int)): fp(f0), gp(g0) { }
    int operator() (int n) const {
        return (*fp)((*gp)(n));
    }
private:
    int (*fp)(int);
    int (*gp)(int);
};
  • k可以用Intcomp组合已有的函数f和g
1
2
3
4
5
6
7
extern int f(int);
extern int g(int);
int main() {
    Intcomp fg(f, g);
    fg(42);
}
  • 从原理上解决组合问题
  • 只能组合函数，不能组合函数对象

函数对象模板

  • 即可组合函数又可组合函数对象
1
2
3
4
5
6
7
8
9
10
11
12
template <class F, class G, class X, class Y>
class Comp {
public:
    Comp(F f0, G g0): f(f0), g(g0) { }
    Y operator()(X x) const {
        return f(g(x));
    }
private:
    F f;
    G g;
};
  • 将类型为F的函数(函数对象)与另一个类型为G的函数(函数对象)组合起来
  • 得到参数类型为X，结果类型为Y的对象
1
2
3
4
int main() {
    Comp<int (*)(int), int (*)(int), int, int> fg(f, g);
    fg(42);
}
  • 若组合函数fg和f
    • Comp<Comp<int (*)(int), int (*)(int), int, int>, int (*)(int), int, int> fgf(fg, f)
    • 非常复杂

隐藏中间类型

  • 类型隐含在组合函数的参数的类型中: Composition<int, int> fg(f, g);
1
2
3
4
5
6
7
template <class X, class Y>
class Composition {
public:
    // ...
    Y operator() (X) const;
    // ...
};
  • 构造函数必须能够接受函数和函数对象的任何组合(包括它自身)
    • 构造函数必须是一个模板
1
2
3
4
5
6
7
8
template <class X, class Y>
class Composition {
public:
    template <class F, class G>
    Composition(F, G);
    Y operator()(X) const;
    // ...
};
  • 类型F和G不属于类Composition的类型，在这里不是模板参数

一种类型包罗万象

  • 重写Comp使Comp<F, G, X, Y>继承自某个不依赖于F或者G的其他类Comp_base<X, Y>

  • 在类Composition中可以保存指向Comp_base<X, Y>的指针

  • Comp_base<X, Y>接受X参数并返回Y结果的任意函数对象

  • 提供虚函数operator(): 纯虚函数
  • 需要虚析构函数
  • 复制Comp类型对象的纯虚函数
1
2
3
4
5
6
7
template <class X, class Y>
class Comp_base {
public:
    virtual Y operator()(X) const = 0;
    virtual Comp_base* clone() const = 0;
    virtual ~Comp_base() { }
};
  • 用Comp_base作基类重写Comp: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template <class F, class G, class X, class Y>
class Comp : public Comp_base<X, Y> {
public:
    Comp(F f0, G g0): f(f0), g(g0) { }
    Y operator() (X x) const {
        return f(g(x));
    }
    Comp_base<X, Y>* clone() const {
        return new Comp(*this);
    }
private:
    F f;
    G g;
};
  • 令Composition包含一个指向Comp_base的指针
1
2
3
4
5
6
7
8
9
10
11
template <class X, class Y>
class Composition {
public:
    template <class F, class G>
    Composition(F, G);
    Y operator() (X) const;
private:
    Comp_base<X, Y>* p;
    // ...
};
  • 复制对象时对指针类型的处理: 复制底层对象
  • 显式复制构造函数和析构函数
1
2
3
4
5
6
7
8
9
10
11
12
13
template <class X, class Y>
class Composition {
public:
    template <class F, class G>
    Composition(F, G);
    Composition(const Composition&);
    Composition& operator=(const Composition&);
    ~Composition();
    Y operator()(X) const;
private:
    Comp_base<X, Y>* p;
};

实现

  • 构造函数用一个指向Comp<F, G, X, Y>的指针初始化类型为Comp_base<X, Y>的成员p
1
2
3
template <class X, class Y>
    template <class F, class G>
    Composition<X, Y>::Composition(F f, G g): p(new Comp<F, G, X, Y>(f, g)) { }
  • 析构函数只删除p所指向的对象
1
2
3
4
template <class X, class Y>
Composition<X, Y>::~Composition() {
    delete p;
}
  • 拷贝构造函数和赋值操作符使用基类Comp_base中的纯虚函数clone
1
2
3
4
5
6
7
8
9
10
11
template <class X, class Y>
Composition::Composition(const Composition& c): p(c.p->clone()) { }
template <class X, class Y>
Composition& Composition::operator=(const Composition& c) {
    if (this != &c) {
        delete p;
        p = c.p->clone();
    }
    return *this;
}
  • operator()覆盖基类Comp_base中的纯虚函数
1
2
3
4
template <class X, class Y>
Y Composition::operator() (X x) const {
    return (*p)(x);
}
  • 可以这样调用
1
2
3
4
5
6
7
8
extern int f(int);
extern int g(int);
extern int h(int);
int main() {
    Composition<int, int> fg(f, g);
    Composition<int, int> fgh(fg, h);
}

Summary

  • 绕过一个看似简单的语言局限所需要的大量工作

    • 扩展语言以使之允许函数组合不像看上去那么简单

  • 标准函数库函数transform: 对序列中的每个元素都运用函数或者函数对象，获得新序列

    • transform(a, a+100, a, f);
  • 使序列的每一个元素都加上一个整数n
1
2
3
4
5
6
7
8
9
class Add_an_integer {
public:
    Add_an_integer(int n0): n(n0) { }
    int operator() (int x) const {
        return x+n;
    }
private:
    int n;
};

  • transform(a, a+100, a, Add_an_integer(n));

  • 函数配接器使得可以在联合的过程中定义类似Add_an_integer的类，而不必编写类的定义

《C++沉思录(Cplusplus Thinking)》笔记