从零开始的 STL 实现记录：Functor

前言

本节开始，将会分析 STL 中的仿函数（Functor）部分的内容。在进入这一章之前，让我们回顾一下到目前为止我们都实现了哪些内容。

首先，我们实现了 Allocator，这个组件负责空间的分配，是其他组件实现的基石；随后我们实现了 Iterator，它是沟通容器与算法之间的桥梁，有了迭代器，才能使算法完全在一个抽象的层面上工作，对于泛型编程的实现十分重要；紧接着我们实现了各种 Container，包括顺序容器与关联容器等，容器是大多数人对 STL 的第一印象，也是最经常被使用的组件；最后我们实现了一大堆的 Algorithm，可以在容器上实现各种各样的操作，如 sort，rotate 等。

到目前为止，似乎已经比较完美了，既然如此，最后的 Functor 与 Adaptor 又有怎样的重要作用呢？

可以这么说，如果把目前为止实现的 STL 内容，比作原版的 MC 的话，那 Functor 和 Adaptor 就是 MC 的 Mod 接口。

是的，即使目前为止的功能已经足够解决大部分编程问题，但它们终究是封闭的，algorithm.h 中的算法虽然多，但总是有限。而 Functor 和 Adaptor 就是对于 STL 功能的极度拓展；有了它们，你可以使得一个函数表现出你想要的功能，可以使你自定义的函数或成员函数能够被纳入 STL 的框架中，与 STL 的其他功能无缝衔接，极大地拓展了 STL 的功能，这可不就是 MC 打了 Mod 吗（。

碎碎念完毕，正式进入 Functor 的分析。

Functor 的概念

所谓仿函数，就是一个 “行为类似于函数” 的对象，为了实现这一点，它所属的类别中必须重载 function call 运算子，即 ()，如此一来，便可以在仿函数的对象后加上一对小括号，以达到类似于函数调用的效果。举个例子：

class Add
{
public:
    int operator()(int a, int b)
    {
        return a + b;
    }
};

Add add;
cout << add(1, 2) << endl;  // 3

以上定义了一个类 Add，并在类中重载了 ()，使得在调用时返回传入参数的和，由 Add 类实例化出的对象就被称为仿函数，这个仿函数可以返回两个 int 的和，使用方法也与普通函数类似。

仿函数的作用主要体现在哪里呢？从上一章实现的各种算法中可以看出，STL 提供的各种算法，往往有两个版本，其中一个版本允许用户输入一个参数来指定函数执行某种策略。例如 sort()，第一个版本是以 operator< 为排序时的元素位置调整依据，第二版本则允许用户指定任何“操作”，使得排序后的相邻元素都能令该操作结果为 true。将某种“操作”当成算法的参数传给算法，我们首先能够想到的方法就是将这一操作封装为一个函数，再将函数指针传递给该算法。如：

void print(int a)
{
    cout << a << " ";
}

class Print
{
public:
    void operator()(int a)
    {
        cout << a << " ";
    }
};

void test()
{
    vector<int> v{1, 2, 3, 4, 5};
    for_each(v.begin(), v.end(), &print);  // 1 2 3 4 5
    cout << endl; 
    for_each(v.begin(), v.end(), Print()); // 1 2 3 4 5
}

这里直接传入 print 给 for_each 也可以，函数会被隐式转化为函数指针。

既然函数指针可以达到与仿函数相同的效果，那为何还要多此一举设计出仿函数呢？原因就是函数指针无法满足 STL 对抽象性的要求，可拓展性也不强。

试想，如果我定义了两个一元函数 f() 与 g()，想要将 f(g()) 这一操作当作参数传递给算法的话，如果单纯地使用函数指针，就需要重新定义一个 h()，完成 f(g()) 的功能，但假设你是用的是 STL 规格的仿函数，就只需要将 compose1(f, g) 传递给算法就行；更别提获得函数的参数类型，返回值类型等“相应型别”了。

因此，STL 采取了类似于 Iterator 中的 Traits 理念，来设计 Functor；利用模板参数推导，获得仿函数的各种相应型别，通过继承的方式，统一仿函数的接口，使得 STL 中的各种仿函数像积木一样，可以随心所欲地配接（Adaptable）。

Functor 的设计

在 STL 六大组件中，仿函数可说是体积最小、观念最简单、实现最容易的一个。但是小兵也能立大功 ——— 它扮演一种“策略”角色，可以让STL 算法有更灵活的演出。而更加灵活的关键，在于STL仿函数的可配接性 (adaptability)。

为了拥有配接能力，每一个仿函数必须定义自己的相应型别，就像迭代器如果要融入整个 STL 大家庭，也必须依照规定定义自己的 5 个相应型别一样。这些相应型别是为了让配接器能够取出，获得仿函数的某些信息。相应型别都只是一些 typedef，所有必要操作在编译期就全部完成了，对程序的执行效率没有任何影响，不带来任何额外负担。仿函数的相应型别主要用来表现函数参数型别和传回值型别。

stl_function.h 定义了两个 classes，分别代表一元仿函数和二元仿函数（STL不支持三元仿函数），其中没有任何 data members 或member functions，唯有一些型别定义，任何仿函数，只要依个人需求选择继承其中一个 class，便自动拥有了那些相应型别，也就自动拥有了配接能力。

// 定义一元函数的参数型别和返回值型别
template <class Arg, class Result>
struct unary_function {
    typedef Arg       argument_type;
    typedef Result    result_type;
};

// 定义二元函数的参数型别的返回值型别
template <class Arg1, class Arg2, class Result>
struct binary_function {
    typedef Arg1      first_argument_type;
    typedef Arg2      second_argument_type;
    typedef Result    result_type;
};

Functors

概念介绍完毕，剩下的部分就很简单了，STL 中的仿函数大致可分为四类：

• 算术类仿函数：主要进行一些计算，大部分都是二元仿函数
• 关系类仿函数：主要进行大小关系等的判断
• 逻辑类仿函数：完成逻辑与、或、非 的操作
• 选择类仿函数：有选择地返回一部分或者全部传入的值

以下直接列出上述的仿函数。

// ====================================== Arithmetic Functor ====================================== //

/// @brief 加法仿函数
/// @tparam T 
template <class T>
struct plus: public binary_function<T, T, T> {
    T operator()(const T& x, const T& y) const { return x + y; }
};

/// @brief 减法仿函数
/// @tparam T
template <class T>
struct minus: public binary_function<T, T, T> {
    T operator()(const T& x, const T& y) const { return x - y; }
};

/// @brief 乘法仿函数
/// @tparam T
template <class T>
struct multiplies: public binary_function<T, T, T> {
    T operator()(const T& x, const T& y) const { return x * y; }
};

/// @brief 除法仿函数
/// @tparam T
template <class T>
struct divides: public binary_function<T, T, T> {
    T operator()(const T& x, const T& y) const { return x / y; }
};

/// @brief 取模仿函数
/// @tparam T
template <class T>
struct modulus: public binary_function<T, T, T> {
    T operator()(const T& x, const T& y) const { return x % y; }
};

/// @brief 取反仿函数
/// @tparam T
template <class T>
struct negate: public unary_function<T, T> {
    T operator()(const T& x) const { return -x; }
};

/// @brief 证同元素，对于加法，返回 0
template <class T>
T identity_element(plus<T>) { return T(0); }

/// @brief 证同元素，对于乘法，返回 1
template <class T>
T identity_element(multiplies<T>) { return T(1); }


// ====================================== Relational Functor ====================================== //

/// @brief 等于仿函数
template <class T>
struct equal_to: public binary_function<T, T, bool> {
    bool operator()(const T& x, const T& y) const { return x == y; }
};

/// @brief 不等于仿函数
template <class T>
struct not_equal_to: public binary_function<T, T, bool> {
    bool operator()(const T& x, const T& y) const { return x != y; }
};

/// @brief 大于仿函数
template <class T>
struct greater: public binary_function<T, T, bool> {
    bool operator()(const T& x, const T& y) const { return x > y; }
};

/// @brief 大于等于仿函数
template <class T>
struct greater_equal: public binary_function<T, T, bool> {
    bool operator()(const T& x, const T& y) const { return x >= y; }
};

/// @brief 小于仿函数
template <class T>
struct less: public binary_function<T, T, bool> {
    bool operator()(const T& x, const T& y) const { return x < y; }
};

/// @brief 小于等于仿函数
template <class T>
struct less_equal: public binary_function<T, T, bool> {
    bool operator()(const T& x, const T& y) const { return x <= y; }
};


// ====================================== Logical Functor ====================================== //

/// @brief 逻辑与仿函数
template <class T>
struct logical_and: public binary_function<T, T, bool> {
    bool operator()(const T& x, const T& y) const { return x && y; }
};

/// @brief 逻辑或仿函数
template <class T>
struct logical_or: public binary_function<T, T, bool> {
    bool operator()(const T& x, const T& y) const { return x || y; }
};

/// @brief 逻辑非仿函数
template <class T>
struct logical_not: public unary_function<T, bool> {
    bool operator()(const T& x) const { return !x; }
};


// ================================ identity、select、project =============================== //

/// @brief 证同仿函数，返回原值
template <class T>
struct identity: public unary_function<T, T> {
    const T& operator()(const T& x) const { return x; }
};

/// @brief 选择仿函数，返回第一个参数
template <class Pair>
struct select1st: public unary_function<Pair, typename Pair::first_type> {
    const typename Pair::first_type& operator()(const Pair& x) const { return x.first; }
};

/// @brief 选择仿函数，返回第二个参数
template <class Pair>
struct select2nd: public unary_function<Pair, typename Pair::second_type> {
    const typename Pair::second_type& operator()(const Pair& x) const { return x.second; }
};

/// @brief 投射仿函数，返回第一个参数
template <class Arg1, class Arg2>
struct project1st: public binary_function<Arg1, Arg2, Arg1> {
    Arg1 operator()(const Arg1& x, const Arg2&) const { return x; }
};

/// @brief 投射仿函数，返回第二个参数
template <class Arg1, class Arg2>
struct project2nd: public binary_function<Arg1, Arg2, Arg2> {
    Arg2 operator()(const Arg1&, const Arg2& y) const { return y; }
};

仿函数的实现十分简单，就是继承了 unary_function 或 binary_function 之一再重载 operator()，便可成为 STL 仿函数的一员，并具备配接能力。

需要注意的是这里的 identity 与 select1st，就是 STL 用于指定 hashtable 的 _ExtractKey 参数的那两个仿函数，指定此参数为 identity，容器就变成了 set，指定为 select1st，容器就变成了 map。

总结

本节，也是本章，介绍了 STL 中的仿函数，主要介绍了这个概念（仿函数：行为类似于函数的对象）提出的必要性（能够作为函数的参数传入）以及 STL 为了使得仿函数具备可配接性做了哪些事情（模板参数推导获取相应型别以及通过继承以向上统一接口）。

可能到这里大家对于“可配接”这件事情的体会还不是很深刻，等到介绍 Adaptor 时，就会拨云见日了。